# Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives

Piotr Faliszewski: AGH University
Piotr Skowron: University of Warsaw
Nimrod Talmon: Ben-Gurion University of the Negev

Social Choice and Welfare, 2018, vol. 51, issue 3, 513-550

Abstract: Abstract 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}}$$ 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.

Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed

Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Ordering information: This journal article can be ordered from
http://www.springer. ... c+theory/journal/355