Maximizing Value in Challenge the Champ Tournaments (aamas25-00041)

Given a finite type set \(T\), a total strength order, rational masses \(\mu_t\ge0\) summing to \(1\), popularity \(p:T\to\mathbb{Q}_{\ge0}\), and threshold \(B\), choose an initial champion \(h\in T\) and a finite ordered mass word \(\mathcal{S}=((\theta_1,a_1),\ldots,(\theta_\ell,a_\ell))\) with \(a_j\ge0\) and \(\sum_{j:\theta_j=t}a_j=\mu_t\). If \(q_0=h\) and \(q_j=W(q_{j-1},\theta_j)\) is the winner type after the first challenger in block \(j\), decide whether \(\sum_{j=1}^{\ell}a_jp(q_j)\ge B\), under the vanishing normalized contribution of the first promotion match.

A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). The support size \(\tau\) counts listed types, not possible types.
The input also contains a strict total strength order on \(T\), popularities \(p:T\to\mathbb{Q}_{\ge0}\), and a threshold \(B\in\mathbb{Q}\), all rationals encoded in binary. Define \(W(s,t)\) as the stronger type when \(s\ne t\), and \(W(t,t)=t\); equal popularities are allowed.
Choose an initial champion \(h\in T\) and a finite ordered mass word \(\mathcal S=((\theta_1,a_1),\ldots,(\theta_\ell,a_\ell))\), where \(\theta_j\in T\), \(a_j\in\mathbb{R}_{\ge0}\), and \(\sum_{j:\theta_j=t}a_j=\mu_t\) for every \(t\in T\). Types may recur, and there is no prescribed bound on \(\ell\).
Set \(q_0=h\) and \(q_j=W(q_{j-1},\theta_j)\), including for zero-mass blocks. The initial champion consumes no mass, and each block contributes exactly \(a_jp(q_j)\), with no separate contribution for its first promotion match.
The decision problem asks whether some such choice satisfies \(\sum_{j=1}^{\ell}a_jp(q_j)\ge B\). Let \(L\) be the total input bit length; state running times in \(\tau\) and \(L\) (here the number of strength types is \(m=\tau\)).

Is this continuous Challenge the Champ value decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finitely many individual players with a strict strength order and nonnegative integer popularities, maximizing the sum of match winners’ popularities is polynomial-time solvable. [Bhaskar, Chaudhary and Dey](https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p307.pdf).
No result settling this exact continuous mass-word problem was identified in the literature search.

Result

The problem is polynomial-time solvable. In fact, an optimal schedule uses exactly \(\tau\) positive-mass blocks, with each type appearing once.

Index the supported types from weakest to strongest as \(t_1,\ldots,t_\tau\), and write \(\mu_i=\mu_{t_i}\) and \(p_i=p(t_i)\). Define the suffix maximum \(M_i=\max_{i\le k\le\tau}p_k\).

We will prove the exact formula
\[ V^*=\sum_{i=1}^{\tau}\mu_iM_i. \]
The decision problem therefore answers yes exactly when \(V^*\ge B\).

1. Upper bound for every admissible mass word

Consider any initial champion and any admissible finite mass word, including words with repeated types or zero-mass blocks.

If block \(j\) has type \(\theta_j=t_i\), then its resulting champion \(q_j=W(q_{j-1},t_i)\) is at least as strong as \(t_i\). Consequently, \(q_j=t_k\) for some \(k\ge i\), and \(p(q_j)\le M_i\).

Because \(a_j\ge0\), the block contributes at most \(a_jM_i\). Summing and using the prescribed total mass of each type gives
\[ \sum_{j=1}^{\ell}a_jp(q_j) \le \sum_{i=1}^{\tau}M_i\sum_{j:\theta_j=t_i}a_j = \sum_{i=1}^{\tau}\mu_iM_i. \]

This bound applies regardless of the initial champion, word length, mass splitting, or zero-mass promotions.

2. A schedule attaining the bound

We partition the strength order into consecutive intervals.

Set \(c_0=0\). Whenever \(c_{r-1}<\tau\), choose \(c_r\) to be the largest index maximizing popularity among indices strictly larger than \(c_{r-1}\). Thus,
\[ c_r=\max\left\{k:c_{r-1}<k\le\tau,\quad p_k=\max_{c_{r-1}<s\le\tau}p_s\right\}. \]

