论文标题
重新审视单跨首选项下的比例表示
Proportional Representation under Single-Crossing Preferences Revisited
论文作者
论文摘要
我们研究了在张伯林下确定获胜委员会的复杂性 - 当选民的偏好在线上或更广泛地在中间图上进行单次交叉时，我们的投票规则（此类图包括，例如，树木和网格）。对于这条线，Skowron等人。 （2015年）描述$ O（N^2MK）$算法（其中$ n $，$ m $，$ k $是选民人数，候选人的数量和委员会规模）；我们表明，简单的调整将时间复杂性提高到$ 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\left(\sqrt{\log k\log\log n}\right)}$ algorithm for the general case and a nearly linear algorithm for the Borda虚假陈述功能。对于树木，我们指出了Clearwater，Puppe和Slinko（2015）提出的算法的问题，并为此而开发了$ O（NMK）$算法。对于网格，我们对最佳解决方案的结构进行了猜想，并描述了一个多项式时算法，该算法在此猜想是正确的话，该算法找到了获胜委员会；我们还解释了如何将该算法转换为双晶近似算法，其正确性不取决于猜想。
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)$ 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\left(\sqrt{\log k\log\log n}\right)}$ 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. 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.
