Proportional approval voting

Method

Like its close cousin, satisfaction approval voting, PAV can be thought of as selecting a committee by testing all possible committees, then choosing the committee with the most votes. In satisfaction approval voting, each voter's ballot is split equally between all ${\displaystyle r}$ candidates they approve of, giving each one ${\displaystyle 1/r}$ votes. If voters are perfectly strategic, and only support as many candidates as their party is entitled to, SAV creates a proportional result.

PAV makes one modification to remove this need for strategy: it only splits a voter's ballot after they have elected a candidate. As a result, voters can freely approve of losing candidates without diluting their ballot. Voters contribute a whole vote to the first candidate they support who is elected; half a vote to the second candidate; and so on.

Thus, if a ballot approves of ${\displaystyle r}$ candidates who are elected, that ballot contributes the ${\displaystyle r}$-th harmonic number to that committee's vote total. In other words:

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

The score for a given committee is calculated as the sum of the scores garnered from all the voters. We then choose the committee with the highest score.

Formally, assume we have a set of candidates ${\displaystyle C=\{c_1,c_2,\dots ,c_m\}}$, a set of voters ${\displaystyle N=\{1,2,\dots ,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 {\mathrm{s}\mathrm{c}}_{\mathrm{P}\mathrm{A}\mathrm{V}}(W)=\sum _{i=1}^n\mathrm{H}(|A_i\cap W|)}$. PAV selects 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.

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+\frac{1}{2}+\dots +\frac{1}{6}\right)+30\cdot \left(1+\frac{1}{2}+\frac{1}{3}\right)+10\cdot 1=147+55+10=212\text{.}}$$All other committees receive a lower score. For example, the score of a committee that consists of only blue candidates would be

${\displaystyle 60\cdot \mathrm{H}(10)+30\cdot \mathrm{H}(0)+10\cdot \mathrm{H}(0)=60\cdot \left(1+\frac{1}{2}+\dots +\frac{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.

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). Further, under mild assumptions (symmetry, continuity and Pareto efficiency), PAV is the only extension of the D'Hondt method that allows personal votes and satisfies the consistency criterion.

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, as well as the weaker property proportional justified representation. It also has optimal proportionality degree. 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).

The committees returned by PAV might not be in the core. 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. Furthermore, PAV satisfies the property of the core if there are sufficiently many similar candidates running in an election.

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. 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. 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)
• Pigou–Dalton principle

PAV fails the following properties:

• House monotonicity. 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. These two alternative methods are also computable in polynomial time, but they fail Pareto efficiency, Consistency, and the Pigou–Dalton principle.

Computation

PAV solutions and their quality can be verified in polynomial-time, making transparency easy. However, the worst-case time complexity is NP-complete, meaning that for some elections it can be difficult or impossible to find an exact solution that guarantees all the theoretical properties of PAV.

In practice, the outcome of PAV can be computed exactly for medium-sized committees (<50 candidates) using integer programming solvers (such as those provided in the abcvoting Python package). Finding an exact solution has time complexity ${\displaystyle O(n{2}^k)}$ with k seats and n voters, making it impractical to calculate by hand for many seats.

From the perspective of parameterized complexity, the problem of computing PAV is theoretically difficult outside of a few exceptional easy cases. Luckily, such cases are often good approximations of real elections, allowing them to be used as heuristics that dramatically reduce the computational effort of finding a correct solution. For example, exact election results can be solved in polynomial time in the case where voters and candidates lie along a single-dimensional political spectrum, and in linear time when voters are strong partisans (i.e. vote for party lists instead of candidates).

Deterministic approximations

Sequential proportional approval voting is a greedy approximation for PAV with a worst-case approximation ratio of ${\displaystyle 1-1/e\approx 0.63}$, so the PAV score of the resulting committee is at least 63% of the optimal. This method can be computed in polynomial time, and the election outcome could potentially be determined by hand. A different approach including derandomized rounding (with the method of conditional probabilities) gives a worst-case approximation ratio of 0.7965; under standard assumptions in complexity theory, this is the best approximation ratio that can be achieved for PAV in polynomial time. The problem of approximating PAV can be also formulated as a minimization problem (instead of maximizing ${\displaystyle {\mathrm{s}\mathrm{c}}_{\mathrm{P}\mathrm{A}\mathrm{V}}(W)}$ we want to minimize ${\displaystyle \sum _{i\in N}\mathrm{H}(k)-{\mathrm{s}\mathrm{c}}_{\mathrm{P}\mathrm{A}\mathrm{V}}(W)}$), in which case the best known approximation ratio is 2.36.

Adaptation to participatory budgeting

Combinatorial participatory budgeting (PB) is a generalization of multiwinner voting in which different candidates have different costs, and the goal is to select a subset of candidates whose total cost is at most a given budget B (in multiwinner voting each candidate has the same cost of 1, and the budget is the required committee size).

There are several ways to extend PAV to PB: one can measure the satisfaction of each voter by the harmonic number of the quantity of winners that he approves, or by the harmonic number of the total cost of winners that he approves. Both extensions fail EJR.

Example. There are four voters and the budget B = 4. There are two projects:

• Project a: cost 4, approved by voters 1, 2, 3.
• Project b: cost 1, approved by voter 4.

The only two nonempty feasible outcomes are {a} and {b}.

EJR, as well as PJR and JR, require that project b is funded, as voter 4 deserves 1/4 of the budget = 1, and wants a project that costs 1. Hence, the outcome must be {b} (note that these axioms do not require that a is funded, as voters 1,2,3 deserve only 3/4 of the budget = 3, and there is no set of projects of total cost at most 3 that they all approve).

On the other hand, both adaptations of PAV select {a}. For the quantity adaptation, it is because {a} gives cardinality-1 satisfaction to three voters, whereas {b} gives cardinality-1 satisfaction to only one voter; for the cost adaptation, it is even more pronounced: {a} gives cost-3 satisfaction to three voters, whereas {b} gives only cost-1 satisfaction, and to only one voter.

In fact, the same example shows that any Thiele rule, maximizing a monotonically increasing function of either the quantity or the cost of approved winners, violates JR.

The example can be generalized as follows. Suppose the budget is n, and there are n voters with the following preferences:

• Some n/2 voters approve one large project, that costs n;
• Other n/2 voters approve n/2 small projects, that cost 1 each.

Then EJR requires to choose the n/2 small projects, but the cost adaptation of PAV choose the one large project. This shows that cost-PAV does not even satisfy EJR-up-to-c projects, for any constant c.