Condorcet-Consistent and Approximately Strategyproof Tournament Rules
Condorcet-Consistent and Approximately Strategyproof Tournament Rules
复制标题
孔多塞一致且近似策略证明的锦标赛规则
DOI：
10.4230/lipics.itcs.2017.35
复制
发表时间：
2016
期刊：
影响因子：
17.6
通讯作者：
S. Weinberg
中科院分区：
文献类型：
--
作者：
Jon Schneider;Ariel Schvartzman;S. Weinberg
我们考虑了$ N $竞争者的圆形巡回赛锦标赛规则的可操作性规则。具体而言，$ n $竞争者正在争夺奖品，而锦标赛规则$ r $地图是所有$ \ binom {n} {2} {2} $ pairwise Matches的结果（称为锦标赛，$ t $） 。规则$ r $是condorcet的一致性，如果每当$ i $赢得她的比赛的所有$ n-1 $，$ r $ $ $ $ i $ i $带有概率$ 1 $。
我们考虑对锦标赛的战略操纵，其中玩家$ j $可能会将他们的比赛投入到球员$ i $上，以增加其中一个赢得比赛的可能性。无论为什么$ j $选择这样做的原因，只要$ \ pr [r（t）= i] $增加超过$ \ pr [r（t）= j] $减少，就存在操纵的可能性。 。不幸的是，众所周知，每个condorcet一致的规则都是可以操纵的（Altman和Kleinberg）。在这项工作中，我们解决了一个问题，即通过尝试最大程度地减少$ \ pr [r（t）= i] $的增加与$ \ pr [r [r（ t）= J] $，用于任何潜在的操纵对。
我们表明，每个condorcet一致的规则实际上都是$ 1/3 $ - 可操作的，并且根据随机的单个消除括号选择获胜者，对于任何$ \ alpha> 1/3 $，都不是$ \ alpha $ - 可容纳$ \ alpha $。我们还表明，许多先前研究的比赛格式都是$ 1/2 $ - 可容纳的，而流行的Copeland规则（任何选择胜利最多的球员的规则）实际上都是$ 1 $ $ 1 $ - 可能是最糟糕的。最后，我们考虑扩展以在两个以上玩家的组合之间进行匹配。
We consider the manipulability of tournament rules for round-robin tournaments of $n$ competitors. Specifically, $n$ competitors are competing for a prize, and a tournament rule $r$ maps the result of all $\binom{n}{2}$ pairwise matches (called a tournament, $T$) to a distribution over winners. Rule $r$ is Condorcet-consistent if whenever $i$ wins all $n-1$ of her matches, $r$ selects $i$ with probability $1$.
We consider strategic manipulation of tournaments where player $j$ might throw their match to player $i$ in order to increase the likelihood that one of them wins the tournament. Regardless of the reason why $j$ chooses to do this, the potential for manipulation exists as long as $\Pr[r(T) = i]$ increases by more than $\Pr[r(T) = j]$ decreases. Unfortunately, it is known that every Condorcet-consistent rule is manipulable (Altman and Kleinberg). In this work, we address the question of how manipulable Condorcet-consistent rules must necessarily be - by trying to minimize the difference between the increase in $\Pr[r(T) = i]$ and decrease in $\Pr[r(T) = j]$ for any potential manipulating pair.
We show that every Condorcet-consistent rule is in fact $1/3$-manipulable, and that selecting a winner according to a random single elimination bracket is not $\alpha$-manipulable for any $\alpha > 1/3$. We also show that many previously studied tournament formats are all $1/2$-manipulable, and the popular class of Copeland rules (any rule that selects a player with the most wins) are all in fact $1$-manipulable, the worst possible. Finally, we consider extensions to match-fixing among sets of more than two players.