Multiwinner approval voting

Last updated

Multiwinner approval voting [1] , also called approval-based committee (ABC) voting, [2] 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.

Contents

Multiwinner approval voting is an adaptation of approval voting to multiwinner elections. In a single-winner approval voting system, it is easy to determine the winner: it is the candidate approved by the largest number of voters. In multiwinner approval voting, there are many different ways to decide which candidates will be elected.

Approval block voting

In approval block voting (also called unlimited voting), each voter either approves or disapproves of each candidate, and the k candidates with the most approval votes win (where k is the predetermined committee size). It does not provide proportional representation.

Proportional approval voting

Proportional approval voting refers to voting methods which aim to guarantee proportional representation in case all supporters of a party approve all candidates of that party. Such methods include Proportional approval voting, [3] [4] Sequential proportional approval voting, Phragmen's voting rules and the Method of Equal Shares. [5] [6] In the general case, proportional representation is replaced by a more general requirement called justified representation.

In these methods, the voters fill out a standard approval-type ballot, but the ballots are counted in a specific way that produces proportional representation. The exact procedure depends on which method is being used.

Party-approval voting

Party-approval voting (also called approval-based apportionment) [7] is a method in which each voter can approve one or more parties, rather than approving individual candidates. It is a combination of multiwinner approval voting with party-list voting.

Other methods

Other ways of extending Approval voting to multiple winner elections are satisfaction approval voting [8] excess method, [9] and minimax approval. [10] These methods use approval ballots but count them in different ways.

Strategic voting

Many multiwinner voting rules can be manipulated: voters can increase their satisfaction by reporting false preferences.

Example

The most common form of manipulation is subset-manipulation, in which a voter reports only a strict subset of his approved candidates. This manipulation is called Hylland free riding [ citation needed ]: the manipulator free-rides on others approving a candidate, and pretends to be worse off than they actually are. Then, the rule is induced to "compensate" the manipulator by electing more of their approved candidates.

As an example, suppose we use the PAV rule with k=3, there are 4 candidates (a,b,c,d), and 5 voters, of whom three support a,b,c and two support a,b,d. Then, PAV selects a,b,c. But if the last voter reports only d, then PAV selects a,b,d, which is strictly better for him.

Strategyproofness properties

A multiwinner voting rule is called strategyproof if no voter can increase his satisfaction by reporting false preferences. There are several variants of this property, depending on the potential outcome of the manipulation:

Strategyproofness properties can also be classified by the type of potential manipulations: [11]

Lackner and Skowron [11] focus on the class of ABC-counting rules (an extension of positional scoring rules to multiwinner voting). Among these rules, Thiele's rules are the only ones satisfying IIA, and dissatisfaction-counting-rules are the only ones satisfying monotonicity. Utilitarian approval voting is the only non-trivial ABC counting rule satisfying both axioms. It is also the only non-trivial ABC counting rule satisfying SD-strategyproofness - an extension of cardinality-strategyproofness to irresolute rules. If utilitarian approval voting is made resolute by a bad tie-breaking rule, it might become non-strategyproof.

Strategyproofness and proportionality

Cardinality-strategyproofness and inclusion-strategyproofness are satisfied by utilitarian approval voting (majoritarian approval voting rule with unlimited ballots), but not by any other known rule satisfying proportionality.

This raises the question of whether there is any rule that is both strategyproof and proportional. The answer is no: Dominik Peters [12] proved that no multiwinner voting rule can simultaneously satisfy a weak form of proportionality, a weak form of strategyproofness, and a weak form of efficiency. Specifically, the following three properties are incompatible whenever k ≥ 3, n is a multiple of k, and the number of candidates is at least k+1:

The proof is by induction; the base case (k=3) was found by a SAT solver. For k=2, the impossibility holds with a slightly stronger strategyproofness axiom.

Degree of manipulability

