Part of the Politics series
Electoral systems
Single-winner/majoritarian Plurality First-past-the-post Plurality at-large (plurality block voting) General ticket (party block voting) Multi-round voting Two-round Exhaustive ballot Primary election Nonpartisan unified top-four Majority at-large (two-round block voting) Ranked / preferential systems Instant-runoff (alternative vote) Contingent vote Coombs' method Condorcet methods (Copeland's, Dodgson's, Kemeny–Young, Minimax, Nanson's, ranked pairs, Schulze, Alternative Smith) Positional voting (Borda count, Nauru/Dowdall method) Bucklin voting Oklahoma primary electoral system Preferential block voting Cardinal / graded systems Score voting Approval voting Combined approval voting Unified primary Usual judgment Satisfaction approval voting Majority judgment STAR voting
Proportional representation Party-list Electoral list open list closed list local lists Apportionment Sainte-Laguë D'Hondt Huntington–Hill Hare Droop Imperiali Hagenbach-Bischoff National remnant Highest averages Largest remainder Proportional forms of ranked voting Single transferable vote Gregory Wright Schulze STV CPO-STV Ranked party list PR Spare vote Proportional forms of cardinal voting Proportional approval voting Sequential proportional approval voting Method of Equal Shares Phragmen's voting rules Biproportional apportionment Fair majority voting Weighted voting Direct representation Interactive representation Liquid democracy
Mixed systems By type of representation Mixed-member majoritarian Mixed-member proportional Non-compensatory mixed systems Parallel voting Majority bonus Compensatory mixed systems Additional member system Mixed single vote (positive vote transfer) Scorporo (negative vote transfer) Mixed ballot transferable vote Alternative Vote Plus Dual-member proportional Rural–urban proportional
Other systems and related theory Semi-proportional representation Single non-transferable vote Limited voting Cumulative voting Binomial voting Other systems Multiple non-transferable vote Double simultaneous vote Proxy voting Delegated voting Indirect STV Liquid democracy Random selection (sortition, random ballot) Supermajority Social choice theory Arrow's theorem Gibbard–Satterthwaite theorem Public choice theory Veto Players List of electoral systems List of electoral systems by country Comparison of electoral systems Effects of electoral systems Political fragmentation Political efficacy Voter turnout
Politics portal
v t e

Proportional approval voting (PAV) is a proportional electoral system for multiwinner elections. It is an extension of the D'Hondt method of apportionment^[1][2] that additionally allows for personal votes (voters vote for candidates, not for a party list). The voters vote via approval ballots where each voter marks those candidates that the voter finds acceptable.

History

PAV is a special case of Thiele's voting rules, proposed by Thorvald N. Thiele.^[3][4][5] It was used in combination with ranked voting in the early 20th century in Sweden, for example between 1909 and 1921 for distributing seats within parties, and in local elections.^[4] After 1921 it was replaced by Phragmén's rules. PAV was rediscovered by Forest Simmons in 2001^[6] who gave it the name "proportional approval voting".

Definition

PAV selects a committee of a fixed desired size with the highest score, where scores are calculated according to the following formula. Given a committee ${\displaystyle W}$, for each voter we check how many candidates in the committee the voter approves. Assuming that the voter voted for ${\displaystyle r}$ candidates in ${\displaystyle W}$, the voter contributes to the score of ${\displaystyle W}$ the value of the ${\displaystyle r}$-th harmonic number, that is:^[6][7]

${\displaystyle \mathrm {H} (r)=1+{\frac {1}{2))+{\frac {1}{3))+\cdots +{\frac {1}{r)){\text{.))}$

The score of ${\displaystyle W}$ is calculated as the sum of the scores garnered from all the voters.

Formally, assume we have a set of candidates ${\displaystyle C=\{c_{1},c_{2},\ldots ,c_{m}\))$, a set of voters ${\displaystyle N=\{1,2,\ldots ,n\))$, and a committee size ${\displaystyle k}$. Let ${\displaystyle A_{i))$ denote the set of candidates approved by voter ${\displaystyle i\in N}$. The PAV score of a committee ${\displaystyle W\subseteq C}$ with size ${\displaystyle |W|=k}$ is defined as ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)=\sum _{i=1}^{n}\mathrm {H} (|A_{i}\cap W|)}$. PAV select the committee ${\displaystyle W}$ with the maximal score.

