论文标题
攻击和捍卫选举的参数化观点
A Parameterized Perspective on Attacking and Defending Elections
论文作者
论文摘要
我们考虑通过分别叙述和改变选票来保护和操纵选举的问题。我们的环境涉及在多个地区举行的基于多数的选举，并且问题制定基于〜[Elkind等，IJCAI 2019]最近提出的模型。事实证明，即使在相当简单的设置中，操纵和保护问题也是NP填充的。我们从参数化的角度研究这些问题，目的是建立更详细的复杂性格局。我们考虑的参数包括选民人数以及攻击者和辩护人的预算。虽然我们在通过选民数量进行参数化时观察到固定参数的障碍性，但我们的主要贡献是与攻击者和辩护人的预算一起工作时的参数硬度。
We consider the problem of protecting and manipulating elections by recounting and changing ballots, respectively. Our setting involves a plurality-based election held across multiple districts, and the problem formulations are based on the model proposed recently by~[Elkind et al, IJCAI 2019]. It turns out that both of the manipulation and protection problems are NP-complete even in fairly simple settings. We study these problems from a parameterized perspective with the goal of establishing a more detailed complexity landscape. The parameters we consider include the number of voters, and the budgets of the attacker and the defender. While we observe fixed-parameter tractability when parameterizing by number of voters, our main contribution is a demonstration of parameterized hardness when working with the budgets of the attacker and the defender.
