Social:Multiwinner approval voting

From HandWiki

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

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.

Majoritarian approval voting

In majoritarian approval voting, the candidates with the largest number of approvals are selected. It is a type of multiple non-transferable vote. It does not provide proportional representation, and is subject to the Burr dilemma, among other problems. There are several variants:

  • In block approval voting (also called unlimited voting), each voter can select an unlimited number of candidates, and the k candidates with the most approval votes win (where k is the predetermined committee size).
  • In limited block approval voting, each voter can select a limited number of candidates, but that limit is more than k.
  • In plurality block voting, each voter has up to as many votes as there are seats to be filled, but no more than one per candidate. Plurality block voting provides majoritarian representation.
  • In limited voting, each voter has less votes than seats to be filled. Limited voting is semi-proportional, as it allows the minority to focus on a small number of candidates and guarantee that at least some of them wins. Voting reform advocates refrain from calling it approval voting,[3] similarly to how first-past-the-post or single-winner limited voting are not considered approval voting.

Example for comparison

Candidates are running in a 3 member district of the 10000 voters. Voters may not cast more than one vote for a single candidate.

  • Under block approval voting (unlimited voting) voter may vote for any number of candidates.
  • Under limited block approval voting voters may cast 6 votes maximum (twice as many as there are winners).
  • Under (plurality) block voting, voters may cast 3 votes (but do not have to).
  • Under limited (block) voting, voters may cast 2 votes maximum.
  • Under the single non-transferable vote, voters may cast 1 vote.

Party A has about 35% support among the electorate (with one particularly well-like candidate), Party B around 25% (with two well-like candidates) and the remaining voters primarily support independent candidates, but mostly lean towards party B if they have to choose between the two parties. All voters vote sincerely, there is no tactical voting.

Candidate Party Block approval voting Limited block approval voting Plurality block voting Limited (block) voting Single non-transferable vote
Votes % Elected? Votes % Elected? Votes % Elected? Votes % Elected? Votes % Elected?
Candidate A1 Party A 4200 42% 8. 4000 40% 5. 3555 36% 3. Yes 1800 18% 4. 800 8% 4.
Candidate A2 Party A 4500 45% 5. 4100 40% 4. 3700 37% 1. Yes 3500 35% 1. Yes 1900 19% 1. Yes
Candidate A3 Party A 3900 39% 9. 3800 40% 7. 3600 36% 2. Yes 2000 20% 2. Yes 700 7% 9.
Candidate B1 Party B 5200 52% 1. Yes 4900 49% 1. Yes 2600 26% 4. 1750 18% 5. 900 9% 3. Yes
Candidate B2 Party B 5000 50% 2. Yes 4600 46% 3. Yes 2500 25% 5. 1950 20% 3. Yes 1100 11% 2. Yes
Candidate B3 Party B 4700 47% 4. 4200 42% 2. Yes 2400 24% 6. 1425 14% 7. 400 4% 12.
Candidate I1 Independent 4400 44% 6. 3800 38% 7. 2300 23% 8. 1400 14% 8. 800 8% 4.
Candidate I2 Independent 4900 49% 3. Yes 4000 40% 5. 2395 20% 7. 1500 15% 6. 800 8% 4.
Candidate I3 Independent 4400 44% 6. 3700 37% 9. 1900 19% 9. 1300 13% 9. 700 7% 7.
Candidate I4 Independent 3900 39% 9. 3200 32% 10. 1800 15% 10 1200 12% 10. 700 7% 7.
Candidate I5 Independent 2600 26% 11. 2000 20% 11. 650 7% 11. 625 6% 11. 600 6% 10.
Candidate I6 Independent 2300 23% 12. 1700 17% 12. 600 6% 12. 550 6% 12. 500 5% 11.
TOTAL votes cast 50000 44000 28000 19000 10000
TOTAL possible votes 120000 60000 30000 20000 10000
Voters 10000 100% 10000 100% 10000 100% 10000 100% 10000 100%
  • Under the single non-transferable vote (not a type of approval voting), the 3 most popular candidates according to voters first preferences are elected, regardless of party affiliation.
  • Under limited voting, it is most likely that the party with a plurality takes 2 seats (the number of votes each voter has), and the minority party receives the remaining seats.
  • Under (plurality) block voting, the party with plurality support most likely wins all seats.
  • Under limited block approval voting voters, voters of independent candidates may use their extra votes to help candidates other than their top3, which may result in the reversal of the plurality block vote result.
  • Under block approval voting, any party-affiliated or independent candidates particularly popular among the population may be elected, but it is possible that about half of the population can elect no representatives.

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,[4][5] Sequential proportional approval voting, Phragmen's voting rules and the Method of Equal Shares.[6][7] 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)[8] 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[9] excess method,[10] and minimax approval.[11] 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: 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:

  • Inclusion-strategyproofness means that no manipulation can result in electing a strict superset of the manipulator's approved candidates (as in the PAV example above).
  • Cardinality-strategyproofness is a stronger property: it means that no manipulation can result in electing a larger number of the manipulator's approved candidates.

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

  • Independence of irrelevant alternatives means that the relative merit of two committees is not influenced by candidates outside these two committees. This prevents a certain form of strategic voting: altering one’s vote with respect to irrelevant candidates to manipulate the outcome.
  • Monotonicity means that a voter never loses from revealing his true set of approved candidates (though a voter gain from approving more candidates). This prevents another form of strategic voting: hiding some approved candidates.