Example 1

Assume 2 seats to be filled, and there are four candidates: Andrea (A), Brad (B), Carter (C), and Delilah (D), and 30 voters. The ballots are:

• 5 voters voted for A and B
• 17 voters voted for A and C
• 8 voters voted for D

There are 6 possible results: AB, AC, AD, BC, BD, and CD.

	AB	AC	AD	BC	BD	CD
score from the 5 voters voting for AB	${\displaystyle 5\cdot \left(1+{\tfrac {1}{2))\right)=7.5}$	${\displaystyle 5\cdot 1=5}$	${\displaystyle 5\cdot 1=5}$	${\displaystyle 5\cdot 1=5}$	${\displaystyle 5\cdot 1=5}$	${\displaystyle 5\cdot 0=0}$
score from the 17 voters voting for AC	${\displaystyle 17\cdot 1=17}$	${\displaystyle 17\cdot \left(1+{\tfrac {1}{2))\right)=25.5}$	${\displaystyle 17\cdot 1=17}$	${\displaystyle 17\cdot 1=17}$	${\displaystyle 17\cdot 0=0}$	${\displaystyle 17\cdot 1=17}$
score from the 8 voters voting for D	${\displaystyle 8\cdot 0=0}$	${\displaystyle 8\cdot 0=0}$	${\displaystyle 8\cdot 1=8}$	${\displaystyle 8\cdot 0=0}$	${\displaystyle 8\cdot 1=8}$	${\displaystyle 8\cdot 1=8}$
Total score	24.5	30.5	30	22	13	25

Andrea and Carter are elected.

Note that Simple Approval shows that Andrea has 22 votes, Carter has 17 votes, Delilah has 8 votes and Brad has 5 votes. In this case, the PAV selection of Andrea and Carter is coincident with the Simple Approval sequence. However, if the above votes are changed slightly so that A and C receive 16 votes and D receives 9 votes, then Andrea and Delilah are elected since the A and C score is now 29 while the A and D score remains at 30. Also, the sequence created by using Simple Approval remains unchanged. This shows that PAV can give results that are incompatible with the method which simply follows the sequence implied by Simple Approval.

Example 2

Assume there are 10 seats to be selected, and there are three groups of candidates: red, blue, and green candidates. There are 100 voters:

• 60 voters voted for all blue candidates,
• 30 voters voted for all red candidates,
• 10 voters voted for all green candidates.

In this case PAV would select 6 blue, 3 red, and 1 green candidate. The score of such a committee would be

$${\displaystyle 60\cdot \mathrm {H} (6)+30\cdot \mathrm {H} (3)+10\cdot \mathrm {H} (1)=60\cdot \left(1+{\tfrac {1}{2))+\ldots +{\tfrac {1}{6))\right)+30\cdot \left(1+{\tfrac {1}{2))+{\tfrac {1}{3))\right)+10\cdot 1=147+55+10=212{\text{.))}$$

${\displaystyle 60\cdot \mathrm {H} (10)+30\cdot \mathrm {H} (0)+10\cdot \mathrm {H} (0)=60\cdot \left(1+{\tfrac {1}{2))+\ldots +{\tfrac {1}{10))\right)\approx 175.73{\text{.))}$

In this example, the outcome of PAV is proportional: the number of candidates selected from each group is proportional to the number of voters voting for the group. This is not coincidence: If the candidates form disjoint groups, as in the above example (the groups can be viewed as political parties), and each voter votes exclusively for all of the candidates within a single group, then PAV will act in the same way as the D'Hondt method of party-list proportional representation.^[1]

Properties

This section describes axiomatic properties of Proportional Approval Voting.

Committees of size one

In an election with only one winner, PAV operates in exactly the same way as approval voting. That is, it selects the committee consisting of the candidate who is approved by the most voters.

Proportionality

Most systems of proportional representation use party lists. PAV was designed to have both proportional representation and personal votes (voters vote for candidates, not for a party list). It deserves to be called a "proportional" system because if votes turn out to follow a partisan scheme (each voter votes for all candidates from a party and no other) then the system elects a number of candidates in each party that is proportional to the number of voters who chose this party (see Example 2).^[1] Further, under mild assumptions (symmetry, continuity and Pareto efficiency), PAV is the only extension of the D'Hondt method that allows personal votes and that satisfies the consistency criterion.^[2]

