Committee scoring voting rules are multiwinner analogues of positional scoring rules which constitute an important subclass of single-winner voting rules. We identify several natural subclasses of committee scoring rules, namely, weakly separable, representation-focused, top- @math -counting, OWA-based, and decomposable rules. We characterize SNTV, Bloc, and @math -Approval Chamberlin--Courant as the only nontrivial rules in pairwise intersections of these classes. We provide some axiomatic characterizations for these classes, where monotonicity properties appear to be especially useful. The class of decomposable rules is new to the literature. We show that it strictly contains the class of OWA-based rules and describe some of the applications of decomposable rules.
@cite_10 @cite_16 studied a class of approval-based rules that is very similar to the class of committee scoring rules (the class was first introduced by Thiele @cite_75 in the 19th century, but was forgotten for some time; some of Thiele's rules were recalled by Kilgour @cite_65 and then by ). Lackner and Skowron @cite_24 studied axiomatic properties of these rules and highlighted their axiomatic similarity to committee scoring rules. Recently, monotonicity notions similar to those studied in this paper were also considered in the context of approval-based multiwinner rules @cite_68 @cite_24 . For more general discussions of the properties of approval-based rules we point the reader to the work of Kilgour and Marshall @cite_52 .
@cite_75 @cite_65 @cite_52 @cite_24 @cite_68 @cite_16 @cite_10
2607903188 2338144305 2763181606 2289435862 196507789 2949245628 2100161145
This paper is an axiomatic study of consistent approval-based multi-winner rules, i.e., voting rules that select a fixed-size group of candidates based on approval ballots. We introduce the class of counting rules, provide an axiomatic characterization of this class and, in particular, show that counting rules are consistent. Building upon this result, we axiomatically characterize three important consistent multi-winner rules: Proportional Approval Voting, Multi-Winner Approval Voting and the Approval Chamberlin--Courant rule. Our results demonstrate the variety of multi-winner rules and illustrate three different, orthogonal principles that multi-winner voting rules may represent: individual excellence, diversity, and proportionality. Committee scoring rules form a rich class of aggregators of voters' preferences for the purpose of selecting subsets of objects with desired properties, e.g., a shortlist of candidates for an interview, a representative collective body such as a parliament, or a set of locations for a set of public facilities. In the spirit of celebrated Young's characterization result that axiomatizes single-winner scoring rules, we provide an axiomatic characterization of multiwinner committee scoring rules. We show that committee scoring rules---despite forming a remarkably general class of rules---are characterized by the set of four standard axioms, anonymity, neutrality, consistency and continuity, and by one axiom specific to multiwinner rules which we call committee dominance. In the course of our proof, we develop several new notions and techniques. In particular, we introduce and axiomatically characterize multiwinner decision scoring rules, a class of rules that broadly generalizes the well-known majority relation. In this paper we study several monotonicity axioms in approval-based multi-winner voting rules. We consider monotonicity with respect to the support received by the winners and also monotonicity in the size of the committee. Monotonicity with respect to the support is studied when the set of voters does not change and when new voters enter the election. For each of these two cases we consider a strong and a weak version of the axiom. We observe certain incompatibilities between the monotonicity axioms and well-known representation axioms (extended proportional justified representation) for the voting rules that we analyze and provide formal proofs of incompatibility between some of these axioms and perfect representation. We characterize the class of committee scoring rules that satisfy the fixed-majority criterion. In some sense, the committee scoring rules in this class are multiwinner analogues of the single-winner Plurality rule, which is uniquely characterized as the only single-winner scoring rule that satisfies the simple majority criterion. We find that, for most of the rules in our new class, the complexity of winner determination is high (i.e., the problem of computing the winners is NP-hard), but we also show some examples of polynomial-time winner determination procedures, exact and approximate. In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as the votes of voters outside the subelectorate, we can conclude which of the m alternatives wins. This corresponds to the notion of compilation complexity, the minimum number of bits required to summarize the votes for a particular rule, which was introduced by [IJCAI-09]. We study three different types of compilation complexity. The first, studied by , depends on the size of the subelectorate but not on the size of the complement (the voters outside the subelectorate). The second depends on the size of the complement but not on the size of the subelectorate. The third depends on both. We first investigate the relations among the three types of compilation complexity. Then, we give upper and lower bounds on all three types of compilation complexity for the most prominent voting rules. We show that for l-approval (when l ≤ m 2), Borda, and Bucklin, the bounds for all three types are asymptotically tight, up to a multiplicative constant; for l-approval (when l > m 2), plurality with runoff, all Condorcet consistent rules that are based on unweighted majority graphs (including Copeland and voting trees), and all Condorcet consistent rules that are based on the order of pairwise elections (including ranked pairs and maximin), the bounds for all three types are asymptotically tight up to a multiplicative constant when the sizes of the subelectorate and its complement are both larger than m1+∊ for some ∊ > 0. The goal of this paper is to propose and study properties of multiwinner voting rules which can be consider as generalisations of single-winner scoring voting rules. We consider SNTV, Bloc, k-Borda, STV, and several variants of Chamberlin--Courant's and Monroe's rules and their approximations. We identify two broad natural classes of multiwinner score-based rules, and show that many of the existing rules can be captured by one or both of these approaches. We then formulate a number of desirable properties of multiwinner rules, and evaluate the rules we consider with respect to these properties. We introduce a class of voting rules called generalized scoring rules. Under such a rule, each vote generates a vector of k scores, and the outcome of the voting rule is based only on the sum of these vectors---more specifically, only on the order (in terms of score) of the sum's components. This class is extremely general: we do not know of any commonly studied rule that is not a generalized scoring rule. We then study the coalitional manipulation problem for generalized scoring rules. We prove that under certain natural assumptions, if the number of manipulators is O(np) (for any p 1 2) and o(n), then the probability that a random profile is manipulable (to any possible winner under the voting rule) is 1--O(e--Ω(n2p--1)). We also show that common voting rules satisfy these conditions (for the uniform distribution). These results generalize earlier results by Procaccia and Rosenschein as well as even earlier results on the probability of an election being tied.