Proportional approval voting

Last updated

Proportional approval voting (PAV) is a proportional electoral system for multiwinner elections. It is a multiwinner approval method that extends the highest averages method of apportionment commonly used to calculate apportionments for party-list proportional representation. [1] However, PAV allows voters to support only the candidates they approve of, rather than being forced to approve or reject all candidates on a given party list. [2]

Contents

In PAV, voters cast approval ballots marking all candidates they approve of; each voter's ballot is then treated as if all candidates on the ballot were on their own "party list." Seats are then apportioned between candidates in a way that ensures all coalitions are represented proportionally.

History

PAV is a special case of Thiele's voting rule, proposed by Thorvald N. Thiele. [3] [4] It was used in combination with ranked voting in the Swedish elections from 1909 to 1921 for distributing seats within parties and in local elections. [4] PAV was rediscovered by Forest Simmons in 2001, [5] who gave it the name "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 candidates they approve of, giving each one 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 the need for this 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 candidates who are elected, that ballot contributes the -th harmonic number to that committee's vote total. In other words: [5] [6]

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 , a set of voters , and a committee size . Let denote the set of candidates approved by voter . The PAV score of a committee with size is defined as . PAV selects the committee 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:

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

ABACADBCBDCD
score from the 5 voters voting for AB
score from the 17 voters voting for AC
score from the 8 voters voting for D
Total score24.530.530221325

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:

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

All other committees receive a lower score. 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. 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, [6] as well as the related property proportional justified representation. [7] It also has optimal proportionality degree. [8] [9] 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). [6]

The committees returned by PAV might not be in the core. [6] [10] 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. [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.

Other properties

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

PAV fails the following properties:

Computation

An integer linear programming formulation for computing winning committees according to PAV. The variable
y
c
{\displaystyle y_{c}}
indicates whether candidate
c
{\displaystyle c}
is selected or not. The variable
x
i
,
l
{\displaystyle x_{i,\ell }}
indicates whether voter
i
{\displaystyle i}
approves at least
l
{\displaystyle \ell }
selected candidates. ILP-PAV.jpg
An integer linear programming formulation for computing winning committees according to PAV. The variable indicates whether candidate is selected or not. The variable indicates whether voter approves at least selected candidates.

PAV solutions and their quality can be verified in polynomial-time, [15] [16] 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 with k seats and n voters.

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).

Deterministic approximations

