| paper | Tournament Fixing Parameterized by Feedback Vertex Set Number Is FPT |
| authors | — |
| venue | AAAI 2023 |
| filed under | voting · tournaments |
| 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
Given a finite type set \(T\), a complete type-level tournament \(H\) with distinguished player \(w\), rational mass vector \(\mu\), and resolution \(N=2^d\), form one tagged \(w\) plus \(N-1\) players with type counts obtained by fixed rounding of \((N-1)\mu\) and canonical within-type outcomes; does some balanced-bracket seeding make \(w\) win? The continuum-limit version asks whether this holds for every sufficiently large \(d\).
A type-blowup balanced knockout tournament with rational type masses, integer capacities at each finite resolution, leaf and subtree type allocations, one tagged target player, and feasibility defined by whether the target wins.
The eventual limit preserves a one-player winning event whose mass tends to zero, so macroscopic type allocations may converge while the decisive bracket-level winner changes and a pure continuum tree has no terminal individual winner.
fatal: False
The mirror covers the paper's main FPT result for Tournament Fixing parameterized by feedback vertex set; it leaves the cited NP-hardness, structural propositions, proof lemmas, and proposed bribery, counting, incomplete-tournament, and double-elimination variants untouched.
The strongest positive case is a single anchor: Theorem 1, proved in this paper. It states that TOURNAMENT FIXING is solvable in time \(2^{O(k\log k)}n^{O(1)}\), where \(k\) is the feedback vertex set number of the tournament digraph. The paper’s NP-hardness statement is only cited from Aziz et al.; I would not use it as a second anchor. Proposition 2, cited from Williams (2010), is useful structural support but is not itself a complexity classification.
My mirror would be Tagged High-Multiplicity Tournament Fixing\(_\infty\).
An instance consists of a finite set \(T\) of ordinary player types, a distinguished target player \(w\), a complete type-level tournament \(H\) on \(T\cup\{w\}\), and a rational mass vector \(\mu\in\Delta(T)\). An arc \(t\to t'\) means that every player of type \(t\) defeats every player of type \(t'\). A type is complete: it includes the player’s predicted result against every other type and against \(w\). Matches between two players of the same ordinary type may be oriented arbitrarily, since whichever player survives still has the same type and the same future behaviour.
The mass \(\mu_t\) is the fraction of a very large population having type \(t\). For each \(N=2^d\), form a finite tournament \(D_N\) containing one copy of \(w\) and \(N-1\) ordinary players, with type counts obtained by rounding \((N-1)\mu\). The action is exactly the paper’s action: choose a bijective seeding of these players into the leaves of a balanced knockout bracket. The objective is that the tagged player \(w\) wins.
The continuous question is whether this remains feasible in the high-multiplicity limit:
\[ \exists d_0\ \forall d\ge d_0,\quad \text{there is a seeding of }D_{2^d}\text{ in which }w\text{ wins}. \]
A solution is therefore an eventual family of seedings \((\phi_{2^d})_{d\ge d_0}\). Equivalently, each seeding induces mass allocations
\[ x_d(t,B)=\frac{1}{2^d} \bigl|\{\text{type-}t\text{ players seeded inside bracket subtree }B\}\bigr|, \]
and the continuous solution is a convergent family of such allocations with limiting type masses \(\mu\) and with \(w\) surviving at the root. A finite-resolution version simply fixes \(d\) and asks the corresponding compressed high-multiplicity decision problem.
This is a genuine population continuization. The intended regime is, for example, millions of entrants in a large esports, robotics, or qualification tournament generated from perhaps 20–100 standardized strength or strategy profiles, with only a few exceptional profiles creating cycles in the type-level outcome relation. Thus \(N\) is enormous, \(\tau=|T|\ll N\), and the meaningful parameter is
\[ k=\operatorname{fvs}(H), \]
the number of exceptional player types whose removal leaves an acyclic type hierarchy. This is the high-multiplicity version of the paper’s own interpretation of feedback vertex set: a few surprising kinds of players, rather than a few surprising matches.
The mirror remains recognizably the authors’ problem. It retains the predictive tournament graph, the balanced knockout tree, the seeding decision, and the favorite winner \(w\). Nothing is fractionalized at the level of match outcomes, and this is not continuity of the outcome space or a noise model. Only behaviorally indistinguishable players are aggregated into masses.
I would expect this mirror to be Class A in the parameterized sense: fixed-parameter tractable in the number \(k\) of exceptional types, perhaps with a target bound of the form
\[ 2^{O(k\log k)}\operatorname{poly}(\tau,L), \]
where \(L\) is the encoding length of the masses and type-level arcs. The paper’s proof gives a credible route. Proposition 2 reduces fixing to finding a \((D,w)\)-binomial arborescence; the algorithm then guesses only \(O(k)\) structurally special positions using LCA-closure and handles the acyclic remainder by dynamic programming. In the high-multiplicity setting, the repeated players on the acyclic backbone should become rational capacities rather than individually enumerated states. The hard technical question is whether the table’s capacities and slots can be represented with bit complexity polynomial in \(L\), rather than polynomial in the expanded population \(N\).
This is not an automatic consequence of Theorem 1. Its \(n^{O(1)}\) term is polynomial in the explicitly expanded tournament, which may be exponential in the encoding length of \(\mu\); moreover, the feedback vertex set of the expanded tournament can be much larger than the feedback vertex set of the type quotient. The continuous result would therefore be a new theorem suggested by the paper, not a repackaging of its runtime.
The main boundary is clear. If \(\tau\) is allowed to grow to \(N\) and every player receives its own type, the model collapses back to ordinary TOURNAMENT FIXING and the cited discrete hardness can transfer. The positive claim concerns the genuine regime \(\tau\ll N\). Natural follow-up questions include whether the compressed problem is FPT in type-level FVS, whether binary-encoded masses introduce continuum-specific weak NP-hardness, whether “eventually feasible” can be replaced by a finite threshold, and whether the same mirror works for bribery, maximum-win variants, counting, incomplete or probabilistic tournaments, double elimination, or directed treewidth.
My weakest point is the tagged target. A named individual has vanishing mass, so one could argue that \(w\) is being preserved as an external atom rather than fully continuized. Removing the tag and asking whether the target *type* wins would be more purely population-based, but it would also weaken the authors’ original question. I think the tagged formulation is defensible because the paper itself singles out one favorite player, and the finite approximants preserve that player exactly. Still, the need to replace player-level FVS by type-level FVS, and to prove that the dynamic programme compresses over enormous multiplicities, is the central unproved step.
Theorem 1 is the only credible anchor: Proposition 2 is structural, and the NP-hardness result is merely cited. The negative case therefore turns on whether Theorem 1 survives aggregation. It does not.
The paper’s parameter is the feedback vertex set of the explicit player-level tournament \(D\). The proof depends on deleting those actual vertices, obtaining a unique topological order \(\sigma\), taking an \(O(k)\)-sized LCA-closure, and injectively embedding every individual player into a binomial arborescence. None of these objects is defined by the type quotient proposed in the case for.
If a cyclic type is repeated \(q\) times, deleting one exceptional type label does not delete its \(q\) player vertices. Indeed, with uniform cross-type outcomes, a cycle among three types produces a cycle using any surviving clone of each type; breaking all such cycles may require deleting an entire type class. Thus the expanded tournament can have feedback vertex set \(\Theta(q)\) even when the type quotient has FVS one. The theorem’s runtime then depends on the multiplicity after all. Replacing player-level FVS by “number of exceptional types” is a new colored/blow-up tournament problem, not the high-multiplicity counterpart of the theorem.
The proof also cannot simply replace repeated players by capacities. Proposition 2 requires an injective copy of the \(n\)-node binomial arborescence. The dynamic programme scans the individual vertices in \(\sigma\), and its slots and capacities describe precisely which individual nodes occupy which tree positions. Aggregating clones removes the injectivity that makes the proposition true. Keeping injectivity leaves the expanded population explicit; dropping it changes the problem. A quotient theorem might be possible, but nothing in Theorem 1 supplies it.
The tagged favorite creates a deeper obstruction. In every proposed limit, \(w\) has mass \(1/N\), hence vanishing mass. Yet the whole objective is whether that one null-mass atom survives a chain of \(\log N\) individual matches. A positive-mass target type does not repair this: “some player of the type wins” is a different objective, and a type-preserving continuum dynamics would no longer answer whether the paper’s favorite player wins.
Nor does the proposed limit of seedings solve the problem. The allocations \(x_d(t,B)\) are indexed by a different finite bracket at every \(d\). Their limiting masses do not retain the decisive information: the final winner has mass \(1/2^d\), and changing the winner can require changing only a vanishing set of leaves while leaving every macroscopic type allocation unchanged. A genuine continuum binary tree has no bottom leaves and therefore no well-defined final individual winner. A finite-depth version is merely a compressed integer tournament; an infinite-depth version loses the winning event.
One can repair this by retaining a tagged atom, a dyadic bracket depth, within-type orders, and discrete winner labels for every subtree. But then the state is again the bracket’s individual combinatorial structure, with masses as bookkeeping. Alternatively, one can define a mass-matching or normalized type-survivor process, but that asks a new continuum elimination problem whose terminal semantics are not Tournament Fixing.
The proponent’s empirical story—many entrants sharing standardized profiles—is not absurd, so the negative case is not airtight as a claim about every conceivable variant. The decisive point is narrower: the paper offers no worthwhile continuous mirror of its actual computational theorem. Its essential objects are individual vertices, an injective bracket embedding, and a vanishingly small designated winner. Once those are preserved, multiplicity is not eliminated; once they are aggregated, the theorem’s problem has been replaced.
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.