| paper | d4-conf-atal-2022-0132 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(P\) partitioned among \(\ell=2^h\) parties, a fixed seeding, and a supported set \(T\) of complete voter rankings with rational masses \(\mu_t\) summing to \(1\), define each pairwise match by strict majority, restricting to societies without pairwise ties or fixing a tie-breaking rule. Compute a pure Nash equilibrium of the one-shot winner-take-all knockout game, or report that none exists.
The electorate is a distribution \(\mu\) over supported ranking types \(T\). Its pairwise majority comparisons induce the tournament digraph; each party still chooses one candidate from its roster, and its utility is \(1\) if its nominee wins and \(0\) otherwise. The seeding and party choices remain finite.
The mirror covers the one-shot win-lose and beyond-win-lose equilibrium results in Theorems 1 and 2; it leaves the dynamic results, seeding selection, and other solution concepts aside.
The strongest credible mirror is the paper’s election setting: voters are the continuous society, and parties are the coalitions choosing nominees. A voter type is a complete ranking of the candidates. If \(T\) is the supported set of rankings, the society is a rational distribution \(\mu\) over \(T\), with \(\mu_t\) the fraction of voters of type \(t\). This fits a high-multiplicity regime where the electorate is very large but has relatively few distinct rankings.
Here is a precise shared instance for the two results I would mirror. Let \(P\) be the candidates, partitioned into \(\ell=2^h\) parties \(\mathcal C=\{C_1,\ldots,C_\ell\}\), with a fixed seeding. Define the match between candidates \(p,q\) from different parties by majority rule: \(p\) beats \(q\) if \(\sum_{t:p\succ_t q}\mu_t>1/2\). Restrict to societies with no pairwise ties, or specify a fixed tie-breaking rule. These comparisons induce the paper’s tournament digraph. A party’s action is still to choose one candidate from its roster; the solution sought is a pure Nash equilibrium of those choices. The electorate’s mass determines the pairwise results, while the party utilities and deviations remain those of the paper.
My lead anchor is Theorem 1, proved in this paper. In the one-shot win-lose game, where each party gets utility \(1\) if its nominee wins and \(0\) otherwise, the authors prove that a Nash equilibrium can be computed in \(n^{O(\log \ell)}\) time, where \(n=|P|\) and \(\ell\) is the number of parties. In full, an equilibrium profile selects one nominee per party so that no losing party can unilaterally replace its nominee and thereby make itself the tournament winner; the algorithm returns an equilibrium if one exists. The paper also notes that its algorithm can find an equilibrium with a specified winner when such one exists.
The continuous problem—call it Majority-Society One-Shot Winner Equilibrium—is: given \(P,\mathcal C\), the seeding, and the supported ranking types with masses \(\mu_t\), find such an equilibrium under the majority-induced tournament, or report that none exists. Its expected direction is tractable by Theorem 1: compute the pairwise results from the listed types and rational masses in polynomial time, then run the paper’s algorithm. The resulting bound is \(n^{O(\log\ell)}+\operatorname{poly}(n,\tau,L)\), where \(\tau=|T|\) and \(L\) is the mass input’s bit length. Further questions include whether the majority-derived tournament structure or small voter support permits a better bound, and how the equilibrium’s existence depends on the voter distribution.
A second, more demanding utility model has a named anchor too: Theorem 2, also proved here. In a one-shot beyond-win-lose game, a party’s utility is the number of rounds its nominee survives; a profile is an equilibrium when no party can improve that number by changing nominees. The theorem proves that computing such a B-W/L Nash equilibrium is polynomial-time solvable. The continuous problem—Majority-Society Advancement Equilibrium—uses the same instance and asks for a nominee profile with no unilateral deviation that lets a party survive more rounds. Its expected direction is polynomial time, after the same polynomial-time construction of the pairwise results. A natural follow-up is whether the result extends to other stage-reward schedules, especially when rewards are not simply the number of rounds reached. Theorem 2 has the stronger running-time guarantee; Theorem 1 is my lead because winner-take-all is the closer fit to the paper’s run-off election motivation.
The paper supplies no named hardness result to anchor, so these are necessarily algorithmic anchors. The scope of this case is fixed-seeding, one-shot nominee selection under win-lose or advancement utilities. It does not cover dynamic, opponent-specific selections or seeding choice.
The weakest point is that the continuous voter society determines the tournament edges but does not change how parties act or how their utilities are measured. The paper takes the tournament digraph as input, so the authors might regard the voter distribution as an application-specific way of generating that input rather than a new central model. Still, the paper explicitly motivates its coalitional tournament model with elections and party nominations. A large electorate represented by masses of ranking types gives those pairwise results a concrete high-multiplicity interpretation, while preserving exactly the strategic question the authors study. The positive case is strongest as a faithful, computable population-based extension—not as a claim that continuity itself makes the equilibrium problem easier.
The voter-distribution construction is the strongest case for a mirror, but it continuizes a different population from the one in Theorems 1 and 2. In those results, the agents choosing and deviating are the coalitions: each has a roster, occupies a particular bracket position, and cares whether that coalition wins or how far it advances. The paper’s input is their partition, seeding, and pairwise tournament relation. It contains no voter types or voter masses.
Adding a society \(\mu\) of voters with rankings is a coherent election variant: use \(\mu\) to compute majority outcomes, then run the equilibrium algorithm. But once those outcomes are computed, \(\mu\) has no further role. It supplies the tournament edges; no voter acts, deviates, or receives utility in either equilibrium concept. Thus the proposed mirrors of Theorem 1 and Theorem 2 have the same limitation: their continuous society determines the input to the game, while the computational question remains about individually identified parties and nominees. That may be a useful way to generate tournament instances, but it does not make the population studied by these results continuous.
Making the coalitions themselves a continuous population fares worse. A knockout tournament needs one coalition in each of its \(\ell=2^h\) leaves, and equilibrium deviations belong to particular coalitions in particular positions. If position is part of a coalition’s complete type, the number of types grows with the bracket; the aggregation has not removed the individual structure. If instead a coalition type carries positive mass across leaves, there is no longer a single entrant at each match or a named coalition whose win or advancement defines utility. Restoring those features brings back a finite set of atomic parties. A mass over nominee candidates would similarly change the object from choosing one player to fractional or randomized nomination.
A highly symmetric bracket with many cloned parties might admit some aggregation, but that would impose a special repeated structure on the tournament and its seeding. The paper’s general model allows arbitrary pairwise outcomes, and its equilibrium conditions depend on which coalition occupies which position. Such a symmetric restriction could define a separate problem; it does not provide a convincing population limit for either theorem as stated.
The negative case is weakest at the paper’s election motivation: the authors might well recognize equilibrium computation when voter masses generate the pairwise results. That is the best surviving angle. But it treats the electorate as an external input to the parties’ game, not as the population whose computational behavior these theorems analyze.
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.