We provide an axiomatic characterization of committee scoring rules, analogues of the scoring rules for the multiwinner elections. We show that committee scoring rules are characterized by the set of four standard axioms, anonymity, neutrality, consistency and continuity, and by two axioms specific to multiwinner rules, committee neutrality and committee dominance. In the course of our proof, we develop several new notions. In particular, we introduce and characterize decision rules, a notion that may be useful on its own. There are many other applications and we point the reader to the works of Lu and Boutilier [34, 35] , Elkind et al. [15], and Skowron et al. [45] for a more detailed discussion with an AI focus. Since there are many different applications of multiwinner elections, there are also many different multiwinner voting rules. For example, there are rules based on the extension of the singlewinner Condorcet principle 2 (see, e.g., the works of Fishburn [22] , Kaymak and Sanver [27], Ratliff [40], and Barberá and Coelho [5]), there are rules based on approval ballots, where voters express which candidates are and which are not acceptable for them (see, e.g., the works of Kilgour [30], Kilgour and Marshall [32], and Aziz et al. [3] ), and there are numerous other rules based on ordinal preference orders, including committee scoring rules. Indeed, even committee scoring rules are very diverse and include simple "best k" rules such as SNTV or k-Borda, more involved rules, such as the Chamberlin-Courant rule [10] that focus on providing proportional representation, or even more involved ones, such as the variants of the OWA-based rules of Skowron et al. [45] and Aziz et al. [4] . Unfortunately, so far our understanding of multiwinner voting is quite limited, especially as compared to the single-winner setting. By providing a Young-style characterization of committee scoring rules, we hope to somewhat rectify this situation. Committee scoring rules extend their single-winner variants as follows. A single-winner scoring rule is a function that given a position of a candidate in a vote (that is, in the ranking of candidates provided by the voter) outputs a score. The score of a candidate in an election is the sum of the scores he or she gets from all the votes, and the candidates with the highest score win. (For example, the Borda score of candidate c in vote v is the number of candidates that v ranks below c; the Borda rule elects candidates with the highest total Borda score.) The difference in the definition of committee scoring rules is that instead of single candidates we elect size-k committees and, so, we need a different notion of a position. Specifically, we say that the position of a committee in a given vote is the set of the positions of its members in this vote. A committee scoring function assigns scores to such committee positions (with m candidates there are m k such committee positions) and the total score of a committee is the sum of the scores it gets from the voters. The committee(s) with the highest score win. (Formally, we consider committee scoring rules as rules that rank committees based on a given profile of votes. That is, a committee scoring rule ranks the committees from the one with the highest score to the one with the lowest one. This means that we view committee scoring rules as social welfare functions, generalized to the multiwinner setting. In this respect, our approach is closer to that of Merlin [37] than to that taken originally by Young [51].) Given the above description, it is quite natural to expect that committee scoring rules are, indeed, the natural generalization of single-winner scoring rules to the multiwinner setting (as much as one can judge naturalness of various notions). Nonetheless, we would like to obtain a formal justification for this intuition and, to this end, we consider Young's characterization of single-winner scoring rules [51] . (We explain the meaning of the axioms below.) Informally put, a voting rule is symmetric if it treats all the voters and all the candidates in a 2 Condorcet principle says that if for some candidate c it holds that for every other candidate d a majority of voters prefers c to d, then c should be the unique winner of the given single-winner election. Including the committee neutrality axiom is inevitable, but also very natural. On one hand, committee scoring rules do satisfy it, and, on the other hand, it is trivially satisfied for single-winner scoring rules (if we take their winners to be single-member committees, then there is nothing to permute). We believe that committee scoring rules form a very important class of multiwinner rules and, thus, deserve a detailed research program. Our characterization is a natural step of this program. In addition to providing a formal argument that committee scoring rules are a natural extension of single-winner scoring rules to the multiwinner setting, the result is useful for the following reasons: 1. Having an axiomatic characterization is very helpful for understanding the nature of committee scoring rules. (Indeed, due to Young's [51] work and the research that followed, scoring rules are among the best-understood and most widely studied single-winner voting rules.) 2. Many rules are much easier to characterize within the class of committee scoring rules than in the unrestricted setting. For example, Faliszewski et al. [18] characterize the Bloc rule among committee scoring rules. Using our results, one obtains an unrestricted characterization. 3. Our proof approach requires introducing several new notions and ideas. In particular, we discuss decision rules, which given two committees can tell which one is better (but we do not impose the transitivity requirement on such rules). While we use them for technical reasons, we envision that they could find an application of their own. The paper is organized as follows. In Section 2 we provide necessary background regarding multiwinner elections and committee scoring rules. In Section 3 we formally describe the axioms that we use in our characterization. Section 4 contains our main result and its proof. The proof is
Skowron et al. REF show that committee scoring rules can be characterized by four standard properties.
Axiomatic Characterization of Committee Scoring Rules
ArXiv
ArXiv
Economics Mathematics Computer Science