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

Abstract

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.