| paper | Single-Winner Voting with Alliances: Avoiding the Spoiler Effect |
| authors | — |
| venue | AAMAS 2024 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper has a natural, author-recognisable population mirror: evaluate its \(IW\)-Plurality or \(IW\)-Maximin rule on rational masses over ranking types. However, every numbered result is axiomatic or rule-design impossibility, and the unnumbered statement that the rules are polynomial-time computable cannot satisfy the explicit named-result requirement for bit (a). The spoiler-repair formulation is a plausible new control problem, but it adds persuasion costs and an optimization objective absent from the paper.
fails bit a — no named computational result to mirror
The direct evaluation is only a high-multiplicity restatement and adds no difficult computational task; this limits its significance but does not invalidate the continuous analogue.
fatal: False
The stated mirror covers weighted evaluation of \(IW\)-Plurality, with \(IW\)-Maximin as an analogous variant; it leaves the \(SW\) variants, Theorem 2, Propositions 1–2, experiments, and nested-alliance discussion without a qualifying computational mirror.
Strictly under the ChoCo screening rule, this paper has no qualifying named computational anchor. Theorem 1 and Theorem 2, both proved here, establish axiomatic properties of \(IW\)- and \(SW\)-rules; Proposition 1 and Proposition 2 establish impossibility results about rule design. None asserts that a computational problem is in \(P\), NP-hard, FPT, or similar. The statement that “all the four alliance-aware rules are polynomial-time computable” is unnumbered and is not presented as a formal complexity theorem. Thus the strict anchor set is empty.
The strongest conditional positive case uses Theorem 1 as a semantic anchor, while explicitly recognising that it is not a qualifying complexity anchor. The lead mirror would be Continuum-IW-Alliance Winner.
An instance consists of candidates \(C\), a partition \(\mathcal A\) of \(C\) into alliances, a finite listed set \(T\subseteq\Pi(C)\) of complete rankings, and rational masses \(\mu_\pi\ge 0\) summing to \(1\). For Plurality, define
\[ p_\mu(c)=\sum_{\pi:\operatorname{top}_\pi(c)=c}\mu_\pi \]
and
\[ p_\mu^{\mathcal A}(c) = \sum_{\pi:\ c\succ_\pi d\text{ for every }d\notin A(c)} \mu_\pi . \]
The winning alliance is
\[ A^\star = \operatorname{arg\,max}_{A\in\mathcal A} \left( \max_{c\in A}p_\mu^{\mathcal A}(c) \right), \]
and the output is
\[ w = \operatorname{arg\,max}_{c\in A^\star}p_\mu(c), \]
with the paper’s fixed lexicographic tie-breaking. The computational question is to output \(w\), or decide whether \(w=c^\star\). The decision variable is the winning candidate; the objective is the paper’s two-round score maximisation. The analogous \(IW\)-Maximin version replaces \(p_\mu\) by
\[ q_\mu(c)=\min_{d\ne c}\sum_{\pi:c\succ_\pi d}\mu_\pi \]
and \(p_\mu^{\mathcal A}\) by
\[ q_\mu^{\mathcal A}(c) = \min_{d\notin A(c)} \sum_{\pi:c\succ_\pi d}\mu_\pi . \]
This is a direct high-multiplicity mirror. A society of \(N\) voters with \(n_\pi/N=\mu_\pi\) gives exactly the same comparisons after multiplying every score by \(N\). The natural regime is a large election with millions of voters but relatively few repeated ballot types: for example, stable ideological or regional blocs ranking a modest slate of candidates, with alliances representing parties or factions. Here \(\tau=|T|\ll N\), while candidates and alliances remain discrete. The paper’s own use of percentages makes this interpretation especially recognisable.
The continuous evaluation problem is plainly Class A: all scores are rational weighted sums or minima of such sums, computable in polynomial time in \(m\), \(\tau\), and the encoding length of \(\mu\). Theorem 1’s axiomatic conclusions also transfer: majority thresholds become \(1/2\), and its arguments depend on score comparisons that are unchanged by replacing counts with masses. This covers the \(IW\)-Plurality and \(IW\)-Maximin portions of Theorem 1, proved here, but not the experiments or the impossibility results.
A more substantive ChoCo extension generated by the paper is Continuum-IW-Plurality Spoiler Repair. Given the same instance, a target alliance \(A^\star\), and type-to-type persuasion costs \(\gamma(\pi,\rho)\), choose transfers \(x_{\pi,\rho}\ge0\) satisfying
\[ \sum_{\rho}x_{\pi,\rho}\le \mu_\pi \]
and
\[ \mu'_\rho = \mu_\rho-\sum_\sigma x_{\rho,\sigma} +\sum_\sigma x_{\sigma,\rho}, \]
so that \(IW\text{-}Plurality(\mu')\in A^\star\), while minimising
\[ \sum_{\pi,\rho}\gamma(\pi,\rho)x_{\pi,\rho}. \]
This is a natural population-level version of “how much support must be moved to prevent the spoiler effect.” With an explicit type list, the Plurality winner conditions become linear after choosing the relevant first- and second-round witnesses, so this version is plausibly Class A via a finite family of LPs. It is, however, an extension of the paper’s question, not a result proved in it.
The weakest point is decisive: the paper’s computational content is real but unnumbered, and the named results are axiomatic rather than complexity-theoretic. Moreover, direct winner evaluation is already easy in the discrete model, so this mirror does not display the characteristic ChoCo phenomenon of population continuity dissolving or exposing computational hardness. The positive case is therefore a credible, author-recognisable Class-A extension, but not a strict qualifying mirror under the programme’s anchor rule.
The paper fails the ChoCo screen before any modelling issue arises. Its numbered results are axiomatic or impossibility results about the existence and properties of alliance-aware rules. Theorem 1 and Theorem 2 do not establish a complexity classification; Propositions 1 and 2 do not concern the complexity of a computational problem. The statement that the four rules are polynomial-time computable is unnumbered and merely observes that the proposed rules can be evaluated. Thus there is no named computational result here to continuize.
The proposed Continuum-IW-Alliance Winner does not repair that deficiency. A distribution \(\mu\) over rankings is certainly a sensible high-multiplicity model: the paper itself uses percentages, and large electorates with repeated ideological blocs are entirely plausible. But the proposed computation is only the paper’s rule evaluated on normalized counts. Multiplying rational masses by a common denominator produces an ordinary election with repeated ballots, while grouping identical ballots in an ordinary election produces \(\mu\). The alliance-aware Plurality and Maximin scores are unchanged up to scale. This is a valid homogeneous reformulation, but not a new computational question exposed by the paper.
Changing the representation does not strengthen the case. Restricting to the top-choice and alliance-prefix information for IW-Plurality still leaves a finite aggregation problem. Replacing rankings by pairwise margins for IW-Maximin likewise compresses the same sufficient statistics. Introducing a continuous ideological space would either reduce, after integrating over ranking regions, to the same finite profile, or move the problem outside the paper into numerical integration and spatial voting. None supplies a paper-native complexity problem.
The proposed spoiler-repair problem is more substantial, but it is not a mirror of Theorem 1. The paper holds the voters, candidates, and alliances fixed and studies which alliance-aware rule should select the winner. The repair problem adds voter persuasion, type-to-type costs, a target alliance, and an optimization objective absent from the paper. It is therefore a generic campaigning or bribery problem wrapped around the rule. The same construction could be applied to any voting rule, regardless of whether that rule had anything to do with alliances or spoilers.
The more direct variants do not change this diagnosis. One could minimize the mass of voters whose rankings must change, study robustness to mass perturbations, or optimize candidate withdrawal and alliance splitting. Those are potentially legitimate continuous social-choice problems, but they are new control and robustness problems, not computational consequences of the paper’s results. Their relevance would have to come from an independently motivated strategic model, not from this paper’s theorems.
The honest negative conclusion is therefore narrower than the requested universal claim: under the strict ChoCo screen, this is a no. The direct continuous evaluation is a high-multiplicity restatement of an axiomatic rule, and the interesting optimization version is an unanchored extension. But the stronger claim that no worthwhile continuous mirror exists in any scenario cannot honestly be sustained. The population model is natural, and a suitably motivated alliance-aware control problem could be worthwhile; it simply is not supplied by 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.