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(n2mk) 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 nm2O(√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.
| Original language | English (US) |
|---|---|
| Title of host publication | 35th AAAI Conference on Artificial Intelligence, AAAI 2021 |
| Publisher | Association for the Advancement of Artificial Intelligence |
| Pages | 5286-5293 |
| Number of pages | 8 |
| ISBN (Electronic) | 9781713835974 |
| DOIs | |
| State | Published - 2021 |
| Event | 35th AAAI Conference on Artificial Intelligence, AAAI 2021 - Virtual, Online Duration: Feb 2 2021 → Feb 9 2021 |
Publication series
| Name | 35th AAAI Conference on Artificial Intelligence, AAAI 2021 |
|---|---|
| Volume | 6A |
Conference
| Conference | 35th AAAI Conference on Artificial Intelligence, AAAI 2021 |
|---|---|
| City | Virtual, Online |
| Period | 2/2/21 → 2/9/21 |
Funding
We thank Arkadii Slinko and Clemens Puppe for answering our questions about the algorithm for CC-WINNER-SCT proposed by Clearwater, Puppe, and Slinko (2015). We also thank the anonymous AAAI-2021 reviewers for their useful suggestions. This work was supported by an ERC Starting Grant ACCORD under Grant Agreement 639945 (Elkind).
ASJC Scopus subject areas
- Artificial Intelligence