Computational Complexity Characterization of Protecting Elections from Bribery
Computational Complexity Characterization of Protecting Elections from Bribery
复制标题
保护选举免受贿赂的计算复杂性表征
DOI：
10.1016/j.tcs.2021.08.036
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Shah, Nolan
中科院分区：
文献类型：
--
作者：
Chen, Lin;Sunny, Ahmed Imtiaz;Xu, Lei;Xu, Shouhuai;Gao, Zhimin;Lu, Yang;Shi, Weidong;Shah, Nolan
选举中的贿赂问题在文献中得到了相当大的关注，在此基础上，已经获得了各种算法和复杂度的结果。在这种情况下，人们自然会问，我们能否保护选举免受潜在的贿赂攻击。我们考虑这样一种情况，即保护者（或辩护者）可以以一定的代价保护选民，使受保护的选民不能被贿赂（例如，通过将选民与潜在的贿赂者隔离开来）。这导致了下面的双层决策问题：保护者是否有可能保护一个适当的选民子集，使得没有一个固定预算的贿赂者可以改变选举结果？本文的目标是充分描述相关保护问题的复杂性。我们进行了广泛的研究保护问题，并提供算法和复杂性的结果。当与在文献中研究的贿赂问题相比，我们观察到，我们研究的保护问题是显着困难的一般。事实上，即使对于非常有限的特殊情况，它也成为102 p-完全的，而大多数贿赂问题都存在于NP中。然而，保护问题并不一定总是更难。有些保护问题仍然可以在多项式时间内解决，而有些问题仍然像贿赂问题一样困难。
The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. In this setting, it is natural to ask whether we can protect an election from potential bribery attacks. We consider a scenario where the protector (or defender) can protect a voter at some cost such that a protected voter cannot be bribed (eg, by isolating the voter from potential bribers). This leads to the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget for bribery can alter the election result? The goal of this paper is to give a full characterization of the complexity of the associated protection problems. We conduct an extensive study on the protection problem and provide algorithmic and complexity results. When compared with the bribery problems that have been studied in the literature, we observe that the protection problem we study is significantly harder in general. Indeed, it becomes Σ 2 p-complete even for very restricted special cases, while most bribery problems lie in NP. However, it is not necessarily the case that the protection problem is always harder. Some of the protection problems can still be solved in polynomial time, while some of them remain as hard as the bribery problem with the same setting.
登录
查看更多内容
投票系统的二分法
DOI：
--
发表时间：
2005
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
E. Hemaspaandra;L. Hemaspaandra
通讯作者：
L. Hemaspaandra
两个边缘覆盖的 NP 硬度泛化与控制和贿赂批准投票的应用
DOI：
10.1016/j.ipl.2015.09.008
发表时间：
2016
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
Robert Bredereck;Nimrod Talmon
通讯作者：
Nimrod Talmon
DOI：
10.24963/ijcai.2019/34
发表时间：
2019-05
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
P. Dey;Neeldhara Misra;Swaprava Nath;Garima Shakya
通讯作者：
P. Dey;Neeldhara Misra;Swaprava Nath;Garima Shakya
单指数时间内的投票和贿赂
DOI：
10.1145/3396855
发表时间：
2018
期刊：
ACM Transactions on Economics and Computation (TEAC)
影响因子：
--
作者：
D. Knop;Martin Koutecký;Matthias Mnich
通讯作者：
Matthias Mnich
加权选举控制
DOI：
10.1613/jair.4621
发表时间：
2013
期刊：
ArXiv
影响因子：
--
作者：
Piotr Faliszewski;E. Hemaspaandra;L. Hemaspaandra
通讯作者：
L. Hemaspaandra