论文标题
关于在基于批准的多获奖者投票中破坏性贿赂的复杂性
On the Complexity of Destructive Bribery in Approval-Based Multi-winner Voting
论文作者
论文摘要
最近已经对基于批准的多翼投票的各种建设性操纵，控制和贿赂问题进行了广泛的研究。但是，他们的破坏性对应物似乎不那么探索。本文调查了五个享有声望的基于批准的多翼投票规则的几个破坏性贿赂问题的复杂性 - 批准投票，满意度批准投票，净满足批准投票，室内林委员会的批准投票和比例批准投票。从广义上讲，这些问题是要确定是否可以通过执行有限数量的修改操作来确定任何获奖委员会的许多给定候选人。我们提供了问题复杂性的完整景观。对于NP硬性问题，我们研究了它们相对于有意义的参数的参数化复杂性。
A variety of constructive manipulation, control, and bribery problems for approval-based multiwinner voting have been extensively studied recently. However, their destructive counterparts seem to be less explored. This paper investigates the complexity of several destructive bribery problems under five prestigious approval-based multiwinner voting rules -- approval voting, satisfaction approval voting, net-satisfaction approval voting, Chamberlin-Courant approval voting, and proportional approval voting. Broadly, these problems are to determine if a number of given candidates can be excluded from any winning committees by performing a limited number of modification operations. We offer a complete landscape of the complexity of the problems. For NP-hard problems, we study their parameterized complexity with respect to meaningful parameters.