Lackner and Skowron [11] quantified the trade-off between strategyproofness and proportionality by empirically measuring the fraction of random-generated profiles for which some voter can gain by misreporting. Example results, when each voter approves 2 candidates, are: Phragmen's sequential rule is manipulable in 66% of the profiles; Sequential PAV - 68%; PAV - 71%; Satisfaction AV and Maximin AV - 86%; Approval Monroe - 92%; Chamberlin-Courant - 95%. They also checked manipulability of Thiele's rules with p-geometric score function (where the scores are powers of 1/p, for some fixed p). Note that p=1 yields utilitarian AV, whereas p→∞ yields Chamberlin-Courant. They found out that increasing p results in increasing manipulability: rules which are more similar to utilitarian AV are less manipulable than rules that are more similar to CC, and the proportional rules are in-between.

Barrot, Lang and Yokoo [13] present a similar study of another family of rules, based on ordered weighted averaging and the Hamming distance. Their family is also characterized by a parameter p, where p=0.5 yields utilitarian AV, whereas p=1 yields egalitarian AV. They arrive at a similar conclusion: increasing p results in a larger fraction of random profiles that can be manipulated.

Restricted preference domains

One way to overcome impossibility results is to consider restricted preference domains. Botan [14] consider party-list preferences, that is, profiles in which the voters are partitioned into disjoint subsets, each of which votes for a disjoint subset of candidates. She proves that Thiele's rules (such as PAV) resist some common forms of manipulations, and it is strategyproof for "optimistic" voters.

Irresolute rules

The strategyproofness properties can be extended to irresolute rules (rules that return several tied committees). Lackner and Skowron [11] define a strong extension called stochastic-dominance-strategyproofness, and prove that it characterizes the utilitarian approval voting rule.

Kluiving, Vries, Vrijbergen, Boixel and Endriss [15] provide a more thorough discussion of strategyproofness of irresolute rules; in particular, they extend the impossibility result of Peters to irresolute rules. Duddy [16] presents an impossibility result using a different set of axioms.

Non-dichotomous preferences

There is an even stronger variant of strategyproofness called Non-dichotomous strategyproofness: it assumes that agents have an underlying non-dichotomous preference relation, and they use approvals only as an approximation. It means that no manipulation can result in electing a committee that is ranked higher by the manipulator. Non-dichotomous strategproofness is not satisfied by any non-trivial multiwinner voting rule. [17]

Scheuerman, Harman, Mattei and Venable [18] [19] present behavioral studies on how people with non-dichotomous preferences behave when they need to provide an approval ballot, when the outcome is decided using utilitarian approval voting.

Extensions

Variable number of winners

Freeman, Kahng and Pennock [20] study multiwinner approval voting in which the number of winners is not fixed in advance, but determined by the votes. For example, when selecting candidates for interview, if there are many strong candidates, then the number of candidates selected for interview may be larger. They extend the notion of average satisfaction to this setting.

Divisible committees

Bei, Lu and Suksompong [21] extend the committee election model to a setting in which there is a continuum of candidates, represented by a real interval [0,c], as in fair cake-cutting. The goal is to select a subset of this interval, with total length at most k, where here k and c can be any real numbers with 0<k<c. They generalize the justified representation notion to this setting. Lu, Peters, Aziz, Bei and Suksompong [22] extend these definitions to settings with mixed divisible and indivisible candidates (see justified representation).

Usage

Multiwinner approval voting, while less common than standard approval voting, is used in several places.

Block approval voting

Further reading

A book on approval-based committee voting. [25]

Implementations

Related Research Articles

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 candidates in any way they want. This criterion was proposed by the British philosopher and logician Michael Dummett.

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.

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

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

In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973. It states that for any deterministic process of collective decision, at least one of the following three properties must hold:

  1. The process is dictatorial, i.e. there is a single voter whose vote chooses the outcome.
  2. The process limits the possible outcomes to two options only.
  3. The process is not straightforward; the optimal ballot for a voter depends on their beliefs about other voters' ballots.

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, at-large, or committeevoting refers to electoral systems that elect several candidates at once. Such methods can be used to elect parliaments or committees.

