Proportional Representation Under Single-Crossing Preferences Revisited

Andrei Costin Constantinescu, Edith Elkind

AAAI 2021 pp. 5286-5293

doi:10.1609/AAAI.V35I6.16667 /aaai/2021/constantinescu2021aaai-proportional/

Abstract

We study the complexity of determining a winning committee under the Chamberlin-Courant voting rule when voters' preferences are single-crossing on a line, or, more generally, on a tree. For the line, Skowron et al. (2015) describe an O(n^2mk) algorithm (where n, m, k are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to O(nmk). We then improve this bound for k=Ω(log n) by reducing our problem to the k-link path problem for DAGs with concave Monge weights, obtaining a nm2^O(√(log k log log n)) algorithm for the general case and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater, Puppe and Slinko (2015), and develop a O(nmk) algorithm for this case as well.

PDF AAAI Semantic Scholar

Cite

Text

Constantinescu and Elkind. "Proportional Representation Under Single-Crossing Preferences Revisited." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I6.16667

Markdown

[Constantinescu and Elkind. "Proportional Representation Under Single-Crossing Preferences Revisited." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/constantinescu2021aaai-proportional/) doi:10.1609/AAAI.V35I6.16667

BibTeX

@inproceedings{constantinescu2021aaai-proportional,
  title     = {{Proportional Representation Under Single-Crossing Preferences Revisited}},
  author    = {Constantinescu, Andrei Costin and Elkind, Edith},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {5286-5293},
  doi       = {10.1609/AAAI.V35I6.16667},
  url       = {https://mlanthology.org/aaai/2021/constantinescu2021aaai-proportional/}
}