Control Complexity in Fallback Voting
Control Complexity in Fallback Voting
复制标题
控制后备投票的复杂性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
J. Rothe
中科院分区：
文献类型：
--
作者：
G. Erdélyi;J. Rothe
我们研究了回退投票的控制复杂性。与操纵和贿赂一样，选举控制描述了改变选举结果的方式;与操纵或贿赂企图不同，控制行动-例如添加/删除/分割候选人或选民-修改选举的参与结构。计算复杂性可以用来保护选举免受控制企图的影响，即，证明选举系统抵抗某种类型的控制表明，相应控制动作的成功虽然不是不可能的，但在计算上是禁止的。
我们发现，后备投票，一个选举系统相结合的批准与多数表决（布拉姆斯和桑弗2009），是抵抗每一个14种常见类型的候选人控制，也对三种类型的选民控制。先前已知的完全抵抗候选人控制的选举系统是复数（Bartholdi III et al. 1992，Hemaspaandra et al. 2007）和基于真诚策略偏好的批准投票（SP-AV）（Erdelyi et al. 2009）。然而，与回退投票相比，多数对选民控制的阻力更小，并且SP-AV（由Erdelyi等人修改）可以说是比回退投票更不自然的系统。
We study the control complexity of fallback voting. Like manipulation and bribery, electoral control describes ways of changing the outcome of an election; unlike manipulation or bribery attempts, control actions---such as adding/deleting/partitioning either candidates or voters---modify the participative structure of an election. Computational complexity can be used to protect elections from control attempts, i.e., proving an election system resistant to some type of control shows that the success of the corresponding control action, though not impossible, is computationally prohibitive.
We show that fallback voting, an election system combining approval with majority voting (Brams & Sanver 2009), is resistant to each of the 14 common types of candidate control, and also to three types of voter control. The only election systems previously known to be fully resistant to candidate control are plurality (Bartholdi III et al. 1992, Hemaspaandra et al. 2007) and sincere-strategy preference-based approval voting (SP-AV) (Erdelyi et al. 2009). However, plurality has fewer resistances to voter control than fallback voting, and SP-AV (as modified by Erdelyi et al. (2009)) is arguably less natural a system than fallback voting.