Properties of multiwinner voting rules

There are many situations where a society needs to select a subset of a given size from the set of available options. For example, in indirect democracies people choose representatives to govern on their behalf, companies select groups of products to promote to their customers (Lu and Boutilier 2011, 2015; Skowron et al. 2016), search engines decide which webpages to display in response to a given query (Dwork et al. 2001), and among many applicants for a job (e.g., a tenure-track position at a university) several get short-listed and invited for interviews. For all these tasks we need formal rules to perform the selection, and the desirable properties of such rules may depend on the task at hand. We view these selection rules as multiwinner voting rules which, given individual preferences and the desired number of winners, output groups of winners, which we call committees.

Multiwinner elections are even more ubiquitous than single-winner ones, but much less studied. They were implicitly considered under the umbrella of choice functions (Arrow 1951; Fishburn 1973), but in this model the size of the elected committee could not be controlled. It was Debord (1993) and Felsenthal and Maoz (1992) who introduced several k-choice functions that elect committees of size exactly k, and investigated their properties. However, even within the space of rules that elect exactly k winners, many distinct models can happily coexist. One way to classify them is according to the type of the input: there are preference-based rules (whose inputs are sequences of linear orders; see, e.g., the work of Brams and Fishburn (2002)), approval-based rules (whose inputs are sequences of dichotomies; see, e.g., the works of Brams et al. (2007), Caragiannis et al. (2010), Kilgour and Marshall (2012), Aziz et al. (2017), and the overview by Kilgour (2010)), and tournament-based rules (whose inputs are either tournaments or weighted tournaments; see the book of Laslier (1997) for a general overview of tournament-based rules). Also, a number of authors consider settings where the compatibility of committee members is an important issue, and therefore voters’ preferences over committees cannot be deduced from their preferences over individual alternatives alone (Ratliff 2006; Uckelman 2010; Ratliff and Saari 2014). For a different perspective on this issue, see the line of work on voting in combinatorial domains ( Lang and Xia (2016) offer a very good overview of this area).

In this work, we focus on the model where the goal is to select a committee of a given size on the basis of voters’ ordinal preferences over the candidates. A number of rules for this task are based on various forms of the Condorcet principle (Fishburn 1981a, b; Gehrlein 1985; Kaymak and Sanver 2003; Ratliff 2003; Barberà and Coelho 2008; Elkind et al. 2015). In contrast, we consider rules that, informally speaking, can be seen as counterparts of positional scoring rules. Our aim is to present a uniform framework for the study of such rules, to identify useful classes of score-based committee selection rules, and to propose a set of natural properties (axioms) against which multiwinner rules can be judged.

We have selected ten voting rules as examples of different ideas pertaining to score-based committee selection: STV, SNTV, k-Borda, Bloc, three variants of the Chamberlin–Courant rule (Chamberlin and Courant 1983; Lu and Boutilier 2011; Betzler et al. 2013), and three variants of the Monroe rule (Monroe 1995; Betzler et al. 2013; Skowron et al. 2015). STV and SNTV are well-known rules that are used for parliamentary elections in several countries;¹ Bloc is a rule that asks each voter to specify her favourite committee of k candidates and selects k candidates that were mentioned more frequently than others; k-Borda picks k alternatives with the highest Borda scores and is representative of rules used for choosing k finalists in a competition (indeed, Formula 1 racing and the Eurovision song contest use scoring rules very similar to Borda). The Chamberlin–Courant and Monroe rules are examples of rules that, like STV, focus on proportional representation, but, unlike STV, explicitly assign a committee member (a representative) to each voter. We also consider two rules that are based on approximation algorithms for, respectively, the Chamberlin–Courant rule (Lu and Boutilier 2011) and the Monroe rule (Skowron et al. 2015); that is, we treat these algorithms as voting rules in their own right. All these rules can be seen as being loosely based on single-winner scoring rules.

We are interested in judging the committee selection rules on our list with respect to their applicability in the following settings:

