论文标题
顺序淘汰投票游戏
Sequential Elimination Voting Games
论文作者
论文摘要
顺序淘汰的投票是一种低通信的投票协议：选民按顺序进行比赛，并消除了一个或多个剩余的候选人，直到只剩下一个候选人为止。尽管已经探索了此类协议的公平性和效率，但战略行为的影响尚未得到解决。我们以顺序淘汰为游戏对投票进行建模。给定固定的消除序列，我们表明结果在相应游戏的所有子游戏中的纳什平衡中都是相同的，并且是多项式时间可计算的。我们衡量因战略行为，真诚行为下的结果以及最大化社会福利的结果而导致的社会福利丧失。我们给出了最差的案例比率的紧密界限，并使用实验表明，操纵的平均影响可能远低于最坏情况。
Voting by sequential elimination is a low-communication voting protocol: voters play in sequence and eliminate one or more of the remaining candidates, until only one remains. While the fairness and efficiency of such protocols have been explored, the impact of strategic behaviour has not been addressed. We model voting by sequential elimination as a game. Given a fixed elimination sequence, we show that the outcome is the same in all subgame-perfect Nash equilibria of the corresponding game, and is polynomial-time computable. We measure the loss of social welfare due to strategic behaviour, with respect to the outcome under sincere behaviour, and with respect to the outcome maximizing social welfare. We give tight bounds for worst-case ratios, and show using experiments that the average impact of manipulation can be much lower than in the worst case.
