How Hard is Control in Single-Crossing Elections?

The strongest honest positive case is Theorem 3, proved in this paper. It states that, for single-crossing elections, both constructive plurality control by adding candidates, Plurality-CCAC, and constructive plurality control by deleting candidates, Plurality-CCDC, are in \( \mathrm{P} \). More explicitly: given a designated candidate \(p\), a bound \(k\), and a single-crossing election, one can decide in polynomial time whether adding at most \(k\) unregistered candidates, or deleting at most \(k\) candidates other than \(p\), can make \(p\) the unique plurality winner. The theorem is proved here, by reducing both problems to the exact-cardinality candidate-addition algorithm of Theorem 2, which in turn uses the dynamic programme of Theorem 1. I will use the CCAC half of Theorem 3 as the lead anchor; the CCDC half is an immediate parallel mirror.

Call the continuous problem \( \mathrm{SC}\text{-}\mathrm{Plurality}\text{-}\mathrm{CCAC}_{\infty} \). An instance consists of a candidate set \(C\), a set \(A\) of unregistered candidates, a preferred candidate \(p\in C\), an integer \(k\), and a finite ordered list of complete ranking types
\[ t_1\prec t_2\prec\cdots\prec t_\tau \]
over \(C\cup A\). Type \(t_i\) has rational mass \(\mu_i\ge 0\), with \(\sum_i\mu_i=1\). The order is required to witness single-crossing: for every pair \(a,b\), the types preferring \(a\) to \(b\) form a prefix or suffix of this order. Equivalently, realise the society as the unit interval \([0,1]\), partitioned into consecutive intervals of lengths \(\mu_1,\ldots,\mu_\tau\), with every voter in the \(i\)-th interval having ranking \(t_i\).

The question is whether there exists \(S\subseteq A\), with \(|S|\le k\), such that \(p\) is the unique plurality winner after the candidates in \(S\) are added. For each \(c\in C\cup S\), its score is
\[ \operatorname{pl}_{\mu,S}(c) = \sum_{i=1}^{\tau} \mu_i\, \mathbf{1}\!\left[c=\operatorname{top}_{t_i}(C\cup S)\right]. \]
A solution is the set \(S\) together with the strict inequalities
\[ \operatorname{pl}_{\mu,S}(p) > \operatorname{pl}_{\mu,S}(c) \qquad \text{for every }c\in (C\cup S)\setminus\{p\}. \]

This is a genuine population continuization, not a fractional-candidate or probabilistic-outcome problem. Candidates remain indivisible and the control action is exactly the paper’s action. What becomes continuous is the electorate: one may have millions of residents but only a few dozen or few hundred ranking blocks, with \(\mu_i\) recording the fraction of the population in each block. Clearing denominators recovers a finite high-multiplicity election exactly. Conversely, a finite election with \(n_i\) voters of type \(t_i\) yields \(\mu_i=n_i/\sum_j n_j\).

A convincing scenario is a large tax or public-policy election. Voters are ordered by income, ideology, or another one-dimensional policy parameter; within broad socioeconomic cohorts, voters have the same ranking over the available candidates. A ballot authority may decide which parties or candidates are allowed onto the ballot, subject to a registration limit \(k\). The electorate is genuinely large, while the number of distinct ranking types is small. This is especially natural here because the paper itself connects single-crossing to the continuous domains of Mirrlees and Roberts. The continuous ordered population is therefore close to the authors’ motivating interpretation, not an unrelated application.

I would expect \( \mathrm{SC}\text{-}\mathrm{Plurality}\text{-}\mathrm{CCAC}_{\infty} \) to be in Class A. The visibility intervals used in Lemma 1 and Theorems 1–2 remain intervals of type blocks. The dynamic programme can replace every voter count by the rational mass of the corresponding blocks. Its states still track candidate positions, the number of candidates selected, and interval endpoints; only the score values become sums of rational numbers. The reductions in Theorem 3 then remain valid, with running time polynomial in \(m\), \(\tau\), \(|A|\), and the bit length of the masses. The important point is that single-crossing still supplies the structural reason for tractability: arbitrary candidate subsets remain an integral search problem, while the ordered population makes their plurality effects dynamically composable.

The paper contains no comparable hardness theorem proved by its authors. The \(\mathrm{NP}\)-completeness statements for unrestricted elections in Table 1 are attributed to earlier work, so I would not falsely present them as a second hardness anchor. The present case therefore covers the paper’s positive single-crossing result, not its entire complexity table.

The weakest point is that population mass is passive in this lead mirror: the decision variable is still the set \(S\) of candidates, not a mass transfer. A sceptical referee could call this a weighted, succinct representation of the paper’s problem rather than a continuum-native optimization problem. I would concede that it is scientifically modest, and I would not claim that it creates a new pricing problem or a continuum-specific complexity class. But it remains a faithful high-multiplicity mirror: the society is now the continuous object, the single-crossing order is preserved, candidate control is unchanged, and the paper’s central structural phenomenon—polynomiality caused by single-crossing—survives the change of population representation.

The mirror naturally generates stronger follow-up questions. One is \( \mathrm{SC}\text{-}\mathrm{Plurality}\text{-}\mathrm{CCDC}_{\infty} \), obtained by choosing a set of at most \(k\) candidates to delete. Another is a continuous Young problem: find the minimum mass of voters that must be removed for a given candidate to become a Condorcet winner. That latter problem is likely tractable by linear programming or weighted median calculations, although the single-crossing structure may become less essential once voter deletion is fractional. Finally, one can ask for the minimum population mass whose removal changes the plurality winner, giving a continuous winner-robustness problem directly related to the paper’s control setting.