On Approximately Strategy-Proof Tournament Rules for Collusions of Size ≥3

A tournament organizer must select one of $n$ possible teams as the winner of a competition after observing all $\binom{n}{2}$ matches between them. The organizer would like to find a tournament rule that simultaneously satisfies the following desiderata. It must be \emph{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 \emph{strongly non-manipulable} for groups of size $k$ at probability $\alpha$ (henceforth, $\kSNMx{k}{\alpha}$), meaning that no subset of $\leq 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~\cite{RSEB} to $d$-ary trees and provide upper bounds to its manipulability. Then, we propose a novel tournament rule that is CC and $\kSNMx{3}{1/2}$, a strict improvement upon the recent work of~\cite{deathmatch} who proposed a CC and $\kSNMx{3}{31/60}$ rule. Finally, we initiate the study of reductions among tournament rules.

• Algorithms and theory