Approximation algorithms can find "good-enough" solutions very quickly in practice. Sequential proportional approval voting modifies PAV, using a greedy algorithm to approximate the result. SPAV has a worst-case approximation ratio of , so the PAV score of the resulting committee is at least 63% of the optimal. [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. [19] The problem of approximating PAV can be also formulated as a minimization problem (instead of maximizing we want to minimize ), in which case the best known approximation ratio is 2.36. [20]

Further reading

See also

Related Research Articles

In mathematics, a transcendental number is a real or complex number that is not algebraic – that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best-known transcendental numbers are π and e.

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design.

<span class="mw-page-title-main">Tropical geometry</span> Skeletonized version of algebraic geometry

In mathematics, tropical geometry is the study of polynomials and their geometric properties when addition is replaced with minimization and multiplication is replaced with ordinary addition:

Proportionality for solid coalitions (PSC) is a fairness criterion for ranked voting systems. It is an adaptation of the proportional representation criterion to voting systems in which there are no parties, the voters can vote directly for candidates, and can rank the candidates in any way they want. This criterion was proposed by the British philosopher and logician Michael Dummett.

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Satisfaction approval voting (SAV), also known as equal and even cumulative voting, is an electoral system that is a form of multiwinner approval voting as well as a form of cumulative voting. In the academic literature, the rule was studied by Steven Brams and Marc Kilgour in 2010. In this system, voters may approve a number of candidates, and each approved candidate receives an equal fraction of the vote. For example, if a voter approves 4 candidates, then each candidate receives a 0.25 fractional vote. The election winners are those candidates that receive the highest fractional vote count.

<span class="mw-page-title-main">Sequential proportional approval voting</span> Multiple-winner electoral system

Sequential proportional approval voting (SPAV) or reweighted approval voting (RAV) is an electoral system that extends the concept of approval voting to a multiple winner election. It is a simplified version of proportional approval voting. It is a special case of Thiele's voting rules, proposed by Danish statistician Thorvald N. Thiele in the early 1900s. It was used in Sweden for a short period from 1909-1921, and was replaced by a cruder "party-list" style system as it was easier to calculate.

Computational social choice is a field at the intersection of social choice theory, theoretical computer science, and the analysis of multi-agent systems. It consists of the analysis of problems arising from the aggregation of preferences of a group of agents from a computational perspective. In particular, computational social choice is concerned with the efficient computation of outcomes of voting rules, with the computational complexity of various forms of manipulation, and issues arising from the problem of representing and eliciting preferences in combinatorial settings.

<span class="mw-page-title-main">Green's law</span> Equation describing evolution of waves in shallow water

In fluid dynamics, Green's law, named for 19th-century British mathematician George Green, is a conservation law describing the evolution of non-breaking, surface gravity waves propagating in shallow water of gradually varying depth and width. In its simplest form, for wavefronts and depth contours parallel to each other, it states:

Combined approval voting (CAV) is an electoral system where each voter may express approval, disapproval, or indifference toward each candidate. The winner is the most-approved candidate.

Combinatorial participatory budgeting,also called indivisible participatory budgeting or budgeted social choice, is a problem in social choice. There are several candidate projects, each of which has a fixed costs. There is a fixed budget, that cannot cover all these projects. Each voter has different preferences regarding these projects. The goal is to find a budget-allocation - a subset of the projects, with total cost at most the budget, that will be funded. Combinatorial participatory budgeting is the most common form of participatory budgeting.

Justified representation (JR) is a criterion of fairness in multiwinner approval voting. It can be seen as an adaptation of the proportional representation criterion to approval voting.

Multiwinner approval voting, also called approval-based committee (ABC) voting, is a multi-winner electoral system that uses approval ballots. Each voter may select ("approve") any number of candidates, and multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

Multiwinner voting, also called multiple-winner elections or committee voting or committee elections, is an electoral system in which multiple candidates are elected. The number of elected candidates is usually fixed in advance. For example, it can be the number of seats in a country's parliament, or the required number of members in a committee.

Phragmén's voting rules are rules for multiwinner voting. They allow voters to vote for individual candidates rather than parties, but still guarantee proportional representation. They were published by Lars Edvard Phragmén in French and Swedish between 1893 and 1899, and translated to English by Svante Janson in 2016.

The Method of Equal Shares is a proportional method of counting ballots that applies to participatory budgeting, to committee elections, and to simultaneous public decisions. It can be used when the voters vote via approval ballots, ranked ballots or cardinal ballots. It works by dividing the available budget into equal parts that are assigned to each voter. The method is only allowed to use the budget share of a voter to implement projects that the voter voted for. It then repeatedly finds projects that can be afforded using the budget shares of the supporting voters. In contexts other than participatory budgeting, the method works by equally dividing an abstract budget of "voting power".

Multi-issue voting is a setting in which several issues have to be decided by voting. Multi-issue voting raises several considerations, that are not relevant in single-issue voting.

An expanding approvals rule(EAR) is a rule for multi-winner elections, which allogs agents to express weak ordinal preferences (i.e., ranking with indifferences), and guarantees a form of proportional representation called proportionality for solid coalitions. The family of EAR was presented by Aziz and Lee.

Fully proportional representation(FPR) is a property of multiwinner voting systems. It extends the property of proportional representation (PR) by requiring that the representation be based on the entire preferences of the voters, rather than on their first choice. Moreover, the requirement combines PR with the requirement of accountability - each voter knows exactly which elected candidate represents him, and each candidate knows exactly which voters he represents.

Thiele's voting rules are rules for multiwinner voting. They allow voters to vote for individual candidates rather than parties, but still guarantee proportional representation. They were published by Thorvald Thiele in Danish in 1895, and translated to English by Svante Janson in 2016. They were used in Swedish parliamentary elections to distribute seats within parties, and are still used in city council elections.

References

  1. 1 2 3 Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018). "Multiwinner Approval Rules as Apportionment Methods". Journal of Theoretical Politics. 30 (3): 358–382. arXiv: 1611.08691 . doi:10.1177/0951629818775518. S2CID   10535322.
  2. 1 2 Lackner, Martin; Skowron, Piotr (2021). "Consistent approval-based multi-winner rules". Journal of Economic Theory. 192: 105173. arXiv: 1704.02453 . doi:10.1016/j.jet.2020.105173. S2CID   232116881.
  3. Thiele, Thorvald N. (1895). "Om Flerfoldsvalg". Oversigt over Det Kongelige Danske Videnskabernes Selskabs Forhandlinger: 415–441.
  4. 1 2 Janson, Svante (2016). "Phragmén's and Thiele's election methods". arXiv: 1611.08826 [math.HO].
  5. 1 2 Kilgour, D. Marc (2010). "Approval Balloting for Multi-winner Elections". In Jean-François Laslier; M. Remzi Sanver (eds.). Handbook on Approval Voting. Springer. pp. 105–124. ISBN   978-3-642-02839-7.
  6. 1 2 3 4 Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. arXiv: 1407.8269 . doi:10.1007/s00355-016-1019-3. S2CID   8564247.
  7. Sánchez-Fernández, Luis; Elkind, Edith; Lackner, Martin; Fernández, Norberto; Fisteus, Jesús; Val, Pablo Basanta; Skowron, Piotr (2017-02-10). "Proportional Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). doi: 10.1609/aaai.v31i1.10611 . hdl: 10016/26166 . ISSN   2374-3468. S2CID   17538641.
  8. Aziz, Haris; Elkind, Edith; Huang, Shenwei; Lackner, Martin; Sánchez Fernández, Luis; Skowron, Piotr (2018). "On the Complexity of Extended and Proportional Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 32 (1): 902–909. doi: 10.1609/aaai.v32i1.11478 . S2CID   19124729.
  9. Skowron, Piotr (2021). "Proportionality Degree of Multiwinner Rules". Proceedings of the 22nd ACM Conference on Economics and Computation. EC-21. pp. 820–840. arXiv: 1810.08799 . doi:10.1145/3465456.3467641. ISBN   9781450385541. S2CID   53046800.
  10. 1 2 3 4 Peters, Dominik; Skowron, Piotr (2020). "Proportionality and the Limits of Welfarism". Proceedings of the 21st ACM Conference on Economics and Computation. EC'20. pp. 793–794. arXiv: 1911.11747 . doi:10.1145/3391403.3399465. ISBN   9781450379755. S2CID   208291203.{{cite book}}: CS1 maint: date and year (link)
  11. Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020). "Approval-Based Apportionment". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1854–1861. arXiv: 1911.08365 . doi:10.1609/aaai.v34i02.5553. S2CID   208158445.
  12. 1 2 3 4 5 Lackner, Martin; Skowron, Piotr (2023). Multi-Winner Voting with Approval Preferences. SpringerBriefs in Intelligent Systems. arXiv: 2007.01795 . doi:10.1007/978-3-031-09016-5. ISBN   978-3-031-09015-8. S2CID   244921148.
  13. Sánchez Fernández, Luis; Fisteus, Jesús (2019). "Monotonicity axioms in approval-based multi-winner voting rules" (PDF): 485–493. arXiv: 1710.04246 .{{cite journal}}: Cite journal requires |journal= (help)
  14. 1 2 Peters, Dominik (2018). "Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections": 1169–1176. arXiv: 1609.03537 .{{cite journal}}: Cite journal requires |journal= (help)
  15. 1 2 Aziz, Haris; Gaspers, Serge; Gudmundsson, Joachim; Mackenzie, Simon; Mattei, Nicholas; Walsh, Toby (2015). Computational Aspects of Multi-Winner Approval Voting. pp. 107–115. arXiv: 1407.3247 . ISBN   978-1-4503-3413-6.
  16. 1 2 Skowron, Piotr; Faliszewski, Piotr; Lang, Jérôme (2016). "Finding a collective set of items: From proportional multirepresentation to group recommendation". Artificial Intelligence. 241: 191–216. arXiv: 1402.3044 . doi:10.1016/j.artint.2016.09.003. S2CID   11313941.
  17. Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Knop, Dusan; Niedermeier, Rolf (2020). "Parameterized Algorithms for Finding a Collective Set of Items". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1838–1845. doi: 10.1609/aaai.v34i02.5551 . S2CID   213963505.
  18. Godziszewski, Michal; Batko, Pawel; Skowron, Piotr; Faliszewski, Piotr (2021). "An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (6): 5448–5455. doi: 10.1609/aaai.v35i6.16686 . S2CID   235306592.
  19. 1 2 Dudycz, Szymon; Manurangsi, Pasin; Marcinkowski, Jan; Sornat, Krzysztof (2020). "Tight Approximation for Proportional Approval Voting". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI-20. pp. 276–282. doi: 10.24963/ijcai.2020/39 . ISBN   978-0-9992411-6-5. S2CID   220484671.
  20. Byrka, Jaroslaw; Skowron, Piotr; Sornat, Krzysztof (2017). Proportional Approval Voting, Harmonic k-median, and Negative Association. Vol. 107. pp. 26:1–26:14. arXiv: 1704.02183 . doi:10.4230/LIPIcs.ICALP.2018.26. ISBN   9783959770767. S2CID   3839722.