Abstract
This paper presents the first tight analysis of a tournament rule's resistance to manipulation by coalitions of three teams. Focusing on the Randomized Death Match (RDM) rule, we prove it is 3-SNM-31/60, meaning a three-team coalition cannot increase its collective win probability by more than 31/60 through match manipulation. Furthermore, we demonstrate that RDM is asymptotically strongly Sybil-proof, effectively penalizing non-dominant teams that attempt to flood the tournament with clones.
Introduction
In competitive environments, such as eSports or traditional sports, tournament rules aggregate pairwise match results to determine an overall winner. Ideally, these rules should satisfy two primary criteria: Condorcet consistency (a team that defeats all others in pairwise matchups should win with 100% probability) and non-manipulability (teams should not be able to "throw" matches to benefit themselves or their allies).
While researchers have established optimal rules for pairs of colluding teams—where the maximum gain is capped at 1/3—the mathematical complexity increases significantly when three or more teams work in concert. Prior to this research, no "tight" bound (an exact maximum possible gain) had been established for any fair tournament rule involving three manipulators. This paper fills this gap by analyzing the Randomized Death Match (RDM) rule and its resistance to both coalition manipulation and Sybil attacks.
Methodology: The Randomized Death Match Rule
The authors focus on the Randomized Death Match (RDM) rule. In this format, the tournament organizer repeatedly selects two teams at random from the remaining pool to play a match. The loser is eliminated, and the process repeats until only one team remains.
To analyze the limits of manipulation within this rule, the authors utilize a first-step analysis framework. Rather than simulating every possible tournament outcome, they model the initial match of the tournament as a transition to a smaller sub-tournament. By applying induction and conducting an exhaustive case-by-case analysis of small tournament structures—specifically focusing on a 5-team "worst-case" scenario—the authors mathematically determined the exact maximum benefit a 3-team coalition could achieve.
Key Insights and Results
The 31/60 Bound
The central contribution of this work is the proof that RDM is 3-SNM-31/60. The authors identified a specific 5-team tournament structure where a 3-team coalition can gain exactly 31/60 in win probability by manipulating their internal matches. Crucially, the paper proves that no other tournament configuration, regardless of size, allows for a larger gain. This improves significantly upon the previous best-known bound of 2/3 (approx. 0.66) for fair rules, lowering it to approximately 0.516.
Monotonicity and Strategy
The analysis reveals that while RDM is "monotone" (losing a match on purpose never increases the loser's individual chance of winning), it is not "strongly monotone." In certain edge cases, flipping a match outcome to help a coalition might actually decrease the coalition's overall win probability. This nuance highlights the complexity of strategic manipulation in randomized formats.
Asymptotic Sybil-Proofness
The paper also addresses Sybil attacks, where a single entity enters multiple "clones" into a tournament to dominate the outcome. The authors prove that RDM is Asymptotically Strongly Sybil-Proof (ASSP). In many systems, more entries equate to a higher win probability; however, in RDM, a "Sybil Paradox" occurs: if a team is not a Condorcet winner (a team that beats everyone else), the probability that the team or any of its clones wins actually approaches zero as the number of clones increases.
Conclusion and Future Work
This research establishes a major milestone in algorithmic game theory by providing the first tight analysis for a Condorcet-consistent rule with more than two manipulators. While the first-step analysis proved successful for coalitions of size $k=3$, the authors acknowledge that the computational complexity grows rapidly for larger groups. Future work may involve automating this case analysis for $k=4$ or $k=5$ and applying the framework to alternative rules, such as "Randomized King of the Hill," to identify even more robust tournament structures.
Summary updated