| paper | d4-conf-aaai-2017-0024 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→P discrete result → its continuous mirror
Answer: \(\mathrm P\); also fixed-parameter tractable parameterized by \(k\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given finitely many competitor types \(T\), rational masses \(\mu_t\) summing to \(1\), a deterministic type-level winner for each match, a target type \(t^\star\), and bracket depth \(R\), can the masses be paired over \(R\) rounds so that the final mass \(2^{-R}\) is entirely of type \(t^\star\)? At round \(r\), choose match masses \(q^r_{\{a,b\}}\geq 0\) satisfying \(2q^r_{\{a,a\}}+\sum_{b\ne a}q^r_{\{a,b\}}=p_a^r\); the next-round mass of each type is the sum of match masses whose winner has that type. The question is whether such a schedule exists.
A continuous population of interchangeable competitor types with rational masses; the decision variables are pairwise match masses at each bracket round, and the objective is to make the entire final survivor mass \(2^{-R}\) belong to the target type. The constraints form a polynomial-size linear program in \(R\), \(|T|\), and the input bit length.
An actual bracket has one named champion, while the mirror asks whether the champion belongs to a target class; this limits the mirror to settings where class-level success is meaningful.
fatal: False
The mirror covers Theorem 1’s seeding-to-winner decision question at target-class granularity. It does not establish the paper’s FPT bound in \(k\), and leaves the structural lemmas and proposed parameterized directions aside.
My lead is Continuous Type Tournament Fixing. The paper’s one named complexity anchor is Theorem 1, proved in this paper: the TOURNAMENT FIXING PROBLEM can be solved in time \(2^{O(k^2\log k)}n^{O(1)}\) on an \(n\)-player tournament with a feedback arc set of size \(k\). Thus it is FPT in the size of a smallest feedback arc set.
A credible high-multiplicity setting is a very large tournament of deterministic automated agents, with many copies of each of a small number of fixed programs. Let a type be a program family: every copy has the same outcome against every *other* type. A match between copies of the same type still produces a winner of that type, so its individual identity does not matter when the question is whether a designated program family wins. The mass \(\mu_t\) is type \(t\)’s fraction of the entrants. The regime is \(N=2^R\) entrants with \(N\gg\tau\), where \(\tau\) is the number of program types; an instance might have millions of entrants but only dozens of types. The target is a designated type, rather than one named copy.
Here is the continuous problem. The input is a finite set of types \(T\), their pairwise deterministic outcomes, rational masses \(\mu_t\geq 0\) summing to \(1\), a target type \(t^\star\), and a bracket depth \(R\). At round \(r\), let \(p_t^r\) be the mass of type \(t\) still in the bracket. Choose nonnegative match masses \(q^r_{\{a,b\}}\) for unordered pairs of types, including \(a=b\), subject to
\[
2q^r_{\{a,a\}}+\sum_{b\ne a}q^r_{\{a,b\}}=p_a^r.
\]
Each match contributes its mass to the type of its winner, giving the next-round masses \(p^{r+1}\). A solution is a sequence of such pairings for \(R\) rounds in which \(p_{t^\star}^R=2^{-R}\), the entire remaining mass. Equivalently, maximize the target type’s final mass and ask whether the maximum is \(2^{-R}\). When the masses are integer multiples of \(1/N\), restricting match masses to those same multiples gives the exact aggregate pairing description of the finite target-type version. Allowing fractional match masses is the continuization.
I expect this mirror to be tractable. The pairing constraints and round-to-round winner updates form a linear optimization problem with \(O(R\tau^2)\) variables and polynomially many constraints, so the continuous problem is in P in \(\tau,R,L\). Its nearly acyclic regime can be described by the feedback arc set size \(k_Q\) of the type-level tournament. I would not claim \(k_Q\) equals the paper’s \(k\): expanding a type into many players can increase the full tournament’s feedback arc set substantially.
The authors could plausibly recognize this as a continuous analogue of their problem: the bracket still uses the same pairwise outcomes and seeding decisions; the model lets a type’s mass split across matches. The important change is explicit: it asks whether a *class* of interchangeable competitors can supply the winner, rather than whether one specified player can. That is the co-modification that makes high multiplicity possible here.
The main follow-up questions are whether the fractional solution can be rounded to a finite seeding with an additive guarantee, whether the continuous optimum has any integrality property, and whether a version that preserves a named target player remains tractable. The weakest point is the target-class change. A particular copy has vanishing mass as \(N\) grows, and its individual same-type match outcomes can affect whether it survives. If the authors regard that identity as central to TFP, this mirror may not pass their recognition test. The class-winner formulation preserves the bracket-fixing question, but it does not settle that objection.
The negative case has one real anchor: Theorem 1. It is a named computational result, so the argument cannot rest on a lack of complexity content. The difficulty is that the result is about arranging *named players* so that one specified player wins.
In a high multiplicity model, players of a type are interchangeable. But the target in TFP is one player among \(N\), whose normalized mass is \(1/N\) and vanishes as the population grows. Tournament fixing eliminates everyone but one, so the decisive outcome sits at the scale that the population description washes out. The natural type-level fix is to ask whether a *class* can win. That is coherent, but it changes the success condition from “this player wins” to “a member of this class wins.” The proponent’s pairing LP models that class-level problem; its tractability is not an objection, but it does not preserve the theorem’s target.
The best identity-preserving rescue is a hybrid model: keep the target as a tagged individual and describe the other players by masses. Yet the tag’s survival depends on a sequence of opponents down to the final rounds, where only a constant number of players remain. Those exact remainders cannot be recovered from ordinary type masses. Tracking them keeps a discrete, identity-level part of the problem inside the model; letting them disappear loses the winner predicate. That is a structural limit of this mirror, not a tie-breaking or integrality detail.
There is also a parameter mismatch. The paper’s \(k\) counts feedback arcs in the individual tournament. A feedback arc between two types in a blow-up can stand for arcs between many pairs of players, so a small feedback arc set in the quotient need not mean small \(k\) in the original tournament. A theorem parameterized by quotient types could be worth studying, but it would be a different parameterized problem.
The weakness in this negative case is real: repeated teams or automated agents with homogeneous outcomes between classes could make class-level tournament fixing a plausible extension. If the authors regard “make this category win” as their problem, the proposed mirror may survive. The strongest claim I can support is narrower: there is no clean population-mass mirror that retains Theorem 1’s designated-player objective; rescuing it requires either changing that objective or retaining a discrete target path through the part of the bracket where the continuum approximation breaks down.
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.