We study properties of voting rules that are relevant to the above-listed settings. Specifically, we discuss properties that are specific to the task of committee selection, such as committee monotonicity, the solid coalitions property, and the consensus committee property, and adapt the standard notions of unanimity, monotonicity, homogeneity, and consistency to the multiwinner setting. For every such property \(\mathcal{P}\) and each rule \(\mathcal{R}\) considered in this paper, we determine if \(\mathcal{R}\) satisfies \(\mathcal{P}\) (sometimes we need to place mild technical conditions on the input, e.g., a rule may satisfy a certain property only if the target committee size divides the number of voters or if the number of voters is sufficiently large). Our results are summarized in Table 1 (see Sect. 10).

In the course of our investigation, we identify an important class of committee selection rules, which we call committee scoring rules. Within the class of committee scoring rules, we distinguish (weakly) separable rules and representation-focused rules. These notions prove to be useful for our analysis, as some axioms turn out to be satisfied by all rules that belong to one of these subclasses, or by an easily identifiable subset of such rules (see, e.g., Theorem 3). Further, we obtain a simple and intuitive characterization of separable committee scoring rules. Namely, we show that all such rules are best-k rules; roughly speaking, this means that each such rule first ranks all candidates and then outputs the top k candidates according to this ranking. We believe that introducing the class of committee scoring rules is one of the most important contributions of this paper. In a series of follow-up papers, Faliszewski et al. conduct a more detailed study of the internal structure of this class of rules (Faliszewski et al. 2016a, b) and Skowron et al. (2016b) provide an axiomatic characterization of such rules.

Our paper is a preliminary attempt to develop a formal framework for the study of preference-based committee selection rules. Thus we use the word axiom quite freely, without implying that our axioms should be viewed as normative requirements. Further, our work focuses on committee selection rules that are based on scoring procedures. Such rules are fundamentally different from those that are motivated by the Condorcet criterion. In particular, in the single-winner case, no scoring rule is Condorcet consistent; consequently, a committee selection rule that reduces to a scoring rule for the case when the target committee size equals one cannot satisfy any reasonable extension of the Condorcet criterion.² It would be very interesting to apply our framework to Condorcet-based rules. However, this task is beyond the scope of this paper, and we leave it as future work.

The remainder of the paper is organized as follows. In Sect. 2 we introduce the basic terminology used throughout the paper; in Sect. 3 we define the rules that we study and put forward two ways of classifying them. In Sect. 4, we define several properties of committee selection rules, and in Sects. 5–8 we study particular groups of these properties in detail. We discuss related literature in Sect. 9 and conclude in Sect. 10.

An election is a pair \(E = (C,V)\), where \(C = \{c_1, \ldots , c_m\}\) is a set of candidates, or alternatives (we will use these two terms interchangeably), and \(V = (v_1, \ldots , v_n)\) is a list of voters. For succinctness, each voter is identified with her preference order, i.e., a ranking of the candidates from the most desirable one to the least desirable one. That is, \(v_i\) refers both to the i-th voter in V and the preference order of that voter. We write \(a\succ _i b\) or \(v_i:a\succ b\) when a is ranked above b in \(v_i\). We write \(\Vert C\Vert \) and \(\Vert V\Vert \) to denote the size of the set C and the length of the list V, respectively. Also, for readability, we use set-theoretic notation when we reason about V: e.g., we write \(V'\subseteq V\) when \(V'\) can be obtained from V by deleting some of the voters. We denote the position of a candidate \(c\in C\) in vote \(v\in V\) by \({{{\mathrm {pos}}}}_v(c)\). If \(V_1\) and \(V_2\) are two lists of voters over the same candidate set C, then \(V_1+V_2\) denotes the concatenation of \(V_1\) and \(V_2\). If V is a list of voters and t is an integer, then tV denotes the concatenation of t copies of V. For \(E_1 = (C,V_1)\) and \(E_2 = (C,V_2)\), we write \(E_1+E_2\) to denote \((C,V_1+V_2)\), and for \(E = (C,V)\) and a positive integer t, we write tE to denote (C, tV). For an integer n, we denote \(\{1, \ldots , n\}\) by [n].

A committee selection rule (or, a multiwinner rule) \({{\mathcal {R}}}\) is a function that, given an election \(E = (C,V)\) and a positive integer k, \(k \le \Vert C\Vert \), returns a non-empty set \({{\mathcal {R}}}(E,k)\) of k-element subsets of C, which we call committees. That is, a rule returns the set of committees that are tied for winning. In practice, one would need to combine such a rule with a tie-breaking mechanism, but for simplicity we mostly disregard this issue here. Brams and Fishburn (2002) introduced choose-k rules, but their definition stipulates that such a rule selects at least k alternatives. Two early papers that focus on rules selecting committees of size exactly k are those of Debord (1993) and of Felsenthal and Maoz (1992).

