Proportional Representation under Single-Crossing Preferences Revisited

Authors

  • Andrei Costin Constantinescu University of Oxford
  • Edith Elkind University of Oxford

Keywords:

Social Choice / Voting

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.

Downloads

Published

2021-05-18

How to Cite

Constantinescu, A. C., & Elkind, E. (2021). Proportional Representation under Single-Crossing Preferences Revisited. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5286-5293. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16667

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms