Proportional representation under single-crossing preferences revisited

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 median graph (this class of graphs includes, e.g., trees and grids). For the line, Skowron et al. (2015) describe an $$\varvec{O}(\varvec{n}^{\varvec{2}}\varvec{mk})$$ O ( n 2 mk ) algorithm (where $$\varvec{n}$$ n , $$\varvec{m}$$ m , $$\varvec{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 $$\varvec{O(nmk)}$$ O ( n m k ) . We then improve this bound even further by reducing our problem to the $$\varvec{k}$$ k -link path problem for complete DAGs with Monge-concave weights, obtaining an $$\varvec{O(n}^{\varvec{1 + o(1)}}\varvec{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 $$\varvec{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.