| paper | Truthful Approximations to Range Voting |
| authors | Aris Filos-Ratsikas, Peter Bro Miltersen |
| venue | WINE 2014 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable for \(m=3\), with rational output support size \(\tau\leq\min\{s,12\}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 7
Given a finite set \(T\subseteq V_3\) of complete canonical cardinal valuation types, compute or approximate \(\rho_{J^\star}(T)=\inf_{\mu\in\Delta(T)}\frac{\sum_{t\in T}\mu_t\sum_{c\in C}p^{J^\star}_c(\mu)u_t(c)}{\max_{c\in C}\sum_{t\in T}\mu_tu_t(c)}\), where \(J^\star=c_1U^1+c_2U^2\) and \(p^{J^\star}_c(\mu)=c_1\sum_{t:c\in\operatorname{Top}_1(t)}\mu_t+\frac{c_2}{2}\sum_{t:c\in\operatorname{Top}_2(t)}\mu_t\); return a certified worst-case mass vector and ratio bound.
Types are complete canonical valuation functions \(t\), the society is mass \(\mu\in\Delta(T)\), the mechanism samples mass and applies the \(U^1/U^2\) lottery, and the objective is worst-case expected social welfare relative to the best alternative.
Under a standard atomless direct-revelation model, one individual's report has zero effect on \(\mu\), so finite-voter truthfulness becomes vacuous; the case does not fully formalize whether the mirror uses prelimit truthfulness or a non-vacuous cohort-level incentive condition.
fatal: False
The mirror covers the constructive guarantee in Theorem 7 and can analogously cover the explicit quadratic-lottery mixture in Theorem 10; it leaves pure upper-bound results, finite-\(n\) tables, and the unrestricted cardinal-mechanism frontier aside.
The strongest honest positive case is that this paper already contains an unusually clean high-multiplicity limit, even though it does not contain a named NP-hardness, P, FPT, or parameterized-complexity theorem. Its named results are approximation theorems. Thus the mirror I can defend is a continuous-population mechanism-design and robust-optimization problem, not a claim that the paper has already classified its computational complexity.
Take \(m=3\) alternatives and let a type be the voter’s complete canonical valuation \(u:M\to[0,1]\), with distinct values, minimum \(0\), and maximum \(1\). This must include cardinal values, not merely rankings, because the paper’s quadratic lottery uses the second-highest value. A society is a finite type set \(T\) together with masses \(\mu\in\Delta(T)\). The intended regime is a large population of residents or users partitioned into a small number of stable valuation classes: perhaps millions of agents but only a dozen or a few dozen distinct calibrated preference profiles. This is precisely high multiplicity, not an artificial change of the problem.
For a mechanism \(J\), let \(p^J_c(\mu)\) be its probability of selecting candidate \(c\). The continuous social welfare and benchmark are \( \mathrm{SW}_J(\mu)=\sum_{t\in T}\mu_t\sum_{c\in M}p^J_c(\mu)u_t(c) \) and \( \mathrm{OPT}(\mu)=\max_{c\in M}\sum_{t\in T}\mu_tu_t(c) \). The robust approximation ratio is \( \rho_J(T)=\inf_{\mu\in\Delta(T)}\mathrm{SW}_J(\mu)/\mathrm{OPT}(\mu) \).
For \(U^q\), the continuum mechanism samples one unit of population mass and chooses uniformly among that voter’s \(q\) highest-ranked alternatives, so \( p^{U^q}_c(\mu)=q^{-1}\sum_{t:c\in\mathrm{Top}_q(t)}\mu_t \). This preserves the paper’s mechanism exactly: random sampling replaces choosing a uniformly random voter, while the lottery over three alternatives remains finite. Truthfulness is inherited from the finite mechanisms and their high-multiplicity limits; it is not being imposed as a vacuous atomless-report condition.
The first anchor is Theorem 7, proved in this paper. It states that if \( c_1=77066611/157737759\approx0.489 \), \( c_2=80671148/157737759\approx0.511 \), and \(J_n=c_1U^1_{3,n}+c_2U^2_{3,n}\), then \( \mathrm{ratio}(J_n)>0.610 \) for every \(n\). Consequently \(r^{OU}_3>0.610\). The authors prove this by reducing the worst case to the twelve quasi-combinatorial valuation types and solving a finite quadratic program.
The corresponding continuous problem is:
“Given a finite set \(T\) of canonical three-candidate valuation types, compute or approximate \( \rho_{J^\star}(T) \) for \(J^\star=c_1U^1+c_2U^2\), and decide whether \( \rho_{J^\star}(T)\ge \rho \). A solution is a certified worst-case mass vector \(\mu\), or an algorithm producing a lower bound and matching worst-case certificate.”
For the paper’s twelve-type catalogue, this is exactly the quadratic-program structure used in the proof, with type counts replaced by masses. The theorem says that its universal version has value greater than \(0.610\). I expect this fixed-\(m\), fixed-type-catalogue problem to be Class A: tractable by finite-dimensional continuous optimization, though I would not claim polynomial time when the type catalogue is part of the input, since general nonconvex quadratic optimization can itself be hard. This is a faithful mirror because neither the objective nor the mechanism has been simplified; only repeated voters have become mass.
My lead anchor is Theorem 9, also proved in the paper. It states \( r^{OU}_{3,23000}\le32093343/52579253<0.611 \) and \( r^O_{3,23000}\le41/64<0.641 \). Together with Lemma 4, the paper concludes \(r^{OU}_3<0.611\) and \(r^O_3\le0.641\). The first bound concerns anonymous neutral ordinal mixed-unilateral mechanisms, which are mixtures of \(U^1,U^2,U^3\). The second concerns all anonymous neutral ordinal mechanisms, including the duple mechanisms \(D^q\). The proof uses five explicit bad type profiles and solves the resulting finite matrix games.
The continuous question is the ordinal frontier problem. Let \(\mathcal C_{OU}\) be the convex hull of \(U^1,U^2,U^3\), and let \(\mathcal C_O\) additionally contain the continuum limits of the \(D^q\) mechanisms. A continuum \(D^\theta\) chooses a pair of alternatives uniformly, compares their masses, and elects an alternative once its supporting mass reaches threshold \(\theta\), otherwise resolving the pair randomly; \(\theta\in[1/2,1]\) represents the limit of \(q/n\). The problem is:
“Given a finite type set \(T\), compute or approximate \( R_{\mathcal C}(T)=\sup_{J\in\mathcal C}\inf_{\mu\in\Delta(T)}\mathrm{SW}_J(\mu)/\mathrm{OPT}(\mu) \), for \(\mathcal C=\mathcal C_{OU}\) and \(\mathcal C=\mathcal C_O\). A solution is an optimal or approximately optimal mixture of mechanisms, together with a worst-case mass distribution certifying its ratio.”
This is the paper’s central asymptotic comparison rewritten as an explicit continuous-population optimization problem. The rational finite profiles used in Theorem 9 are exactly rational mass vectors, and arbitrary mass vectors arise as limits of such profiles. The expected classification is again Class A for three alternatives and a fixed finite catalogue: the paper already reduces the problem to finite matrix games and quadratic programs. With \(m\) or \(|T|\) variable, continuum-specific hardness from nonconvex mass optimization is plausible, but it is not forced by the paper.
The third anchor is Theorem 10, proved here using the earlier quadratic-lottery result of Feige and Tennenholtz. It states that the limiting approximation ratio of \(Q_n\) is exactly \( (\sqrt5-1)/2\approx0.618 \). It also states that the mechanism choosing random-favorite with probability \(29/100\) and quadratic-lottery with probability \(71/100\) has ratio greater than \(33/50=0.660\).
The continuous quadratic-lottery mechanism is completely explicit. For a sampled type \(t\), let \(\alpha_t\) be the value of its second-ranked alternative. If its alternatives are \(c^{(1)}\succ c^{(2)}\succ c^{(3)}\), choose them with probabilities \( (4-\alpha_t^2)/6 \), \( (1+2\alpha_t)/6 \), and \( (1-2\alpha_t+\alpha_t^2)/6 \), respectively. The population mechanism samples \(t\) according to \(\mu\) and applies those probabilities. The continuous problem is:
“Given a finite cardinal type set \(T\), compute \( \rho_Q(T) \), and compute or approximate \( \sup_{\lambda\in[0,1]}\rho_{\lambda U^1+(1-\lambda)Q}(T) \). A solution is the mixing parameter \(\lambda\), the induced lottery rule, and a worst-case mass vector.”
The expected answer is Class A for fixed \(m=3\) and finite \(T\), because the resulting objective is an explicitly given quadratic-fractional optimization problem. Theorem 10 predicts the continuum values \( (\sqrt5-1)/2 \) for \(Q\) and more than \(0.660\) for the stated mixture. Further questions include whether a larger cardinal truthful mechanism class can beat this bound, and whether the continuous frontier has an exact finite-type certificate analogous to the paper’s twelve-type reduction.
The weakest point is that the paper itself is already very close to this mirror. Its Lemma 5, Lemma 6, asymptotic quantities \(r^O_m\) and \(r^{OU}_m\), and the fraction variables \(x_1,\ldots,x_{12}\) effectively use population proportions before calling them a separate continuous model. The mirror may therefore look like an explicit reformulation of an asymptotic analysis rather than a new problem. There is also a genuine modelling issue for arbitrary cardinal mechanisms: in a purely atomless direct-revelation model, one individual cannot change \(\mu\), so truthfulness becomes vacuous. The defensible response is to define the mirror as the high-multiplicity limit of the paper’s finite truthful mechanisms, especially sampled-voter mechanisms such as \(U^q\) and \(Q\), and to treat general continuum truthfulness as a separate question.
That weakness does not destroy the positive case. The paper supplies a precise two-way dictionary: rational \(\mu\) is a finite profile, repeated copies realize high multiplicity, and finite profiles converge to arbitrary mass distributions. More importantly, the resulting questions are not about fractional outcomes or noise; the continuous object is the society itself, while the outcome remains a lottery over the same alternatives. The paper therefore supports a credible Class-A continuization of its approximation problems, even though it supplies no complexity-theoretic hardness anchor.
The decisive objection comes before modelling: this paper has no named computational result of the kind ChoCo is meant to continuize. Its Theorems 7, 9, and 10 give approximation-ratio bounds for mechanism classes. They do not give a complexity classification, an input-dependent algorithm, an FPT result, or a hardness result for a computational problem. The matrix games and quadratic programs in the proofs are proof devices for fixed small parameters, not algorithms whose complexity is analysed. Thus “compute the continuous approximation ratio” is a new problem invented around the paper, not a continuous mirror of one of its computational contributions.
The high-multiplicity model itself is perfectly sensible here; the agents are anonymous, welfare is additive, and repeated valuation types are plausible. That concession defeats any objection based on individuality. It also exposes the redundancy of the proposed anchors: the paper already performs the relevant population aggregation internally.
For Theorem 7, the proposed continuous mechanism is exactly the proof’s existing fraction formulation. For \(J=c_1U^1+c_2U^2\),
\[ p_c(\mu) = c_1\sum_{t:c\in\operatorname{Top}_1(t)}\mu_t + \frac{c_2}{2}\sum_{t:c\in\operatorname{Top}_2(t)}\mu_t. \]
The paper’s variables \(x_1,\ldots,x_{12}\) are already precisely such population masses. Lemma 5 further says that, for the relevant ordinal mechanisms, worst cases reduce to the twelve quasi-combinatorial types. Consequently, fixing that catalogue merely re-runs the quadratic program already used to prove the \(0.610\) bound. Allowing an arbitrary finite \(T\) produces a potentially interesting robust-optimization problem, but it is no longer a continuization of Theorem 7: it is a new problem whose input is a chosen valuation catalogue, and whose difficulty comes from nonconvex optimization over that catalogue rather than from population multiplicity.
Theorem 9 has the same defect. Its matrix-game proof explicitly encodes profiles by type fractions and even gives five rational mass vectors as the bad instances. Replacing those fractions by \(\mu\) does not expose a missing computational question; it restates the proof in the language of distributions. The proposed \(D^\theta\) family is a reasonable asymptotic extension of the finite threshold mechanisms, but optimizing over \(\theta\), mixtures, and mass vectors is a new mechanism-design frontier problem. It is not an algorithmic result from the paper, and its central difficulty lies in optimizing over mechanisms and worst-case profiles, not in representing a large society continuously.
Theorem 10 is even less promising as an anchor. The quadratic lottery already samples one voter and applies a formula determined by that voter’s second-ranked value. In a mass notation,
\[ p_c(\mu)=\sum_{t\in T}\mu_t q_c(t), \]
which is simply the finite mechanism averaged over the empirical type distribution. Lemma 7 then performs the same reduction to quasi-combinatorial types that the proposed mirror would use. The golden-ratio limit and the \(0.660\) mixture bound are therefore already high-multiplicity calculations in substance. Asking for the best \(\lambda\) in \(\lambda U^1+(1-\lambda)Q\) is a legitimate one-dimensional extension, but not a computational mirror of Theorem 10. Asking whether arbitrary cardinal truthful mechanisms do better is exactly the paper’s own open problem, not something made computationally meaningful by replacing voters with mass.
There is also a serious incentive-theoretic problem with calling these limits truthful. In an atomless society, changing one individual’s report does not change \(\mu\), so direct-revelation truthfulness of a population-level map is vacuous. The finite \(1/n\)-scale incentive constraint disappears in the limit. One can define the continuum mechanism as “sample a type according to \(\mu\), then apply \(U^q\) or \(Q\),” but that is a chosen limit convention, not an inherited direct-revelation theorem. Alternatively, one can allow a positive-mass type cohort to deviate, but that introduces coalition or type-level strategyproofness, a new property absent from the paper.
So the proponent has shown that a coherent high-multiplicity reinterpretation exists. That is not enough here. Each anchor either has already been expressed through type fractions in the paper’s own proof, or becomes a freshly invented robust-optimization problem with no computational theorem to mirror. The paper may inspire a new continuous mechanism-design project, but it does not supply a worthwhile ChoCo continuization under the programme’s computational-anchor requirement.
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.