Fixing a Tournament

Virginia Vassilevska WilliamsAAAI 2010 · DOI

In competitive sports and gaming, the "bracket" often determines the narrative. A powerhouse might exit early due to a tough first-round draw, while an underdog coasts to the finals through a favorable path. This raises a fundamental computational question: given the outcomes of all possible match-ups, can a tournament designer rig the bracket to ensure a specific player wins?

In the paper "Fixing a Tournament," Virginia Vassilevska Williams (AAAI-10) explores the complexity of the Tournament Fixing Problem (TFP), also known as Agenda Control.

The Tournament Fixing Problem

The TFP asks whether there exists a balanced single-elimination bracket (a binary tree) such that a designated player $A$ wins. The problem is analyzed under two primary constraints:

  1. General Graphs: Only specific pairs of players are permitted to face each other.
  2. Tournament Graphs: Every pair of players has a deterministic outcome, and any pair can be matched in any round.

Computational Hardness in General Graphs

The paper establishes that TFP is NP-complete for general graphs. This means that if match-ups are restricted (e.g., due to regional seeding or scheduling constraints), finding a winning bracket is computationally intractable for large $n$.

The proof relies on a reduction from Exact Cover by 4-Sets (X4C). The construction maps an instance of X4C to a tournament structure where the designated player can only win if a specific set of match-ups—corresponding to an exact cover—can be arranged.

Figure 1: A reduction from Exact Cover by 4-Sets to the Tournament Fixing Problem, illustrating the complex dependencies required to prove NP-completeness in general graphs.

This reduction demonstrates that the jump from unrestricted to restricted match-ups creates a significant complexity barrier, moving the problem from polynomial-time solvable to the NP-complete class.

Sufficient Conditions in Tournament Graphs

In contrast to general graphs, tournament graphs—where any two players can meet—often allow for efficient solutions. The author uses inductive graph theory to identify "binomial winners." A balanced tournament bracket is mathematically represented as a spanning binomial arborescence.

Key insights include:

  • The Power of the "King": A "king" is a player who beats everyone else either directly or via a 2-step path (beating someone who beats their rival).
  • Out-degree Thresholds: Any king with an out-degree (direct wins) of at least $n/2$ is guaranteed to be a binomial winner. Such a bracket can be constructed in polynomial time.
  • Super-Kings: The paper introduces "super-kings"—players who beat many of those who beat them. Even with a low overall win rate, a super-king can often be "fixed" into a winning position.

Noisy Tournament Models

The research also evaluates these findings against the Braverman–Mossel Noisy Sampling Model. This model generates tournament graphs where match outcomes follow an underlying ranking but include random "noise" (upsets).

The results are striking: if the noise level $q$ is sufficiently high ($q > 4\sqrt{\ln n / n}$), almost any player in the tournament can be fixed as the winner with high probability. This suggests that in highly unpredictable environments, the power of the tournament designer is nearly absolute.

Conclusion

Williams' work clarifies the boundaries of tournament manipulation. While restricted match-ups make "rigging" the bracket a hard problem, the existence of "kings" and high levels of competitive parity (noise) make it surprisingly easy for a designer to pick a winner in unrestricted tournaments. Future work remains to bridge the gap between deterministic models and the probabilistic nature of real-world sports.

Summary updated

BibTeX
@inproceedings{williams2010fixing,
  author = {Virginia Vassilevska Williams},
  title = {{Fixing a Tournament}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7617},
}
Figure