| paper | Awareness of Voter Passion Greatly Improves the Distortion of Metric Social Choice |
| authors | Ben Abramowitz, Elliot Anshelevich, Wennan Zhu |
| venue | WINE 2019 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm{P}\). A minimizing deterministic winner and its exact worst-case distortion are polynomial-time computable. For every fixed \(\Theta\), \(\sup_\mu V(\Theta,\mu)=D_\Theta\); mass admissibility guarantees this bound, and the displayed weighted rule satisfies admissibility and attains the bound globally. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 25
statement extracted from the paper’s text layer
Given two candidates \(P,Q\), thresholds \(1\leq\tau_1<\cdots<\tau_m\), and rational masses \(\mu(A_l),\mu(B_l),\mu(U)\), choose a deterministic winner using only those masses and determine the minimum worst-case distortion over all metric-consistent latent completions, including whether the mass version of Condition 18 and Weighted Majority Rule 4 achieves \(D_\Theta\).
Use finite complete latent types \(\theta=(r,a,b)\), with report \(r\), costs \(a=d(v,P)\), \(b=d(v,Q)\), and mass \(\nu_\theta\); the mechanism observes only the report marginal \(\mu\), chooses \(P\) or \(Q\), and minimizes the worst-case ratio of aggregate social costs over completions satisfying \(a,b\geq0\), \(|a-b|\leq1\leq a+b\), after normalizing \(d(P,Q)=1\).
The mirror must clearly distinguish the observable report-mass vector from the latent full cost-vector types, since social cost depends on coordinates the mechanism does not observe.
fatal: False
The mirror covers the two-candidate threshold results in Theorems 19 and 25 and extends naturally to Theorem 14; it does not fully cover the ideal-candidate-distortion results or every exact-strength variant.
The strongest mirror is a high-multiplicity, robust version of the paper’s two-candidate problem with thresholded preference strengths. I would treat this as a genuine population continuization, while preserving the paper’s finite candidate set, hidden metric, ordinal reports, and distortion objective.
A complete latent voter type is \(\theta=(r,z)\), where \(r\) is the voter’s reported ordinal and threshold information and \(z=(d(v,P),d(v,Q))\) is the voter’s full metric cost vector. Thus two voters of the same type have identical preferences, threshold reports, and costs. The mechanism does not observe \(z\), exactly as in the paper; it observes only the aggregate report distribution \(\bar\mu\). A high-multiplicity society has mass on finitely many such types, with \(n\gg |T|\). The mass of a type is its fraction of the population.
For fixed thresholds \(1\leq\tau_1<\cdots<\tau_m\), the observable report types are \(A_l\), voters who prefer \(P\) and whose strength lies in \([\tau_l,\tau_{l+1})\), \(B_l\), the analogous voters preferring \(Q\), and \(U\), voters whose preference is too weak to identify. The continuous input is the mass vector \(\bar\mu\) on these report types.
The latent metric completions of \(\bar\mu\) are all distributions of full types consistent with those reports and with a common metric on \(P,Q\). Since distortion is scale-invariant, normalize \(d(P,Q)=1\). For a selected candidate \(X\), define its robust distortion by
\(R_X(\bar\mu)=\sup_{\nu\text{ consistent with }\bar\mu}\frac{\int d(v,X)\,d\nu(v)}{\min_{Y\in\{P,Q\}}\int d(v,Y)\,d\nu(v)}.\)
The continuous problem is:
Given \(\Theta=\{\tau_1,\ldots,\tau_m\}\) and the mass distribution \(\bar\mu\) over thresholded voter types, choose \(P\) or \(Q\) minimizing \(R_X(\bar\mu)\). Equivalently, design a deterministic rule \(f(\bar\mu)\) minimizing its worst-case distortion over all report distributions and all consistent metric completions.
My lead anchor is Theorem 19, proved in this paper. It states that, for two candidates and \(m\) fixed thresholds, let \(\tau_0=1/\tau_1\), \(\tau_{m+1}=\infty\), and
\(D_\Theta=\max_{0\leq l\leq m}\left\{\frac{\tau_l\tau_{l+1}+2\tau_{l+1}-1}{\tau_l\tau_{l+1}+1}\right\}.\)
If \(k\) satisfies \(\tau_k\leq D_\Theta<\tau_{k+1}\), then any single-winner rule satisfying Condition 18 has distortion \(D_\Theta\), and no deterministic mechanism can achieve a smaller distortion. In the paper’s notation, the condition for selecting \(P\) is
\(\sum_{l=k}^{m}\frac{\tau_{l+1}-D_\Theta}{\tau_{l+1}-1}|B_l| \leq \sum_{l=1}^{m}\frac{D_\Theta\tau_l-1}{\tau_l+1}|A_l| + \sum_{l=1}^{k-1}\frac{D_\Theta-\tau_{l+1}}{\tau_{l+1}+1}|B_l|,\)
with the symmetric condition, obtained by interchanging \(A\) and \(B\), governing \(Q\).
The continuous mirror replaces every cardinality by mass. Thus the \(P\)-condition is exactly the same inequality with \(|A_l|\) replaced by \(\bar\mu(A_l)\) and \(|B_l|\) by \(\bar\mu(B_l)\). The solution is the candidate whose condition holds; if both hold, use a fixed tie-breaking convention. The paper’s Theorem 25, also proved here, supplies a concrete weighted-majority implementation of this rule: undecided mass receives weight \(0\), and each threshold class receives the weights specified in Weighted Majority Rule 4.
This mirror should be tractable—indeed, for fixed thresholds it is evaluated by a finite number of arithmetic operations on the mass vector, and its robust optimization formulation is a finite linear-fractional problem after normalizing \(d(P,Q)\). More importantly, the lower bound survives exactly: the paper’s one-dimensional adversarial constructions use fixed population fractions such as \(1/2\), so they are already continuous mass constructions in disguise. The continuous optimum should therefore be exactly \(D_\Theta\), not merely asymptotically close to it.
The regime is plausible in a referendum, public consultation, or platform election with millions of participants and two proposals. A type can represent a repeated issue-attitude cluster: the same ranking and the same coarse strength category, with standardized latent distances to the proposals. The number of report types is only \(2m+1\), or at worst a modest finite catalogue of full voter clusters, while the population is enormous. This is precisely the paper’s own interpretation of aggregate information: its mechanisms use counts of strength classes, and the text explicitly notes that aggregate threshold information is sufficient.
The second, broader anchor is Theorem 14, proved here. It considers multiple candidates, ordinal preferences, and one strength threshold \(\tau\). It forms a weighted majority graph using Weighted Majority Rule 1, then selects a candidate in the uncovered set. Its distortion is at most
\(\min\left\{ \max\left\{\frac{3\tau-1}{\tau+1},\frac{\tau+2}{\tau}\right\}+2,\; \max\left\{\left(\frac{3\tau-1}{\tau+1}\right)^2,\left(\frac{\tau+2}{\tau}\right)^2\right\} \right\}.\)
The corresponding continuous problem has a finite candidate set \(C\), and a mass distribution over voter types consisting of a complete ranking together with a strong/weak label for every candidate pair. For each pair \(P,Q\), strong supporters receive weight \((\tau+1)/(\tau-1)\) when \(\tau\geq1+\sqrt2\), and weight \(\tau\) otherwise; weak supporters receive weight \(1\). Pairwise winners are computed from masses, the weighted majority graph is formed, and the solution is any candidate in its uncovered set. The objective remains the worst-case ratio between that candidate’s integral social cost and the minimum integral social cost of an available candidate.
This is also Class A: the graph and uncovered set are computable in polynomial time in the number of candidates and supported voter types, and the proof of Theorem 14 transfers from sums to integrals. A natural further question is whether the continuous robust optimum can improve the paper’s bound, rather than merely reproduce its uncovered-set guarantee.
The paper’s authors should recognize both mirrors as their problem. Candidates remain discrete; only the population becomes a distribution. Preference strengths remain partial information, not utilities or known absolute costs. The metric uncertainty and the distortion objective are unchanged. This is not continuity in the outcome space, a probabilistic voting model, or a noise model.
The main weakness is that this paper contains no named NP-hardness, P-versus-NP, W[1]-hardness, or FPT result. Its named results are mechanism and approximation theorems, not complexity classifications. Consequently, this mirror cannot honestly be advertised as showing that discrete hardness dissolves in the continuum. For Theorem 19 especially, the continuous proof may look like a clean replacement of counts by masses. I would concede that. The positive claim is narrower: the paper provides a particularly well-formed Class A seed for continuous computational social choice, with an exact high-multiplicity formulation, an optimal two-candidate rule, and a natural open problem about instance-specific robust optimization and multi-candidate optimality.
The strongest negative case is that this paper contains no computational problem whose complexity changes when the population is made continuous. Its numbered results are distortion guarantees, lower bounds, and characterizations of voting rules—not complexity classifications, optimization algorithms, or hardness results. A continuous mirror can therefore be written, but it has no natural complexity landscape for ChoCo to chart.
Theorem 19 is the best-looking anchor, but it is already almost entirely an aggregate-count theorem. In the two-candidate setting, every relevant instance is summarized by the numbers \(|A_l|\), \(|B_l|\), and \(|C|\). Weighted Majority Rule 4 already operates only on those counts. Replacing them by masses \(\mu(A_l)\), \(\mu(B_l)\), and \(\mu(C)\) produces the same inequalities by normalization. The lower-bound constructions using halves of the population are indeed valid mass constructions, but that shows that the theorem has already discarded population granularity; it does not create a new continuous computational problem.
The proponent’s robust formulation does not repair this. If the latent type is \((r,z)\), where \(z\) contains absolute distances, then the proposed observable \(2m+1\) report classes are not complete voter types in the programme’s sense. They merge voters with different costs, even though those costs determine the objective. If \(z\) is included in the type, the type space is generally continuous and hidden from the mechanism. If it is omitted, the proposed problem is a distributionally robust mechanism-design problem over hidden metric completions, not the paper’s continuous-population version. Restricting \(z\) to a finite catalogue would be legitimate, but would introduce a new model and abandon the paper’s arbitrary-metric setting.
Nor does the robust optimization formulation yield a meaningful new algorithmic task here. The paper already optimizes over all metric completions in its worst-case distortion definition, and Theorem 19 already gives the optimal rule for every threshold profile. Computing an instance-specific robust winner is simply evaluating the same weighted inequalities. Calling that a finite linear-fractional program supplies a new encoding of the proof, not a population-continuization whose tractability depends on high multiplicity.
Theorem 14 has the same defect at a larger scale. A voter type consisting of a ranking and a strong/weak label for each pair is a perfectly reasonable repeated type. But the theorem’s algorithm already needs only pairwise aggregate support. The weighted majority graph is computed from sums of class counts, and the uncovered set is computed entirely on the candidate side. Replacing sums by integrals changes neither the input structure nor the computational task. The multi-candidate version retains no population-level combinatorics for continuization to dissolve.
A stronger mirror using exact preference-strength distributions does not help. It either produces integrals of the same per-voter weights—again a normalization of the existing proof—or includes absolute latent costs, in which case it becomes a new hidden-type robust optimization problem. Similarly, a mirror of “ideal candidate distortion” would principally continuize the candidate/outcome space through the hypothetical point \(Z^*\), which is outside the programme’s population-continuization target.
There is no valid objection based on multiplicity itself: referenda or platform elections with repeated attitude clusters are plausible high-multiplicity regimes, and social cost is additive rather than identity-dependent. Nor is the continuum degenerate. Thus the negative case cannot honestly claim that no coherent continuous model exists. Its narrower claim is that the proposed models are either a mass-normalized restatement of results already expressed through aggregate counts, or a new robust mechanism-design programme not anchored in a computational result of this paper. If ChoCo counts that new programme as worthwhile in its own right, Theorem 19 survives; under a stricter requirement of a genuine computational mirror, neither anchor earns one.
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.