The indices strictly increase, so the construction terminates at some \(c_R=\tau\). Define \(I_r=\{c_{r-1}+1,\ldots,c_r\}\). These intervals partition all supported types.

For every \(i\in I_r\), we have \(M_i=p_{c_r}\). Indeed:

• Every index \(k\ge i\) also satisfies \(k>c_{r-1}\), so maximality of \(c_r\) gives \(p_k\le p_{c_r}\).
• Since \(i\le c_r\), the suffix defining \(M_i\) contains \(c_r\).

Together these imply the claimed equality.

Choose the initial champion \(h=t_{c_1}\). For each interval \(I_r\), append the following blocks:

• The block \((t_{c_r},\mu_{c_r})\).
• One block \((t_i,\mu_i)\) for each \(i\in I_r\setminus\{c_r\}\), in any order.

We verify the champion and payoff at each stage.

For the first stage, the first block leaves the champion equal to \(t_{c_1}\), because \(W(t_{c_1},t_{c_1})=t_{c_1}\). Its mass is included in the word and earns \(\mu_{c_1}p_{c_1}\); the initial choice itself contributes nothing.

For every later stage, the previous champion is \(t_{c_{r-1}}\). Since \(c_r>c_{r-1}\), the first block promotes \(t_{c_r}\) and contributes exactly \(\mu_{c_r}p_{c_r}\), as stipulated by the objective.

Every remaining type in \(I_r\) is weaker than \(t_{c_r}\), so the champion remains \(t_{c_r}\) throughout that stage. Hence type \(t_i\), for every \(i\in I_r\), contributes exactly \(\mu_ip_{c_r}=\mu_iM_i\).

Each type appears exactly once with its entire prescribed mass. The word is therefore admissible, has exactly \(\tau\) positive-mass blocks, and attains
\[ \sum_{i=1}^{\tau}\mu_iM_i. \]

Combined with the upper bound, this proves the formula for \(V^*\). Equal popularities require no perturbation: the stated tie rule handles them directly.

3. Algorithm and binary running time

Once types are in strength order, compute the suffix maxima by scanning backwards:
\[ M_\tau=p_\tau,\qquad M_i=\max\{p_i,M_{i+1}\}. \]

Then compute \(V^*=\sum_i\mu_iM_i\) exactly and compare it with \(B\). This requires \(O(\tau)\) rational arithmetic operations. Retaining the largest maximizing index at each suffix also constructs the optimal word in \(O(\tau)\) additional operations.

For an explicit bit bound, write the input rationals as \(\mu_i=u_i/v_i\), \(p_i=x_i/y_i\), and \(B=b/d\), with positive denominators. Let
\[ D=d\prod_{i=1}^{\tau}v_i\prod_{i=1}^{\tau}y_i. \]
Its binary length is \(O(L)\), because the lengths of all these input denominators sum to at most \(L\).

If \(M_i=p_{k_i}\), then \(v_i y_{k_i}\) divides \(D\). Consequently,
\[ DV^*=\sum_{i=1}^{\tau}u_i x_{k_i}\frac{D}{v_i y_{k_i}}, \qquad DB=b\frac{D}{d} \]
are integers that can be computed exactly. All intermediate integers have \(O(L)\) bits: individual products have this size, and nonnegativity together with \(\sum_i\mu_i=1\) gives \(0\le V^*\le\max_i p_i\).

Using schoolbook integer arithmetic, the computation takes \(O(\tau L^2)\) bit operations after obtaining the strength order. Even if sorting is needed, the additional \(O(\tau\log\tau)\) strength comparisons preserve polynomial time. Since \(m=\tau\), the arithmetic bound is also \(O(mL^2)\).

The construction follows the same greedy record structure as the discrete algorithm in Theorem 2 of [Bhaskar, Chaudhary and Dey](https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p307.pdf). The argument above proves optimality directly for the specified continuous objective.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned continuous problem correctly. The upper bound applies to every admissible finite mass word, and the construction attains it using exactly \(\tau\) positive-mass blocks. The claimed polynomial bit complexity is justified. I found no major or minor issues.

• Definitions and scope.

Indexing the listed types from weakest to strongest is legitimate because the input supplies a strict total strength order. The suffix maximum \(M_i=\max_{i\le k\le\tau}p_k\) exists for every \(i\), since its indexing set is finite and nonempty.

