Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
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.
Cite
Text
Sornat et al. "Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/69Markdown
[Sornat et al. "Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/sornat2022ijcai-near/) doi:10.24963/IJCAI.2022/69BibTeX
@inproceedings{sornat2022ijcai-near,
title = {{Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules}},
author = {Sornat, Krzysztof and Williams, Virginia Vassilevska and Xu, Yinzhan},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {482-488},
doi = {10.24963/IJCAI.2022/69},
url = {https://mlanthology.org/ijcai/2022/sornat2022ijcai-near/}
}