Multiwinner voting

Multiwinner voting,[1] also called multiple-winner elections[2] or committee voting[3] or committee elections,[4] 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.

There are many scenarios in which multiwinner voting is useful. They can be broadly classified into three classes, based on the main objective in electing the committee:[5]

  1. Excellence. Here, each voter is an expert, and each vote expresses his/her opinion about which candidate/s is "better" for a certain task. The goal is to find the "best" candidates. An example application is shortlisting: selecting, from a list of candidate employees, a small set of finalists, who will proceed to the final stage of evaluation (e.g. using an interview). Here, each candidate is evaluated independently of the other candidates. If two candidates are similar, then probably both will be elected (if they are both good), or both will be rejected (if both are bad).
  2. Diversity. Here, the elected candidates should be as different as possible. For example, suppose the candidates are possible locations for constructing a facility, such as a fire station. Most citizens naturally prefer a fire station in the city center. However, there is no need to have two fire-stations in the same place; it is better to diversify the selection and put the second station in a more remote location. In contrast to the "excellence" setting, if two candidates are similar, then probably exactly one of them will be elected. Another scenario in which diversity is important is when a search engine selects results for display, or when an airline selects movies for screening during a flight.
  3. Proportionality. Here, the elected candidates should represent in scientifically-balanced way the diverse opinion held by the population of voters, measured by the votes they cast, as much as possible. This is a common goal in parliamentary elections; see proportional representation.

Basic concepts

A major challenge in the study of multiwinner voting is finding reasonable adaptations of concepts from single-winner voting. These can be classified based on the voting type - approval voting vs. ranked voting.

Some election systems elect multiple members by competition held among individual candidates. Such systems are some variations of Multiple non-transferable voting and Single transferable voting.

In other systems, candidates are grouped in committees (slates) and voters cast votes for the committees (or slates). These committee-based systems are described here:

Approval voting for committees
Main article: Multiwinner approval voting

Approval voting is a common method for single-winner elections and sometimes for multiwinner elections. In single-winner elections, each voter marks the candidate he approves, and the candidate with the most votes wins.

With multiwinner voting, there are many ways to decide which candidate should be elected. In some, each voter ranks the candidates; in others they cast X votes. As well, each voter may cast single or multiple votes.

Already in 1895, Thiele suggested a family of weight-based rules.[3][6] Each rule in the family is defined by a sequence of k weakly-positive weights, w1,...,wk (where k is the committee size). Each voter assigns, to each committee containing p candidates approved by the voter, a score equal to w1+...+wp. The committee with the highest total score is elected. Some common voting rules in Thiele's family are:

  • Multiple non-transferable vote (MNTV): the weight vector is (1,1,...,1). It is also called plurality-at-large approval-voting.
  • Approval-Chamberlin-Courant (ACC): the weight vector is (1,0,...,0). That is, each voter gives 1 point to a committee, iff it contains one of his approved candidates.
  • Proportional approval voting (PAV): the weight vector is the Harmonic progression (1, 1/2, 1/3, ...., 1/k).

There are rules based on other principles, such as minimax approval voting[7] and its generalizations,[8] Phragmen's voting rules.[9] and the Method of Equal Shares.[10][11]

Computing the winner with SNTV can be done in polynomial time, but with ACC it is NP-hard,[12] as well as with PAV.

Positional scoring rules for committees

Positional scoring rules are common in rank-based single-winner voting. Each voter ranks the candidates from best to worst, a pre-specified function assigns a score to each candidate based on his rank, and the candidate with the highest total score is elected.

In multiwinner voting held using these systems, we need to assign scores to committees rather than to individual candidates. There are various ways to do this, for example:[1]

  • Single non-transferable vote: each voter gives 1 point to a committee, if it contains his most preferred candidate. In other words: each voter votes for a single candidate in a contest that elects multiwinners, and the k candidates with the largest number of votes are elected. This generalizes First-past-the-post voting. It can be computed in polynomial time.
  • Multiple non-transferable vote (also called bloc voting): each voter gives 1 point to a committee for each open seat in his top k. In other words: each voter votes for k candidates where k seats are open, and the k candidates with the largest number of votes are elected.
  • k-Borda: each voter gives, to each committee member, his Borda count. Each voter ranks the candidates and the rankings are scored together. The k candidates with the highest total Borda score are elected.
  • Borda-Chamberlin-Courant (BCC): each voter gives, to each committee, the Borda count of his most preferred candidate in the committee.[13] Computing the winner with BCC is NP-hard.[12]

Condorcet committees