The proof uses precisely the specified objective: the initial champion consumes no mass, a block receives the popularity of its resulting champion, and a promotion contributes no additional reward.

• Upper bound for arbitrary words.

For a block of type \(t_i\), the definition of \(W\) ensures that its resulting champion has index \(k\ge i\). This holds whether the incumbent is weaker, stronger, or equal to \(t_i\). Consequently, \(p(q_j)\le M_i\).

Multiplication by \(a_j\ge0\) preserves this inequality. Summing and grouping blocks by their listed type is valid because the word is finite. The mass constraints then give the claimed bound
\(\sum_j a_jp(q_j)\le\sum_i\mu_iM_i\).

This reasoning covers arbitrary initial champions, repeated types, real block masses, and zero-mass promotions. In particular, zero-mass blocks can change the champion, but they do not invalidate the bound on any subsequent block.

• Interval construction and termination.

Whenever \(c_{r-1}<\tau\), the set of candidate indices is nonempty, so the largest maximizing index \(c_r\) exists. By definition, \(c_{r-1}<c_r\le\tau\).

Thus the process terminates at \(\tau\): it cannot continue indefinitely, and its stopping condition cannot hold at an index below \(\tau\). The intervals \(I_r=\{c_{r-1}+1,\ldots,c_r\}\) are disjoint and cover every listed type.

For \(i\in I_r\), every index in the suffix beginning at \(i\) belongs to the set over which \(c_r\) maximizes popularity. Hence \(M_i\le p_{c_r}\). Conversely, \(c_r\ge i\), so \(c_r\) belongs to that suffix and \(M_i\ge p_{c_r}\). The stated equality \(M_i=p_{c_r}\) follows. Equal popularities cause no difficulty.

• Admissibility and attainment.

The initial choice \(h=t_{c_1}\) is allowed. Its own mass remains available for the first block, as required by the task. That block leaves the champion unchanged and earns exactly \(\mu_{c_1}p_{c_1}\).

Within the first interval, every other scheduled type is weaker than \(t_{c_1}\), so the champion remains \(t_{c_1}\). At each later interval, its first block promotes \(t_{c_r}\), since \(c_r>c_{r-1}\). Every remaining block in that interval preserves this champion.

Therefore each type \(t_i\) earns exactly \(\mu_ip_{c_r}=\mu_iM_i\). Each listed type occurs once with its prescribed positive mass, establishing admissibility and exactly \(\tau\) positive-mass blocks.

The construction attains the universal upper bound. Thus the formula describes an attained maximum, rather than merely a supremum, and comparison with \(B\) exactly decides feasibility.

• Algorithm and bit complexity.

The backward recurrence correctly computes all suffix maxima using a linear number of rational comparisons. Retaining the largest maximizing index also supplies the interval endpoints; enumerating their disjoint intervals requires only linear additional work.

The common denominator
\(D=d\prod_i v_i\prod_i y_i\)
has \(O(L)\) bits. For every selected suffix maximizer \(k_i\), the product \(v_i y_{k_i}\) divides \(D\), including when the same popularity is selected for several types. The integer expressions for \(DV^*\) and \(DB\) are therefore exact.

Numerators and denominators have input bit lengths bounded by \(L\). Moreover, nonnegativity and mass normalization give \(0\le V^*\le\max_i p_i\), which bounds the accumulating integer sum by \(D\max_i p_i\). The claimed \(O(L)\) intermediate bit lengths are consequently valid. A negative threshold merely makes \(DB\) a signed integer of the same asymptotic bit length.

Schoolbook multiplication, division, and rational comparison on these integers justify \(O(\tau L^2)\) bit operations after obtaining the strength order. The separately stated sorting overhead preserves polynomial time. Substituting \(m=\tau\) is correct.

• Boundary cases and citation.

For \(\tau=1\), the construction consists of the sole type’s block and attains its popularity, since its mass is \(1\). All-zero popularities and tied popularities are covered directly. Arbitrary rational thresholds, including equality with the optimum, are handled by exact comparison.

The structural comparison with the discrete algorithm is accurate: its proof likewise repeatedly selects a most popular player among those stronger than the preceding selected player. The continuous proof is self-contained and does not apply the discrete theorem to a different objective. [Bhaskar, Chaudhary and Dey, Theorem 2](https://www.ifaamas.org/Proceedings/aamas2025/pdfs/p307.pdf).

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