Multiwinner voting

Multiwinner^[1] or committee^[2][3] voting refers to electoral systems that elect several candidates at once. Such methods can be used to elect parliaments or committees or boards of directors.

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, voters judge the quality of each candidate individually. The goal is to find the "objectively" 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 others. If two candidates are similar, then probably both will be elected or both will be rejected.
2. Diversity. Here, the elected candidates should be as different as possible. For example, suppose the contest is about choosing locations for two fire stations or other facility. Most citizens naturally prefer a fire station in the city centre. 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 less central location. In contrast to the "excellence" setting, if two candidates are similar and are chosen, the best result will not result. 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. As well, elected members should represent the diverse opinion held by the voters, shown by the votes they cast, as much as possible.
3. Proportionality. Here, elected candidates should fairly represent the diverse voting groups as shown by the votes cast by the voters, measured by the votes they cast, as much as possible. A majority group should win the majority of seats; less-popular parties should win fewer seats. This is a common goal in parliamentary elections; see proportional representation.

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—ranked voting as used in instant-runoff voting and single transferable voting vs. approval voting.

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

Some election systems elect multiple members by competition held among individual candidates. Each voter votes directly for one or more individual candidates. These systems include Plurality block voting and single non-transferable voting, adaptations of first-past-the-post voting to a multiwinner contest. Under SNTV, each voter casts only one vote, and that means no one party can take all the seats; although, because plurality system is used to allocate seats, parties are not guaranteed to take their proportional share of seats. A ranked-vote version of SNTV, Single transferable voting, elects a mixed, balanced group of members in a single contest in almost all cases.

In other systems, candidates are grouped in committees (slates or party lists) and voters cast votes for the committees (or slates). Sometimes only one slate or party takes all the seats, and sometimes members of various slates are elected.

Single transferable voting elects a mixed, balanced group of members in a single contest. It does this partly by allowing votes cast on unelectable candidates to be transferred to more-popular candidates. The quota used in STV ensures minority representation—no one group can take all the seats unless the district magnitude is small, or one party takes a great proportion of the votes cast.

Approval voting is a common method for single-winner elections and sometimes for multiwinner elections. In single-winner elections, voters mark their approved candidates, and the candidate with the most votes wins.

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, w₁, ..., w_k (where k is the committee size). Each voter assigns, to each committee containing p candidates approved by the voter, a score equal to w₁ + ... + w_p. 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, if and only if 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^[6] and its generalisations,^[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 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: voters each give one point to a committee, if it contains their 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.^[12] Computing the winner with BCC is NP-hard.^[11]

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;^[13][14] a committee is a Condorcet committee if 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 exists a Condorcet committee.^[15]
• Another adaptation was by Gehrlein^[16] and Ratliff;^[17] a committee is a Condorcet committee if each candidate in it is preferred, by a majority of voters, to each candidate outside it. A multiwinner voting rule is sometimes called stable if it selects a Condorcet set whenever it exists.^[18] Some stable rules are:^[19]
  • 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.^[20]
• A third adaptation was by Elkind, Lang and Saffidine;^[21] a Condorcet winning set is a set that, for each member d not in the set, a majority of the voters prefers some member in the set to d.

Excellence means that the elected 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 reapplied, then the first k candidates should still be elected. Some families of committee-monotone rules are:

• Sequential rules:^[18] 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).^[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 means that the elected committee should contain the most-preferred candidates of as many voters as possible. Formally, the following axioms are reasonable for diversity-centred 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:^[22] if a committee is elected, and some voter shifts upwards the rank of his most-preferred winner, then the same committee should be elected.

Proportionality means that each cohesive group of voters (that is: a group of voters with similar preferences, sometimes called a unanimous constituency) should be represented by a number of winners proportional to its size (the number of votes it receives). Formally, if the committee is of size k and there are n voters then each committee member represents n / k voters; and if L × n/k voters rank the same L candidates at the top (or give approval to the same L candidates) then those 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 produced by the STV election system; see justified representation and proportionality for solid coalitions.

Proportionality may be measured just on the one usable preference that determines the vote's placement. In fact, in STV, only one preference is considered for each vote (unless fractional transfers are used as under a Gregory method). Blocks of party votes stay intact if back-up preferences are marked along party lines, but that is not always the case—in STV voters have the liberty to mark their preferences as they desire, even across party lines. Under STV the elected committee is composed of diverse representatives. Each substantial (quota-sized) group, as determined by the placement of the vote according to the top usable marked preference, elects its preferred candidate.

Haret, Klumper, Maly and Schafer^[23] define, for each multiwinner voting instance, a corresponding budgeting game. In their game, each player has a fixed budget, and can choose a distribution of this budget among the candidates (so the strategy space of each player is a simplex). Each issue is active if its total allotment is least 1 and inactive otherwise. The utility of a player is the number of active issues that the player approves.

They prove that this game is a potential game and thus always has a pure-strategy Nash equilibrium. They also present several variants of equilibria in this game, and prove that they are equivalent (under certain assumptions) to various notions of justified representation in multiwinner voting.

• Participatory budgeting—can be seen as a generalisation of multiwinner voting where candidates have different costs