Even if the voters do not follow the partisan scheme, the rule provides proportionality guarantees. For example, PAV satisfies the strong fairness property called extended justified representation,^[7] as well as the related property proportional justified representation.^[8] It also has optimal proportionality degree.^[9][10] All these properties guarantee that any group of voters with cohesive (similar) preferences will be represented by a number of candidates that is at least proportional to the size of the group. PAV is the only method satisfying such properties among all PAV-like optimization methods (that may use numbers other than harmonic numbers in their definition).^[7]

The committees returned by PAV might not be in the core.^[7][11] However, it guarantees 2-approximation of the core, which is the optimal approximation ratio that can be achieved by a rule satisfying the Pigou–Dalton principle of transfers.^[11] Furthermore, PAV satisfies the property of the core if there are sufficiently many similar candidates running in an election.^[12]

PAV fails priceability (that is, the choice of PAV cannot be always explained via a process where the voters are endowed with a fixed amount of virtual money, and spend this spend money on buying candidates they like) and fails laminar proportionality.^[11] Two alternative rules that satisfy priceability and laminar proportionality, and that have comparably good proportionality-related properties to PAV are the Method of Equal Shares and Phragmén's Sequential Rules.^[13] These two alternative methods are also computable in polynomial time, yet they fail Pareto efficiency.

Other properties

Apart from properties pertaining to proportionality, PAV satisfies the following axioms:

• Pareto efficiency,
• Consistency,
• Support monotonicity (if the support of a winning candidate increases, i.e., more voters vote for this candidate, then this candidate remains winning),^[14]
• Pigou–Dalton principle.^[11]

PAV fails the following properties:

• House monotonicity.^[13] Two alternative methods that satisfy house monotonicity and that have comparably good proportionality-related properties to PAV are Sequential Proportional Approval Voting and Phragmén's Sequential Rules.^[13] These two alternative methods are also computable in polynomial time, but they fail Pareto efficiency, Consistency, and the Pigou–Dalton principle.^[13]

Computation

Computing the winning committee under PAV is NP-hard,^[16][17] making it a computationally demanding voting method as the number of candidates and seats increase. Under a brute force approach, if there were m candidates and k seats, then there would be

${\displaystyle {\binom {m}{k))={\frac {m!}{k!(m-k)!))}$

combinations of candidates to compare with each election.^[18] For example, if there were 24 candidates for 4 seats, there would be 10,626 combinations for which we would need to calculate PAV scores. An election requiring this many calculations would necessitate vote counting by computer. For medium-size elections, the outcome of PAV can be computed by using integer programming solvers. The ILP implementation of PAV is part of the Python package abcvoting.^[19] When k is fixed (a constant), the brute-force computation of PAV takes polynomial time, i.e. ${\displaystyle O(nm^{k})}$, where n is the number of voters.

Sequential proportional approval voting is a method that can be considered an approximation of PAV with approximation ratio equal to ${\displaystyle 1-1/e\approx 0.63}$, so the PAV score of the resulting committee is at most 37% worse than optimal.^[17] This method can be computed in polynomial time, and the election outcome could potentially be determined by hand. Sequential proportional approval voting on its own exhibits good properties and can be used as a full-fledged election system, though formally it fails all the proportionality properties that distinguish PAV. A more complex approach based on randomized rounding gives an approximation ratio of 0.7965.^[20] Under standard assumptions in complexity theory, this is the best approximation ratio that can be achieved for PAV in polynomial time.^[20] The problem of approximating PAV can be also formulated as the a minimization problem (instead of maximizing ${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)}$ we want to minimize ${\displaystyle \textstyle \sum _{i\in N}\mathrm {H} (k)-\mathrm {sc} _{\mathrm {PAV} }(W)}$), in which case the best known approximation ratio is 2.36.^[21]

From the perspective of parameterized complexity, the problem of computing PAV is typically hard, with a few exceptional easy cases.^[16][22] The problem is NP-hard even in the two-dimensional spatial model of voting.^[23] It is solvable in polynomial time in the case of a single dimension.^[15]

Beyond approval committee elections

PAV can be used for voting on an agenda consisting of a number of independent issues, on which yes/no decisions need to be made.^[24][25]