Lackner and Skowron[12] 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[13] 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:

  • Subset-inclusion-strategyproofness: if an agent i with approved-candidates Ai reports a subset of Ai (and all other reports are the same), then no previously-unelected candidate from Ai is elected. This property is weaker than inclusion-strategyproofness, as it considers only one type of manipulation: reporting a subset of one’s truthful approval set.
  • Party-list-proportionality: We define a party-list profile as a profile characteristic of party-list voting, that is: there is a partition of the voters into k groups and a partition of the projects into k subsets, such that each voter from group i votes only and for all projects in group i. Party-list proportionality means that, in a party-list profile, if some singleton ballot {x} appears at least B/n times, then x is elected. This property is weaker than the property of lower quota from apportionment, and weaker than the justified representation property.
    • An alternative property, for which the impossibility holds, is disjoint diversity. It means that, in a party-list profile with at most k different parties, the rule selects at least one member from each party.
  • Weak efficiency: if a candidate x is not supported by anyone, and there are at least k candidates that are supported, then x is not elected.

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[12] 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 utiltiarian AV are less manipulable than rules that are more similar to CC, and the proportional rules are in-between.

Barrot, Lang and Yokoo[14] 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[15] 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[12] define a strong extension called stochastic-dominance-strategyproofness, and prove that it characterizes the utilitarian approval voting rule.

Kluiving, Vries, Vrijbergen, Boixel and Endriss[16] provide a more thorough discussion of strategyproofness of irresolute rules; in particular, they extend the impossibility result of Peters to irresolute rules. Duddy[17] 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.[18]

