| paper | On the Distortion of Voting With Multiple Representative Candidates |
| authors | Yu Cheng, S. Dughmi, D. Kempe |
| venue | AAAI 2018 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
None of the named results has the required computational character: they are analytic distortion characterizations or bounds. The proposed evaluation of \(\Phi(V,T,d,\mu,n)\) is a reasonable computational sequel, but the paper already defines the society by a distribution \(q\) and the corresponding expected distortion. It therefore does not continuize a discrete population or mirror a computational result of this paper.
fails bit a — no named computational result to mirror
Theorem 3.1, Corollary 3.2, Lemma 3.3, and the paper's rule-specific distortion consequences are analytic results; no qualifying computational result is covered.
The strongest honest conclusion is qualified: there is a natural high-multiplicity computational problem here, but this paper does not contain a qualifying computational anchor. Worse for a positive case, its voter population is already continuous: Section 2 defines a density \(q\) over metric locations, explicitly allows point masses, and says that finite or countable voter sets are merely cosmetic variants.
The closest possible anchor is Theorem 3.1, proved in this paper. It states that a positional voting system \(V=(g_n)_{n\ge 1}\) has constant expected distortion—uniformly over the metric space and the number \(n\) of i.i.d. representative candidates—if and only if there are constants \(n_0\) and \(y\in(0,1)\) such that, for every \(n\ge n_0\),
\[ y\sum_{k=0}^{\lceil y(n-1)\rceil-1} \bigl(g_n(k)-g_n(\lceil y(n-1)\rceil)\bigr) > (1-y)\sum_{k=n-\lceil y(n-1)\rceil}^{n-1} \bigl(1-g_n(k)\bigr). \]
Corollary 3.2, also proved here, says that for a consistent positional system with limit scoring rule \(g\), nonconstancy of \(g\) on \((0,1)\) implies constant expected distortion, whereas if \(g\) is constant there with value other than \(1\), expected distortion is not constant. Thus Borda and \(k\)-approval with \(k=\Theta(n)\) have constant expected distortion, while Plurality, Veto, Dowdall, and \(k\)-approval with \(k=o(n)\) have super-constant distortion. Lemma 3.3 gives the universal upper bound \(n+1\) for every positional or non-positional voting system with \(n\) representative candidates.
These are substantial analytic results, but they are not results about membership in P, NP-hardness, approximation algorithms, parameterized complexity, or computation of an underlying optimization problem. The paper contains no named computational result of the kind required by the continuization programme. The cited hardness and distortion literature cannot repair that gap.
The strongest charitable mirror would therefore be the following new problem.
Finite-Support Continuous Representative-Distortion Evaluation. An instance consists of a finite metric type space \(T\), rational masses \(\mu_t\) summing to \(1\), rational distances \(d(t,t')\), a positional rule \(g_n\), and a candidate count \(n\). A type is a complete metric location: all voters of type \(t\) have mass \(\mu_t\), identical distances to every possible candidate type, and therefore identical rankings in every realised slate. A slate \(C=(t_1,\ldots,t_n)\) is sampled independently from \(\mu\), exactly as in the paper’s representative-candidate model.
For a realised slate, voters rank candidates by distance. The voting rule selects \(w(C)\). The social cost of a candidate of type \(t_i\) is
\[ c_\mu(t_i)=\sum_{t\in T}\mu_t d(t,t_i), \]
and \(o(C)\) is the minimum-cost candidate in the slate. The task is to compute, exactly or within a specified approximation guarantee,
\[ \Phi(V,T,d,\mu,n) = \mathbb E_{C\sim\mu^n} \left[ \frac{c_\mu(w(C))}{c_\mu(o(C))} \right]. \]
A natural decision version asks whether \(\Phi\le K\). This keeps the population continuous while retaining integral candidate slots and the paper’s i.i.d. representative-candidate mechanism; it is not an outcome-space relaxation.
The regime is plausible for a large electorate consisting of many repeated spatial or ideological types—say, millions of residents concentrated in a moderate number of neighbourhood-position types—while the number \(\tau=|T|\) is small relative to the population. Mass is the fraction of residents of each type, not an attempt to target named individuals.
I would expect the bounded-\(\tau\) version to be Class A. With fixed tie-breaking, the realised distortion depends on the candidate type-count vector \(\kappa\), and there are \(\binom{n+\tau-1}{\tau-1}\) such vectors. Enumerating them and weighting each by its multinomial probability gives an exact algorithm polynomial in \(n\) for fixed \(\tau\). Theorem 3.1 and Corollary 3.2 would then serve as uniform performance guarantees for the computed expectation. The genuinely interesting open question is whether exact or approximate evaluation is fixed-parameter tractable, or polynomial in \(\tau\), when the type space is part of the input.
The weakest point is decisive: this is a new computational layer placed on top of a model the paper already presents as continuous. It is therefore a credible ChoCo research direction, but not a strong mirror of a computational theorem in this paper. A referee would likely recognise the problem as a natural computational sequel to Cheng–Dughmi–Kempe, not as a continuization of one of their named computational results.
The strongest negative case is structural: this paper has no qualifying computational anchor, and its population is already continuous.
Theorem 3.1 is an asymptotic characterization of a sequence of scoring rules \((g_n)_{n\ge 1}\). It has no finite input instance, computational task, complexity claim, or algorithm to continuize. Corollary 3.2 merely interprets that characterization through the limiting scoring rule \(g\). Lemma 3.3 is an analytic bound on expected distortion. All three concern the number of candidates and the geometry of the metric space, not a discrete population whose multiplicity could be replaced by mass.
The proposed evaluation problem does not repair this. Taking a finite metric type space \(T\) with masses \(\mu_t\) is already an instance of the paper’s model: choose \(\Omega=T\), give location \(t\) point mass \(\mu_t\), and the paper’s integral becomes
\[ c_\mu(t_i)=\sum_{t\in T}\mu_t d(t,t_i). \]
The paper explicitly allows point masses and says finite or countable voter sets are merely cosmetic variants. Thus \(\Phi\) is the computational evaluation of an expectation already defined in the paper, not a continuous-population mirror of a discrete computational problem. If \(\mu_t=n_t/N\), it is simply the empirical distribution of a finite electorate; if \(T\) is uncountable, one has returned to the paper’s original model.
Exact or approximate computation of
\[ \mathbb{E}_{C\sim\mu^n} \left[\frac{c_\mu(w(C))}{c_\mu(o(C))}\right] \]
could be a worthwhile computational sequel. But it adds an algorithmic layer to an already-continuous analytic model; it does not continuize the population. Its parameter \(\tau\) measures the support used to encode \(q\), while \(n\) is the number of sampled candidates, not population multiplicity. Calling this a mirror would therefore confuse “computing the paper’s quantity” with “replacing a discrete society by a continuous one.”
The stronger alternatives fail for the same reason. A continuum of candidate locations changes the candidate side rather than the population side. A high-multiplicity electorate is already represented by the paper’s point-mass distributions. A decision problem about whether a scoring-rule family has constant expected distortion would concern the rule family, not continuization of society. Adding robustness, optimization, or design would produce new research questions rather than mirrors of the stated results.
So the honest conclusion is not that the proposed expectation problem is useless. It may be interesting. The conclusion is narrower but decisive for ChoCo: this paper already performs the relevant population continuization, while providing no named computational result whose discrete version can be mirrored. Any worthwhile computational project built around it is a sequel to the paper’s continuous model, not a continuous mirror of the 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.