In single-winner voting, a Condorcet winner is a candidate who wins in every head-to-head election against each of the other candidates. A Condorcet method is a method that selects a Condorcet winner whenever it exists. There are several ways to adapt Condorcet's criterion to multiwinner voting:

  • The first adaptation was by Peter Fishburn:[14][15] a committee is a Condorcet committee iff it is preferred, by a majority of voters, to any other possible committee. Fishburn assumed that the voters rank committees by the number of members in their approval set (i.e., they have dichotomous preferences). Later works assumed that the voters rank committees by other criteria, such as by their Borda count. It is coNP-complete to check if a committee satisfies this criterion, and coNP-hard to decide if there exist a Condorcet committee.[16]
  • Another adaptation was by Gehrlein[17] and Ratliff:[18] a committee is a Condorcet set iff each candidate in it is preferred, by a majority of voters, to each candidate outside it. A multiwinner voting rule is sometimes called stable iff it selects a Condorcet set whenever it exists.[19] Some stable rules are:[20]
    • Multiwinner Copeland's method: each committee is scored by the "number of external defeats": the number of pairs (c,d) where c is in the committee, d is not, and c is preferred to d by a majority of the voters.
    • Multiwinner Minimax Condorcet method: each committee is scored by the "size of external opposition": the minimum, over all pairs (c,d), of the number of voters who prefer c.
    • Multiwinner variants of some other Condorcet rules.[21]
  • A third adaptation was by Elkind, Lang and Saffidine:[22] a Condorcet winning set is a set that, for each member d not in the set, some member c in the set is preferred to d by a majority. Based on this definition, they present a different multiwinner variant of the Minimax Condorcet method.

Other criteria

Computing Pareto-efficient committees is NP-hard in general.[23]

Excellence elections

Excellence means that the committee should contain the "best" candidates. Excellence-based voting rules are often called screening rules.[19] They are often used as a first step in a selection of a single best candidate, that is, a method for creating a shortlist. A basic property that should be satisfied by such a rule is committee monotonicity (also called house monotonicity, a variant of resource monotonicity): if some k candidates are elected by a rule, and then the committee size increases to k+1 and the rule is re-applied, then the first k candidates should still be elected. Some families of committee-monotone rules are:

  • Sequential rules:[19] using any single-winner voting rule, pick a single candidate and add it to the committee. Repeat the process k times.
  • Best-k rules:[1] using any scoring rule, assign a score to each candidate. Pick the k candidates with the highest scores.

