Introduction
Single-elimination (SE) tournaments are a staple of competitive sports and decision-making processes. A fundamental question for tournament designers is the "Tournament Fixing Problem" (TFP): given a set of players and their pairwise match outcomes, can one construct a bracket such that a specific favorite player wins? While TFP is known to be NP-complete in general, researchers have long sought to identify classes of "strong" players for whom the problem becomes tractable. This paper explores the boundaries of this complexity, examining whether structural advantages like being a "King" or a "3-King" simplify the task of fixing a tournament.
Complexity of Fixing
The authors demonstrate that even significant structural advantages do not necessarily make TFP easy. Through a series of sophisticated graph-theoretic reductions, they prove that the problem remains NP-hard even under restrictive conditions. For instance, fixing a tournament for a "King"—a player who can reach any other player in at most two steps in the tournament graph—is NP-hard even if that King defeats 25% of the field.
As shown in the figure above, the authors establish hardness for several variants:
- (a) King-TFP: Proving hardness for players with a distance-2 reach.
- (b) 3King-TFP: Extending hardness to "3-Kings" who can reach others in three steps.
- (c) Nearly-As-Strong-TFP: Hardness for players with specific out-degree constraints.
- (d) Bribery-TFP: A variant where the organizer can pay players to lose, which remains hard even with a limited bribery budget.
Notation and Structural Analysis
To facilitate their proofs and algorithmic developments, the authors establish a rigorous mathematical framework for describing tournament states. This notation allows for precise tracking of player neighborhoods and survival across multiple rounds of play.
Beyond hardness results, this structural analysis leads to new sufficient conditions for a player to be an SE winner. By examining perfect matchings between player subsets, the authors identify graph properties that guarantee a 3-King can win, providing a counterpoint to the worst-case hardness results.
Modeling "Choking" in Tournaments
A key contribution of this work is the introduction of the "Choking Model," which adds a layer of psychological realism to tournament theory. In this probabilistic model, players generally follow a hierarchy, but "strong" players have a defined probability $q$ of "choking" (losing) against significantly "weaker" opponents.
Interestingly, the authors prove that even with the possibility of choking, top-tier players remain highly likely to have a winning seeding available. Specifically, any player in the top $n/3$ of the field is an SE winner with high probability, provided the choking parameters are within reasonable bounds. This suggests that while finding the optimal bracket is computationally hard, the existence of such a bracket is common for elite competitors.
Algorithmic Improvements
The paper also presents a significant algorithmic advancement for the exact counting of winning seedings. The authors develop a dynamic programming approach that runs in $O(2^n \text{poly } n)$ time. This represents a substantial improvement over the previous state-of-the-art complexity of $O(2.8285^n)$, moving the field closer to the theoretical efficiency limits for these types of combinatorial problems.
Conclusion
This research clarifies the computational landscape of tournament fixing. By proving that even "Kings" face NP-hard paths to victory and introducing more realistic probabilistic models like the Choking Model, the authors bridge the gap between abstract graph theory and the practical realities of competitive play. Their improved exact algorithm further provides a more powerful tool for analyzing tournament structures in both theoretical and applied contexts.
Summary updated