Scheuerman, Harman, Mattei and Venable[19][20] 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[21] 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[22] 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[23] extend these definitions to settings with mixed divisible and indivisible candidates (see justified representation#divisible).

Usage

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

Block approval voting

  • Korean villages used block approval voting for competitive elections following the surrender of Japan, according to observations made by journalist Anna Louise Strong in 1946: "In one village there were twelve candidates, of whom five were to be chosen for the Village Committee. Each voter was given twelve cards, bearing the names of the candidates. He then cast his chosen ones into the white box and the rejected ones into the black."[24]
  • Several Swiss cantons elect their government using such methods and so do French cities with population below 1000.[25]
  • In 1963, the proportional representation system in East Germany was replaced by a procedure in which the candidates had to receive more than 50% of the votes. Had more candidates than seats in this constituency won the majority, the order of the list would determine who would join the Volkskammer.

Further reading

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

Implementations

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" (in en). Social Choice and Welfare 48 (2): 461–485. doi:10.1007/s00355-016-1019-3. https://ideas.repec.org/a/spr/sochwe/v48y2017i2d10.1007_s00355-016-1019-3.html. 
  3. ↑ "Voting Systems Confused with Approval Voting". https://www.electionscience.org/library/voting-systems-confused-with-approval-voting/. 
  4. ↑ http://www2.math.uu.se/~svante/papers/sjV9.pdf [bare URL PDF]
  5. ↑ Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2016). "Multiwinner Approval Rules as Apportionment Methods". arXiv:1611.08691 [cs.GT].
  6. ↑ 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. doi:10.1145/3391403.3399465. ISBN 9781450379755. 
  7. ↑ 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. 
  8. ↑ Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020-04-03). "Approval-Based Apportionment" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 34 (2): 1854–1861. doi:10.1609/aaai.v34i02.5553. ISSN 2374-3468. https://ojs.aaai.org/index.php/AAAI/article/view/5553. 
  9. ↑ Plaza, Enric. Technologies for political representation and accountability. http://www.iiia.csic.es/~enric/papers/egov.pdf. Retrieved 2011-06-17. 
  10. ↑ https://as.nyu.edu/content/dam/nyu-as/faculty/documents/Excess%20Method%20(final).pdf [bare URL PDF]
  11. ↑ LeGrand, Rob; Markakis, Evangelos; Mehta, Aranyak (2007). Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems - AAMAS '07. pp. 1. doi:10.1145/1329125.1329365. ISBN 9788190426275. http://pages.cs.aueb.gr/~markakis/research/aamas07-minmax.pdf. Retrieved 2011-06-17. 
  12. ↑ 12.0 12.1 12.2 12.3 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. https://dl.acm.org/doi/abs/10.5555/3304415.3304464. 
  13. ↑ Peters, Dominik (2021). "Proportionality and Strategyproofness in Multiwinner Elections". arXiv:2104.08594 [cs.GT].
  14. ↑ 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. https://dl.acm.org/doi/abs/10.5555/3091125.3091212. 
  15. ↑ 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. https://dl.acm.org/doi/abs/10.5555/3463952.3463984. 
  16. ↑ 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, https://ebooks.iospress.nl/doi/10.3233/FAIA200085, retrieved 2023-10-27 
  17. ↑ 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. https://www.sciencedirect.com/science/article/pii/S0165176514001372. 
  18. ↑ 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. https://www.jstor.org/stable/1955800. 
  19. ↑ 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. ISBN 978-1-4503-7518-4. https://dl.acm.org/doi/abs/10.5555/3398761.3399052. 
  20. ↑ Scheuerman, Jaelle; Harman, Jason; Mattei, Nicholas; Venable, K. Brent (2021-05-18). "Modeling Voters in Multi-Winner Approval Voting" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 35 (6): 5709–5716. doi:10.1609/aaai.v35i6.16716. ISSN 2374-3468. https://ojs.aaai.org/index.php/AAAI/article/view/16716. 
  21. ↑ 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. https://dl.acm.org/doi/abs/10.5555/3491440.3491459. 
  22. ↑ Bei, Xiaohui; Lu, Xinhang; Suksompong, Warut (2022-06-28). "Truthful Cake Sharing" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 36 (5): 4809–4817. doi:10.1609/aaai.v36i5.20408. ISSN 2374-3468. https://ojs.aaai.org/index.php/AAAI/article/view/20408. 
  23. ↑ Lu, Xinhang; Peters, Jannik; Aziz, Haris; Bei, Xiaohui; Suksompong, Warut (2023-06-26). "Approval-Based Voting with Mixed Goods" (in en). Proceedings of the AAAI Conference on Artificial Intelligence 37 (5): 5781–5788. doi:10.1609/aaai.v37i5.25717. ISSN 2374-3468. https://ojs.aaai.org/index.php/AAAI/article/view/25717. 
  24. ↑ Strong, Anna. "In North Korea: First Eye-Witness Report" (in en). https://www.marxists.org/reference/archive/strong-anna-louise/1949/in-north-korea/ch04.htm. 
  25. ↑ Vander Straeten, Karine; Lachat, Romain; Laslier, Jean-François (2018). "Chapter 9: Strategic voting in multi-winner elections with approval balloting: An application to the 2011 regional government election in Zurich". 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. 
  26. ↑ Lackner, Martin; Skowron, Piotr (2023) (in English). Multi-Winner Voting with Approval Preferences. Springer Nature. ISBN 978-3-031-09016-5. https://library.oapen.org/handle/20.500.12657/60149. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Social:Multiwinner_approval_voting&oldid=3311815"