The property of committee monotonicity is incompatible with the property of stability (a particular adaptation of Condorcet's criterion): there exists a single voting profile that admits a unique Condorcet set of size 2, and a unique Condorcet set of size 3, and they are disjoint (the set of size 2 is not contained in the set of size 3).[19]

On the other hand, there exists a family of positional scoring rules - the separable positional scoring rules - that are committee-monotone. These rules are also computable in polynomial time (if their underlying single-winner scoring functions are).[1] For example, k-Borda is separable while Multiple non-transferable vote is not.

Diversity elections

Diversity means that the committee should contain the top-ranked candidates of as many voters as possible. Formally, the following axioms are reasonable for diversity-centered applications:

  • Narrow-top criterion:[1] if there exists a committee of size k containing the top-ranked candidate of every voter, then it should be elected.
  • Top-member monotonicity:[24] if a committee is elected, and some voter shifts upwards the rank of his most-preferred winner, then the same committee should be elected.

Proportional elections
Main article: Justified representation

Proportionality means that each cohesive group of voters (that is: a group of voters with similar preferences) should be represented by a number of winners proportional to its size. Formally, if the committee is of size k, there are n voters, and some L*n/k voters rank the same L candidates at the top (or approve the same L candidates), then these L candidates should be elected. This principle is easy to implement when the voters vote for parties (in party-list systems), but it can also be adapted to approval voting or ranked voting; see justified representation.

Further reading
  • Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation.[25]
  • Budgeted Social Choice: From Consensus to Personalized Decision Making.[26]
  • Achieving fully proportional representation: Approximability results.[27]

See also
  • Participatory budgeting - can be seen as an extension of multiwinner voting in which each candidate has a "cost". In multiwinner voting, the price of each candidate is 1, and the budget is k.

References
  1. Elkind, Edith; Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii (2017-03-01). "Properties of multiwinner voting rules". Social Choice and Welfare. 48 (3): 599–632. doi:10.1007/s00355-017-1026-z. ISSN 1432-217X. PMC 7089675. PMID 32226187.
  2. "RangeVoting.org - Glossary". rangevoting.org. Retrieved 2021-06-25.
  3. 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. doi:10.1007/s00355-016-1019-3. S2CID 8564247.
  4. Bock, Hans-Hermann; Day, William H.E.; McMorris, F.R. (1998-05-01). "Consensus rules for committee elections". Mathematical Social Sciences. 35 (3): 219–232. doi:10.1016/S0165-4896(97)00033-4. ISSN 0165-4896.
  5. Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon (2017-10-26). "Multiwinner Voting: A New Challenge for Social Choice Theory". In Endriss, Ulle (ed.). Trends in Computational Social Choice. Lulu.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: multiple names: authors list (link)
  6. 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. ISSN 2374-3468. S2CID 17538641.
  7. Brams, Steven J.; Kilgour, D. Marc; Sanver, M. Remzi (2007-09-01). "A minimax procedure for electing committees". Public Choice. 132 (3): 401–420. doi:10.1007/s11127-007-9165-x. ISSN 1573-7101. S2CID 46632580.
  8. Amanatidis, Georgios; Barrot, Nathanaël; Lang, Jérôme; Markakis, Evangelos; Ries, Bernard (2015-05-04). "Multiple Referenda and Multiwinner Elections Using Hamming Distances: Complexity and Manipulability". Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems. AAMAS '15. Istanbul, Turkey: International Foundation for Autonomous Agents and Multiagent Systems: 715–723. ISBN 978-1-4503-3413-6.
  9. Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2017-02-10). "Phragmén's Voting Methods and Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). doi:10.1609/aaai.v31i1.10598. ISSN 2374-3468. S2CID 2290202.
  10. 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.
  11. 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.
  12. Procaccia, Ariel D.; Rosenschein, Jeffrey S.; Zohar, Aviv (2007-04-19). "On the complexity of achieving proportional representation". Social Choice and Welfare. 30 (3): 353–362. doi:10.1007/s00355-007-0235-2. S2CID 18126521.
  13. Chamberlin, John R.; Courant, Paul N. (1983). "Representative Deliberations and Representative Decisions: Proportional Representation and the Borda Rule". The American Political Science Review. 77 (3): 718–733. doi:10.2307/1957270. ISSN 0003-0554. JSTOR 1957270. S2CID 147162169.
  14. Fishburn, Peter C. (1981-10-01). "Majority committees". Journal of Economic Theory. 25 (2): 255–268. doi:10.1016/0022-0531(81)90005-3. ISSN 0022-0531.
  15. Fishburn, Peter C. (1981-12-01). "An Analysis of Simple Voting Systems for Electing Committees". SIAM Journal on Applied Mathematics. 41 (3): 499–502. doi:10.1137/0141041. ISSN 0036-1399.
  16. Darmann, Andreas (2013-11-01). "How hard is it to tell which is a Condorcet committee?". Mathematical Social Sciences. 66 (3): 282–292. doi:10.1016/j.mathsocsci.2013.06.004. ISSN 0165-4896. PMC 4376023. PMID 25843993.
  17. Gehrlein, William V. (1985-12-01). "The Condorcet criterion and committee selection". Mathematical Social Sciences. 10 (3): 199–209. doi:10.1016/0165-4896(85)90043-5. ISSN 0165-4896.
  18. Ratliff, Thomas C. (2003-12-01). "Some startling inconsistencies when electing committees". Social Choice and Welfare. 21 (3): 433–454. doi:10.1007/s00355-003-0209-y. ISSN 1432-217X. S2CID 36949675.
  19. Barberà, Salvador; Coelho, Danilo (2008). "How to choose a non-controversial list with k names". Social Choice and Welfare. 31 (1): 79–96. doi:10.1007/s00355-007-0268-6. ISSN 0176-1714. JSTOR 41107910. S2CID 16974573.
  20. Coelho, Danilo; Barberà, Salvador (2005). Understanding, evaluating and selecting voting rules through games and axioms. Bellaterra: Universitat Autònoma de Barcelona. ISBN 978-84-689-0967-7.
  21. Kamwa, Eric (2017-05-01). "On stable rules for selecting committees". Journal of Mathematical Economics. 70: 36–44. doi:10.1016/j.jmateco.2017.01.008. ISSN 0304-4068.
  22. Elkind, Edith; Lang, Jérôme; Saffidine, Abdallah (2015). "Condorcet winning sets". Social Choice and Welfare. 44 (3): 493–517. doi:10.1007/s00355-014-0853-4. ISSN 0176-1714. JSTOR 43662603. S2CID 31128109.
  23. Aziz, Haris; Monnot, Jérôme (2020-02-17). "Computing and testing Pareto optimal committees". Autonomous Agents and Multi-Agent Systems. 34 (1): 24. arXiv:1803.06644. doi:10.1007/s10458-020-09445-y. ISSN 1573-7454. S2CID 3955482.
  24. Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii; Talmon, Nimrod (2016-07-09). "Committee scoring rules: axiomatic classification and hierarchy". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 250–256. ISBN 978-1-57735-770-4.
  25. Skowron, Piotr; Faliszewski, Piotr; Lang, Jerome (2015-01-01). Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation. pp. 2131–2137. arXiv:1402.3044. Bibcode:2014arXiv1402.3044S. ISBN 978-0262511292. {{cite book}}: |journal= ignored (help)
  26. Lu, Tyler; Boutilier, Craig (2011-01-01). Budgeted Social Choice: From Consensus to Personalized Decision Making. pp. 280–286. doi:10.5591/978-1-57735-516-8/IJCAI11-057. ISBN 9781577355137. {{cite book}}: |journal= ignored (help)
  27. Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (2015-05-01). "Achieving fully proportional representation: Approximability results". Artificial Intelligence. 222: 67–103. arXiv:1312.4026. doi:10.1016/j.artint.2015.01.003. S2CID 467056.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.