| paper | Fixing Knockout Tournaments With Seeds |
| authors | Pasin Manurangsi, Warut Suksompong |
| venue | IJCAI 2022 |
| filed under | frontier · knockout |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given \(m=2^r\) candidates, a rational distribution \(\mu\) over complete rankings, \(m/2\) designated seeds, and a target candidate \(c^\star\), define \(a\succ_\mu b\) when \(a\) has strict majority support over \(b\). Decide whether a valid seeded knockout bracket exists whose winner under \(\succ_\mu\) is \(c^\star\).
Types are complete rankings \(t\) of the candidate set \(C\), carrying mass \(\mu_t\) with \(\sum_t\mu_t=1\); these masses induce the majority tournament. The decision variable is a valid seeded bracket, and the objective is whether its deterministic winner is \(c^\star\).
The majority relation is a sufficient statistic, so population mass is not manipulated, priced, or optimized; the proponent does not show that the population must remain computationally relevant after aggregation.
fatal: False
The mirror covers Theorems 5.2 and 5.1, the seeded-TFP hardness results. It leaves the structural results, probabilistic theorem, and \(2^n n^{O(1)}\)-time counting algorithm unaddressed.
The strongest positive case is a continuous-population version of the paper in which the players remain atomic candidates, while the society generating their pairwise outcomes becomes continuous. This is the right continuization: the paper’s tournament graph is a pairwise-comparison object, and in a social-choice interpretation those comparisons can be induced by a distribution of voter rankings.
My lead anchor is Theorem 5.2, proved in this paper. It states that TFP is NP-complete when the number of seeds is maximal, \(s=n/2\). The reduction starts with an arbitrary non-seeded TFP instance on \(n\) players, adds \(n\) new players \(V'\) who all lose to every original player, and makes all players in \(V'\) seeds. Seed constraints force every first-round match to pair one original player with one seeded player from \(V'\). Thus the original players alone survive to the second round, and the new seeded instance is winnable by \(x\) exactly when the original instance is.
I would mirror it by the following problem.
Continuous Seeded Majority-TFP\(_{\mathrm{half}}\). An instance consists of:
For distinct candidates \(a,b\), define \(a\succ_\mu b\) when
\[ \sum_{t:a\succ_t b}\mu_t>\frac12. \]
Instances may be promised to have no pairwise ties. The question is whether there exists a balanced valid seeded bracket, obeying the paper’s rule that the top two seeds meet only in the final, the top four only in the semifinals, and so on, whose winner under \(\succ_\mu\) is \(c^\star\). A solution is such a bracket.
This is a genuine continuous-population problem. The society is the distribution \(\mu\), not a finite list of named voters. A rational distribution \(\mu_t=n_t/N\) is exactly the high-multiplicity version of a finite electorate with \(n_t\) voters of ranking type \(t\); scaling all multiplicities leaves the induced tournament unchanged. Conversely, every rational continuous instance expands to a finite profile after clearing denominators.
The regime is natural for large-scale knockout voting: a large electorate evaluates proposals, parties, teams, or policy alternatives through repeated ranking templates. There may be millions of voters but only a modest number of recurring preference types. Seed status belongs to candidates, as in the paper, while population mass determines their pairwise comparisons.
The paper’s hardness transfers. Every finite tournament graph can be realized as a strict majority relation of a polynomial-size finite preference profile by the standard majority-realization construction. Therefore, take the seeded tournament produced by the proof of Theorem 5.2 and encode its pairwise edges as the majority relation of a rational distribution \(\mu\). The target wins in the continuous problem exactly when it wins in the paper’s seeded instance. Membership in NP is immediate: pairwise majority comparisons and bracket verification are polynomial-time, and the bracket is a polynomial-size certificate. Hence Continuous Seeded Majority-TFP\(_{\mathrm{half}}\) is NP-complete.
This is a Class B mirror. The reduction’s combinatorics live in the candidate set and the constrained bracket, not in the number of individually named voters. Making the electorate continuous therefore does not dissolve the hardness. That is a meaningful computational conclusion, not a collision: the paper has an exogenous tournament graph, whereas the mirror makes the society producing that graph explicit.
A second, independently useful anchor is Theorem 5.1, also proved in the paper. It states that TFP is NP-complete for every constant permitted number of seeds. The proof first treats \(s=4\): from a non-seeded instance \(V\), it constructs blocks \(V_1\) and \(V_2\) of sizes \(n\) and \(2n\), each with a locally unbeatable player \(x_1\) or \(x_2\); all block players defeat the original players except that \(x\) defeats \(x_1\) and \(x_2\). The seed placement forces \(x\)’s quarter to contain exactly the original instance. The proof then generalizes this construction to every fixed \(s=2^t\), using blocks \(V_i\) of sizes \(2^{i-1}n\) and a hierarchy of seeds.
The corresponding continuous problem is:
Continuous Seeded Majority-TFP\(_s\). Given a rational ranking distribution \(\mu\) over \(m\) candidates, a fixed permitted seed count \(s\), a valid assignment of seed numbers, and a target \(c^\star\), decide whether a valid seeded bracket can make \(c^\star\) win the majority tournament induced by \(\mu\), and output the bracket if one exists.
For each fixed \(s\), this problem is NP-complete by the same majority-realization argument. The result is especially useful because it shows that the mirror remains meaningful both with a constant number of seeds and with the maximum number of seeds. The difficulty is not an artefact of a large seed hierarchy.
The weakest point is that the paper itself treats the tournament graph as primitive; it does not study voter populations or majority aggregation. Thus this mirror adds a social-choice layer. If the authors insist that their intended application is literal sports competition with externally determined match outcomes, they might regard it as an extension rather than their exact model. Still, the extension preserves the candidates, pairwise winner relation, seed constraints, bracket action, and winner objective, and every tournament graph remains representable by a society. That makes the correspondence substantially stronger than merely replacing \(n\) by a fractional population.
I would therefore cover Theorems 5.2 and 5.1, with Theorem 5.2 as the lead. I would not stretch the mirror to the structural king/superking results or to the random-model theorem: those concern properties of an already-given tournament or randomness over match outcomes, whereas the two NP-completeness theorems give the clearest computational anchors.
Natural follow-up questions are whether hardness persists when the number of ranking types is fixed or very small, whether approximate masses and pairwise near-ties admit robust algorithms, and how much population mass must be changed to make a target candidate a seeded knockout winner.
The strongest negative case is that the proposed mirror does not make the population a computational object. Let \(G_\mu\) be the tournament induced by the strict majority relation
\[ a\succ_\mu b \quad\Longleftrightarrow\quad \sum_{t:a\succ_t b}\mu_t>\frac12. \]
The proposed problem is then exactly \(F(G_\mu,S,c^\star)\), where \(F\) is the paper’s seeded-TFP predicate. Once \(G_\mu\) has been formed, every feature of the society disappears: no mass is transferred, priced, constrained, allocated, or optimized. Seed feasibility and bracket success depend only on atomic candidates and their pairwise edges. Thus \(\mu\) is an alternative encoding of the tournament graph, rather than a high-multiplicity version of the paper’s computational problem.
This criticism applies equally to both anchors. In Theorem 5.2, the added set \(V'\) consists of seeded candidates, not a population whose mass affects the decision. Encoding the resulting graph by a ranking distribution does not continuize the reduction’s construction: it merely supplies a social-choice explanation for the already-given edges. Theorem 5.1 has the same defect. Its blocks \(V_i\) are blocks of candidates placed in a seed hierarchy, not blocks of voter types. Varying the number of seeds therefore does not create a second population-level anchor.
The majority-realization argument actually exposes the problem. Since every tournament can be represented by a rational distribution over complete rankings, the proposed domain includes every paper instance. With sparse support, this is a polynomial-size encoding of the graph; with a genuinely bounded type space, arbitrary tournament realization is lost and the claimed reductions no longer anchor the problem. The positive case therefore has to choose between a population layer that is eliminable and a restricted social-choice problem that is no longer the theorem being mirrored.
A better version could make the population matter by allowing mass transfers, campaign costs, margin objectives, or robustness against voter changes. For example, one could ask for the minimum mass of ranking types that must be converted so that a valid seeded bracket makes \(c^\star\) win. That would be a legitimate ChoCo problem, and perhaps an interesting one. But it is a new bribery or control problem: the paper contains no voters, costs, budgets, margins, or population intervention. Likewise, replacing majority by expected match outcomes turns the model into a stochastic or noise formulation, while using pairwise margins changes the tournament rule itself.
This is a real objection to calling the proposed construction a worthwhile continuous mirror, but it is not a decisive universal negative. The electorate-ranking scenario is natural, rational profiles are genuine high-multiplicity societies, and the programme explicitly allows Class B mirrors whose hardness survives continuization. The majority-realization construction is not a novelty collision, and nothing in the paper prevents its pairwise tournament from being socially generated.
So I cannot honestly defeat the two anchors under the programme’s rules. The negative case is that they are population encodings rather than population computations; the positive case survives unless “worthwhile” requires the population to be directly manipulated or to enter the objective.
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.