How to Make Knockout Tournaments More Popular?

Juhi Chaudhary, Hendrik Molter, Meirav Zehavi

TL;DR

Researchers have introduced a new computational problem: Tournament Value Maximization. Instead of seeding a bracket to help a specific player win, this approach seeks the optimal seeding to maximize the total "value"—profit, viewership, or excitement—of all matches played. The paper maps out the mathematical landscape of this problem, proving it is generally hard to solve perfectly but offering efficient algorithms for several realistic scenarios.

What Problem Does This Paper Address?

In sports like tennis or the knockout stages of the World Cup, the "seeding" (how players are placed in the bracket) determines which matchups occur. Traditionally, computer science research has focused on "Tournament Fixing"—the ethically dubious task of rigging a bracket so a specific favorite wins.

However, tournament directors have a different goal: maximizing the bottom line. They want the most "valuable" matches to happen. A "local derby" between two rivals or a "clash of titans" between superstars generates more revenue and engagement than a lopsided match between unknowns. The authors formalize this as a combinatorial optimization problem: Given a set of players and a "score" for every possible matchup, how do you arrange the bracket to maximize the sum of scores for all matches that actually take place?

Methods

The authors model the tournament as a complete binary tree where winners of each round advance. They assume a linear ordering of strengths, meaning the stronger player always beats the weaker one (a common simplification in tournament theory).

To tackle the complexity, they categorize the problem based on the "value function":

  1. Unrestricted: Match values can be anything.
  2. Round-Oblivious: A match between Player A and Player B has the same value whether it happens in the first round or the finals.
  3. Win-Count Oriented: The total value depends only on how many matches each player wins.
  4. Player Popularity-Based: Each player has a "popularity score," and the match value is determined by the winner's popularity.

The researchers use L-reductions from MAX (2,3)-SAT to prove hardness and develop Dynamic Programming (DP) and Fixed-Parameter Tractable (FPT) algorithms to find solutions.

Datasets

As a theoretical study in computational complexity, this paper does not use empirical datasets or training data. Instead, it relies on mathematical proofs and algorithmic analysis. The "inputs" are abstract sets of $n$ players (where $n$ is a power of 2) and defined game-value functions.

Key Insights and Ideas

  • The Complexity Barrier: Even in the simplest case—where match values are only 0 or 1—the problem is NP-hard and APX-hard. This means there is no "perfect" fast algorithm, and even getting a very close approximation is computationally difficult.
  • The "Matching" Approximation: The authors show that by simply calculating a "maximum-weight matching" (pairing players to maximize the value of just the first round), you can guarantee a $(1/\log n)$-factor approximation of the total possible tournament value.
  • Open and Closed Subtournaments: To solve the "win-count oriented" version, the authors introduced a clever way to track "open" subtournaments (brackets where a winner hasn't been decided yet). This allowed them to create a quasipolynomial-time algorithm ($n^{O(\log n)}$), which is much faster than an exhaustive search.
  • Influential Sets: They discovered that if only a small number of players ($k$) are actually "popular" (contributing value to matches), the problem becomes much easier to solve (Fixed-Parameter Tractable).

Key Results

The paper provides a "wide spectrum" of results, summarized in the following table:

Restriction Hardness Algorithmic Result
Unrestricted NP-hard / APX-hard -
Round-oblivious NP-hard / APX-hard $(1/\log n)$-factor approximation
Win-count oriented - $n^{O(\log n)}$ (Quasipolynomial)
Popularity-based - Linear-time (for 2 player values)

Specifically, they proved that if you only have two types of players ("popular" and "unpopular"), you can find the absolute best seeding in linear time using a simple greedy approach.

Limitations and Future Work

  • Deterministic Outcomes: The model assumes the stronger player always wins. In reality, sports are defined by upsets. Future work could incorporate probabilistic outcomes (e.g., Player A has a 70% chance of beating Player B).
  • Value Function Complexity: The current "popularity-based" model is simple. The authors suggest looking at more complex functions, such as match values defined by the product of the two players' popularity scores.
  • Approximation Gaps: While they provided a $(1/\log n)$ approximation, they leave open the question of whether a constant-factor approximation (a much stronger guarantee) is possible for non-round-oblivious tournaments.

Summary updated

Abstract

Given a mapping from a set of players to the leaves of a complete binary tree (called a seeding), a knockout tournament is conducted as follows: every round, every two players with a common parent compete against each other, and the winner is promoted to the common parent; then, the leaves are deleted. When only one player remains, it is declared the winner. This is a popular competition format in sports, elections, and decision-making. Over the past decade, it has been studied intensively from both theoretical and practical points of view. Most frequently, the objective is to seed the tournament in a way that ``assists'' (or even guarantees) some particular player to win the competition. We introduce a new objective, which is very sensible from the perspective of the directors of the competition: maximize the profit or popularity of the tournament. Specifically, we associate a ``score'' with every possible match, and aim to seed the tournament to maximize the sum of the scores of the matches that take place. We focus on the case where we assume a total order on the players' strengths, and provide a wide spectrum of results on the computational complexity of the problem.
BibTeX
@inproceedings{chaudhary2024how,
  author = {Juhi Chaudhary and Hendrik Molter and Meirav Zehavi},
  title = {{How to Make Knockout Tournaments More Popular?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28814},
}

Loading related content...

Figure