论文标题
在两次交战的选举中投票
Voting in Two-Crossing Elections
论文作者
论文摘要
我们介绍了两次交叉选举，作为单跨选举的概括，显示了许多新的结果。首先，我们表明，通过减少经过良好研究的连续问题，可以在多项式时间内认识到两次交叉选举。我们还猜测，认识到$ k $串联的选举通常是NP的完整选举，通过与与连续的问题相似的问题相关的证据，这在文献中被证明是困难的。单跨选举表现出及士性的多数关系，从中许多重要的结果。另一方面，我们表明，古典的Debord-McGarvey定理仍然可以证明是两条交叉的，这意味着任何加权多数锦标赛都是通过两次交战的选举引起的。这表明许多投票规则在包括凯门尼和斯莱特在内的两次选举下都是NP-Hard。这与单线案例相反，并概述了单跨和两跨之间的重要复杂性边界。随后，我们表明，对于两次交叉选举，可以通过制定一个完全单模型的线性程序来在多项式时间内计算所有候选人的年轻分数。最后，我们考虑具有任意疾病的Chamberlin-Courant规则，并表明可以使用基于动态编程的方法在多项式时间内计算获胜委员会。
We introduce two-crossing elections as a generalization of single-crossing elections, showing a number of new results. First, we show that two-crossing elections can be recognized in polynomial time, by reduction to the well-studied consecutive ones problem. We also conjecture that recognizing $k$-crossing elections is NP-complete in general, providing evidence by relating to a problem similar to consecutive ones proven to be hard in the literature. Single-crossing elections exhibit a transitive majority relation, from which many important results follow. On the other hand, we show that the classical Debord-McGarvey theorem can still be proven two-crossing, implying that any weighted majority tournament is inducible by a two-crossing election. This shows that many voting rules are NP-hard under two-crossing elections, including Kemeny and Slater. This is in contrast to the single-crossing case and outlines an important complexity boundary between single- and two-crossing. Subsequently, we show that for two-crossing elections the Young scores of all candidates can be computed in polynomial time, by formulating a totally unimodular linear program. Finally, we consider the Chamberlin-Courant rule with arbitrary disutilities and show that a winning committee can be computed in polynomial time, using an approach based on dynamic programming.
