A committee selection rule (or, multiwinner voting rule) is a mapping that takes a collection of strict preference rankings and a positive integer k as input, and outputs one or more subsets of candidates of size k. In this paper we consider committee selection rules that can be viewed as generalizations of single-winner scoring rules, including SNTV, Bloc, k-Borda, STV, as well as several variants of the Chamberlin–Courant rule and the Monroe rule and their approximations. We identify two natural broad classes of committee selection rules, and show that many of the existing rules belong to one or both of these classes. We then formulate a number of desirable properties of committee selection rules, and evaluate the rules we consider with respect to these properties.
30 January 2011 in Journal of Artificial Intelligence Research
We characterize the class of committee scoring rules that satisfy the fixed-majority criterion. We argue that 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 define top-k-counting committee scoring rules and show that the fixed-majority consistent rules are a subclass of the top-k-counting rules. We give necessary and sufficient conditions for a top-k-counting rule to satisfy the fixed-majority criterion. We show that, for many top-k-counting rules, the complexity of winner determination is high (formally, we show that the problem of deciding if there exists a committee with at least a given score is \({\mathrm {NP}}\)-hard), but we also show examples of rules with polynomial-time winner determination procedures. For some of the computationally hard rules, we provide either exact FPT algorithms or approximate polynomial-time algorithms.
2 October 2014 in Autonomous Agents and Multi-Agent Systems