| paper | Margin of victory for tournament solutions |
| authors | Markus Brill, Ulrike Schmidt-Kraepelin, Warut Suksompong |
| venue | AI 2022 |
| filed under | voting · tournaments |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{TC}\): polynomial-time solvable, including an attaining rational distribution. For each fixed \(k\geq4\), computing the value for \(k\)-kings is NP-hard. The degree identity holds with probability tending to one, simultaneously for all candidates and all admissible \(k\), as well as for \(\mathrm{TC}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 18
statement extracted from the paper’s text layer
Given candidates \(C\), ranking types \(T\), a rational society distribution \(\mu\) with no pairwise majority ties, a target \(x\), and \(S\in\{\mathrm{TC},k\text{-kings}\}\), compute the signed minimum number of pairwise majority orientations that must be reversed to change \(x\)’s status in \(S(T_\mu)\), together with a rational distribution \(\nu\) attaining it; under a uniform-random induced tournament, determine whether the degree formula of Theorem 18 holds with high probability.
A high-multiplicity election with ranking types \(t\), society mass \(\mu_t\), and post-intervention mass \(\nu_t\); the decision variable is \(\nu\), while the objective is the edge distance \(d_E(T_\mu,T_\nu)\), with \(T_\mu\) the strict majority tournament.
The opponent’s strongest point is that \(\nu\)’s type masses disappear after forming \(T_\nu\), so the mirror is only a compressed tournament representation; the proponent acknowledges this limitation but does not make the edge-reversal objective population-sensitive.
fatal: False
The mirror covers Theorem 18 for \(\mathrm{TC}\) and \(k\)-kings under the uniform-random induced-tournament regime. It leaves the axiomatic structural results, experiments, and computational claims inherited from earlier work outside the anchor.
The honest positive case is narrow but real. This paper has no numbered NP-hardness, membership-in-\(\mathrm P\), FPT, or approximation theorem of its own. The strongest admissible anchor is therefore Theorem 18, an algorithmic average-case result rather than a worst-case complexity classification.
Theorem 18, proved in this paper, states that if \(S\in\{\mathrm{TC},k\text{-kings}\}\), \(4\le k\le n-1\), and \(T\) is drawn from the uniform random tournament model, then with high probability, simultaneously for every alternative \(x\),
\[ \mathrm{MoV}_S(x,T) = \min\left( \operatorname{outdeg}_T(x), \min_{y\neq x}\operatorname{indeg}_T(y) \right). \]
Thus, although exact computation of the margin of victory can be difficult in general, in a sufficiently large random tournament it is given by a simple degree formula. The proof is in this paper; it uses Lemma 11, which is cited from Brill et al. (2020), and probabilistic bounds including the cited result of Fey (2008).
My mirror would be Continuous Tournament MoV. There are \(m\) alternatives \(C\), and a voter type is a complete ranking \(t\) of \(C\). A society is a rational distribution \(\mu\) over ranking types. Its majority tournament \(T_\mu\) has \(a\to b\) exactly when
\[ \sum_{t:a\succ_t b}\mu_t>\frac12, \]
assuming no pairwise ties. Given \(S\in\{\mathrm{TC},k\text{-kings}\}\), a target alternative \(x\), and \(\mu\), define
\[ \mathrm{CMoV}_S(x,\mu) = \begin{cases} \min_{\nu}\ d_E(T_\mu,T_\nu) &\text{if }x\in S(T_\mu),\\[2mm] -\min_{\nu}\ d_E(T_\mu,T_\nu) &\text{if }x\notin S(T_\mu), \end{cases} \]
where \(\nu\) ranges over rational ranking distributions with no pairwise ties, and
\[ d_E(T_\mu,T_\nu) = \left|\left\{\{a,b\}: T_\mu\text{ and }T_\nu\text{ orient }\{a,b\}\text{ differently} \right\}\right|. \]
The solution is the minimum signed number of aggregate pairwise comparisons that must be changed to make \(x\) leave or enter the winner set, together with an attaining post-intervention distribution \(\nu\). Equivalently, the action variable is an edge-reversal set \(R\), but the society before and after the intervention is represented continuously by \(\mu\) and \(\nu\).
This is a plausible high-multiplicity regime. Think of a very large electorate of voters or referees using a small collection of recurring ranking templates: perhaps millions of voters but only \(\tau\) observed ranking types, with \(\tau\ll N\). The paper already treats tournaments as majority-comparison objects and explicitly interprets edge reversals as bribery or manipulation. Replacing finite multiplicities by \(\mu_t\) is therefore recognizable as the population-level version of its problem. It does not continuize candidates, outcomes, or time.
For societies whose induced tournament is uniform random, Theorem 18 gives the expected outcome of the mirror: with high probability, every \(\mathrm{CMoV}_S(x,\mu)\) is computable from the majority tournament’s degrees by the displayed formula. Constructing \(T_\mu\) takes polynomial time in the number of represented types, candidates, and input bit length, after which the formula and a witnessing reversal set are immediate. This is a Class A result in the same distributional/high-probability sense as the paper’s theorem.
For arbitrary \(\mu\), however, I would expect hardness to transfer rather than disappear. Every finite tournament can be represented as the majority relation of a finite ranking profile, hence as a rational high-multiplicity society. So a worst-case hard discrete tournament-MoV instance embeds directly into this continuous problem. The random regime is tractable; the unrestricted regime is plausibly Class B.
This mirror covers only Theorem 18’s \(\mathrm{TC}\) and \(k\)-kings result. I would not use the paper’s remarks that \(\mathrm{MoV}_{\mathrm{UC}}\) is efficiently computable or that \(k\)-kings is computationally hard as additional anchors: those claims are attributed to Brill et al. (2020), not proved as numbered computational results here.
The weakest point is that the paper often takes the tournament itself as primitive, so \(\mu\) may look like an alternative representation of \(T\), rather than a source of genuinely new computational structure. A stronger follow-up would charge for population mass moved,
\[ \min_{\nu}\frac12\|\nu-\mu\|_1 \]
subject to changing \(x\)’s tournament-solution status, or would weight each comparison reversal by its pairwise majority margin. Those variants would make the continuous population operational rather than merely representational, and their complexity is an open question generated by this mirror.
The negative case is decisive at the anchor stage: this paper proves no qualifying computational result of its own. Theorem 18 is a probabilistic structural identity for random tournaments, not a complexity theorem about a problem whose input is a society. The paper’s computational claims—efficient computation for the uncovered set and hardness for \(k\)-kings—are explicitly inherited from Brill et al. (2020), not established here. The remaining numbered results are axiomatic, structural, or probabilistic. Thus the proposed mirror is not anchored in a computational contribution of this paper.
Even setting that gate aside, the proposed Continuous Tournament MoV is not a continuization of the population. Let \(T_\mu\) be the majority tournament induced by \(\mu\). The proposed intervention does not constrain how much population changes; it only asks for another distribution \(\nu\) whose tournament differs on as few edges as possible. But every tournament \(T'\) can be realized as the majority relation of a rational distribution over rankings. Therefore, for either constructive or destructive MoV,
\[ \min_{\nu:\,x\text{ changes status in }T_\nu} d_E(T_\mu,T_\nu) = \min_{R:\,x\text{ changes status in }T_\mu^R}|R| = \mathrm{MoV}_S(x,T_\mu). \]
The distribution \(\mu\) is consequently only a hidden representation of the tournament. All information about population frequencies disappears once \(T_\mu\) is formed. Different societies with radically different type masses but the same majority tournament receive exactly the same answer. This is a tournament MoV instance with an unnecessary population certificate, not a continuous-population problem.
The proposed random regime does not repair this. Theorem 18 samples each tournament edge independently. A deterministic society \(\mu\) is not itself a random tournament, and the paper gives no natural stochastic process on high-multiplicity ranking distributions whose majority tournament has that law. One can artificially lift every random tournament to a McGarvey-style ranking profile, but that merely chooses a profile representation after sampling the tournament. The theorem remains entirely about the tournament and its degrees; it says nothing about population mass, type frequencies, or population interventions.
The stronger suggestion,
\[ \min_{\nu}\frac12\|\nu-\mu\|_1, \]
would at least make the population operational. But it is then a new voter-bribery or profile-manipulation problem, not a mirror of the paper’s MoV result. The paper’s intervention is reversal of tournament edges, with cost measured in reversed comparisons. It neither defines nor analyses the mass required to move one society to another. Its random-tournament theorem gives no algorithm, bound, or structural insight for this new objective. Calling that problem a better mirror changes the intervention model precisely where the paper’s contribution lies.
The same objection applies to margin-weighted edge reversals. If costs depend on majority margins, that can produce an interesting continuous optimization problem, but the edge margins are newly introduced population data; the paper’s MoV is still only the unweighted tournament quantity. Any worthwhile result would come from the added mass-transport or margin geometry, not from continuizing a named result of this paper.
The paper’s experiments with voter models do not provide another route. They study how tournaments generated from finite random profiles behave, while the formal MoV object remains the tournament. Replacing the 51 voters by a distribution over ranking types would be a sensible modelling exercise, but with the paper’s edge-reversal objective it collapses to the identity above. With a mass-sensitive objective it becomes a new study lacking an anchor in the paper.
So the honest verdict is not that continuous population questions about tournament manipulation are impossible or intrinsically uninteresting. They may be worthwhile ChoCo problems in their own right. The stronger claim is narrower but sufficient here: this paper offers no computational theorem whose continuous-population mirror it is worth developing, and the proponent’s only proposed mirror is exactly invariant under replacing the society by its induced tournament.
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.