Where Are the Hard Manipulation Problems?

The strongest honest positive case is conditional: the paper has a natural continuous-population analogue, but it fails the programme’s formal anchor requirement.

The supplied text contains no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational result. Its relevant claims are prose summaries: the abstract says that STV manipulation is NP-hard; the introduction says that many voting rules are NP-hard to manipulate, citing [3]; and the final paragraph says that manipulating round-robin and cup tournaments is polynomial-time decidable, citing [12]. None is proved or stated as a named result in this paper. Thus there is no qualifying anchor to restate, and no fully compliant positive case can honestly be claimed.

If the anchor rule were relaxed to permit the paper’s prose-level claim about STV, my lead mirror would be:

Continuous STV Mass Manipulation. An instance consists of a finite candidate set \(C\), rational masses of sincere voter types \(\sigma_r\) indexed by rankings \(r\in S_C\), rational masses \(\rho_t\) of manipulable types, a preferred candidate \(c^\star\), and a fixed unique-winner or co-winner convention. A type records the voter’s truthful ranking and manipulability status; manipulable mass may report any ranking. A solution is a family of transfers \(x_{t,r}\ge 0\) satisfying
\[ \sum_{r\in S_C}x_{t,r}=\rho_t \]
for every manipulable type \(t\). The resulting ranking mass is
\[ \mu'_r=\sigma_r+\sum_t x_{t,r}. \]
The question is whether some feasible \(x\) makes \(c^\star\) win under the ordinary STV elimination rule applied to the weighted profile \(\mu'\).

This is a genuine population continuization of manipulation, not a change to fractional outcomes: candidates remain discrete, STV remains unchanged, and only the electorate becomes a distribution. The natural regime is a large platform, membership organisation, or mass election with millions of voters but relatively few recurring preference and eligibility templates. A campaign can influence a fraction of a homogeneous segment rather than target named individuals. That is precisely a high-multiplicity interpretation.

The authors would recognise the question: it asks whether a preferred candidate can be made to win by changing the reports of a manipulable coalition. The only change is that the coalition is represented by mass transfers rather than an explicit list of voters. For rational masses, finite elections embed directly by setting \(\sigma_r=n_r/n\) and \(\rho_t=k_t/n\); conversely, rational continuous solutions can be scaled to a finite electorate after clearing denominators.

I would expect this problem to be Class B when the number of candidates is variable: the combinatorics of STV elimination remain, and discrete manipulation instances embed into the continuous model. There is also a useful positive possibility: for fixed \(m=|C|\), one can enumerate elimination orders and express the conditions for each order as a linear program over the transfer variables. Thus the continuous model may expose an \(m\)-parameterized tractable regime even where the general problem remains hard.

The weakest point is decisive: this mirror is anchored only to an informal claim in a tutorial, not to a named result proved in the paper. A second vulnerability is that divisibility may dissolve hardness caused by individual coalition structure. The case survives only if the relevant hardness is genuinely in the candidate/elimination structure rather than in identity-level constraints. I would therefore record the paper as having a plausible continuous mirror, but no admissible computational anchor under ChoCo’s stated rules.