Multiwinner voting

Last updated

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

Contents

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: [4]

  1. Excellence. Here, each voter expresses their 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

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 called Thiele's voting rules. [2] [5] 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:

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

The complexity of determining the winners vary: MNTV winners can be found in polynomial time, while Chamberlin-Courant [11] and PAV are both NP-hard.

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]

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:

Excellence elections

Excellence means that the committee should contain the "best" candidates. Excellence-based voting rules are often called screening rules. [18] 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:

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). [18]

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:

Proportional elections

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 and proportionality for solid coalitions.

See also

Related Research Articles

<span class="mw-page-title-main">Approval voting</span> Single-winner electoral system

Approval voting is an electoral system in which voters can select any number of candidates instead of selecting only one.

In an election, a candidate is called a Condorcet, beats-all, or majority-rule winner if more than half of voters would support them in any one-on-one matchup with another candidate. Such a candidate is also called an undefeated, or tournament champion, by analogy with round-robin tournaments. Voting systems where a majority-rule winner will always win the election are said to satisfy the Condorcetcriterion. Condorcet voting methods extend majority rule to elections with more than one candidate.

The Borda count electoral system can be combined with an instant-runoff procedure to create hybrid election methods that are called Nanson method and Baldwin method. Both methods are designed to satisfy the Condorcet criterion, and allow for incomplete ballots and equal rankings.

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.

The Borda count is a family of positional voting rules which gives each candidate, for each ballot, a number of points corresponding to the number of candidates ranked lower. In the original variant, the lowest-ranked candidate gets 0 points, the next-lowest gets 1 point, etc., and the highest-ranked candidate gets n − 1 points, where n is the number of candidates. Once all votes have been counted, the option or candidate with the most points is the winner. The Borda count is intended to elect broadly acceptable options or candidates, rather than those preferred by a majority, and so is often described as a consensus-based voting system rather than a majoritarian one.

The majority loser criterion is a criterion to evaluate single-winner voting systems. The criterion states that if a majority of voters prefers every other candidate over a given candidate, then that candidate must not win.

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.


A major branch of social choice theory is devoted to the comparison of electoral systems, otherwise known as social choice functions. Viewed from the perspective of political science, electoral systems are rules for conducting elections and determining winners from the ballots cast. From the perspective of economics, mathematics, and philosophy, a social choice function is a mathematical function that determines how a society should make choices, given a collection of individual preferences.

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.

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.

Compilation complexity is the smallest number of bits required to summarize a input to a function, such that the output of the function can be computed correctly. The notion was particularly studied in voting theory. Often, a group has to accept a decision, but some of the voters have not arrived yet. It is desired to take the votes of the present voters and summarize them such that, when the other voters arrive, we can determine the winner. The compilation complexity of a voting-rule is the smallest number of bits required for the summary.

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. 1 2 3 4 5 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. 1 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. 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.
  4. 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)
  5. 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.
  6. 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.
  7. 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.
  8. 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). arXiv: 2102.12305 . doi: 10.1609/aaai.v31i1.10598 . ISSN   2374-3468. S2CID   2290202.
  9. 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.
  10. Pierczyński, Grzegorz; Peters, Dominik; Skowron, Piotr (2021). "Proportional Participatory Budgeting with Additive Utilities". Proceedings of the 2021 Conference on Neural Information Processing Systems. NeurIPS'21. arXiv: 2008.13276 .
  11. 1 2 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 1 2 3 4 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.
  19. 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.
  20. 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. S2CID   125508393.
  21. 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.
  22. 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.