The Distortion of Distributed Voting (d4-conf-sagt-2019-0022)

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 society is given by its support: the list of \(\tau\) valuation types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type has a binary rational vector \(v_t\in\mathbb{Q}_{\ge0}^{m}\) satisfying \(\sum_a v_{t,a}=1\), with \(m\ge2\).
Input also includes an integer \(k\ge2\), encoded in unary, and a fixed priority order on alternatives. Let \(\theta\) be the highest-priority maximizer of \(\sum_t\mu_t v_{t,a}\).
A districting consists of real masses \(x_{t,d}\ge0\), for \(d\in\{1,\ldots,k\}\), satisfying \(\sum_d x_{t,d}=\mu_t\) and \(\sum_t x_{t,d}=1/k\); types may be split freely across districts.
District \(d\) elects the highest-priority maximizer \(j_d\) of \(\sum_t x_{t,d}v_{t,a}\). Each district contributes one vote. Decide whether some districting satisfies \(|\{d:j_d=\theta\}|>|\{d:j_d=a\}|\) for every \(a\ne\theta\), so that \(\theta\) wins regardless of final tie-breaking.
Let \(L\) be the total binary bit length of the masses, valuations, and priority order; state running times in \(m,\tau,k,L\).

Is this continuous districting decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For indivisible voters, the corresponding symmetric Range Voting districting problem is NP-complete for every fixed \(k\ge2\), even when the number \(n\) of voters satisfies \(n\le m\). [Source](https://repository.essex.ac.uk/27911/1/1905.01882.pdf).
No result settling exactly the continuous decision problem above was located in the literature search.

Result

The problem is in \(\mathrm{P}\). In fact, every valid instance is a yes-instance: proportional splitting makes \(\theta\) win every district. This applies to arbitrary supports and valuation profiles, including national ties.

Proof

For each alternative \(a\), define its national score by \(S_a=\sum_{t=1}^{\tau}\mu_t v_{t,a}\). By hypothesis, \(\theta\) is the highest-priority alternative among those maximizing \(S_a\).

Assign \(x_{t,d}=\mu_t/k\) for every type \(t\) and every district \(d\).

Feasibility. Each assigned mass is nonnegative. For every type \(t\), its total assigned mass is \(\sum_{d=1}^{k}x_{t,d}=k(\mu_t/k)=\mu_t\). For every district \(d\), its total mass is \(\sum_{t=1}^{\tau}x_{t,d}=(1/k)\sum_{t=1}^{\tau}\mu_t=1/k\). Thus all districting constraints hold.

District winners. The score of alternative \(a\) in district \(d\) is \(\sum_{t=1}^{\tau}x_{t,d}v_{t,a}=S_a/k\). Since \(1/k\) is positive, the district score vector has exactly the same comparisons and ties as the national score vector. Every district therefore has the same set of score maximizers as the nation. Applying the stipulated common priority order gives \(j_d=\theta\) in every district.

Consequently, \(\lvert\{d:j_d=\theta\}\rvert=k\), whereas \(\lvert\{d:j_d=a\}\rvert=0\) for every \(a\ne\theta\). Since \(k\ge2\), the required strict inequalities hold. This proves the claim.

Running time and exact representation

On the promised domain of valid inputs, the decision algorithm simply returns yes. Its running time is \(O(1)\) after receiving the input, or \(O(L+k)\) if reading the entire input is included.

The witness also has polynomial size. Write each input mass as \(\mu_t=p_t/q_t\), with positive integers \(p_t,q_t\). Represent \(x_{t,d}\) exactly as \(p_t/(kq_t)\); reduction to lowest terms is unnecessary. The explicit table of \(\tau k\) entries has total bit length \(O(kL+\tau k\log(k+1))\). Using elementary integer arithmetic, a conservative construction-time bound is \(O(L+k+\tau k(L+\log(k+1))^2)\).

Computing \(\theta\) is unnecessary for the decision or the construction. If its identity is also requested, exact national-score computation and priority-based comparisons take \(O(m\tau L^2)\) bit operations using elementary arithmetic.

Relation to indivisible districting

The [cited paper](https://repository.essex.ac.uk/27911/1/1905.01882.pdf) models districting by partitioning individual voters. The proportional assignment above relies on the explicit permission to split every type freely. Hence the indivisible hardness result does not obstruct this construction.

The stated continuous problem is completely resolved; obtaining a nontrivial feasibility question would require an additional restriction that excludes proportional splitting.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover fully resolves the task. Every valid instance admits the stated districting, and the decision problem is in \(\mathrm{P}\). No major or minor issues were found.

Step-by-step verification

• Scope and quantifiers. The construction applies to every support and valuation profile allowed by the task. It does not require any restriction on \(m\), \(\tau\), the valuation denominators, or the national score ties. Freely splitting each type is explicitly permitted.

• Feasibility. The assignment \(x_{t,d}=\mu_t/k\) is well-defined and positive because \(\mu_t>0\) and \(k\ge2\). The two required equalities are correctly checked:

\[ \sum_{d=1}^{k}x_{t,d}=\mu_t, \qquad \sum_{t=1}^{\tau}x_{t,d}=\frac1k. \]
Thus neither the type masses nor the district capacities are violated.

• District scores. Substitution into the district score formula correctly gives

\[ \sum_{t=1}^{\tau}x_{t,d}v_{t,a} =\frac1k\sum_{t=1}^{\tau}\mu_t v_{t,a} =\frac{S_a}{k}. \]
This identity holds for every alternative and every district.

• Comparisons and tie-breaking. Multiplication by the positive number \(1/k\) preserves all strict comparisons and equalities. Consequently, the district maximizer set equals the national maximizer set. The task stipulates the same fixed priority order, so the selected winner is indeed \(\theta\) in every district. National ties cause no gap.

• Strict final victory. The resulting district counts are \(k\) for \(\theta\) and zero for every other alternative. Since \(k\ge2\), all required strict inequalities hold. The argument establishes the requested victory regardless of final tie-breaking.

• Decision running time. Returning yes without examining the profile is valid on the explicitly promised domain of valid inputs. The stated \(O(1)\) decision time and \(O(L+k)\) bound when reading the input are consistent with the binary data and unary encoding of \(k\). The prover does not claim that malformed inputs can be validated in constant time.

• Witness representation and construction. The rational representation \(p_t/(kq_t)\) is exact; lowest-term reduction is unnecessary. Repeating each mass in \(k\) districts multiplies the original mass-encoding contribution by \(k\), and the denominator multiplication introduces \(O(\log(k+1))\) additional bits per entry. Thus

\[ O\!\left(kL+\tau k\log(k+1)\right) \]
is a valid total-size bound. The stated construction-time bound using elementary integer arithmetic is conservative and polynomial in the requested parameters.

• Optional computation of \(\theta\). The bound \(O(m\tau L^2)\) is also conservative. For each alternative, exact accumulation of its rational score uses intermediate numerator and denominator lengths bounded by \(O(L)\); elementary arithmetic therefore supports the claimed bound. Priority-based comparisons fit within it. This optional computation is not needed for the decision or the witness construction.

• Relation to the cited model. The cited paper explicitly models districts as a partition of individual voters, with symmetric districts containing equal voter counts. This supports the prover’s distinction between indivisible districting and the freely splittable model here. No hardness theorem from that paper is used in the proof. [Source: *The distortion of distributed voting*](https://repository.essex.ac.uk/27911/1/1905.01882.pdf).

Actionable feedback

No repair or additional clarification is necessary. The universal construction, feasibility verification, treatment of ties, strict victory condition, and polynomial bounds all stand as written.

⟨structured verdict parsed — rendered above⟩