Proportional approval voting
Condorcet methods Positional voting Cardinal voting Quota-remainder methods Approval-based committees Fractional social choice Semi-proportional representation By ballot type Pathological response Strategic voting Paradoxes of majority rule Positive results Proportional approval voting (PAV) is a proportional electoral system for multiwinner elections.
Seats are then apportioned between candidates in a way that ensures all coalitions are represented proportionally.
PAV is a special case of Thiele's voting rule, proposed by Thorvald N.
[4] PAV was rediscovered by Forest Simmons in 2001,[5] who gave it the name "proportional approval voting."
In satisfaction approval voting, each voter's ballot is split equally between all
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.
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: There are 6 possible results: AB, AC, AD, BC, BD, and CD.
In this case, the PAV selection of Andrea and Carter is coincident with the Simple Approval sequence.
This shows that PAV can give results that are incompatible with the method which simply follows the sequence implied by Simple Approval.
There are 100 voters: In this case PAV would select 6 blue, 3 red, and 1 green candidate.
For example, the score of a committee that consists of only blue candidates would be 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.
[1] This section describes axiomatic properties of Proportional Approval Voting.
In an election with only one winner, PAV operates in exactly the same way as approval voting.
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 satisfies the consistency criterion.
[2] Even if the voters do not follow the partisan scheme, the rule provides proportionality guarantees.
[10] Furthermore, PAV satisfies the property of the core if there are sufficiently many similar candidates running in an election.
[11] 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.
[10] 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.
[12] These two alternative methods are also computable in polynomial time, yet they fail Pareto efficiency.
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).
From the perspective of parameterized complexity, the problem of computing PAV is theoretically difficult outside of a few exceptional easy cases.
[15][17][18] 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,[14] and in linear time when voters are strong partisans (i.e. vote for party lists instead of candidates).
[16] 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;[19] under standard assumptions in complexity theory, this is the best approximation ratio that can be achieved for PAV in polynomial time.