Fractional approval voting is an electoral system using approval ballots, in which the outcome is fractional: for each alternative j there is a fraction pj between 0 and 1, such that the sum of pj is 1. It can be seen as a generalization of approval voting: in the latter, one candidate wins and the other candidates lose. The fractions pj can be interpreted in various ways, depending on the setting. Examples are:

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.

Budget-proposal aggregation (BPA) is a problem in social choice theory. A group has to decide on how to distribute its budget among several issues. Each group-member has a different idea about what the ideal budget-distribution should be. The problem is how to aggregate the different opinions into a single budget-distribution program.

Participatory budgeting experiments are experiments done in the laboratory and in computerized simulations, in order to check various ethical and practical aspects of participatory budgeting. These experiments aim to decide on two main issues:

  1. Front-end: which ballot type to use as an input? See Participatory budgeting ballot types for common types of ballots.
  2. Back-end: Which rule to use for aggregating the voters' preferences? See combinatorial participatory budgeting for detailed descriptions of various aggregation rules.

Belief merging, also called belief fusion or propositional belief merging, is a process in which an individual agent aggregates possibly conflicting pieces of information, expressed in logical formulae, into a consistent knowledge-base. Applications include combining conflicting sensor information received by the same agent and combining multiple databases to build an expert system. It also has applications in multi-agent systems.

In participatory budgeting, one of the design decisions is what ballot type will be used for preference elicitation - how each voter should express his or her preferences over the projects. Different cities use different ballot types, and various experiments have been conducted to assess the advantages and disadvantages of each type.

