| paper | The Distortion of Distributed Voting |
| authors | Aris Filos-Ratsikas, Evi Micha, A. Voudouris |
| venue | SAGT 2019 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm{P}\)); every valid instance admits a districting in which \(\theta\) wins all \(k\) districts. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6.2
statement extracted from the paper’s text layer
Given \(m\) alternatives, \(k\ge2\) equal-mass districts, finite valuation types \(T\) with rational masses \(\mu_t\) summing to \(1\) and unit-sum vectors \(v_t\), and aggregate Range Voting winner \(\theta\), choose \(x_{t,d}\ge0\) satisfying \(\sum_d x_{t,d}=\mu_t\) and \(\sum_t x_{t,d}=1/k\); each district elects an alternative maximizing \(\sum_t x_{t,d}v_{t,a}\), and decide whether \(\theta\) wins the final election by district-win count.
A finite distribution \(\mu\) over complete cardinal valuation types \(v_t\), with mass-assignment variables \(x_{t,d}\) forming equal-mass districts; the objective is feasibility of making the aggregate Range Voting winner \(\theta\) win the final district-count vote.
The opponent correctly observes that proportional assignment makes the entire continuous problem a generic feasibility construction, so the paper contributes no nontrivial continuous districting landscape; this limits informativeness but does not invalidate the faithful question.
fatal: False
It covers the Range Voting best-case symmetric-districting problem behind Theorems 6.1–6.3, including the disappearance of their discrete obstruction; it leaves the worst-case distortion results, Plurality districting results, experiments, and other rules untouched.
The strongest mirror is the paper’s best-case districting problem for Range Voting.
My lead anchor is Theorem 6.2, proved in this paper by reduction from constrained Partition. It states: when \(n\le m\), for every \(k\ge2\), deciding whether there exists a symmetric \(k\)-districting such that the socially optimal alternative wins the district-based election, with Range Voting used locally, is NP-complete. The input consists of \(n\) voters, \(m\) alternatives, and cardinal unit-sum valuations; the districts must have equal size, each district elects its welfare-maximizing alternative, and the alternative winning the most districts is the final winner.
A natural continuous counterpart is:
Continuous Optimal-RV Districting. An instance consists of \(m\) alternatives, \(k\) equal-mass districts, and finitely many valuation types \(t\in T\). Type \(t\) has a rational unit-sum valuation vector \(v_t\in\mathbb{Q}^m\) and population mass \(\mu_t\), with \(\sum_t\mu_t=1\). Let \(\theta\) be the aggregate Range Voting winner, so \(\theta\in\arg\max_a\sum_t\mu_t v_{t,a}\). The decision variable is \(x_{t,d}\), the mass of type \(t\) assigned to district \(d\). It must satisfy \(\sum_d x_{t,d}=\mu_t\) and \(\sum_t x_{t,d}=1/k\). District \(d\) elects \(r_d\in\arg\max_a\sum_t x_{t,d}v_{t,a}\), using a fixed tie-breaking rule. The question is whether there exists such an assignment for which \(\theta\) wins the final election, namely, receives the largest number of district victories.
This is exactly the paper’s underlying problem with voters replaced by a distribution over complete valuation types. The alternatives remain discrete, local winners remain discrete, and the final aggregation still counts district victories. Only the population is continuized. The action is still districting; \(x\) records mass assigned to districts, not fractional alternatives or fractional utility.
In the high-multiplicity regime, this problem is immediately tractable. Assign every type proportionally to every district: \(x_{t,d}=\mu_t/k\). Then every district has the same composition as the whole population, and its score for alternative \(a\) is \(\frac1k\sum_t\mu_t v_{t,a}\). Consequently every district elects the aggregate Range Voting winner \(\theta\), so \(\theta\) wins all \(k\) districts. The continuous problem is therefore always a “yes” instance, solvable by constructing this assignment in polynomial time.
That is not a change of question that merely makes it easy. It identifies precisely what the discrete NP-hardness is exploiting: an individual number-voter in the reduction must be placed wholly in one district. In the continuum, a large cohort of identical voters can be divided across districts while every individual still receives one district assignment. The constrained-Partition obstruction disappears because population mass is divisible. This is a clean Class A outcome and a useful negative result about hardness transfer: Theorem 6.2’s hardness does not survive as population multiplicity is removed.
The regime is plausible for a large association, federation, or deliberative organization with many members but relatively few repeated utility profiles—for example, members grouped by department, profession, or standardized survey response. If \(N\gg |T|\), with \(\mu_tN\) members of each type, proportional assignment is the natural high-multiplicity operation. For denominators divisible by \(k\), it can be implemented exactly in the discrete model; otherwise it can be rounded, with vanishing score error as \(N\) grows.
The same mirror also covers the \(n>m\) hardness result, Theorem 6.3, proved here for \(k\ge5\): its continuous version has the same proportional solution. It also explains why the impossibility in Theorem 6.1 is specifically an indivisibility phenomenon: although the discrete paper constructs instances where no symmetric districting lets the optimal alternative win, proportional type-splitting makes the aggregate optimum win every continuous district.
The weakest point is that the paper’s reductions use many item-specific voter types, so their instances are not themselves high-multiplicity societies: the number of distinct types tracks the number of voters. Thus I am not claiming that the paper has already supplied a hard continuous instance. The claim is narrower: the paper’s best-way districting question has a faithful, socially plausible high-multiplicity mirror, and in that mirror the discrete hardness dissolves for a transparent structural reason. If districts must respect geography, eligibility, or indivisible organizational units, this mirror would no longer be appropriate; those constraints would generate the next, genuinely nontrivial continuous problem.
The strongest negative case is that all three anchors collapse for the same reason. In the proposed continuous model, for every type \(t\) and district \(d\), assign
\[ x_{t,d}=\frac{\mu_t}{k}. \]
Every district then has exactly the population composition of the whole society, scaled by \(1/k\). Hence its Range score is
\[ \sum_t x_{t,d}v_{t,a} =\frac{1}{k}\sum_t\mu_t v_{t,a}. \]
If \(\theta\) is the aggregate Range winner, \(\theta\) therefore wins every district under the same tie-breaking rule. This works for every \(m\), \(k\), and type space—even a continuous one, using the product measure \(\mu\otimes\mathrm{Unif}([k])\).
That defeats Theorems 6.2 and 6.3 as computational mirrors. Their NP-hardness is entirely the difficulty of placing indivisible number-voters into whole districts. Once mass can be divided, the constrained-Partition gadget disappears completely. The continuous problem has no remaining optimization, pricing problem, parameter dependence, or hard instances: every instance is accepted by the same product construction. Calling this a Class A result is formally defensible, but it is a generic coupling observation, not a continuous districting landscape specific to this paper.
Theorem 6.1 fares no better. Its impossibility instances become immediate yes-instances under the same assignment. Strengthening the mirror to require strict local victories does not help: whenever \(\theta\) strictly wins in aggregate, every proportional district gives it the same positive margin divided by \(k\). Requiring geographic contiguity, district eligibility, or indivisible organizational cohorts could restore a nontrivial problem, but those are additional constraints absent from the paper. If cohorts may no longer be split, the computational object is again a finite packing problem; if geography is added, the result is a new geometric districting problem rather than a mirror of Theorems 6.1–6.3.
The proposed high-multiplicity scenario does not rescue the anchor. A large organization with repeated valuation types is precisely the setting in which proportional assignment is easiest to implement: with sufficiently many members, assign \(\mu_tN/k\) members of each type to every district. Rounding only produces a finite approximation to an already trivial continuous construction.
This is therefore a genuine weakness in the paper as a source for ChoCo: its best computational results concern indivisible districting, while continuization removes the entire object those results analyze. The honest qualification is that the proponent’s construction is mathematically valid and could count as a modest Class A boundary result—“population divisibility destroys this hardness.” I cannot honestly claim that no reader could find that worthwhile. But it does not provide the nontrivial continuous-computational mirror the programme is seeking; any interesting rescue requires adding structure that belongs to a different problem.
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.