1 Introduction
-
Parliamentary elections Voting rules for such elections should respect the “one person, one vote” principle. This is reflected in the requirement that each elected member should represent approximately the same number of voters. Some such rules make use of electoral districts, i.e., they are based on holding separate (possibly multiwinner) elections in different parts of the country, while others treat the whole country as a single constituency, and focus on proportional representation of different population groups or political parties.
-
Shortlisting Consider a situation where a position is filled at a university. Each faculty member ranks applicants in order to create a short-list of those to be invited for an interview. One of the important requirements in this case is that if some candidate is shortlisted when k applicants are selected, then this candidate should also be shortlisted if the list is extended to \(k+1\) applicants.
-
Movie selection Based on rankings provided by different customer groups, an airline has to decide which (few) movies to offer on their long-distance flights. It is important that each passenger finds something satisfying to watch. This task is similar to parliamentary elections, but without the need to ensure that each movie would be watched by the same number of people. It is, however, quite different from shortlisting: If there are two similar job candidates, then it is desirable to interview either both of them or neither of them, whereas if two movies are similar, it makes sense to pick at most one of them. Skowron et al. (2016) discuss this view of multiwinner elections and provide a number of other examples and applications.
2 Preliminaries
3 Committee selection rules
3.1 Common committee selection rules
-
Plurality score The Plurality score of a candidate c is the number of votes where c is ranked first.
-
\({\mathbf {t}}\) -approval score Let t be a positive integer. The t-approval score of a candidate c is the number of votes where c is ranked in top t positions.
-
Borda score Let v be a vote in an election (C, V). The Borda score that candidate \(c\in C\) receives from v is \(\Vert C\Vert -{{{\mathrm {pos}}}}_v(c)\). The Borda score of c in (C, V) is the sum of c’s Borda scores from all votes in V.
-
s-score The three types of scores listed above are special cases of the following general framework. Consider a setting with a candidate set C, \(\Vert C\Vert =m\), and a score vector \(\mathbf{s}=(s_1, \ldots , s_m)\), where \(s_1\ge s_2\ge \cdots \ge s_m\) and \(s_1>s_m\). We define the \(\mathbf{s}\)-score of a candidate a in an election (C, V) with \(V = (v_1,\ldots ,v_n)\) asIt is then immediate that the Plurality score is the \((1,0, \ldots , 0)\)-score, the t-approval score is the \((\underbrace{1,\ldots ,1}_t,0,\ldots ,0)\)-score, and the Borda score is the \((m-1, m-2, \ldots , 0)\)-score.$$\begin{aligned} \text {sc}_\mathbf{s}(a)= \sum _{i=1}^n s_{\text {pos}_{v_i}(a)}. \end{aligned}$$
-
Single transferable vote (STV) STV is a multistage elimination rule that works as follows. In each stage, if there is a candidate c whose Plurality score is at least \(q = \left\lfloor \frac{\Vert V\Vert }{k+1} \right\rfloor + 1\) (the so-called Droop quota), we do the following: (a) include c in the winning committee, (b) delete q votes where c is ranked first, so that each of these votes is ‘transferred’ to the candidate currently ranked right after c, and (c) remove c from all the remaining votes. If each candidate’s Plurality score is less than q, a candidate with the lowest Plurality score is deleted from all votes. We repeat this process until k candidates are selected. Note that parallel-universes tie-breaking requires us to consider all possible ways to select a candidate among those whose score meets or exceeds the quota, to identify q votes to be deleted among those where this candidate is ranked first (note that this determines the ‘transfers’, i.e., how many extra votes will be gained by each surviving candidate), and to pick a candidate to be eliminated among those with the lowest score; a committee wins under STV if it can be obtained by the procedure described above for some sequence of such choices. There are also many other variants of STV; we point the reader to the work of Tideman and Richardson (2000) for details. In particular, the reader can verify that all results in our paper continue to hold if we require that the number of the ‘extra’ votes of a selected candidate c that are transferred to another candidate a is proportional to the number of votes of the form \(c\succ a\succ \cdots \) at the respective stage.
-
Single nontransferable vote (SNTV) SNTV returns k candidates with the highest Plurality scores (thus one can think of SNTV as simply k-Plurality).
-
Bloc Bloc returns k candidates with the highest k-approval scores. Observe that by using k-approval where k is the target committee size, we ensure that when all voters rank the candidates in the same way, the unique winning committee consists of the candidates ranked in top k positions by all the voters (whereas for s-approval with \(s\ne k\) this is not the case).
-
\({\mathbf {k}}\) -Borda k-Borda returns k candidates with the highest Borda scores.
-
The Chamberlin–Courant and Monroe rules These rules explicitly aim at proportional representation. The main idea is to provide an optimal assignment of committee members to voters, by using a satisfaction function to measure the quality of the assignment. A satisfaction function is a nonincreasing mapping \(\alpha :{{\mathbb {N}}} \rightarrow {{\mathbb {N}}}\). Intuitively, \(\alpha (i)\) is a voter’s satisfaction from being represented by a candidate that this voter ranks in position i. We primarily focus on the Borda satisfaction function, which for m candidates is defined as \(\alpha ^m_{{{{\beta }}}}(i) = m-i\). A function \(\varPhi :V \rightarrow C\) is called an assignment function. We write \(\varPhi (V)=\{\varPhi (v)\mid v\in V\}\). We say that \(\varPhi \) is a k-assignment function if \(\Vert \varPhi (V)\Vert \le k\). Intuitively, \(\varPhi (V)\) is the elected committee where voter v is represented by candidate \(\varPhi (v)\). There are several ways to compute the societal satisfaction from an assignment; we focus on the following two:where \(\alpha \) is the given satisfaction function. The former one, \(\ell _1(\varPhi )\), is a utilitarian measure, which sums the satisfactions of all the voters, and the latter one, \(\ell _{\min }(\varPhi )\), is an egalitarian measure, which considers the satisfaction of the least satisfied voter.$$\begin{aligned} \ell _1(\varPhi ) = \sum _{v \in V} \alpha ( {{{\mathrm {pos}}}}_v(\varPhi (v)) ), \quad \ell _{\min }(\varPhi ) = \min _{v \in V}\left\{ \alpha ({{{\mathrm {pos}}}}_v(\varPhi (v)) \right\} , \end{aligned}$$Let \(\alpha \) be a satisfaction function and let \(\ell \) be \(\ell _1\) or \(\ell _{\min }\). The Chamberlin–Courant rule with parameters \(\ell \) and \(\alpha \) (\(\ell \)-\(\alpha \)-CC) finds a k-assignment function \(\varPhi \) that maximizes \(\ell (\varPhi )\) and declares the candidates in \(\varPhi (V)\) to be a winning committee. If \(\Vert \varPhi (V)\Vert < k\), the rule fills in the missing committee members in an arbitrary way and outputs all resulting committees. Note that this class of rules includes SNTV: indeed, SNTV is exactly \(\ell _1\)-\(\alpha _1\)-CC, for satisfaction function \(\alpha _1\) given by \(\alpha _1(i)=1\) if \(i=1\) and \(\alpha _1(i)=0\) if \(i>1\). The \(\ell \)-\(\alpha \)-Monroe rule is defined similarly to \(\ell \)-\(\alpha \)-CC, except that we optimize over k-assignment functions that additionally satisfy the so-called Monroe criterion, which requires that exactly k candidates are elected and each elected candidate is assigned to either \( \lfloor \frac{n}{k} \rfloor \) or \(\lceil \frac{n}{k} \rceil \) voters. To simplify notation, we omit \(\alpha ^m_{{{{\beta }}}}\) when referring to the Monroe/CC rule with the Borda satisfaction function.For the Chamberlin–Courant rule, for each set of candidates \(C' \subseteq C\) we define the assignment function \(\varPhi ^{{{\mathrm {CC}}}}(C'):V\rightarrow C'\) as follows: for each voter v the candidate \(\varPhi ^{{{\mathrm {CC}}}}(C')(v)\) is v’s top candidate in \(C'\). If W is a winning committee under the Chamberlin–Courant rule, then \(\varPhi ^{{{\mathrm {CC}}}}(W)\) is an optimal assignment function.The utilitarian variants of these rules, i.e., \(\ell _1\)-CC and \(\ell _1\)-Monroe, were introduced by Chamberlin and Courant (1983) and by Monroe (1995), respectively; similar ideas are discussed by Sugden (1984) in a game-theoretic context. The egalitarian variants were introduced by Betzler et al. (2013). Unfortunately, these rules are hard to compute, irrespective of tie-breaking, both for the Borda satisfaction function (Lu and Boutilier 2011; Betzler et al. 2013) and for various approval-based satisfaction functions (Procaccia et al. 2008; Betzler et al. 2013).
-
Approximate variants of \({\varvec{\ell }_\mathbf{1}}\)-Monroe and \({\varvec{\ell }_\mathbf{1}}\)-CC Complexity results for \(\ell _1\)-CC and \(\ell _1\)-Monroe inspired research on designing efficient approximation algorithms for these rules. Here, in the spirit of Caragiannis et al. (2014), we consider these algorithms as full-fledged multiwinner rules. We refer to the rules based on approximation algorithms for \(\ell _1\)-CC and \(\ell _1\)-Monroe as Greedy-CC and Greedy-Monroe, respectively. Greedy-CC was proposed by Lu and Boutilier (2011) and Greedy-Monroe by Skowron et al. (2015). Both rules use the Borda satisfaction function, aggregated in the utilitarian way (i.e., by using \(\ell _1\)). They proceed in k iterations; in the i-th iteration, \(i\in [k]\), they build a set \(W_i\) of cardinality i so that \(\emptyset = W_0 \subset W_1 \subset W_2 \subset \cdots \subset W_k\). The set \(W_k\) is declared to be the winning committee. In the i-th iteration, \(i\in [k]\), Greedy-CC picks a candidate \(c_i \in C {\setminus } W_{i-1}\) that maximizes \(\ell _1(\varPhi ^{{{\mathrm {CC}}}}(W_{i-1}\cup \{c_i\}))\), and sets \(W_i = W_{i-1} \cup \{c_i\}\). In particular, \(c_1\) is an alternative with the highest Borda score.Greedy-Monroe, in addition to the sets \(W_0, \ldots , W_k\), also maintains lists of voters \(\emptyset = V_0 \subset V_1 \subset \cdots \subset V_k = V\). The list \(V_i\), \(i\in [k]\), consists of voters that already have candidates assigned to them after the i-th iteration. In the i-th iteration, \(i\in [k]\), the rule picks a number \(n_i \in \{\lceil \frac{n}{k}\rceil , \lfloor \frac{n}{k}\rfloor \}\) (see below for the choice criterion) and then picks a candidate \(c_i \in C {\setminus } W_{i-1}\) and a group \(V'\) of \(n_i\) voters from \(V{\setminus } V_{i-1}\) that jointly maximize the Borda score of \(c_i\) in \(V'\). The rule sets \(W_i = W_{i-1}\cup \{c_i\}\) and \(V_i = V_{i-1} \cup V'\) (intuitively, Greedy-Monroe assigns \(c_i\) to the voters in \(V'\)). Regarding the choice of \(n_i\), if n is of the form \(kn'+n''\), where \(0 \le n'' < k\), then Greedy-Monroe sets \(n_i\) to \(\lceil \frac{n}{k}\rceil \) for \(i=1, \ldots , n''\) and to \(\lfloor \frac{n}{k}\rfloor \) for \(i=n''+1, \ldots , k\). For instance, \(c_1\) and \(V_1\) are chosen so that for every candidate \(c\in C\) and every group of voters \(V'\subseteq V\) of size \(n_1\) it holds that the Borda score of \(c_1\) in \((C, V_1)\) is at least as high as the Borda score of c in \((C, V')\) (and, in particular, \(c_1\) is a Borda winner in \((C, V_1)\)).Greedy-CC and Greedy-Monroe output committees that approximately satisfy the optimality criteria of \(\ell _1\)-CC and \(\ell _1\)-Monroe. In particular, Greedy-CC finds a committee W such that the satisfaction of the voters \(\ell _1(\varPhi ^{{{\mathrm {CC}}}}(W))\) is at least \(1-\frac{1}{e}\) of the satisfaction achieved under \(\ell _1\)-CC (Lu and Boutilier 2011). Greedy-Monroe finds a committee that achieves at least a \(1-\frac{k}{2m-1} - \frac{H_k}{k}\) fraction of the satisfaction given by \(\ell _1\)-Monroe, where \(H_k=\sum _{i=1}^{k}\frac{1}{k}\) (Skowron et al. 2015); for many practical settings, this value is quite close to 1.
3.2 Two types of multiwinner rules
4 Axioms
-
Nonimposition For each set of candidates C and each k-element subset W of C, there is an election \(E = (C,V)\) such that \({{\mathcal {R}}}(E,k) = \{W\}\).
-
Consistency For every pair of elections \(E_1 = (C,V_1)\), \(E_2 = (C,V_2)\) over a candidate set C and each \(k \in [\Vert C\Vert ]\), if \({{\mathcal {R}}}(E_1,k) \cap {{\mathcal {R}}}(E_2,k) \ne \emptyset \) then \({{\mathcal {R}}}(E_1+E_2,k) = {{\mathcal {R}}}(E_1,k) \cap {{\mathcal {R}}}(E_2,k)\).
-
Homogeneity For every election \(E = (C,V)\), each \(k \in [\Vert C\Vert ]\), and each \(t \in {{\mathbb {N}}}\) it holds that \({{\mathcal {R}}}(tE,k) = {{\mathcal {R}}}(E,k)\).
-
Monotonicity For every election \(E = (C,V)\), each \(c \in C\), and each \(k \in [\Vert C\Vert ]\), if \(c\in W\) for some \(W \in {{\mathcal {R}}}(E,k)\), then for every \(E'\) obtained from E by shifting c one position forward in some vote v it holds that:
-
Committee monotonicity For every election \(E = (C,V)\) the following conditions hold:
-
Solid coalitions For every election \(E = (C,V)\) and each \(k \in [\Vert C\Vert ]\), if at least \(\frac{\Vert V\Vert }{k}\) voters rank some candidate c first then c belongs to every committee in \({{\mathcal {R}}}(E,k)\).
-
Consensus committee For every election \(E = (C,V)\) and each \(k \in [\Vert C\Vert ]\), if there is a k-element set W, \(W \subseteq C\), such that each voter ranks some member of W first and each member of W is ranked first by either \(\lfloor \frac{\Vert V\Vert }{k} \rfloor \) or \(\lceil \frac{\Vert V\Vert }{k} \rceil \) voters then \({{\mathcal {R}}}(E,k) = \{W\}\).
-
Unanimity For every election \(E = (C,V)\) and each \(k \in [\Vert C\Vert ]\), if each voter ranks the same k candidates W on top (possibly in different order), then \({{\mathcal {R}}}(E,k) = \{W\}\) (strong unanimity) or \(W \in {{\mathcal {R}}}(E,k)\) (weak unanimity).
-
Fixed majority For every election \(E = (C,V)\) and each \(k \in [\Vert C\Vert ]\), if there is a k-element set W, \(W \subseteq C\), such that a strict majority of voters rank all members of W above all non-members of W, then \({{\mathcal {R}}}(E,k) = \{W\}\).
5 Committee monotonicity
6 Dummett’s proportionality
7 Monotonicity
8 Consistency and homogeneity
9 Related work
Rule | Committee | Solid | Consensus | Unanimity | Monotonicity | Homogeneity | Consistency |
---|---|---|---|---|---|---|---|
Monotonicity | Coalitions | Committee | |||||
STV |
\(\times \)
|
\(\surd \) (\(\diamond \)) |
\(\surd \) (\(\diamond \)) | Strong |
\(\times \)
|
\(\surd \)(\(\heartsuit \)) |
\(\times \)
|
SNTV |
\(\surd \)
|
\(\surd \)
|
\(\surd \)
| Weak | C+NC |
\(\surd \)
|
\(\surd \)
|
Bloc |
\(\times \)
|
\(\times \)
|
\(\times \)
| Fix maj. | C+NC |
\(\surd \)
|
\(\surd \)
|
k-Borda |
\(\surd \)
|
\(\times \)
|
\(\times \)
| Strong | C+NC |
\(\surd \)
|
\(\surd \)
|
\(\ell _1\)-CC |
\(\times \)
|
\(\times \)
|
\(\surd \)
| Weak | C |
\(\surd \)
|
\(\surd \)
|
\(\ell _{\min }\)-CC |
\(\times \)
|
\(\times \)
|
\(\surd \)
| Weak | C |
\(\surd \)
|
\(\times \)
|
Greedy-CC |
\(\surd \)
|
\(\times \)
|
\(\times \)
| Weak |
\(\times \)
|
\(\surd \)
|
\(\times \)
|
\(\ell _1\)-Monroe |
\(\times \)
|
\(\times \)
|
\(\surd \)
| Strong |
\(\times \)
|
\(\surd \) (\(\clubsuit \)) |
\(\times \)
|
\(\ell _{\min }\)-Monroe |
\(\times \)
|
\(\times \)
|
\(\surd \)
| Strong |
\(\times \)
|
\(\surd \) (\(\clubsuit \)) |
\(\times \)
|
Greedy-Monroe |
\(\times \)
|
\(\surd \)
|
\(\surd \)
| Strong |
\(\times \)
|
\(\surd \) (\(\spadesuit \)) |
\(\times \)
|