论文标题
新的复杂性结果是对Borda的联盟操纵
New Complexity Results on Coalitional Manipulation of Borda
论文作者
论文摘要
Borda投票规则是$ Z $候选人的位置评分规则，以便在每次投票中，第一个候选人获得$ z-1 $积分，第二$ Z-2 $点等等。 Borda规则的获胜者是总分最高的候选人。我们在具有两个非操纵器的环境中研究了Borda规则的操纵问题，而非操纵者的投票之一是加权的。根据非操纵器的重量，我们证明了计算复杂性的鲜明对比：当重量大于$ 1 $时，问题是NP-HARD，而存在有效的算法，可以在最多$ 1 $的重量时找到操纵。
The Borda voting rule is a positional scoring rule for $z$ candidates such that in each vote, the first candidate receives $z-1$ points, the second $z-2$ points and so on. The winner in the Borda rule is the candidate with highest total score. We study the manipulation problem of the Borda rule in a setting with two non-manipulators while one of the non-manipulator's vote is weighted. We demonstrate a sharp contrast on computational complexity depending on the weight of the non-manipulator: the problem is NP-hard when the weight is larger than $1$ while there exists an efficient algorithm to find a manipulation when the weight is at most $1$.
