A tournament organizer must select one of n possible teams as the winner of a competition after observing all \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) \) matches between them. The organizer would like to find a tournament rule that simultaneously satisfies the following desiderata. It must be Condorcet-consistent (henceforth, CC), meaning it selects as the winner the unique team that beats all other teams (if one exists). It must also be strongly non-manipulable for groups of size k at probability \(\alpha \) (henceforth, \(k\text {-}\textsc {SNM}\text {-}\alpha \) ), meaning that no subset of \(\le k\) teams can fix the matches among themselves in order to increase the chances any of it’s members being selected by more than \(\alpha \) . Our contributions are threefold. First, wee consider a natural generalization of the Randomized Single Elimination Bracket rule from [18] to d-ary trees and provide upper bounds to its manipulability. Then, we propose a novel tournament rule that is CC and \(3\text {-}\textsc {SNM}\text {-}1/2\) , a strict improvement upon the recent work of [7] who proposed a CC and \(3\text {-}\textsc {SNM}\text {-}31/60\) rule. Finally, we initiate the study of reductions among tournament rules.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Approximately Strategy-Proof Tournament Rules for Collusions of Size at Least Three

  • David Mikšaník,
  • Ariel Schvartzman,
  • Jan Soukup

摘要

A tournament organizer must select one of n possible teams as the winner of a competition after observing all \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) \) matches between them. The organizer would like to find a tournament rule that simultaneously satisfies the following desiderata. It must be Condorcet-consistent (henceforth, CC), meaning it selects as the winner the unique team that beats all other teams (if one exists). It must also be strongly non-manipulable for groups of size k at probability \(\alpha \) (henceforth, \(k\text {-}\textsc {SNM}\text {-}\alpha \) ), meaning that no subset of \(\le k\) teams can fix the matches among themselves in order to increase the chances any of it’s members being selected by more than \(\alpha \) . Our contributions are threefold. First, wee consider a natural generalization of the Randomized Single Elimination Bracket rule from [18] to d-ary trees and provide upper bounds to its manipulability. Then, we propose a novel tournament rule that is CC and \(3\text {-}\textsc {SNM}\text {-}1/2\) , a strict improvement upon the recent work of [7] who proposed a CC and \(3\text {-}\textsc {SNM}\text {-}31/60\) rule. Finally, we initiate the study of reductions among tournament rules.