Robust Value Maximization in Challenge the Champ Tournaments with Probabilistic Outcomes
2026-02-16 • Computer Science and Game Theory
Computer Science and Game TheoryData Structures and Algorithms
AI summaryⓘ
The authors study a tournament style called Challenge the Champ, where players face off one by one, and the winner faces the next challenger. Each player has a popularity score that adds value when they win a match. Unlike past work that assumed matches have certain outcomes, this research considers that match results can be unpredictable or probabilistic. They find that it's very hard to plan the order of players beforehand to guarantee high total value in these uncertain situations, but if the order can adapt based on match results or if uncertainty is limited, good strategies can be made.
tournament formatseedingprobabilistic outcomesvalue maximizationadaptive algorithmsrobust optimizationChallenge the Champapproximation hardnessnon-adaptive algorithms
Authors
Umang Bhaskar, Juhi Chaudhary, Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman
Abstract
Challenge the Champ is a simple tournament format, where an ordering of the players -- called a seeding -- is decided. The first player in this order is the initial champ, and faces the next player. The outcome of each match decides the current champion, who faces the next player in the order. Each player also has a popularity, and the value of each match is the popularity of the winner. Value maximization in tournaments has been previously studied when each match has a deterministic outcome. However, match outcomes are often probabilistic, rather than deterministic. We study robust value maximization in Challenge the Champ tournaments, when the winner of a match may be probabilistic. That is, we seek to maximize the total value that is obtained, irrespective of the outcome of probabilistic matches. We show that even in simple binary settings, for non-adaptive algorithms, the optimal robust value -- which we term the \textsc{VnaR}, or the value not at risk -- is hard to approximate. However, if we allow adaptive algorithms that determine the order of challengers based on the outcomes of previous matches, or restrict the matches with probabilistic outcomes, we can obtain good approximations to the optimal \textsc{VnaR}.