| paper | An Exercise in Tournament Design: When Some Matches Must Be Scheduled |
| authors | — |
| venue | AAAI 2024 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Mass-Demand-\(TF_R\): Given a finite type tournament with deterministic winner map, rational type masses, \(R\) rounds, demanded type arcs \(S\), and rational quotas \(\rho\), decide whether nonnegative round-by-type match masses satisfy survivor conservation, deterministic winner transitions, and total mass at least \(\rho\) for every demanded arc.
An atomless high-multiplicity single-elimination tournament with interchangeable type mass μ; round-pairing masses are decision variables, and feasibility or revenue is measured by type-pair demand quotas.
Different submasses of one type may satisfy different demanded pair quotas, so the formulation does not preserve the paper's single-player shared-arborescence obligation.
fatal: False
Covers the central demanded-match and revenue objective, including a bounded-feedback type restriction; it does not preserve the named-player SBA structure or directly mirror Theorems 2 and 3.
The strongest positive case is a population-level version of the paper’s own revenue-maximization interpretation of Demand-TF. I would make this a Class-A mirror: the indivisible bracket is replaced by a mass-valued bracket, while pairwise outcomes remain deterministic.
My lead anchor is Theorem 1, proved in this paper: “DEMAND-TF is NP–complete.” The second, more structured anchor is Theorem 4, also proved here: “An instance of DEMAND-TF, \((T,S)\), can be solved in time \(n^{O(k)}\) where \(k\) is the feedback arc set number of \(T\).”
Consider a large tournament circuit with millions of entrants but only a moderate number of operationally relevant player types: for example, performance bands crossed with region, club, audience profile, or qualification route. A type \(t\) completely specifies everything the tournament uses: its deterministic result against every other type, and whether a match against another type is commercially demanded. Let \(P\) be the finite type set, \(|P|=\tau\), and let \(\mu_t\) be the fraction of entrants of type \(t\). Thus \(N\gg\tau\), and agents of the same type are genuinely interchangeable.
The tournament organizer does not choose a permutation of named players. The organizer chooses a mass-valued bracket. Fix \(R\) rounds. Let \(a_t^r\) be the mass of surviving type-\(t\) winner tokens after round \(r\), with \(a_t^0=\mu_t\). Let \(x_{tu}^r\) be the mass of matches between types \(t\) and \(u\) in round \(r\), where \(t\le u\) and \(x_{tt}^r\) denotes same-type matches. If \(w(t,u)\) is the deterministic winner, then the mass bracket must satisfy
\[ 2x_{tt}^r+\sum_{u\neq t}x_{\{t,u\}}^r=a_t^r \]
for every type \(t\), and
\[ a_v^{r+1}=\sum_{\{t,u\}:w(t,u)=v}x_{\{t,u\}}^r. \]
These are simply the conservation and winner-transition equations for a continuum of parallel sub-brackets. The variables are not lottery probabilities: they describe measurable portions of an atomless population being paired. Any feasible mass flow can be realized by partitioning each current type mass into the prescribed pieces and pairing those pieces measure-preservingly.
For each demanded arc \((t,u)\in S\), give the organizer a rational quota \(\rho_{tu}\). The direct normalized analogue of requiring one occurrence in an \(N=2^R\)-player tournament is \(\rho_{tu}=1/N=2^{-R}\); a more meaningful population-scale version lets \(\rho_{tu}\) be, say, one percent of the relevant tournament population. The continuous problem is:
Mass-Demand-TF\(_R\). Given \((P,w,\mu,R,S,\rho)\), find a mass bracket \(x\) satisfying the conservation and winner-transition equations and
\[ > \sum_{r=0}^{R-1}x_{\{t,u\}}^r\ge \rho_{tu} > \]
for every demanded arc \((t,u)\in S\). Equivalently, minimize total unmet demand, or maximize the mass-weighted revenue
\[ > \sum_{(t,u)\in S}\sum_r x_{\{t,u\}}^r > \]
subject to the bracket constraints.
This is a precise continuous question: the instance consists of a finite type tournament, rational type masses, a number of rounds, demanded type-pairs and rational demand quotas; a solution is the sequence of nonnegative match-mass variables and induced winner masses. It is a linear program with \(O(R\tau^2)\) variables and constraints, so it is solvable in time polynomial in \(R\), \(\tau\), and the encoding length of the rational data.
This is recognizable as the paper’s problem rather than an unrelated relaxation. The paper explicitly says that Demand-TF is a special case of revenue maximization, with unit revenue for demanded matches and zero for all other matches. Replacing the count of matches by the mass of matches is exactly what that interpretation calls for when the entrants come in large interchangeable classes. The deterministic tournament digraph remains central; only the population and the bracket’s integrality are continuized.
For Theorem 1, the prediction is therefore tractability. The discrete NP-hardness comes from having to assemble one integral spanning binomial arborescence containing every demanded arc. In the mass version, a type population can be split across different sub-brackets, and the recursive packing obstruction becomes a linear mass-flow constraint. This is a genuine Class-A phenomenon: continuity removes the combinatorial difficulty caused by indivisible player copies.
The second mirror is the structured version corresponding to Theorem 4.
Near-Acyclic Mass-Demand-TF\(_R(k)\). The input additionally contains a linear ability order \(\sigma\) on the types and a feedback arc set \(F\) of size at most \(k\), with all arcs outside \(F\) agreeing with \(\sigma\). Decide whether a feasible mass bracket meets all demand quotas.
The regime is plausible in exactly the way the authors motivate their theorem: most player classes follow a clear ability ranking, with only a small number of upset relations. The continuous problem is again polynomial-time solvable, in fact fixed-parameter tractable in \(k\) vacuously, because the LP does not need to enumerate the exceptional arcs at all. Theorem 4’s \(n^{O(k)}\) packing algorithm is replaced by a polynomial mass-transport formulation. This does not diminish the relevance of the theorem; it identifies what the theorem’s discrete parameter is measuring and shows that its role disappears once repeated player classes become divisible.
The expected further programme is not exhausted by the LP. One should prove a rounding theorem: given a feasible mass bracket, how large must a finite high-multiplicity tournament be before a bracket meeting every quota up to additive \(O(1/N)\) exists? One can also ask for round-specific quotas, weighted audience revenue, fairness constraints between type classes, or probabilistic pairwise outcomes. The most interesting boundary question is whether imposing a single common integral bracket template, rather than allowing measurable splitting, restores the paper’s NP-hardness or produces a new continuum-specific difficulty.
I would not claim that Theorem 2’s ETH and parameterized lower bounds transfer. Those bounds are driven by the discrete vertex-level structure and by integral bracket construction; the mass formulation is specifically designed to dissolve that source of hardness. Nor would I claim to mirror Theorem 3’s exact-exponential algorithm. The positive case rests on Theorems 1 and 4 and covers the central Demand-TF objective, not every result in the paper.
The weakest point is clear: the continuous problem no longer asks for one bracket in which each named demanded match occurs exactly once. It asks for a measurable population bracket in which each demanded type-pair receives a prescribed amount of match mass. If the authors regard named rivalries and one-off matches as essential, they may reasonably call this too relaxed. But in a genuine high-multiplicity setting, “this particular copy of type \(t\) meets that particular copy of type \(u\)” has no population-level meaning; a positive quota for the type-pair is the honest replacement. The paper’s own revenue formulation supplies the bridge. Under that reading, Mass-Demand-TF is a credible continuous mirror, with Theorem 1 as the strongest anchor and Theorem 4 as its natural structured refinement.
The strongest negative case is that the proposed Mass-Demand-TF does not actually continuize Demand-TF; it replaces it with a different aggregate throughput problem.
Theorem 1 is about a set \(S\) of arcs between named players and one spanning binomial arborescence containing all of them. Each player occurs once, and the same player must carry all of its demanded matches through one coherent path of the bracket. That shared identity is the source of the edge-extension/subgraph-isomorphism structure.
The mass LP discards precisely this constraint. If \(u\) has demanded matches against \(v\) and \(w\), its variables may use one mass of \(u\)-copies against \(v\) and a different mass of \(u\)-copies against \(w\), even in the same round. The original problem requires one \(u\) to survive and play both matches at compatible heights. This is not merely a change in the answer; it is a loss of the object being constrained.
Replicating the population does not resolve the problem cleanly. There is a trilemma:
The last option is coherent, but it is a new commercial scheduling problem. The paper’s “unit revenue per demanded match” interpretation does not by itself make it the same problem: normalizing that revenue sends each individual rivalry to zero, while keeping positive revenue changes a named rivalry into a recurring type-level relationship.
The best repair would be to preserve demand profiles: a mass unit of type \(u\) would have to follow one bracket path and satisfy its several obligations coherently. But then the state must record which obligations a unit has fulfilled, or equivalently which complete bracket template it belongs to. That restores the discrete coupling the LP removed, potentially with exponentially many states or integral template choices. If instead one allows a distribution over templates, one is measuring the fraction of independent tournaments that succeed, not designing one population-level bracket.
Theorem 4 has an additional mismatch. A single upset between two types produces \(\Theta(N_tN_u)\) upset arcs after blowing the types up into \(N_t,N_u\) copies. Thus the paper’s feedback-arc parameter is not preserved under high multiplicity. Defining feedback arcs on the type quotient gives a sensible new parameter, but it is no longer the parameter in Theorem 4; moreover, the proposed LP is polynomial for every quotient, so the theorem’s compactness and packing machinery has disappeared rather than been continuized.
This is not an objection that the continuous version becomes easy. Easy Class-A mirrors are valuable. The objection is that the easy version is obtained by erasing the identity-and-single-bracket structure that makes the paper’s named results what they are.
I would therefore reject the proposed mirrors as faithful anchors for this paper. The negative case is not airtight, however. If the programme accepts recurring type-level audience demand as an independently meaningful tournament market, Mass-Demand-TF is a legitimate new continuous problem and could justify a green verdict. What cannot honestly be claimed is that the paper itself supplies a strong, identity-preserving continuous mirror of Theorems 1 or 4.
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.