d4-conf-atal-2015-0056

The strongest case I see is a mass-valued version of the paper’s weighted Copeland result.

Theorem 4, proved in this paper, says that for every fixed \(0\leq\alpha<1\), weighted manipulation under Copeland\(_\alpha\) is polynomial-time solvable in single-peaked elections, without bounding the number of candidates or manipulators. Voters have nonnegative integer weights, and the result holds in both the unique-winner and non-unique-winner models. The hardness results in the paper’s tables are credited to earlier work, rather than stated as numbered results proved here, so I would not use them as anchors.

Here is the continuous problem I would hand to a prover. Fix candidates \(C\), a target \(p\), a known left-to-right order \(L\), and a fixed rational \(\alpha\in[0,1)\). The nonmanipulating society is given by a support list of single-peaked rankings \(\succ_i\), each with rational mass \(\mu_i\). A strategic bloc has mass \(\beta\), with \(\sum_i\mu_i+\beta=1\). The bloc shares a target \(p\), sincere type, voting rights, and the same set of permitted reports: all rankings single-peaked with respect to \(L\). Choose rational masses \(x_\sigma\geq 0\), one for each permitted report \(\sigma\), with \(\sum_\sigma x_\sigma=\beta\). For each pair \(a,b\), compute
\[ Q(a,b)=\sum_i \mu_i\,\mathbf 1[a\succ_i b]+\sum_\sigma x_\sigma\,\mathbf 1[a\succ_\sigma b]. \]
The question is whether an allocation \(x\) makes \(p\) a Copeland\(_\alpha\) co-winner, using \(Q(a,b)>Q(b,a)\) for a win and equality for a tie. A solution is the allocation of the bloc’s mass among its permitted reports; it can be given as a sparse list of positive-mass reports.

This has a plausible high-multiplicity regime: a large election or organization-wide poll with a known left-right issue axis, many voters but relatively few distinct rankings, and a sizable coordinated bloc. The bloc might be party or union members following a common endorsement. Its size is meaningfully described as a fraction \(\beta\); its members share a type and objective, while the rest of society is represented by masses \(\mu_i\). That keeps the paper’s manipulation question intact: the decision is still whether strategic voters can make \(p\) win, and their reports obey the same single-peaked restriction.

I expect this mirror to be Class A, tractable. The bridge is unusually direct. Clear the rational denominators to obtain integer voter weights; scaling all weights by the same positive factor preserves every pairwise win and tie. If a successful continuous strategy splits the bloc among reports, the paper’s proof of Theorem 4 gives a successful strategy in which all manipulators use one common report. Thus the mass allocation can be replaced by putting all \(\beta\) on that report. The theorem’s weighted-median structure extends to rational masses, and its algorithm is polynomial in the candidate count, support size, and mass bit length.

The scope is only Theorem 4: strict single-peakedness and weighted Copeland\(_\alpha\) for \(\alpha<1\). This does not mirror Theorems 1–3 on bounded single-peaked width, Borda, or Maximin. A natural next question is whether the same mass formulation remains tractable when the known domain is widened to single-peaked width \(k>1\).

The soft spot is also clear: this continuous question is very close to the paper’s integer-weighted problem, and denominator scaling plus Theorem 4 largely settles it. That makes it a modest mirror rather than a new complexity frontier. Still, the paper gives a concrete, recognizable continuous-population question, and the fact that its answer is tractable is a meaningful bridge from weighted electorates to rational mass distributions.