| paper | Adaptive Manipulation for Coalitions in Knockout Tournaments |
| authors | Juhi Chaudhary, Hendrik Molter, Meirav Zehavi |
| venue | AAAI 2025 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 9 supplies a genuine computational result, satisfying bit (a), but the proposed mirror continuizes the number of independent tournament instances rather than the participating population. Its occupation measures average finite-instance histories and introduce no mass-valued population manipulation. A single-tournament continuum would require new bracket, matching, and target semantics beyond a mirror of this paper.
fails bit b — no continuous question survives
The batch construction is only an ensemble of finite ACCM-KT instances: the distribution changes which finite players appear in each edition, while no continuum of participants interacts in one tournament.
fatal: True
The proposal targets only Theorem 9's ACCM-KT parameterized algorithm; it does not mirror the paper's hardness results, best-response results, generalized tournaments, or non-adaptive problem.
The strongest honest case is a qualified yes, anchored on Theorem 9 alone.
Theorem 9, proved in this paper, states that ACCM-KT is solvable in \((|C|+x)^{O(|C|+x)}n^{O(1)}\) time, where \(x\) is the size of a minimum random game cover. This is the result I would mirror; I would not try to claim that the paper’s PH-hardness results automatically transfer to a few-type population model.
The natural regime is a large batch of identically formatted knockout competitions: an online qualification platform, algorithmic-agent benchmark, or mass decision process runs a very large number \(K\) of seeded cups. Each cup has the same balanced bracket, but its entrants are drawn from a small collection of recurring behavioural types. A type records the entrant’s seed role, performance phenotype, coalition affiliation, and whether it is the designated target role. Two entrants of the same type have the same pairwise win probabilities, strategic rights, and target status. Thus this is genuine high multiplicity: with a fixed bracket of \(n\) slots and \(q\) phenotypes, there are at most \(nq\) types but \(Kn\) agents, so \(Kn/(nq)=K/q\) grows without bound.
The continuous population is described by rational masses \(\mu_{\ell,a}\), where \(\ell\) is a bracket slot and \(a\) is a performance type. It is the fraction of editions in which slot \(\ell\) is occupied by type \(a\). The target slot \(\ell^\star\) is occupied by the same target role in every edition. Pairwise probabilities \(p(a,b)\) remain exactly the paper’s probabilities; they are not replaced by expected scores or fractional outcomes.
A precise problem is the following.
Batch-ACCM-KT\(_\infty\). An instance consists of a complete balanced binary bracket \(B\) with \(n\) leaves, a finite type set \(A\), rational masses \(\mu_{\ell,a}\), rational pairwise probabilities \(p(a,b)\), a set of coalition types, a target slot \(\ell^\star\), and a rational threshold \(t\). Each edition independently receives a type-labelled seeding according to the product distribution induced by the \(\mu_{\ell,a}\). In every round, after observing the current type-labelled seeding, coalition entrants may intentionally lose their games, subject to the paper’s rule that two coalition players in the same game cannot both throw.
A solution is an adaptive policy \(\pi\) mapping every observed current seeding and round to a feasible throw/no-throw decision. Its value is
\[ V(\pi)=\Pr_{\mu,p,\pi}[\text{the target role at }\ell^\star\text{ wins the bracket}]. \]
The question is whether some policy has \(V(\pi)\ge t\). Equivalently, in the continuum limit, \(V(\pi)\) is the mass of tournament editions whose champion is the target role. A mass-flow formulation uses variables \(\rho_{k,s,a}\), the mass of editions in round-\(k\) state \(s\) taking action \(a\), with the usual transition equations induced by \(p\). This makes the action variable and objective explicit, and preserves adaptiveness rather than replacing it with a static mass transfer.
This is recognisably the paper’s problem. The probability threshold has the same meaning, the coalition still observes advancement round by round, and the action is still intentional forfeiture. The only change is that repeated, behaviourally identical entrants are represented by mass. In an applied setting, the continuous value is also the limiting empirical fraction of target wins over a very large batch of competitions.
The expected classification is Class A in the parameterized regime corresponding to Theorem 9. Let \(\kappa\) be the number of coalition types and let \(\chi\) be the size of a minimum vertex cover in the type interaction graph whose edges represent non-deterministic type pairs, including self-interactions. The paper’s coalition-skeleton dynamic program suggests that, when \(\kappa+\chi\) is small, the mass process can be summarized by the counts or masses of coalition and uncertain types; all other match outcomes are deterministic. The candidate result would be an exact algorithm fixed-parameter tractable in \(\kappa+\chi\), polynomial in the bracket size, number of types, and encoding length of the rational masses.
That conclusion is not automatic from Theorem 9: repeated copies create binomial or multinomial mass distributions, and a proof would need to control their bit complexity and show that the type-level state space remains manageable. But this is precisely a natural continuous-optimization question: an exponentially large policy/state LP whose useful compression depends on a structural cover parameter. It also generates worthwhile follow-ups: whether a type-level best-response analogue of Corollary 11 is FPT; whether the general unparameterized problem is continuum-specifically hard; and whether a genuine single-mass knockout, rather than a batch of brackets, admits the same Bellman or occupation-measure formulation.
The weakest point is that the cleanest mirror is a high-multiplicity batch of tournaments, not one physical tournament containing infinitely many interchangeable players. If the authors insist that ACCM-KT means exactly one cup, with one champion and an individually named \(e^\star\), then replacing \(e^\star\) by a replicated target role and taking the mass of successful editions may look like a change of instance regime rather than a literal limit. I would concede that. The positive case is therefore not “knockout tournaments are naturally fluid” in general. It is narrower: the paper’s probabilistic adaptive manipulation problem has a credible high-multiplicity realization in large populations of repeated, type-homogeneous knockout competitions, and Theorem 9 gives a principled algorithmic anchor for studying its type-level mass version.
The proponent’s only anchor, Theorem 9, does not survive as a continuous-population mirror. The proposed construction continuizes the number of tournament editions, not the population inside a tournament.
For a realised type-labelled seeding \(\sigma\), let \(v(\sigma)\) be the optimal adaptive winning probability for the target. Because the policy observes the current seeding and can act separately in each edition, the batch problem is simply
\[ \max_\pi V(\pi)=\sum_{\sigma}\Pr_\mu[\sigma]\,v(\sigma). \]
Thus \(\mu\) merely supplies a distribution over independent ACCM-KT instances. No mass is transferred, no population is manipulated, and no agents of the same type interact as a continuum. The proposed \(\rho_{k,s,a}\) variables are occupation measures over histories of a finite stochastic game; they do not produce the kind of type-mass optimization that motivates ChoCo. Calling this a continuous society is therefore no more justified than calling an average-case analysis a continuum-agent model.
The high-multiplicity defence does not repair this. In the paper, a player’s bracket position is consequential: it determines whom they can meet and when. Consequently, the seeding position must be part of a complete type. The proponent’s \((\ell,a)\) types acknowledge this. But then repeated copies of a type occur only in different tournament editions; within any one edition there is still exactly one agent per bracket role. The construction is a large batch of finite tournaments, not one tournament whose society has become continuous.
The best attempt to obtain a genuine single-tournament limit is also problematic. With fixed \(n\), there is no multiplicity limit. Letting \(n\) grow produces a different tournament model, requiring a choice of continuum matching, bracket geometry, and limiting dynamics. More importantly, the paper’s objective concerns the identity of a designated player \(e^\star\), while a fixed player has zero mass in a nonatomic population. Replacing “\(e^\star\) wins” by “some player of the target type wins” avoids that problem only by changing the computational problem. Retaining a distinguished target and a finite coalition yields a hybrid model with exceptional atoms, not the paper’s population-as-distribution setting.
One might instead couple the batch editions through a common coalition budget or require one policy to be used everywhere. But either move creates a new inter-edition resource-allocation or policy-learning problem. It is no longer ACCM-KT with a continuous society; the population is functioning as an ensemble of instances, and the computational question has changed accordingly. If the policy may condition on the full observed bracket, the same type can rationally take different actions in different contexts. If it may not, adaptiveness—the paper’s central feature—is being removed. Encoding every relevant context into the type space merely recreates an exponentially large history space.
Nor does Theorem 9 itself provide the missing bridge. Its dynamic program tracks configurations of named players in named bracket positions and counts wins of individual players in a random-game cover. Replacing those players by masses does not preserve those states: bracket position, sibling identity, and coalition status remain essential. The proposed fixed-parameter algorithm for the mass version is explicitly only a conjectural extension, not a consequence of Theorem 9.
So the paper has genuine named computational results, and its high-multiplicity batch interpretation is not nonsensical. But that interpretation belongs to distributional or ensemble analysis of repeated tournaments. Under ChoCo’s stated scope—making the society participating in one computational social-choice instance continuous—it supplies no worthwhile mirror of Theorem 9. A continuum tournament might be an interesting new research topic, but it would be a new model requiring new semantics, not a continuous mirror of this paper.
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.