A Complexity-of-Strategic-Behavior Comparison between Schulze's Rule and Ranked Pairs
A Complexity-of-Strategic-Behavior Comparison between Schulze's Rule and Ranked Pairs
复制标题
舒尔茨规则与排名对之间的策略行为复杂性比较
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Lirong Xia
中科院分区：
文献类型：
--
作者：
D. Parkes;Lirong Xia
Schulze的规则和排名对是两种满足许多天然公理特性的condorcet方法。舒尔兹的统治在许多组织的选举中使用，包括维基梅迪亚基金会，瑞典和德国海盗党，黛比安项目和Gento项目。这两种规则都可以通过克隆替代方案来控制，但是对于它们的战略鲁棒性，包括一个或多个选民对操纵的抵制，通过添加或删除替代方案，增加或删除票数以及贿赂来控制。考虑到计算障碍，我们表明，这些类型的战略行为对于排名对（建设性，使替代方案成为胜利者又具有破坏性，在排除替代方案中排除了替代方案）。相比之下，舒尔兹的统治至少至少对一个联盟的一名选民和破坏性操纵的建设性操纵仍然很容易受到伤害。作为第一个这样的多项式时间规则，已知可以抵抗所有此类操作，并考虑了广泛的公理支持，对实际应用来说，排名成对似乎值得考虑。
Schulze's rule and ranked pairs are two Condorcet methods that both satisfy many natural axiomatic properties. Schulze's rule is used in the elections of many organizations, including the Wikimedia Foundation, the Pirate Party of Sweden and Germany, the Debian project, and the Gento Project. Both rules are immune to control by cloning alternatives, but little is otherwise known about their strategic robustness, including resistance to manipulation by one or more voters, control by adding or deleting alternatives, adding or deleting votes, and bribery. Considering computational barriers, we show that these types of strategic behavior are NP-hard for ranked pairs (both constructive, in making an alternative a winner, and destructive, in precluding an alternative from being a winner). Schulze's rule, in comparison, remains vulnerable at least to constructive manipulation by a single voter and destructive manipulation by a coalition. As the first such polynomial-time rule known to resist all such manipulations, and considering also the broad axiomatic support, ranked pairs seems worthwhile to consider for practical applications.