| paper | The Distortion of Approval Voting with Runoff |
| authors | — |
| venue | AAMAS 2023 |
| filed under | voting · distortion |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5.8
statement extracted from the paper’s text layer
Given candidates \(C\), threshold \(\tau=1/m\), and a rational finite-support society \(\mu\in\Delta(T)\) whose types specify unit-sum utilities, approval sets, and consistent rankings, compute the winner distribution of the Theorem 5.8 randomized majority-runoff rule and establish its worst-case mean-welfare distortion over all such societies.
A finite catalogue of complete voter types carries masses \(\mu_t\); approval totals, pairwise-runoff totals, and welfare are linear sums over those masses, and the objective is worst-case expected-welfare distortion.
Optimizing over every possible pair-selection kernel \(F\) is not itself a finitely represented computational synthesis problem.
fatal: False
The mirror covers the paper's approval-based finalist-selection and runoff distortion bounds, including Theorems 5.2, 5.8, 6.2, and 6.3; it leaves the simulations and unrestricted rule-synthesis questions outside the direct result transfer.
The paper has a strong continuous-population mirror. Its finite-\(n\) formulation is already homogeneous: approval totals, pairwise-majority totals, and social welfare are all sums over voters, while distortion is a ratio of such sums. Replacing voter counts by population shares is therefore not a cosmetic limit; it gives the same information structure for a genuinely high-multiplicity electorate.
My lead mirror is Continuous Approval–Majority-Runoff Distortion Design. Fix candidates \(C\), a common approval threshold \(\tau\), and a finite catalogue \(T\) of voter types. A type \(t\) consists of a unit-sum utility vector \(u_t\in\mathbb{Q}_{\geq0}^C\) and a strict ranking \(\sigma_t\) consistent with it. A society is a rational mass vector \(\mu\in\Delta(T)\). Thus the first-stage observable input is approval-ballot mass
\[
b_S=\sum_{t:\{c:u_t(c)\geq\tau\}=S}\mu_t
\]
for each approval set \(S\subseteq C\); the hidden utilities remain hidden, exactly as in the paper. An anonymous pair-selection rule \(F\) maps \(b\) to a distribution over unordered candidate pairs. For a selected pair \(\{a,b\}\), majority runoff chooses \(a\) when
\[
\sum_{t:a\succ_{\sigma_t}b}\mu_t\geq\tfrac12
\]
(with a specified tie rule). Social welfare is mean welfare,
\[
W_\mu(c)=\sum_t\mu_tu_t(c).
\]
The objective is to choose \(F\) minimizing worst-case distortion
\[
\sup_{(T,\mu)}\frac{\max_c W_\mu(c)}
{\mathbb E_{c\sim \mathrm{maj}\circ F}[W_\mu(c)]}.
\]
A solution is an explicitly evaluable pair rule \(F\), together with its worst-case guarantee; on a supplied society it must output its pair distribution and resulting winner distribution. This is the continuous version of precisely the authors’ design question, not merely approval voting with fractional outcomes.
The regime is a large primary, municipal election, union election, or membership referendum with recurring constituencies: for example, geographic/occupational/policy blocs who share a standardized preference-intensity profile, ranking, and threshold-based ballot instruction. There may be millions of voters but tens, hundreds, or thousands of such types. The utility vector is part of the type because it matters to the distortion benchmark, even though the mechanism does not observe it. This is not an assertion that every electorate has few utility types; it is a specific and plausible high-multiplicity regime.
The principal anchors are Theorem 5.2 and Theorem 5.8, both results of this paper. Theorem 5.2 proves here that every randomized approval-based pair-selection rule followed by majority runoff has distortion \(\Omega(m)\), even if it is given exact utilities. Theorem 5.8 states an explicit randomized rule—always retain the most-approved candidate, and mix the second-most-approved candidate with a uniformly random alternative—that at \(\tau=1/m\) has distortion at most \(4m\); its proof is deferred to the full version. These are unusually clean continuous anchors. The lower-bound construction is already described in fractions just below and above one half, and its force is unchanged when those fractions are literal masses. The upper bound uses only aggregate approval and welfare inequalities, so it transfers directly from counts divided by \(n\) to integrals against \(\mu\).
I expect this lead problem to be Class A in the programme’s sense, with an important qualification: executing the exhibited rule on a finite type catalogue is plainly polynomial—compute approval masses and pairwise masses, then scan \(m\) candidates—and the paper already gives the asymptotically optimal \(\Theta(m)\) design guarantee. What remains open is not population-multiplicity hardness but sharper mechanism-design questions: exact optimal constants, characterization of optimal pair-selection kernels, and efficient certification of a proposed rule’s worst-case distortion. This paper does not itself offer an NP-hardness/P classification; its named results are approximation/distortion theorems. That is still a worthwhile mirror, but it is not an LP-with-pricing showcase like continuous swap bribery.
A second, independently good mirror is Continuous Approval–Proportional-Runoff Distortion Design. The instance and first-stage rule \(F\) are identical, except that after selecting \(\{a,b\}\), the outcome chooses \(a\) with probability
\[
p_{ab}=\sum_{t:a\succ_{\sigma_t} b}\mu_t
\]
and \(b\) with probability \(1-p_{ab}\). The objective is again minimax distortion against the mean-welfare optimum. Here the continuous society is especially natural: “candidate \(a\) is selected with probability equal to the fraction preferring \(a\)” is literally a population-share rule, not a surrogate for an individual-level process.
The relevant anchors are Theorem 6.2 and Theorem 6.3, proved or stated in this paper (the latter’s proof is deferred to the full version). They show, for deterministic first-stage pair selection, that choosing the two most-approved candidates has distortion at most \(8(1/\tau+m)\), while every such rule has distortion at least \(\frac12(1/\tau-1)\), in the stated threshold range. At \(\tau=1/m\), the continuous design problem consequently has \(\Theta(m)\) distortion. This is a second Class-A-looking problem: finite-support society instances are easy to evaluate, and the central upper and lower bounds do not rely on individual granularity. The remaining computational questions concern optimal randomized first-stage rules, including the same gap the paper identifies for proportional runoff.
The authors would, I think, recognize both mirrors immediately. Nothing has been dumbed down: the mechanism still sees only approval ballots initially; rankings are used only in the runoff; utilities are hidden but define welfare; and the first-stage choice remains the central design variable. Dividing every voter count and welfare by \(n\) turns their definitions into the displayed mass model without changing distortion. Proportional runoff being a lottery is an outcome-space feature, but it is not why this counts as continuization; it counts because the electorate itself is the distribution \(\mu\).
The weakest point is the utility type space. Real voters who submit the same approval ballot and ranking need not have identical cardinal intensities, so a small exact catalogue can be demanding. The right positive claim is therefore regime-specific: standardized constituency models, survey-derived archetypes, or a rational utility grid can make it appropriate, and arbitrary populations can be approximated by finite-support societies. Majority runoff adds a related discontinuity near a \(50\!:\!50\) pairwise split: tiny mass changes can reverse a winner. That is a real substantive feature of runoff elections, not an artefact to hide. It weakens easy finite-to-continuous stability claims near ties, but does not undermine the mirror or the paper’s worst-case results, which already concern precisely such aggregate-majority behavior.
The negative case is decisive on scope: this paper has no named computational problem to continuize. Its numbered theorems are distortion bounds—information-theoretic guarantees and impossibility statements about voting rules—not complexity classifications or algorithms for a finite, encoded instance. That is exactly the category the programme’s screen excludes. A population-share restatement may be perfectly natural, but it remains a distortion analysis, not continuous computational social choice.
This defeats the main anchors. Theorem 5.2 is an adversarial welfare lower bound, even with utilities revealed; it does not establish hardness of computing a winner, a pair, or a manipulation. Theorem 5.8 supplies a fixed, elementary pair rule and proves a bound on its worst-case ratio. Replacing counts by masses preserves its proof, but only because both are aggregate inequalities. On a finite type catalogue, evaluating that rule is merely summing approval and pairwise-preference masses; no new computational problem has appeared.
The same applies to Theorems 6.2 and 6.3. They bound the distortion of a particular deterministic finalist-selection rule and of all such rules, respectively. Proportional runoff’s use of a population fraction is indeed naturally expressed with mass, but that makes the *outcome rule* convenient to write, not the population a source of a new algorithmic optimization question. It is precisely the sort of outcome-probability continuity that must not be mistaken for the programme’s target.
The proponent’s proposed “design” problem conceals the missing computational specification. \(F\) is an arbitrary map from approval-mass vectors to distributions over pairs; optimizing over all such maps is a minimax characterization, not a finite search, decision, or approximation problem. Supplying a society with its utilities does not repair this: those utilities are deliberately hidden from the mechanism in the paper, and if the designer may use them, the informational model changes. If \(F\) must instead be represented by a circuit, a finite rule language, a Lipschitz kernel, a learned model, or a finite utility grid, then certification or synthesis may become computationally interesting—but those are new representation and uncertainty assumptions, not a mirror of any result here.
A better high-multiplicity story therefore does not save the anchors. Large elections with recurring voter types are plausible, and the paper’s results extend to them almost verbatim. That supports a continuous *restatement* of this distortion theory. But the programme is not collecting natural restatements of aggregate voting models; it is seeking computational landscapes unlocked by treating society as a distribution. This paper contributes no such landscape to transfer upward.
So the honest conclusion is not that continuous approval-runoff distortion is ill-defined or socially implausible. It is that it is already, in substance, an analytic worst-case distortion framework whose claims survive normalization by \(n\). Any worthwhile ChoCo question inspired by it would have to add a new computational task—rule synthesis under a restricted representation, robust design under a statistical model, manipulation of mass, or similar—and would be a new project rather than a continuous mirror of the paper’s named results.
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.