Search versus Decision for Election Manipulation Problems
Search versus Decision for Election Manipulation Problems
复制标题
选举操纵问题的搜索与决策
DOI：
10.1145/3369937
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Curtis Menton
中科院分区：
文献类型：
--
作者：
E. Hemaspaandra;L. Hemaspaandra;Curtis Menton
大多数关于操纵选举复杂性的理论定义都集中在识别哪些实例可以成功操纵的决策问题上，而不是寻找成功的操纵行为的搜索问题上。由于后者对于操纵者来说是一个更自然的目标，如果这两个复杂性可能不同，那么定义的重点可能会被误导。我们的主要结果是它们可能确实不同：如果P≠NP∩coNP(众所周知，如果整数因式分解很难，它本身也成立)，那么对于选举操纵、选举贿赂和某些类型的选举控制，对于某些选举系统，识别哪些实例可以被成功操纵的问题是多项式时间可解的，但是产生成功的操作的任务不能在多项式时间内完成。
Most theoretical definitions about the complexity of manipulating elections focus on the decision problem of recognizing which instances can be successfully manipulated rather than the search problem of finding the successful manipulative actions. Since the latter is a far more natural goal for manipulators, that definitional focus may be misguided if these two complexities can differ. Our main result is that they probably do differ: If P ≠ NP ∩ coNP (which itself is well known to hold if integer factoring is hard), then for election manipulation, election bribery, and some types of election control, there are election systems for which the problem of recognizing which instances can be successfully manipulated is polynomial-time solvable, yet the task of producing the successful manipulations cannot be done in polynomial time.
DOI：
10.1016/j.jcss.2014.11.002
发表时间：
2015-06
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
G. Erdélyi;M. Fellows;J. Rothe;Lena Schend
通讯作者：
G. Erdélyi;M. Fellows;J. Rothe;Lena Schend