A Parameterized Perspective on Protecting Elections
A Parameterized Perspective on Protecting Elections
复制标题
DOI：
10.24963/ijcai.2019/34
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
P. Dey;Neeldhara Misra;Swaprava Nath;Garima Shakya
中科院分区：
文献类型：
--
作者：
P. Dey;Neeldhara Misra;Swaprava Nath;Garima Shakya
我们在两个问题中研究了最佳防御和最佳攻击问题的参数化复杂性。选民攻击者可以攻击，如果选举被攻击，但在最佳辩护问题中没有捍卫选举。知道防守者是否有可能在大多数K_D选民群体中辩护的策略，无论哪种K_A选民将攻击者攻击分组，选举的外部都不会改变。我们想知道攻击者是否有可能采用攻击K_A投票小组的策略，以至于无论是哪个K_D投票小组辩护，选举的结果始终与原始（没有任何攻击）我们表明，最佳防御问题和最佳攻击问题在每个评分规则上都可以进行计算，即使我们只有3个candidates，我们也表明了每个评分规则的最佳防御问题。对于参数k_a和k_d的condorcet投票规则是w [2] - hard，而它允许由组合参数（ka，ka，ka，ka，ka， KD）。国防问题并从经验上表明，它们在合理的投票概况上有效地表现。
We study the parameterized complexity of the optimal defense and optimal attack problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers k_a and k_d corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the optimal defense problem, we want to know if it is possible for the defender to commit to a strategy of defending at most k_d voter groups such that, no matter which k_a voter groups the attacker attacks, the out-come of the election does not change. In the optimal attack problem, we want to know if it is possible for the attacker to commit to a strategy of attacking k_a voter groups such that, no matter which k_d voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one. We show that both the optimal defense problem and the optimal attack problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only3candidates. We also show that the optimal defense problem for every scoring rule and the Condorcet voting rule is W[2]-hard for both the parameters k_a and k_d, while it admits a fixed parameter tractable algorithm parameterized by the combined parameter (ka, kd). The optimal attack problem for every scoring rule and the Condorcet voting rule turns out to be much harder – it is W[1]-hard even for the combined parameter (ka, kd). We propose two greedy algorithms for the OPTIMAL DEFENSE problem and empirically show that they perform effectively on reasonable voting profiles.