Maximizing Value in Challenge the Champ Tournaments

Umang Bhaskar, Juhi Chaudhary, Palash Dey ∗ · 2025

Read Maximizing Value in Challenge the Champ Tournaments by Umang Bhaskar, Juhi Chaudhary, Palash Dey ∗ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12569.txt.

Introduction

Bhaskar, Chaudhary, and Dey study value maximization in Challenge the Champ tournaments, in a paper from twenty twenty-five. In this format, players challenge the reigning champion in a fixed order. Winners replace the champion and face the next challenger. Organizers choose the order to maximize match value, like viewership.

Match outcomes are modeled by a directed strength graph. Value representations for matches vary across the analysis. The computational complexity of optimal ordering is fully characterized. Earlier work covered knockout tournaments with acyclic strength graphs. General graphs and this format now get complete answers.

Catalog record

CREATORUmang Bhaskar, Juhi Chaudhary, Palash Dey ∗
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12569

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Maximizing Value in Challenge the Champ Tournaments Umang Bhaskar, Juhi Chaudhary, Palash Dey ∗ Abstract A tournament is a method to decide the winner in a competition, and describes the overall sequence in which matches between the players are held. While deciding a worthy winner is the primary goal of a tournament, a close second is to maximize the value generated for the matches played, with value for a match measured either in terms of tickets sold, television viewership, advertising revenue, or other means. Tournament organizers often seed the players — i.e., decide which matches are played — to increase this value. We study the value maximization objective in a particular tournament format called Challenge the Champ . This is a simple tournament format where an ordering of the players is decided. The first player in this order is the initial champion. The remaining players in order challenge the current champion; if a challenger wins, she replaces the current champion. We model the outcome of a match between two players using a complete directed graph, called a strength graph , with each player represented as a vertex, and the direction of an edge indicating the winner in a match. The value-maximization objective has been recently explored for knockout tournaments when the strength graph is a directed acyclic graph (DAG). We extend the investigation to Challenge the Champ tournaments and general strength graphs. We study different representations of the value of each match, and completely characterize the computational complexity of the problem. Keywords: Tournaments, Challenge the Champ, Algorithms, NP-hardness, Value Maximization 1 Introduction Tournaments 1 1 1 In this paper, a tournament will denote a competition format, and not a complete directed graph. are a fundamental mechanism for determining winners in diverse competitive settings by systematically comparing participants through a series of pairwise matches. The most illustrative example of tournaments is sports competitions, ranging from prestigious international events like the Olympics and World Cups to local school sports and college contests. Different tournament formats, such as knockout tournament [ 20 , 23 ] , round-robin tournament [ 16 , 19 ] , double-elimination tournament [ 2 , 18 ] , Swiss-Sytem [ 17 , 21 ] are commonly employed and have been widely studied by researchers over the years, where each format offers a distinct approach with its own advantages and disadvantages for ranking and elimination. Challenge the Champ — also known as stepladder — is one such tournament format, which, despite its simplicity, is relatively underexplored in the literature compared to other tournament variants. Given n players, a Challenge the Champ tournament proceeds in n-1 rounds. A player is initially chosen as the champ, and in each successive round, a new player challenges the current champ. If a player defeats the current champ, she becomes the new champ. The champ at the end of the final round is the tournament winner. See Fig. 1 for an illustration. Challenge the champ is a single-elimination tournament , where a player is eliminated once she loses a match. Thus, in a single-elimination tournament with n players, there are exactly n-1 matches, though there are of course many ways to decide the player in each match 2 2 2 A knockout tournament, which takes the form of a binary tree, is also sometimes referred to as a single-elimination tournament. However, we use the more general definition of single-elimination tournaments in this paper . Note that the order in which the players challenge the current champ — called the seeding — significantly influences the outcome of the tournament. E.g., a fixed player i has a better likelihood of winning the tournament if she challenges the champ late in the tournament after the stronger players have been eliminated, rather than very early. Owing to their simplicity and often dramatic nature — allowing a new entrant to beat the current champion and take over the title — Challenge the Champ tournaments and its variants are used in multiple sports, including ten-pin bowling, squash, badminton, and basketball [ 22 , 1 ] . Beyond the world of sports, a continuous variant of stepladder tournaments is also used for ranking workers in organisations [ 12 ] , making it a compelling tournament format for theoretical studies. In fact, some of our results obtained from studying Challenge the Champ tournaments are applicable to all single-elimination tournaments, further reinforcing their importance. Figure 1: A Challenge the Champ tournament, with players seeded (e_{1},e_{2},\ldots,e_{n}) . In each round i , player e_{i+1} challenges the current champ — the winner of the previous round. Table 1: Our results for value maximization in Challenge the Champ tournaments. Problem Pair-Based Win-Count-Based Player-Popularity-Based CTC-VM-Dag \mathsf{NP} -complete for binary values ( Theorem 11 ) P ( Theorem 7 ) P ( Theorem 2 ) CTC-VM \mathsf{NP} -complete (Follows from Theorem 11 ) \mathsf{NP} -complete for binary values ( Theorem 8 ) and linear-after-threshold ( Theorem 10 ) P for binary values ( Theorem 3 ) \mathsf{NP} -complete for ternary values ( Theorem 5 ) Challenge the Champ tournaments have previously attracted some attention from researchers, though this has been focused on the complexity of manipulation to ensure a given player wins the tournament [ 11 , 4 ] . We are, however, interested in the objective of value maximization in sports tournaments. Arguably, many competitions are organized to maximize some measure of value — whether advertising revenue, viewership, or attendance. Given a tournament format — such as knockout, or Swiss-system — often this value-maximization objective influences the matches that are played as well, e.g., through the choice of groups, or seeding of the players. This objective is measured by assigning a non-negative integer value to each potential match between the players. Such an approach reflects the practical scenario where matches hold varying levels of importance, influenced by factors like geopolitics, historical rivalries, intrinsic fan following, or the relative strength of the teams. Prioritizing high-value matches becomes essential, especially when only a subset of potential matches can be played, as it helps attract viewers and advertisers. The tournament value is then defined as the total sum of the values of all matches that are actually played. This metric is crucial for evaluating and optimizing the overall appeal and financial success of the tournament. We study the problem of value maximization in Challenge the Champ tournaments. Given the expanding body of research on tournaments, we believe that studying value maximization in the simple but interesting Challenge the Champ tournament format is an important research problem. To complete the picture, we need a way of determining the outcome when two players compete. For this, we use a strength graph , which is a complete directed graph with a vertex for each player. A directed edge (i,j) indicates that player i beats player j in a match. Although value maximization has been previously examined in knockout tournaments [ 8 , 5 ] , the investigation is restricted to the case where the strength graph is a directed acyclic graph (DAG). Our study extends this inquiry to Challenge the Champ tournaments. We investigate scenarios where the strength graph is either a DAG or a complete directed graph, and provide a thorough analysis of

Read the complete text