An expanding approvals rule(EAR) is a rule for multi-winner elections, which allows 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. ↑ Aziz, Haris; Gaspers, Serge; Gudmundsson, Joachim; Mackenzie, Simon; Mattei, Nicholas; Walsh, Toby (2014-07-11). "Computational Aspects of Multi-Winner Approval Voting". arXiv: 1407.3247 [cs.GT].
  2. ↑ 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.
  3. ↑ http://www2.math.uu.se/~svante/papers/sjV9.pdf [ bare URL PDF ]
  4. ↑ Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2016). "Multiwinner Approval Rules as Apportionment Methods". arXiv: 1611.08691 [cs.GT].
  5. ↑ 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.
  6. ↑ Pierczyński, Grzegorz; Peters, Dominik; Skowron, Piotr (2020). "Proportional Participatory Budgeting with Additive Utilities". Proceedings of the 2021 Conference on Neural Information Processing Systems. NeurIPS'21. arXiv: 2008.13276 .
  7. ↑ Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020-04-03). "Approval-Based Apportionment". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1854–1861. arXiv: 1911.08365 . doi:10.1609/aaai.v34i02.5553. ISSN   2374-3468. S2CID   208158445.
  8. ↑ Plaza, Enric. Technologies for political representation and accountability (PDF). CiteSeerX   10.1.1.74.3284 . Retrieved 2011-06-17.
  9. ↑ https://as.nyu.edu/content/dam/nyu-as/faculty/documents/Excess%20Method%20(final).pdf [ bare URL PDF ]
  10. ↑ LeGrand, Rob; Markakis, Evangelos; Mehta, Aranyak (2007). Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems - AAMAS '07 (PDF). p. 1. doi:10.1145/1329125.1329365. ISBN   9788190426275. S2CID   13870664 . Retrieved 2011-06-17.
  11. 1 2 3 4 Lackner, Martin; Skowron, Piotr (2018-07-13). "Approval-based multi-winner rules and strategic voting". Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI'18. Stockholm, Sweden: AAAI Press: 340–346. ISBN   978-0-9992411-2-7.
  12. ↑ Peters, Dominik (2021). "Proportionality and Strategyproofness in Multiwinner Elections". arXiv: 2104.08594 [cs.GT].
  13. ↑ Barrot, Nathanaël; Lang, Jérôme; Yokoo, Makoto (2017-05-08). "Manipulation of Hamming-based Approval Voting for Multiple Referenda and Committee Elections". Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. AAMAS '17. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 597–605.
  14. ↑ Botan, Sirin (2021-05-03). "Manipulability of Thiele Methods on Party-List Profiles". Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '21. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 223–231. ISBN   978-1-4503-8307-3.
  15. ↑ Kluiving, Boas; de Vries, Adriaan; Vrijbergen, Pepijn; Boixel, Arthur; Endriss, Ulle (2020), "Analysing Irresolute Multiwinner Voting Rules with Approval Ballots via SAT Solving", ECAI 2020, IOS Press, pp. 131–138, doi:10.3233/faia200085 , retrieved 2023-10-27
  16. ↑ Duddy, Conal (2014-07-01). "Electing a representative committee by approval ballot: An impossibility result". Economics Letters. 124 (1): 14–16. doi:10.1016/j.econlet.2014.04.009. ISSN   0165-1765.
  17. ↑ Niemi, Richard G. (1984). "The Problem of Strategic Behavior under Approval Voting". The American Political Science Review. 78 (4): 952–958. doi:10.2307/1955800. ISSN   0003-0554. JSTOR   1955800. S2CID   146976380.
  18. ↑ Scheuerman, Jaelle; Harman, Jason L.; Mattei, Nicholas; Venable, K. Brent (2020-05-13). "Heuristic Strategies in Uncertain Approval Voting Environments". Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '20. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 1993–1995. arXiv: 1912.00011 . ISBN   978-1-4503-7518-4.
  19. ↑ Scheuerman, Jaelle; Harman, Jason; Mattei, Nicholas; Venable, K. Brent (2021-05-18). "Modeling Voters in Multi-Winner Approval Voting". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (6): 5709–5716. arXiv: 2012.02811 . doi: 10.1609/aaai.v35i6.16716 . ISSN   2374-3468. S2CID   227335243.
  20. ↑ Freeman, Rupert; Kahng, Anson; Pennock, David M. (2021-01-07). "Proportionality in approval-based elections with a variable number of winners". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI'20. Yokohama, Yokohama, Japan: 132–138. ISBN   978-0-9992411-6-5.
  21. ↑ Bei, Xiaohui; Lu, Xinhang; Suksompong, Warut (2022-06-28). "Truthful Cake Sharing". Proceedings of the AAAI Conference on Artificial Intelligence. 36 (5): 4809–4817. arXiv: 2112.05632 . doi:10.1609/aaai.v36i5.20408. ISSN   2374-3468.
  22. ↑ Lu, Xinhang; Peters, Jannik; Aziz, Haris; Bei, Xiaohui; Suksompong, Warut (2023-06-26). "Approval-Based Voting with Mixed Goods". Proceedings of the AAAI Conference on Artificial Intelligence. 37 (5): 5781–5788. arXiv: 2211.12647 . doi: 10.1609/aaai.v37i5.25717 . ISSN   2374-3468.
  23. ↑ Strong, Anna. "In North Korea: First Eye-Witness Report". Marxists Internet Archive. Retrieved May 14, 2019.
  24. ↑ Vander Straeten, Karine; Lachat, Romain; Laslier, Jean-François (2018). Stephenson, Laura B.; Aldrich, John H.; Blais, André (eds.). Chapter 9: Strategic voting in multi-winner elections with approval balloting: An application to the 2011 regional government election in Zurich. Ann Arbor, Michigan: The University of Michigan Press. pp. 178–202.{{cite encyclopedia}}: |work= ignored (help)
  25. ↑ Lackner, Martin; Skowron, Piotr (2023). Multi-Winner Voting with Approval Preferences. Springer Nature. hdl:20.500.12657/60149. ISBN   978-3-031-09016-5.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.