Ties in Multiwinner Approval Voting

Łukasz Janeczko; Piotr Faliszewski

IJCAI 2023poster6 citations

Ties in Multiwinner Approval Voting

Abstract

We study the complexity of deciding if there is a tie in a given approval-based multiwinner election, as well as the complexity of counting tied winning committees. We consider a family of Thiele rules, their greedy variants, Phragmen's sequential rule, and Method of Equal Shares. For most cases, our problems are computationally hard, but for sequential rules we find an FPT algorithm for discovering ties (parameterized by the committee size). We also show experimentally that in elections of moderate size ties are quite frequent.

Game Theory and Economic Paradigms: GTEP: Computational social choice

BibTeX

@inproceedings{ijcai2023p308,
  title     = {Ties in Multiwinner Approval Voting},
  author    = {Janeczko, Łukasz and Faliszewski, Piotr},
  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-23}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Edith Elkind},
  pages     = {2765--2773},
  year      = {2023},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2023/308},
  url       = {https://doi.org/10.24963/ijcai.2023/308},
}