Maximizing Value in Challenge the Champ Tournaments

The strongest honest case is a population-level stepladder: many entrants are interchangeable within a finite set of strength-and-value types, and the organizer schedules masses of entrants rather than named individuals. I would anchor the case primarily on Theorem 2, with Theorem 11 as a more ambitious second anchor.

The natural regime is a large promotion ladder or sports league. There may be \(N\) entrants but only \(\tau\) meaningful types, with \(N\gg\tau\): for example, combinations of strength tier, popularity tier, and rivalry profile. A type contains every feature relevant to the tournament. Two entrants of one type have the same outcomes against every other type and the same value parameters. Thus this is genuine high multiplicity, not an assumption that arbitrary named players are interchangeable.

Let \(T\) be the finite type set, with masses \(\mu_\theta\in\mathbb{Q}_{\ge 0}\) satisfying \(\sum_{\theta\in T}\mu_\theta=1\). A continuum seeding is an initial champion type \(h\), followed by a finite mass word
\[ \mathcal{S}=((\theta_1,a_1),\ldots,(\theta_\ell,a_\ell)), \]
where \(a_j\ge 0\) and
\[ \sum_{j:\theta_j=\theta}a_j=\mu_\theta \]
for every \(\theta\). Repeated occurrences of a type allow arbitrary interleaving, just as in an ordinary seeding. If \(q_0=h\) is the current champion and \(W(q,\theta)\) is the winner type when \(\theta\) challenges \(q\), define
\[ q_j=W(q_{j-1},\theta_j). \]
A block of mass \(a_j\) then consists of \(a_j\) challengers of type \(\theta_j\). The one match that may change the champion has vanishing normalized mass; this is exactly the \(N\to\infty\) limit. A rational mass word lifts to a finite tournament by rounding its block masses, with only \(O(\tau^2/N)\) normalized error in the DAG cases below.

My lead problem is:

\[ \textsc{Pop-CTC-VM}_{\infty}^{\mathrm{Dag}}. \]

The input is a finite type set \(T\), a total strength order \(\succ\) on \(T\), a rational population distribution \(\mu\), a popularity \(p(\theta)\in\mathbb{Q}_{\ge0}\) for each type, and a target \(B\). The question is whether there is an initial champion and a feasible mass word with
\[ \Phi_{\mathrm{pop}}(\mathcal{S}) =\sum_{j=1}^{\ell} a_j\,p(q_j)\ge B. \]
The output is the initial champion and the mass word itself.

This is the continuous high-multiplicity form of the player-popularity-based CTC-VM-Dag problem. It mirrors Theorem 2, which is proved in this paper, not cited from elsewhere: “There is a polynomial-time algorithm for CTC-VM-Dag for player-popularity-based tournament value functions.”

I would expect \(\textsc{Pop-CTC-VM}_{\infty}^{\mathrm{Dag}}\) to be Class A. In a DAG, the champion type can only move upward in the strength order. Hence a schedule has only \(\tau\) possible record changes. Once the current champion is fixed, masses of weaker types can be coalesced or split according to their popularity without affecting the state. The exchange argument in Theorem 2 is already a statement about cumulative capacities; replacing integer numbers of weaker players by masses \(\mu_\theta\) is mathematically natural. A dynamic program or a small linear optimization model over record types should therefore give an exact algorithm polynomial in \(\tau\) and the encoding length.

The authors should recognize this as their problem. The paper itself motivates value by tickets, viewership, advertising, and fan popularity, and explicitly notes continuous stepladder tournaments for ranking workers. The continuous model does not replace their winner rule or their value objective; it replaces repeated interchangeable entrants by mass. It also preserves their stronger observation that Challenge the Champ is optimal among all single-elimination formats in the DAG popularity setting.

This anchor generates several useful questions: does the continuous algorithm extend to the binary general-strength result of Theorem 3; can the discrete optimum be recovered within an additive \(O(\tau/N)\) error; and can one characterize when a continuum seeding is representable by only \(O(\tau)\) macroscopic blocks?

A second, more ambitious mirror uses the paper’s pair-based result.

\[ \textsc{Pair-CTC-VM}_{\infty}^{\mathrm{Dag}}. \]

The input is again \(T,\mu\), and a total strength order, but now includes a binary type-pair value
\[ \rho:T\times T\to\{0,1\}. \]
The type includes its complete row of pair values, so the model retains arbitrary rivalry or audience effects between types. Let \(\rho(\theta,\theta)\) denote the value of a match between two members of the same type; if such matches are neutral in the application, it is simply set to \(0\).

For a mass word, if \(\theta_j\) is weaker than or equal to the current champion \(q_{j-1}\), the champion remains \(q_{j-1}\) throughout the block and the block contributes
\[ a_j\rho(q_{j-1},\theta_j). \]
If \(\theta_j\succ q_{j-1}\), the first challenger promotes the new champion, and the remaining mass meets a champion of type \(\theta_j\), contributing
\[ a_j\rho(\theta_j,\theta_j) \]
in the normalized limit. Thus
\[ \Phi_{\mathrm{pair}}(\mathcal{S}) = \sum_{\theta_j\not\succ q_{j-1}} a_j\rho(q_{j-1},\theta_j) + \sum_{\theta_j\succ q_{j-1}} a_j\rho(\theta_j,\theta_j). \]
The decision question is whether \(\Phi_{\mathrm{pair}}(\mathcal{S})\ge B\).

This mirrors Theorem 11, which states that CTC-VM-Dag is NP-complete for binary pair-based tournament value functions. In the supplied conference text the proof is omitted and referred to the authors’ full version [3]; it is therefore an author-proved result, not prior work being cited as a black box.

Here I would expect a dichotomy. In the intended regime of a moderate type alphabet, the mass problem looks like Class A: the current champion moves monotonically, and divisible type masses can be allocated among the intervals between record changes. A continuous LP or dynamic program should be able to optimize those allocations. But if \(\tau\) is unrestricted and the pair matrix itself is allowed to encode a 3-D-Matching instance, hardness may survive through the type interaction structure. That would be Class B hardness, driven by the number and arrangement of types rather than by population multiplicity. Determining whether the fractional mass relaxation destroys the reduction is precisely a worthwhile continuization question.

The weakest point is the atomless limit of a single-champion tournament. One individual can dethrone the champion, but that promotion match has zero mass as \(N\) grows. Consequently, the continuous pair objective may lose some of the discrete combinatorics that Theorem 11 exploits, especially if the original application cares about named rivalries rather than type-level rivalries. Also, if every player has an idiosyncratic strength and pair-value row, then \(\tau\) is essentially \(N\), and there is no meaningful high-multiplicity regime.

For that reason I would not claim that this paper as a whole has a continuous mirror. The win-count results, especially Theorems 7 and 8, need an additional modelling decision because an individual’s win count does not aggregate automatically into population mass. But Theorem 2 supplies a clean, defensible mirror, and Theorem 11 supplies a serious boundary question. Together they show that Challenge the Champ value maximization is not merely a story about named players: at least its additive popularity and pair-value formulations admit a credible continuous-population interpretation.