Requiring committee selection rules to pick fixed-size committees is natural if, for example, the goal is to elect a parliament whose size is fixed by the constitution. However, as a consequence, we are sometimes forced to elect committees that are Pareto dominated under reasonable preference extensions: e.g., if in each vote the candidates are ranked as \(a\succ b\succ c \succ d\) and \(k=2\), the voters may prefer \(\{a\}\) to \(\{a, b\}\), but selecting a alone is not possible in our model. Alternatively, we could require \({{\mathcal {R}}}(E,k)\) to return committees of size at most k. The latter approach is also studied in the literature (either explicitly or implicitly), but we adopt the former one due to its simplicity and applicability in our settings of interest.

We now provide definitions of the committee selection rules that we study and discuss two general ways of defining such rules.

We now present some properties (axioms) that may be desirable for committee selection rules. We use the standard axioms for single-winner rules as our starting point, and modify them on the basis of ideas from the literature that are specific to committee selection. Due to our choice of focus, we do not include properties based on the Condorcet principle, such as, e.g., stability, as defined by Gehrlein (1985). We stress that, since committee selection rules have a very diverse range of applications, our properties should not necessarily be understood in the normative way: the desirability of a particular property can only be evaluated in the context of a specific application. Throughout this section, we write \({{\mathcal {R}}}\) to denote a multiwinner rule; given an election \(E=(C, V)\) and a positive integer k with \(k\le \Vert C\Vert \), \({{\mathcal {R}}}(E, k)\) outputs a non-empty set of size-k subsets of C.

Our first axiom is nonimposition. It requires that each size-k set of candidates can be the unique winner. This is a basic requirement that is trivially satisfied by all rules that we consider.The next three axioms—consistency, homogeneity, and monotonicity—are adapted from the single-winner setting. For the first two, the adaptation is straightforward.We now consider monotonicity. If c belongs to a winning committee W then, generally speaking, we cannot expect W to remain winning when c is moved forward in some vote. For example, this shift may hurt other members of W. Indeed, none of our rules satisfies this strict version of monotonicity. However, there are two natural relaxations of this condition. One option is to require that after the shift c belongs to some winning committee. Alternatively, we may restrict forward movements of c, prohibiting it to overtake other members of W. (We point the reader to the work of Sanver and Zwicker (2012) for an extensive discussion of monotonicity in the context of irresolute voting rules.) Our next axiom, committee monotonicity, is specific to committee selection, as it deals with changing the size of the desired committee. Intuitively, it requires that when we increase the target committee size, none of the already selected candidates should be dropped. Our phrasing is somewhat involved because \({{\mathcal {R}}}\) may return a set of tied committees; a similar notion for resolute multiwinner rules, i.e., rules that always output a single committee, was introduced earlier by Barberà and Coelho (2008) under the name of enlargement consistency. The second condition in the definition above aims to prevent the following situation. Consider an election E with candidate set \(C = \{a,b,c, \ldots \}\) and a rule \({{\mathcal {R}}}\) with \({{\mathcal {R}}}(E,1) = \{\{a\}\}\), \({{\mathcal {R}}}(E,2) = \{\{a,b\}, \{b,c\}\}\). Intuitively, \({{\mathcal {R}}}\) is not committee-monotone because of the unexpected appearance of the committee \(\{b, c\}\) in \({{\mathcal {R}}}(E,2)\), but this is not captured by condition (1) above. Under our definition, \({{\mathcal {R}}}\) is not committee-monotone because it violates condition (2).

In Sect. 5 we discuss committee monotonicity in detail and use it to axiomatize best-k rules. We note that committee monotonicity in the context of multiwinner voting has been discussed by other authors, but under different names and usually by arguing that it is paradoxical that a given voting rule fails committee monotonicity (Staring 1986; Ratliff 2003; Barberà and Coelho 2008). In contrast, we argue (Sect. 5) that in some applications failing this axiom may be seen as a desirable feature of a committee selection rule.

