ML Anthology

Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives

Piotr Faliszewski, Piotr Skowron, Arkadii M. Slinko, Nimrod Talmon
AAAI 2016 pp. 482-488
doi:10.1609/AAAI.V30I1.10031 /aaai/2016/faliszewski2016aaai-multiwinner/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Faliszewski et al. "Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10031

Markdown

[Faliszewski et al. "Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/faliszewski2016aaai-multiwinner/) doi:10.1609/AAAI.V30I1.10031

BibTeX

@inproceedings{faliszewski2016aaai-multiwinner,
  title     = {{Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives}},
  author    = {Faliszewski, Piotr and Skowron, Piotr and Slinko, Arkadii M. and Talmon, Nimrod},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {482-488},
  doi       = {10.1609/AAAI.V30I1.10031},
  url       = {https://mlanthology.org/aaai/2016/faliszewski2016aaai-multiwinner/}
}