Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules

Krzysztof Sornat; Virginia Vassilevska Williams; Yinzhan Xu

IJCAI 2022poster11 citations

Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules

Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu

Abstract

We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given n voters and m candidates, it runs in almost linear time in the input size improving the previous best O(nm^2) time algorithm. We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set D has logarithmic size. Actually, our algorithm runs in 2^|D| * poly(n,m) time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.

Agent-based and Multi-agent Systems: Computational Social Choice

BibTeX

@inproceedings{ijcai2022p69,
  title     = {Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules},
  author    = {Sornat, Krzysztof and Williams, Virginia Vassilevska and Xu, Yinzhan},
  booktitle = {Proceedings of the Thirty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-22}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Lud De Raedt},
  pages     = {482--488},
  year      = {2022},
  month     = {7},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2022/69},
  url       = {https://doi.org/10.24963/ijcai.2022/69},
}