Proportional representation under single-crossing preferences revisited

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 median graph (this class of graphs includes, e.g., trees and grids). For the line, Skowron et al. (2015) describe an O(n^2mk) O ( n 2 mk ) algorithm (where n n , m m , k 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) O ( n m k ) . We then improve this bound even further by reducing our problem to the k k -link path problem for complete DAGs with Monge-concave weights, obtaining an O(n^1 + o(1)m) O ( n 1 + o ( 1 ) m ) algorithm for arbitrary misrepresentation functions and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater et al. (2015), and develop an O(nmk) O ( n m k ) algorithm for this case as well. For grids, we formulate a conjecture about the structure of optimal solutions, and describe a polynomial-time algorithm that finds a winning committee if this conjecture is true; we also explain how to convert this algorithm into a bicriterial approximation algorithm whose correctness does not depend on the conjecture.