Econ Papers Daily / 期刊论文
单交叉偏好下的比例代表制再探讨
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 $$\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.
中文摘要
摘要 本文研究在选民偏好满足直线单峰性，或更一般地在中间图（此类图包括树和网格等）上满足单峰性时，基于Chamberlin–Courant投票规则确定获胜委员会的复杂度问题。针对直线情形，Skowron等人（2015）提出了一个$$\varvec{O}(\varvec{n}^{\varvec{2}}\varvec{mk})$$ O ( n 2 mk ) 算法（其中$$\varvec{n}$$ n 、$$\varvec{m}$$ m 、$$\varvec{k}$$ k 分别表示选民数、候选人数和委员会规模）；我们证明通过简单调整可将时间复杂度改进至$$\varvec{O(nmk)}$$ O ( n m k ) 。进一步地，通过将问题归约为具有Monge-凹权重的完全有向无环图的$$\varvec{k}$$ k -链路路径问题，我们针对任意失真函数获得了$$\varvec{O(n}^{\varvec{1 + o(1)}}\varvec{m})$$ O ( n 1 + o ( 1 ) m ) 算法，并针对Borda失真函数提出了近线性算法。对于树形结构，我们指出Clearwater等人（2015）算法中存在的问题，并为此情形同样开发了$$\varvec{O(nmk)}$$ O ( n m k ) 算法。针对网格结构，我们提出了关于最优解结构的猜想，并描述了在该猜想成立时可在多项式时间内找到获胜委员会的算法；同时说明如何将该算法转化为不依赖该猜想的双准则近似算法。