Control complexity in Bucklin and fallback voting: An experimental analysis
Control complexity in Bucklin and fallback voting: An experimental analysis
复制标题
控制巴克林和后备投票的复杂性：实验分析
DOI：
10.1016/j.jcss.2014.11.003
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Lena Schend
中科院分区：
文献类型：
--
作者：
G. Erdélyi;M. Fellows;J. Rothe;Lena Schend
选举中的控制模拟了外部行为者试图通过重组选举本身来改变选举结果的情况。相应的决策问题已被证明是NP-困难的各种投票系统。特别是，在我们的同伴论文[16]中，我们已经证明了回退和Bucklin投票对几乎所有常见的控制类型都有抵抗力（就NP-硬度而言）。虽然操纵的NP-硬度结果（篡改选举结果的另一种方式）已经在实验上受到挑战（参见，例如，沃尔什的工作[38]，[37]），这样的实验方法是非常缺乏控制。我们第一次在实验环境中解决NP难控制问题。我们的实验允许更细粒度的分析和比较，在各种控制方案，投票分布模型，投票系统，而不仅仅是说明所有这些控制问题的NP-硬度。
Control in elections models situations in which an external actor tries to change the outcome of an election by restructuring the election itself. The corresponding decision problems have been shown NP-hard for a variety of voting systems. In particular, in our companion paper [16], we have shown that fallback and Bucklin voting are resistant (in terms of NP-hardness) to almost all of the common types of control. While NP-hardness results for manipulation (another way of tampering with the outcomes of elections) have been challenged experimentally (see, e.g., the work of Walsh [38], [37]), such an experimental approach is sorely missing for control. We for the first time tackle NP-hard control problems in an experimental setting. Our experiments allow a more fine-grained analysis and comparison—across various control scenarios, vote distribution models, and voting systems—than merely stating NP-hardness for all these control problems.
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