论文标题
安全的贿赂有多难？
How Hard is Safe Bribery?
论文作者
论文摘要
选举中的贿赂是计算社会选择中有充分的控制问题之一。在本文中，我们提出并研究了安全的贿赂问题。在这里，贿赂的目的是要求受贿的选民以这样一种方式投票，以至于贿赂从未比新赢家更喜欢原始的赢家（未经贿赂选举），即使贿赂选民没有完全遵循贿赂选民的建议。确实，在贿赂的许多申请中，例如，贿赂经常对贿赂选民最终遵循她的建议有限的控制权，因此可以想象，受贿的选民可以部分或完全忽略贿赂的建议。在本文中，我们为许多常见的投票规则提供了一个全面的复杂性理论景观。
Bribery in an election is one of the well-studied control problems in computational social choice. In this paper, we propose and study the safe bribery problem. Here the goal of the briber is to ask the bribed voters to vote in such a way that the briber never prefers the original winner (of the unbribed election) more than the new winner, even if the bribed voters do not fully follow the briber's advice. Indeed, in many applications of bribery, campaigning for example, the briber often has limited control on whether the bribed voters eventually follow her recommendation and thus it is conceivable that the bribed voters can either partially or fully ignore the briber's recommendation. We provide a comprehensive complexity theoretic landscape of the safe bribery problem for many common voting rules in this paper.
