| paper | How to Make Knockout Tournaments More Popular? |
| authors | — |
| venue | AAAI 2024 |
| filed under | voting · tournaments |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given ordered finite strength tiers \(T\), rational masses \(\mu_t\) summing to one, bracket height \(h\), two popularity values \(q_t\) in \(\{a,b\}\), and target \(B\), let \(N=2^h\) and use normalized mass-flow variables \(y_{t,r}\) and \(a_{i,r}\) for type mass assigned to \(r\)-round subtournaments and open-subtournament counts divided by \(N\). Require \(a_{0,h}=1/N\), \(a_{0,r}=0\) for \(r<h\), \(\sum_r y_{t,r}=\mu_t\), \(a_{i,r}=a_{i-1,r}-y_{i,r}+\sum_{s>r}y_{i,s}\), \(0\le y_{i,r}\le a_{i-1,r}\), and \(a_{\tau,r}=0\). Decide whether there is a feasible trajectory with \(\sum_{t,r} r q_t y_{t,r}\) at least \(B\).
A high-multiplicity knockout bracket with ordered strength tiers as types, population masses replacing player counts, open-subtournament mass-flow variables, and total popularity-per-win as the objective.
The fractional mass-flow LP is not shown to represent one height-h bracket: scaling a rational solution may produce an ensemble or a larger bracket, changing the available rounds and round-dependent values.
fatal: False
Covers the win-count-oriented and two-popularity branches, especially Theorems 8 and 10; it leaves Theorems 5-7, 12, 15 and arbitrary pair- or round-dependent value functions alone.
The strongest positive case is the paper’s win-count-oriented branch, especially Theorem 8, with Theorem 10 as a narrower and more operationally plausible special case.
A credible regime is a very large knockout competition whose players come from a small number of recurring classes. A type is not merely “popular” or “strong”: it is the complete tuple consisting of its strength rank, its win-value profile, and its predicted outcome against every other type. Thus two players of type \(t\) are interchangeable in the paper’s model. The population is a distribution \(\mu\) over \(\tau\) such types, with \(N=2^h\) total player-mass and \(N\mu_t\) players of type \(t\). The intended regime is \(N\gg\tau\): for example, a federation or esports organiser has millions of entrants but only a few dozen strength/marketability classes and only class-level forecasts.
My lead mirror is Continuous Win-Count Tournament Maximization.
Its input is:
The induced match-value function is exactly the paper’s win-count-oriented form:
\[
v(t,t',r)=p(\max(t,t'),r),
\]
where the stronger type wins.
A continuous solution is a mass assignment \(y_{t,r}\ge0\). Here \(y_{t,r}\) is the amount of type-\(t\) player mass assigned as the winner of an open subtournament with \(r\) rounds. To certify that this assignment comes from a bracket, introduce \(a_{i,r}\), the amount of \(r\)-round subtournaments still open after processing the first \(i\) strength types. The constraints are
\[ a_{0,h}=1,\qquad a_{0,r}=0\ (r<h), \]
\[ \sum_{r=0}^{h}y_{i,r}=N\mu_i, \]
\[ a_{i,r} = a_{i-1,r}-y_{i,r} +\sum_{q=r+1}^{h}y_{i,q}, \]
\[ 0\le y_{i,r}\le a_{i-1,r}, \qquad a_{\tau,r}=0. \]
The objective is
\[
\max \sum_{t,r}p(t,r)y_{t,r},
\]
or its normalization by \(N\). The decision question is whether this value is at least \(B\). A solution is the feasible mass trajectory \((y,a)\); when all masses are integral it reconstructs an ordinary seeding, and rational solutions can be implemented exactly after scaling to sufficiently many identical bracket copies.
This is not an arbitrary fluid reformulation. The variables \(a_{i,r}\) are precisely the paper’s “subtournament profiles” from the proof of Lemma 9 and Theorem 8, with integer counts replaced by mass. The paper’s named anchor is Theorem 8, which states that TOURNAMENT VALUE MAXIMIZATION with a win-count-oriented game-value function is solvable in \(n^{O(\log n)}\) time. It is proved by the authors; the supplied version contains the proof. The supporting structural characterization is Proposition 3, also proved by the authors.
The continuous version should be Class A. Its state equations and objective are linear, with \(O(\tau h)\) variables and constraints, so it is a rational LP solvable in time polynomial in \(\tau,h\), and the encoding length. Continuization removes the integer profile counts that make the paper’s dynamic program quasipolynomial. This is exactly the kind of gain the ChoCo programme is looking for: the bracket structure remains, but the high-multiplicity population turns the profile evolution into continuous optimization.
A second, narrower mirror is Two-Popularity-Type Tournament Maximization. Restrict each type to a popularity value \(q_t\in\{a,b\}\), with \(a>b\), and set
\[ p(t,r)=r q_t. \]
Then every match contributes the popularity of its winner, independently of the round. The instance is again \((T,\mu,h,q,B)\), and the question is whether a feasible mass trajectory satisfies
\[ \sum_{t,r} r q_t y_{t,r}\ge B. \]
This is a direct high-multiplicity version of the paper’s player-popularity-based setting. Its named anchor is Theorem 10, which states that the discrete problem is solvable in linear time when there are only two popularity values. The theorem is the authors’ result, with the proof deferred to their full version.
The expected continuous algorithm is the mass analogue of their greedy algorithm: process strength types from strongest to weakest; assign popular mass to the largest currently open subtournaments and unpopular mass to the smallest, splitting only at a boundary when necessary. The state has only \(h+1\) subtree sizes, so the compressed continuous problem should be solvable in polynomial time in \(\tau,h\), with an especially simple greedy implementation. This is a convincing scenario because “many entrants share one of two marketability classes” is not an artificial change to the paper’s question; it is exactly the paper’s own popularity-based restriction combined with high multiplicity.
The mirror deliberately does not claim to cover Theorems 5 and 6. Their NP-hardness reductions use highly individualized pair values, and those values may force \(\tau\) to grow with the reduction. Nor does it claim that arbitrary round-dependent or pair-specific value functions become tractable. The positive scope is the win-count-oriented and two-popularity branches.
The weakest point is that the continuous solution permits player mass to be split across open subtrees, whereas the paper studies one deterministic bracket with one player per leaf. If a referee insists on that literal one-bracket interpretation, this is a relaxation rather than an exact replacement. The defence is that it is the standard high-multiplicity relaxation: integral mass trajectories are exactly the paper’s seedings, and every rational trajectory can be realised after scaling by many interchangeable copies. The natural follow-up questions are therefore whether the LP has a bounded integrality gap for one bracket, whether its solutions can be rounded with a controlled additive loss, and where the continuous win-count model ceases to remain tractable when type profiles or pairwise values become genuinely heterogeneous.
The strongest objection is to the proposed regime, not to the paper’s computational content. Theorem 8 is a genuine named complexity result, so the “no result to mirror” objection is unavailable. But the proponent’s actual type construction does not produce high multiplicity in the paper’s model.
The paper assumes a strict strength ordering: player \(i\) beats player \(j\) precisely when \(i>j\). Strength rank is therefore part of the player’s complete computational type, and every player has a distinct rank. If the proposed type includes “strength rank,” then \(\tau=n\), not \(\tau\ll n\). The claimed federation with millions of players but only a few dozen types is incompatible with the paper’s input model. If rank is omitted, the winner of a match is no longer determined. If players are grouped into strength tiers, one has introduced ties and must specify same-tier outcomes and tie-breaking; that is a natural new model, but it is not the strict-order problem proved in Theorem 8.
There is also a more serious gap in the claimed LP interpretation. Its fractional variables describe a mixture of partial brackets: a fraction of a type can be assigned as the winner of a root-sized subtournament and another fraction as the winner of a smaller one. Scaling a rational solution produces several copies of the original height-\(h\) tournament, not one tournament with the same structure. Combining those copies into one bracket changes the height to \(h+\log K\), and hence changes the available rounds and the values \(p(t,r)\). Thus the LP is evidently a sensible fractional or ensemble relaxation, but the proponent has not shown that it is the high-multiplicity version of one knockout tournament. Exactness, or even a controlled rounding guarantee for arbitrary encoded values, remains an additional theorem rather than a consequence of the formulation.
The same criticism applies to Theorem 10. Under the paper’s strict ordering, two players with the same popularity value are still different types because their strength ranks differ. A genuine high-multiplicity version again requires replacing the strict order by finitely many strength tiers and declaring that all players in a tier are interchangeable. That may be a plausible application, but it is a new tiered tournament model, not simply the continuous mirror of the stated theorem.
That is the best negative case, but it does not sustain the universal conclusion. Once strength tiers are explicitly admitted, the objection about identity disappears: for the win-count and popularity objectives, same-tier players really are interchangeable, and the mass-flow formulation becomes a coherent computational problem. The two-popularity case is especially difficult to dismiss: its objective \(p(t,r)=rq_t\) is naturally additive, its population interpretation is plausible, and its continuous formulation appears to be exactly the sort of LP/greedy problem ChoCo wants.
So one can reject the proponent’s claim that their LP is already an exact mirror of the paper’s one-bracket problem. One cannot honestly reject every worthwhile continuous mirror. Theorem 10, and probably the tiered version of Theorem 8, survive once the re-modeling and the relationship between fractional brackets and a single large tournament are stated precisely.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.