The complexity of manipulative attacks in nearly single-peaked electorates

My strongest mirror is candidate control, anchored in Theorem 4.7.

Theorem 4.7, proved in this paper by reductions from X3C, states that both constructive control by adding candidates (CCAC) and constructive control by deleting candidates (CCDC) for plurality elections over swoon-SP societies are NP-complete. For CCAC, the input contains registered candidates \(C\), spoiler candidates \(A\), a plurality electorate whose votes are swoon-SP with respect to a societal axis \(L\), a preferred candidate \(p\in C\), and a bound \(K\). The question is whether at most \(K\) candidates from \(A\) can be added so that \(p\) becomes a winner. The paper proves this directly, using X3C: each set becomes a spoiler candidate, each universe element becomes a registered candidate, and carefully repeated vote blocks make \(p\) a winner exactly when the selected spoilers form an exact cover. The CCDC half similarly asks whether at most \(K\) candidates can be deleted to make \(p\) win, and is also proved NP-complete.

The continuous question I would put to the authors is:

Continuous Swoon-SP Plurality Candidate-Addition Control. An instance consists of disjoint finite candidate sets \(C\) and \(A\), a preferred candidate \(p\in C\), an integer \(K\), a societal axis \(L\) over \(C\cup A\), and a finite-support rational distribution \(\mu\) over complete rankings of \(C\cup A\). Every ranking in the support must be swoon-SP with respect to \(L\): after removing its top-ranked candidate, the remaining ranking must be single-peaked with respect to \(L\) with that candidate removed. For \(A'\subseteq A\), \(|A'|\le K\), restrict every ranking to \(C\cup A'\). Candidate \(c\) then receives plurality score

\[ \operatorname{sc}_{\mu,A'}(c) = \sum_{t:\operatorname{top}(t|_{C\cup A'})=c}\mu_t. \]

The question is whether there exists such an \(A'\) for which \(p\) maximizes this score. A solution is the selected candidate set \(A'\).

This is genuinely a population continuization. The mass \(\mu_t\) is the fraction of a large electorate having complete type \(t\); candidates remain indivisible, and the control action remains the integral choice of a candidate subset. Nothing about the outcome space, time, or axioms is being continuized. A finite election with repeated ballots is recovered by normalizing ballot multiplicities, while the continuous problem also permits arbitrary rational population proportions.

A convincing regime is a large political or platform electorate organized into recurring issue-position and demographic blocs. Millions of voters may share one of a relatively small number of complete ranking types. A “swoon” can represent a recurring bloc whose ordinary ordering follows the societal axis but whose top choice is determined by a salient candidate-specific consideration. Thus the relevant comparison is \(N\gg\tau\): many agents, but relatively few distinct ranking types. This is a much better high-multiplicity story than treating a seven-person committee as a continuum.

I would expect this problem to remain NP-hard, placing it in Class B. The hardness in Theorem 4.7 lives in the integral candidate-choice problem, not in the identities of individual voters. In the paper’s X3C construction, the many repeated voters can be collapsed into masses. For example, the \(2k\) voters associated with a set-element incidence become one type with mass \(2k\); the blocks of \(p\)-top, \(d\)-top, and \(b_i\)-top voters likewise become a small number of weighted types. After normalization, all plurality comparisons are unchanged. Selecting at most \(k\) spoiler candidates still corresponds exactly to selecting at most \(k\) sets, and \(p\) wins exactly when those sets form an exact cover. Thus the discrete hardness transfers upward to the continuous-population problem.

The mirror is plausible because it preserves every substantive ingredient of the paper’s problem: plurality, candidate entry, the target candidate, the societal axis, the swoon-SP restriction, and the winner condition. Only the population representation changes from a long list of voters to a distribution over voter types. The continuous version is therefore not a softened surrogate; it asks the same control question in the high-multiplicity regime.

This mirror covers the CCAC part of Theorem 4.7 emphatically. The same construction gives a CCDC mirror, with a distribution over swoon-SP rankings and an integral deletion set of size at most \(K\). Further questions include parameterized complexity in the number of ranking types, approximation when candidate control is allowed to be fractional or probabilistic, and whether hardness persists under a bounded number of swoon types.

The weakest point is that the continuous problem has an almost immediate embedding of the discrete problem: rational masses can encode repeated voters exactly. Consequently, this mirror is unlikely to make the problem tractable; its value is instead to show that continuization does not help when the combinatorics live in the candidate agenda. That is still a substantive ChoCo question, and precisely the Class B boundary the programme is meant to chart.