| paper | d4-conf-ijcai-2018-0577 |
| 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: Polynomial-time solvable (\(\mathrm{P}\)) in \((Rm^2+L)^{O(1)}=(R\tau^2+L)^{O(1)}\) time; also fixed-parameter tractable with parameter \(k\), independently of \(k\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given entrant types \(T\), a tournament relation \(\succ\) between distinct types, rational initial masses \(\mu_t\) summing to \(1\), a target type \(t^\star\), and \(R\) bracket rounds, decide whether nonnegative match masses \(x^r_{\{t,u\}}\) and survivor masses \(p_t^r\) exist with \(p_t^0=\mu_t\), \(2x^r_{\{t,t\}}+\sum_{u\ne t}x^r_{\{t,u\}}=p_t^{r-1}\), and \(p_t^r=x^r_{\{t,t\}}+\sum_{u\ne t:\,t\succ u}x^r_{\{t,u\}}\), such that \(p_{t^\star}^R=2^{-R}\).
Represent the society by rational type masses \(\mu_t\), with deterministic outcomes \(\succ\) between types. At each round, \(x^r_{\{t,u\}}\) is the mass of type-\(t\) and type-\(u\) matches, and \(p_t^r\) is the surviving mass of type \(t\). The displayed pairing and survivor constraints define a linear feasibility problem; the target wins exactly when \(p_{t^\star}^R=2^{-R}\).
Theorem 1 asks whether a named player can win, while this LP lets any member of the target type win; the proponent flags this shift but does not establish that the authors would accept a type champion as the same objective.
fatal: False
The mirror covers Theorem 1's seeding-feasibility objective at the type level. It leaves the named-player guarantee, the \(k^\star\)-parameterized running-time analysis, and cited background results outside the mirror.
My positive case is narrow: tournament fixing has a credible high-multiplicity mirror when the desired winner is a *type* of entrant, and the types have consistent predicted outcomes against one another.
The anchor is Theorem 1, proved in this paper. It says that Tournament Fixing Problem, given a tournament \(D\), a target player \(v^\star\), and parameter \(k^\star\) equal to the feedback arc set number of \(D\), can be solved in time \(2^{O(k^\star\log k^\star)}n^{O(1)}\). For a yes-instance, the algorithm also constructs a seeding in that time. The paper’s introduction reports earlier NP-hardness of unrestricted TFP by Aziz et al.; that is cited background, not a numbered result proved here, so it is not a separate anchor. The paper also uses Proposition 1, cited to Williams (2010): TFP is yes exactly when \(D\) contains a spanning binomial arborescence rooted at \(v^\star\). That gives a useful structural bridge from a seeding to a tree.
Here is the regime I would use. Imagine a large elimination contest among entrants from a small number of delegations or archetypes. The organizer’s question is whether a member of a favored delegation can win. Forecasts are consistent at the type level: any entrant of type \(t\) beats any entrant of type \(u\) whenever \(t\) beats \(u\). If two entrants of the same type meet, one advances, but the winner is still of that type. The outcome of interest is therefore the winning type; individual identity within a type does not affect the question. The population may have \(n=2^R\) entrants, with \(n_t\) of type \(t\), while the number \(\tau\) of represented types stays small. This is a plausible high-multiplicity regime for a contest where the delegation or entrant category is the meaningful winner.
I would call the mirror Continuous Type Tournament Fixing, \(\mathrm{CTF}_\infty\). An instance gives a finite set \(T\) of entrant types, a tournament relation on distinct types, a distribution \(\mu\) with positive rational masses \(\mu_t\) summing to \(1\), a target type \(t^\star\), and a bracket depth \(R\). The mass \(\mu_t\) is the fraction of entrants of type \(t\). The relation \(t\succ u\) means a type-\(t\) entrant beats a type-\(u\) entrant. For each round \(r\), let \(p_t^r\) be the mass of surviving entrants of type \(t\), starting with \(p_t^0=\mu_t\). Choose nonnegative match masses \(x^r_{\{t,u\}}\). Every entrant must be paired, so for each \(t\),
\(2x^r_{\{t,t\}}+\sum_{u\ne t}x^r_{\{t,u\}}=p_t^{r-1}\).
The next-round mass is
\(p_t^r=x^r_{\{t,t\}}+\sum_{u\ne t:\,t\succ u}x^r_{\{t,u\}}\).
A same-type match contributes one survivor of that type. The question is whether such flows exist for \(R\) rounds with \(p_{t^\star}^R=2^{-R}\), meaning all final survivor mass is of the target type. The flows themselves are a solution certificate. There is no cost objective: as in TFP, the task is to decide whether a bracket arrangement can produce the desired winner.
This is a continuous version of the seeding decision, rather than a change to fractional outcomes or random predictions: the population is the object represented by mass, and the choices describe how mass is paired at each bracket level. It is a relaxation of the discrete version. When \(n=2^R\) and \(\mu_t=n_t/n\), the discrete entrants give the corresponding type proportions; the continuous model allows divisible mass instead of requiring every pairing to use integral entrants. That change is exactly what makes the model amenable to an LP. There are \(O(R\tau^2)\) match variables and \(O(R\tau)\) mass constraints, so feasibility is polynomial in \(\tau\), \(R\), and the input bit length. I expect this mirror to be Class A, tractable. The theorem’s feedback-arc parameter \(k^\star\) need not control the LP’s running time.
I think the authors could recognize this as their bracket-feasibility question in a type-based regime: it retains deterministic head-to-head results, seeding through a binary elimination structure, and the goal of arranging the bracket so the favored outcome wins. The main co-modification is that the target is a favored type rather than a named player. That is also the weakest point. The paper studies whether one particular \(v^\star\) can win, while this mirror treats members of a type as interchangeable and asks whether that type can win. If the authors regard individual identity as essential even when the question only concerns the winner’s type, they may reject it as their problem.
The scope is just Theorem 1’s seeding-feasibility result. The LP also raises useful follow-up questions: when does a feasible continuous flow yield a discrete seeding at a given population size, and how large can the gap between the two be? A closer version retaining one named target player would also be valuable, but it would need to track that player’s bracket path while aggregating the rest of the society.
Theorem 1 is a genuine computational anchor: it gives an FPT algorithm for deciding whether a specified vertex \(v^\star\) can win. The strongest case against a mirror is that the identity of that vertex is central to the problem, while the proposed continuous model makes the target a whole type.
For a tournament type to be complete, its members must have the same match outcomes against every other type. That is a demanding assumption in the paper’s deterministic model: grouping entrants by delegation or playing style does not establish that every member beats and loses to the same outsiders. Replacing those outcomes with average or probabilistic matchups would change the model in a different way. If uniform outcomes do hold, asking whether a type can win is sensible, but it lets any member of that type stand in for the target. The tournament may then have a winner of the right category even when the specified player cannot win. Proposition 1’s rooted arborescence makes the distinction concrete: its root is \(v^\star\), not a category containing possible roots.
A stronger repair would keep \(v^\star\) as a distinguished player and represent the remaining entrants by continuous masses of types. But \(v^\star\) then has zero mass in the population limit. The mass-flow constraints can describe what happens to the crowd, but the condition that this particular zero-mass player survives to the root needs an additional discrete state tracking its path through the bracket. Giving its type positive mass instead restores a mass constraint by representing interchangeable copies, and changes the target back to a type. The hybrid model is coherent, but the champion’s identity remains a separate discrete object.
There is also a gap between the paper’s parameterized regime and the likely type structure. A small feedback arc set means the tournament is close to transitive; it does not imply that many players have the same complete matchup profile. In fact, a near-transitive tournament can have distinct profiles for almost every player. The few-type mirror therefore relies on large blocks of entrants with uniform outcomes, a structure the theorem does not supply and that may be hard to justify for the sports settings motivating the paper.
That is the best negative case I can make, but it does not establish the requested universal claim. A tournament with genuinely interchangeable entrants and a meaningful type-level winner is plausible, and the continuous bracket question appears well-posed there. The case against is strongest when insisting on the paper’s named-player objective; it weakens if the authors accept a type as the desired winner, or a distinguished player against a continuous crowd, as their problem.
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.