Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard
Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard
复制标题
博尔达规则下的无权联合操纵是 NP 难的
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
Nadja Betzler;Rolf Niedermeier;G. Woeginger
Borda投票规则是一项位置评分规则，对于M候选人来说，对于每一个投票，第一个候选人都会获得M-1分，第二个M-2分等等。 Borda获胜者是总分最高的候选人。确定Borda下未加权联盟操纵的计算复杂性是一个突出的公开问题：可以在选举中添加一定数量的额外选票（称为操纵者），以使杰出的候选人成为赢家吗？我们通过向两个操纵者和三票投票展示NP硬度来解决这个开放问题。此外，我们讨论了这种硬度结果的扩展和局限性。
The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m- 1 points, the second m- 2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.