Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
Authors: Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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(nm2) 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. |
| Researcher Affiliation | Academia | Krzysztof Sornat1 , Virginia Vassilevska Williams2 , Yinzhan Xu2 1AGH University, Poland 2MIT CSAIL, USA |
| Pseudocode | No | The paper describes algorithms verbally and through lemmas and theorems, but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements or links regarding open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on algorithm design and complexity, and thus does not involve empirical training on datasets. No dataset access information is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical validation experiments. Thus, there are no training/test/validation dataset splits mentioned. |
| Hardware Specification | No | This is a theoretical paper focused on algorithms and complexity, and therefore does not mention any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper focused on algorithms and complexity. While it mentions the real-RAM and word-RAM models of computation, it does not specify any software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper focused on algorithms and complexity. It does not describe an experimental setup with hyperparameters or system-level training settings. |