| paper | Approval with Runoff |
| authors | Théo Delemazure, Jérôme Lang, Jean-François Laslier, M. Remzi Sanver |
| venue | IJCAI 2022 |
| filed under | frontier · knockout |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's numbered results are axiomatic impossibility and property theorems, not computational complexity or algorithmic results. Although the proposed continuous winner problem is a sensible population mirror, the programme requires a named computational result from the paper, which is absent.
fails bit a — no named computational result to mirror
No eligible numbered computational result exists to anchor the otherwise faithful continuous mirror.
fatal: True
The mirror covers the Section 3 approval-with-runoff rule family and the Section 5 distributional perspective, but not the axiomatic Theorems 1–4, the empirical analysis, or any computational result.
The best positive case is that this paper has a very natural population mirror, and Section 5 nearly writes it down. The important limitation is that the paper contains no qualifying named computational-complexity result. Theorem 1 proves that no AVR rule is both weakly strategy-proof and Pareto-efficient; Theorem 2 proves that no AVR rule is both clone-proof and Pareto-efficient; Theorem 3 proves that no AVR rule is simultaneously monotonic, weakly clone-proof, and neutral; and Theorem 4 summarizes further axiomatic properties. These are all proved here, but none asserts NP-hardness, membership in P, parameterized complexity, or a comparable computational classification. The exact triangular-distribution formula in Section 5 is unnumbered. Thus, strictly under the programme’s anchor requirement, this paper has no eligible computational anchor.
Nevertheless, my lead candidate for a genuine follow-up problem is Continuous \(\alpha\)-AVR Winner. Let \(C\) be the candidates and let \(T\) be a finite set of approval-preference types. A type \(\theta\) consists of a complete ranking \(\pi_\theta\) and an approval threshold \(k_\theta\), hence an approval set \(A_\theta\) consisting of the first \(k_\theta\) candidates in the ranking. The society is a rational distribution \(\mu\in\Delta(T)\), where \(\mu_\theta\) is the fraction of voters of type \(\theta\).
Define
\[ S_\mu(x)=\sum_{\theta:x\in A_\theta}\mu_\theta, \qquad S_\mu(xy)=\sum_{\theta:\{x,y\}\subseteq A_\theta}\mu_\theta. \]
For a fixed \(\alpha\in[0,1]\), the first-round finalist pairs are
\[ F^\alpha_\mu = \arg\max_{\{x,y\}\subseteq C} \left(S_\mu(x)+S_\mu(y)-\alpha S_\mu(xy)\right). \]
Thus \(\alpha=0\) gives MAV, \(\alpha=\tfrac12\) gives PAV, and \(\alpha=1\) gives CCAV. For each finalist pair, the second-round winner is determined by weighted majority: \(x\) beats \(y\) when
\[ \sum_{\theta:x\succ_\theta y}\mu_\theta > \sum_{\theta:y\succ_\theta x}\mu_\theta. \]
The problem is: given \((C,T,\mu,\alpha,c^\star)\), compute the finalist pairs and the resulting winner set, or decide whether \(c^\star\) is a winner. The decision variable is the selected finalist pair; its objective is precisely the paper’s weighted approval objective, followed by the paper’s majority runoff.
This is a faithful mirror rather than a simplification. The types preserve exactly the information used by the paper—approval sets and rankings—and mass merely replaces repeated ballots by population fractions. The relevant regime is a large electorate with relatively few recurring approval-preference types: for example, a national election with millions of voters, perhaps \(m=10\)–\(20\) candidates, and ideological or demographic blocs sharing the same ranking and approval threshold. Section 5 makes this especially plausible: the authors already study a distribution of voters, and a one-dimensional Euclidean distribution induces a finite distribution over AP types once candidates and the approval radius are fixed.
With explicitly represented types, this problem is plainly Class A. All approval scores, joint scores, and pairwise majority margins can be computed in \(O(\tau m^2)\) arithmetic operations, after which all candidate pairs are evaluated. For rational input, the exact winner is computable in time polynomial in \(m\), \(\tau\), and the encoding length. This is a legitimate continuous-population problem, though not a hardness-dissolution result: the paper supplies no discrete hardness result for it.
The mirror naturally generates more consequential ChoCo questions. One could ask for the minimum-cost mass transfer that makes \(c^\star\) win under \(\alpha\)-AVR, with costs for converting one AP type into another. For each possible finalist pair, the finalist inequalities and majority condition are linear in the post-intervention masses, so explicit-type versions appear amenable to LP. One could also study minimum \(L_1\) population perturbations that change the winner, or optimize \(\alpha\) itself.
The weakest point is decisive: Continuous \(\alpha\)-AVR Winner is mostly a weighted evaluation problem, not a paper-level complexity problem. It gives a sensible mirror and a plausible Class A starting point, but it cannot be anchored to Theorems 1–4 without violating the programme’s exclusion of axiomatic continuization. The paper therefore supports the claim that a continuous population model is natural for Approval with Runoff, but it does not itself provide the named computational result needed for a strong continuization case.
The proponent’s first observation is decisive under the programme’s anchor requirement: this paper has no named computational result to continuize. Theorems 1–4 are axiomatic impossibility and property results. Section 5 contains an exact formula, but not a computational-complexity theorem; Section 6 is empirical. The paper’s remark that plurality with runoff is “very easy to manipulate” is neither formalized nor proved here. Thus no eligible result survives as an anchor.
The proposed Continuous \(\alpha\)-AVR Winner is a faithful high-multiplicity representation, but it has almost no population-level computational content. Define
\[ q(\mu)=\bigl(S_\mu(c),\,S_\mu(cd),\,M_\mu(c,d)\bigr)_{c,d\in C}, \]
where \(M_\mu(c,d)\) is the pairwise majority margin. Every finalist choice and every runoff winner is determined entirely by \(q(\mu)\). Two distributions over approval-preference types with the same \(q(\mu)\) are indistinguishable to every \(\alpha\)-AVR rule. The exponentially many rankings, or a continuum of ideological positions, therefore collapse to \(O(m^2)\) aggregate statistics.
This is not an objection that the answer happens to be polynomial. The more fundamental point is that the proposed problem is only weighted evaluation of a finite collection of candidate pairs; the society itself is not an algorithmically relevant object. There is no pricing problem, transport structure, or population-dependent combinatorial phenomenon. If the Section 5 Euclidean model is used, positions can be partitioned into finitely many cells on which rankings and approval sets are identical. The density contributes only the mass of each cell. Any difficulty caused by an implicit density or a difficult integration oracle would be an input-representation issue, not a computational consequence of continuizing the electorate.
The suggested improvements do not repair this. Varying \(\alpha\) merely compares \(O(m^2)\) affine functions of \(\alpha\), so its breakpoints can be enumerated. Continuous versions of monotonicity, clone-proofness, and strategyproofness remain axiomatic questions, which the programme explicitly excludes. A single voter’s manipulation becoming measure zero is not, by itself, an objection—the natural positive-mass coalition version is available—but that version is a new strategic problem, not a computational result of this paper.
The proposed mass-transfer problem is the strongest possible rescue, but it is not a mirror of anything the paper proves. With an explicitly listed type set, fix a finalist pair \(\{x,y\}\), impose the linear inequalities making it optimal under the \(\alpha\)-AV objective, impose the linear majority condition, and minimize transfer cost. Enumerating finalist pairs gives a linear program. The same applies to minimum \(L_1\) perturbations. This is a legitimate new intervention model, but the paper supplies neither the intervention operation nor a cost structure. With arbitrary costs, the interesting mathematics comes from the added cost matrix; with adjacent-swap or spatial costs, it comes from an added transport geometry. That machinery could be attached to almost any finite-statistic voting rule and is not specific to Approval with Runoff.
I would therefore reject this paper as a source for a continuous-computational mirror. The high-multiplicity regime itself is entirely sensible—large electorates with recurring approval-preference types are a plausible setting—but the paper offers only a weighted restatement of an already finite aggregation rule. A continuous coalition-bribery project could be worthwhile as a new research direction, so the universal negative is not logically airtight. It is nevertheless unsupported by this paper: no qualifying computational anchor exists, and every richer mirror requires importing the substantive computational problem from outside it.
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.