How to Make Knockout Tournaments More Popular?

Juhi Chaudhary, Hendrik Molter, Meirav Zehavi

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.

Introduction

In major sporting events like the knockout stages of the World Cup or Grand Slam tennis tournaments, the "seeding"—the specific placement of players or teams in the bracket—is a critical decision. Traditionally, computational research has focused on "Tournament Fixing," where the goal is to manipulate the bracket to ensure a specific favorite wins.

However, tournament directors often have a different priority: Tournament Value Maximization (TVM). Their goal is to maximize the total "value" of the tournament, which could represent ticket sales, television viewership, or overall fan excitement. A match between two legendary rivals or a high-stakes "clash of titans" is far more valuable than a predictable match between unknowns. This paper formalizes TVM as a combinatorial optimization problem, seeking the optimal seeding to maximize the sum of scores for all matches that occur.

Problem Modeling and Methods

The researchers model the tournament as a complete binary tree where winners advance through rounds. A key assumption is a linear ordering of strengths, meaning the stronger player always defeats the weaker one. This simplification allows for a rigorous mathematical analysis of how seeding affects the eventual match lineup.

To understand the complexity of TVM, the authors categorize the problem based on the "value function" of the matches:

  1. Unrestricted: Match values are arbitrary.
  2. Round-Oblivious: The value of a match between two players is constant regardless of which round it occurs in.
  3. Win-Count Oriented: The value depends solely on the number of matches each player wins.
  4. Player Popularity-Based: Each player has a popularity score, and the match value is derived from the winner's popularity.

To prove the inherent difficulty of these problems, the researchers utilize L-reductions from MAX (2,3)-SAT, a specific variant of the satisfiability problem.

The MAX (2,3)-SAT problem definition used for hardness reductions in the paper's proofs.

Key Insights and Results

The paper maps out a "wide spectrum" of results, demonstrating that while the general problem is computationally difficult, specific realistic constraints allow for efficient solutions.

  • The Complexity Barrier: Even in the simplest unrestricted cases, the problem is both NP-hard and APX-hard, meaning no efficient algorithm can find a perfect solution, and even close approximations are difficult to guarantee.
  • Approximation Strategies: For round-oblivious tournaments, the authors show that a "maximum-weight matching" (optimizing just the first round) provides a $(1/\log n)$-factor approximation of the total tournament value.
  • Algorithmic Breakthroughs: For win-count oriented scenarios, they developed a quasipolynomial-time algorithm ($n^{O(\log n)}$). Furthermore, if match values are determined by a small set of "influential" players, the problem becomes Fixed-Parameter Tractable (FPT).
A comprehensive summary of the hardness and algorithmic results for various tournament restrictions.

Conclusion and Future Work

This research provides the first deep dive into the complexity of maximizing tournament popularity. While the current model assumes deterministic outcomes (the stronger player always wins), it sets the stage for future work involving probabilistic outcomes and more complex value functions, such as those where match value is a product of both players' popularities. The search for a constant-factor approximation for non-round-oblivious tournaments remains an intriguing open question for the field.

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},
}
Figure