The next three axioms represent three implementations of Dummett’s condition known as proportionality for solid coalitions (Dummett 1984). Dummett’s original proposal is as follows: Consider an election with n voters where the goal is to pick k candidates. If for some \(\ell \in [k]\) there is a group of \(\frac{\ell n}{k}\) voters that all rank the same \(\ell \) candidates on top, these \(\ell \) candidates should be in the (unique) winning committee. This requirement, which aims to capture the idea of proportional representation, seems to be very strong, and very few rules satisfy it.³ The following three axioms are weaker, but reflect the same idea (for a discussion of similar ideas in the context of approval-based rules, we point the readers to the work of Aziz et al. (2017) on justified representation). We emphasize that the axioms in our list are suitable for rules that are preference-based and, moreover, are—in some broad sense—close to scoring rules. There are, however, axioms for preference-based rules that are geared towards the Condorcet principle. The following axiom is an example (Debord 1993), though it can also be seen as a generalization of the unanimity property.

Almost all rules considered in this paper fail to satisfy this axiom. For most of them, this is already the case in the single-winner setting, i.e., when \(k=1\). Indeed, Plurality is the only single-winner scoring rule guaranteeing that a candidate ranked on top by a majority of the voters is the unique winner. However, quite interestingly, Bloc does satisfy the fixed majority property. To see this, consider an election (C, V) with \(\Vert V\Vert =n\) and a committee W such that a majority of voters rank all members of W in top k positions. Under Bloc each candidate in W gets at least \(\lfloor n/2\rfloor +1\) points, whereas each candidate in \(C{\setminus } W\) gets at most \(\lfloor n/2\rfloor \) points, which means that the Bloc score of every committee \(W'\ne W\) is lower than that of W. This is yet another feature that distinguishes Bloc from separable committee scoring rules (even though Bloc is weakly separable). For more detailed discussion of fixed-majority consistency in the context of committee scoring rules, we point the readers to the follow-up work of Faliszewski et al. (2016b).

In the remainder of the paper, we consider the axioms listed in this section one by one, and, for each of them, we determine which of the voting rules described in Sect. 3 satisfy it. A summary of our results is provided in Table 1 in Sect. 10.

Some authors believe that committee monotonicity is an important requirement. In particular, Staring (1986) demonstrated that the Bloc rule is very far from being committee monotonic, and called this phenomenon the increasing-committee-size paradox. Specifically, he described a profile where the winning committee of size three was disjoint from the winning committee of size two, and the winning committee of size four was disjoint from both of them. A variant of the increasing-committee-size paradox has been recently considered by Kamwa and Merlin (2015). For several other rules (not considered in our paper), similar phenomena were observed by Ratliff (2003), in a paper titled “Some Startling Inconsistencies when Electing Committees”. Barberà and Coelho (2008) argue that for shortlisting it is desirable to consider weakly Condorcet-consistent rules. They then show that weak Condorcet-consistency (which, in this context, they call stability) and committee monotonicity are incompatible, and argue that this is one reason why (weakly) Condorcet-consistent rules are not used in practice.

In contrast, we believe that the desirability of committee monotonicity depends strongly on the application. In particular, we agree with Barberà and Coelho (2008) that if we are choosing finalists of a competition, then it is imperative to use a rule that has this property; however, in the context of proportional representation insisting on a committee-monotone rule may prevent us from selecting a truly representative committee. Indeed, the latter point was already noted by Black. In his classical work Black (1958) considers a society with single-peaked preferences regarding the left-right political spectrum. He observes that if we are choosing a single candidate (i.e., if \(k=1\)) then it is most natural to select a candidate that holds the most centrist position (i.e., the top choice of the median voter). However, if we are to select two candidates to represent the society (i.e., if \(k=2\)), then, intuitively, a committee consisting of a “moderate left-wing” candidate and a “moderate right-wing” candidate would be more representative than any committee of the form \(\{c, d\}\), where c is the top choice of the median voter: if d is to the left of c, the right-wing voters are neglected, and if d is to the right of c, the left-wing voters are neglected.

By combining Theorems 1 and 2, we conclude that all separable committee scoring rules, including, in particular, SNTV and k-Borda, satisfy committee monotonicity. We will now show that Greedy-CC satisfies committee monotonicity as well, and hence it is a best-k rule.

Theorem 1 shows that separable committee scoring rules are associated with scoring social welfare functions. In contrast, Greedy-CC cannot be defined in such a way and, in particular, the social preference function \(F_ CC \) constructed in the proof of Proposition 2 does not correspond to a social welfare function.

The remaining rules considered in our paper fail committee monotonicity (as mentioned above, the case of Bloc was resolved by Staring (1986); the proof of Proposition 3 includes an explicit construction for Bloc for the sake of completeness).

Properties in the spirit of Dummett’s proportionality condition (with the exception of unanimity) are geared toward rules that aim to achieve proportional representation of the voters. Thus, the results of this section can be used to judge committee selection rules from this perspective.

We start by considering the solid coalitions property. It is easy to see that it is satisfied by SNTV, and also by STV when the number of voters is sufficiently large.

On the other hand, even though the solid coalitions property seems to be very much in spirit of the Chamberlin–Courant and Monroe rules, \(\ell _1\)-Monroe, \(\ell _1\)-CC, \(\ell _{\min }\)-Monroe, and \(\ell _{\min }\)-CC fail to satisfy it.

Interestingly, Greedy-Monroe performs better in this regard than \(\ell _1\)-Monroe.

We believe that the solid coalitions property is desirable, but not crucial for applications that aim at proportional representation (e.g., parliamentary elections): indeed, a voter may be reasonably well represented even if her top choice is not included in the committee. In contrast, the consensus committee property, which we discuss next, seems to be fundamental. Indeed, it is satisfied by almost all rules that aim to achieve proportional representation.

When k divides n, the consensus committee property is satisfied by every rule that has the solid coalitions property. In particular, it is satisfied by SNTV, STV (if there are sufficiently many voters) and Greedy-Monroe. It is also satisfied by \(\ell _1\)-CC, \(\ell _{\min }\)-CC, \(\ell _1\)-Monroe, and \(\ell _{\min }\)-Monroe: this is immediate from the definitions of these rules. Interestingly, however, Greedy-CC fails the consensus committee property. This reveals a major deficiency of this rule: when deciding whether to include some candidate c into the committee, it takes into account the preferences of the voters to whom c would not be assigned. This is very problematic for a rule that seeks to approximate \(\ell _1\)-CC. Observe, however, that it is exactly this feature of Greedy-CC that makes this rule committee monotone.

For SNTV, \(\ell _1\)-CC, and k-Borda, the above results can also be seen as incarnations of the following two more general results regarding committee scoring rules.

Our final instantiation of Dummett’s proportionality for solid coalitions is the unanimity property. Every committee scoring rule satisfies its weak variant.

It is immediate that \(\ell _1\)-Monroe, \(\ell _{\min }\)-Monroe, Greedy-Monroe, Bloc and k-Borda satisfy strong unanimity. In contrast, SNTV, \(\ell _1\)-CC, \(\ell _{\min }\)-CC, and Greedy-CC do not have this property: given an election where all voters have the same preference order, each of these rules outputs all committees that include the candidate ranked first by all voters. Finally, we note that STV satisfies strong unanimity. Indeed, if there is a set of candidates W, \(\Vert W\Vert =k\), such that each of the n voters ranks the candidates from W in top k positions, then in every round of STV there is a candidate from W that is ranked first by at least \(\lceil \frac{n}{k}\rceil \ge \lfloor \frac{n}{k+1}\rfloor +1\) voters.

Being monotonic is a natural and easily satisfiable condition for single-winner rules. Among the few examples of prominent non-monotonic single-winner rules are STV and the Dodgson rule (see, e.g., the work of Brandt 2009). In contrast, for multiwinner rules monotonicity is a rather demanding property. However, all committee scoring rules satisfy candidate monotonicity, and all weakly separable committee scoring rules satisfy non-crossing monotonicity.

In contrast, one of the implications of our next result is that a committee scoring rule that is not weakly separable may fail non-crossing monotonicity. (Indeed, in a follow-up paper, Faliszewski et al. (2016a) have shown that among committee scoring rules, only weakly separable rules satisfy non-crossing monotonicity.)

While \(\ell _{\min }\)-CC satisfies one of our monotonicity properties, \(\ell _{\min }\)-Monroe fails both of them.

The remaining committee selection rules studied in this paper fail each of our monotonicity criteria. For STV this is well-known even for \(k=1\). The other three rules are captured by the following proposition.

For single-winner rules, Young’s famous theorem (Young 1975) says that only scoring rules and their compositions satisfy consistency. The situation for multiwinner voting rules seems to be similar. Here, we show that every committee scoring rule satisfies consistency, whereas other rules we consider fail it. In a very recent paper, Skowron et al. (2016b) provide a Young-style characterization of committee scoring rules, which explains our observations.

Now let us turn our attention to the negative results. Note first that some of the rules we consider cannot be consistent by Young’s theorem, because for \(k=1\) they are not scoring rules (or their compositions). Specifically, this is the case for STV, \(\ell _{\min }\)-CC and \(\ell _{\min }\)-Monroe.

This argument does not apply to \(\ell _1\)-Monroe, Greedy-CC and Greedy-Monroe: for \(k=1\) each of these rules is equivalent to Borda, which is consistent. For these rules, we provide a direct proof.

We now consider homogeneity. Naturally, committee scoring rules are homogeneous because consistency implies homogeneity. For other rules, the situation is more complex.

We omit the formal proof of Proposition 13; for both rules, the result follows immediately from the definition of the rule.

Interestingly, none of the variants of Monroe’s rule is homogeneous.

On the positive side, if the number of voters is divisible by the target committee size, then \(\ell _1\)-Monroe and \(\ell _{\min }\)-Monroe are homogeneous. In essence, this means that these variants of Monroe’s rule fail homogeneity because of rounding imposed by Monroe’s criterion. One solution would be to clone each voter k times when seeking a committee of size k. We do not consider this modification of Monroe’s rule here, as it is fundamentally incompatible with the idea of fully proportional representation: effectively, under this approach a voter would be fractionally represented by multiple candidates, and it is not clear how to interpret such assignments. However, it would be interesting to see how the satisfaction of a committee elected in this way compares to that of a committee elected without cloning.

Proposition 16 relies heavily on parallel-universes tie-breaking. It is possible to refine the intermediate tie-breaking procedure of Greedy-Monroe so that it becomes homogeneous when k divides \(\Vert V\Vert \). We omit the details here.

Having characterized a number of natural committee selection rules with respect to the axioms we proposed, we are now in a position to discuss how our results and approaches compare to prior work. The literature on the properties of committee selection rules is still somewhat sparse (at least compared to the body of work on single-winner rules), and it is scattered among different fields of research, ranging from behavioral science, through political science and social choice theory, to computer science. Here we review papers that are most similar in spirit to our work.

In a closely related paper, Felsenthal and Maoz (1992) consider four k-choice functions: the Plurality rule (i.e., in our terminology, the SNTV rule), the Approval rule,⁴ the Borda rule (i.e., k-Borda), and STV. They adapt a range of single-winner normative properties to the committee selection setting and study them in the context of these rules. In contrast with our work, they consider axioms motivated by the Condorcet principle, while we focus on axioms that capture ideas related to proportional representation. However, both papers consider monotonicity, though our analysis is somewhat more detailed in that we study two variants of this property (candidate monotonicity and non-crossing monotonicity), as well as committee monotonicity (Felsenthal and Maoz use the term ‘continuity’) and consistency (also known as reinforcement). Interestingly, consistency also plays an important role in the work of Bock et al. (1998) on consensus-based multiwinner rules. Debord (1993) also introduced several axioms for multiwinner rules. These axioms, however, are geared towards the rules that elect what he calls k-elites, which are multiwinner analogs of Condorcet winners.

Young’s consistency-based characterization of scoring rules, as well as his characterization of the Borda rule, have already inspired researchers working on committee selection rules. For example, Debord (1992) extended Young’s characterization of Borda to the case of k-Borda, and very recently Skowron et al. (2016b) extended Young’s ideas to characterize the class of committee scoring rules. Faliszewski et al. (2016b) study a subclass of committee scoring rules which they call top-k-counting rules, and provide an axiomatic characterization of the Bloc rule, which belongs to this class. Faliszewski et al. (2016a) propose a hierarchy of committee scoring rules.

Skowron (2015) offers a different perspective on committee selection rules. He assumes that the elected committee will have to make several decisions, i.e., vote on a number of issues, and that voters evaluate committees based on the final outcome of this two-stage process (which the voter can predict to a certain extent). The performance of a committee selection rule then depends on the single-winner voting rule that the committee will use to make its decisions. In this setting, several voting rules that we consider, such as \(\ell _1\)-CC, emerge as optimal voting rules for appropriate assumptions about voters’ preferences.

There is also a considerable amount of work on committee selection rules in the framework of approval voting. Kilgour (2010) describes a number of approval-based voting rules that elect a committee of fixed size and establishes some of their basic properties. Kilgour and Marshall (2012) give an excellent survey of approval-based committee selection rules and propose some new ones. A recent paper by Aziz et al. (2017) is conceptually similar to our work: there, the authors consider a number of popular approval-based committee selection rules, introduce a new axiom for such rules—similar in spirit to Dummett’s solid coalitions property and called justified representation—and check which of the rules in their list satisfy it.

We conclude our discussion of related work by mentioning a very recent paper by Elkind et al. (2017), where the authors visually present aggregated outcomes of a number of multiwinner voting rules. Their experimental results confirm our theoretical predictions, and also reveal some effects that are hard to discover by purely theoretical means.

We formalized a number of natural properties of committee selection rules and conducted a comprehensive comparison of ten prominent committee selection rules with respect to these properties. Our results are summarized in Table 1. In the course of our study, we identified two natural families of committee selection rules—best-k rules and committee scoring rules—and related these families of rules to the properties we consider. In particular, we characterized best-k rules as the only rules that satisfy committee monotonicity, identified simple conditions on committee scoring rules that ensure the consensus committee property or non-crossing monotonicity, and showed that all committee scoring rules satisfy weak unanimity, candidate monotonicity, and consistency.

We believe that the results in this paper improve our understanding of applicability of various multiwinner rules to particular tasks. For example, we see that best-k rules are well-suited for selecting a group of finalists in a competition, whereas STV and rules based on Monroe’s criterion (\(\ell _1\)-Monroe, \(\ell _{\min }\)-Monroe, and Greedy-Monroe) seem to be more appropriate for applications that require proportional representation (e.g., parliamentary elections).

In this context, Greedy-Monroe is particularly interesting. It was introduced as an approximation algorithm for \(\ell _1\)-Monroe, but, according to our criteria, it is more attractive than the original rule. Therefore, we believe that Greedy-Monroe should be treated as a full-fledged voting rule. In contrast, Greedy-CC, which was designed as an approximation algorithm for \(\ell _1\)-CC, does not appear to perform well in our comparison. Indeed, it fails to satisfy the solid coalitions property (like \(\ell _1\)-CC, but unlike Greedy-Monroe) or the consensus committee property (unlike every other rule that focuses on some form of proportional representation). The latter fact can be seen as a consequence of Greedy-CC satisfying committee monotonicity (which we argued to be incompatible with the goal of proportional representation). Given this comparison, it is tempting to simply use Greedy-Monroe in place of Greedy-CC. However, perhaps a better idea would be to modify Greedy-Monroe by allowing it to decide how many voters to consider in each iteration. We believe that studying such variant of Greedy-Monroe is an important research direction.

Finally, our results regarding SNTV are quite interesting. This is the only separable committee scoring rule that is also representation-focused. Moreover, it satisfies almost all axioms considered in our work, except strong unanimity. One explanation for this fact is that it can be viewed as a ‘budget-constrained’ variant of the Tullock rule (Tullock 1967); this is the rule that simply picks all the candidates that are ranked first by at least one voter. The Tullock rule possesses nice axiomatic properties, but cannot be used to output a committee of a given size. Of course, since SNTV ignores each voter’s preferences beyond the top candidate, it may return highly counterintuitive results in many cases. For instance, it is extremely indecisive when voters are unanimous: in this case, it may return any committee containing the candidate ranked first by all voters (in particular, it may select a committee that does not include the candidate ranked second by all voters). Also, if the opinions are widely divided, a small group of voters can easily coordinate their efforts to get their preferred candidate elected, even if this candidate is ranked last by all other voters. These flaws of SNTV severely restrict the range of scenarios where it can be used.