Research map / Learning theory and algorithms / Submodular and game algorithms
How to Make Knockout Tournaments More Popular?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Tournament Value Maximization, seeding knockout tournaments to maximize total match value under a strength ordering, with NP/APX-hardness, approximation, quasi-polynomial, greedy and FPT algorithms.
Problem
Choosing a seeding of a single-elimination knockout tournament to maximize the total value (profit/popularity) of the matches played, assuming a linear strength ordering of players.
Approach
Shifts the seeding objective from making a specific player win to maximizing the summed score of matches that take place, and gives a complexity map (hardness reductions from Max (2,3)-SAT plus algorithms for restricted game-value classes).
Key results
- Tournament Value Maximization is NP-hard and APX-hard even when game values are in {0,1}, and for round-oblivious values with three distinct values.
- A polynomial-time 1/log n-approximation via maximum-weight matching for round-oblivious game values.
- A greedy linear-time algorithm for player popularity-based values with two popularity values, and an n^{O(log n)} dynamic program for win-count oriented value functions.
Limitations
- Hardness results hold even for restricted value functions; general case remains hard.
- Approximation ratio 1/log n is tight for the presented algorithm, so it is weak.
- Assumes deterministic predictions with a linear strength ordering.
Experimental setup
Metrics: tournament value approximation ratio
Builds on: Tournament Fixing
Closest papers by meaning
- Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable (AAAI 2017 · similarity 0.88)
- Adaptive Manipulation for Coalitions in Knockout Tournaments (AAAI 2025 · similarity 0.86)
- An Exercise in Tournament Design: When Some Matches Must Be Scheduled (AAAI 2024 · similarity 0.84)
- A Matching-Based Algorithm for the Traveling Tournament Problem (AAAI 2025 · similarity 0.78)
- Competition among Pairwise Lottery Contests (AAAI 2024 · similarity 0.77)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.77)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.