Hybrid Elections Broaden Complexity-Theoretic Resistance to Control

The strongest positive case is a Kemeny-based mirror. It is a genuine population continuization: the voters become a distribution over complete rankings, while the candidate-control action remains discrete.

My lead anchor is Theorem 2.4. The paper states that, for each of Dodgson, Kemeny, and Young elections, constructive control by adding candidates, deleting candidates, adding voters, and deleting voters is \(\Theta_2^p\)-hard. The theorem is derived in this paper from the cited \(\Theta_2^p\)-hard winner results and the observation that winner determination is a zero-budget special case of several control problems; the underlying winner hardness is therefore imported from earlier work rather than newly reduced here.

I would mirror its Kemeny-deletion entry as follows.

Call the problem Continuous Constructive Kemeny Candidate-Deletion Control. An instance consists of a finite candidate set \(C\), a target candidate \(c\in C\), an integer \(k<|C|\), and a rational society distribution \(\mu\) over the complete rankings \(T_C\) of \(C\). Thus \(\mu_\rho\) is the fraction of the electorate whose ranking is \(\rho\), with \(\sum_{\rho\in T_C}\mu_\rho=1\).

For every candidate set \(C'\subseteq C\), define the weighted Kemeny objective by minimizing \(\sum_{\rho\in T_{C'}}\mu_\rho d_{\mathrm{KT}}(\pi,\rho)\) over rankings \(\pi\) of \(C'\), where the rankings and the masses are restricted to \(C'\). A candidate is a Kemeny winner if it is first in some optimal ranking; \(c\) is the unique winner if it is the only candidate that can be first in an optimum.

The question is whether there exists \(D\subseteq C\setminus\{c\}\), with \(|D|\leq k\), such that \(c\) is the unique Kemeny winner on \(C\setminus D\). Equivalently, the optimization version asks for the minimum number of candidates whose deletion makes \(c\) the unique winner.

This is a natural high-multiplicity regime. Imagine a very large platform ranking products, pages, or policies, where millions of users generate only a comparatively small collection of recurring complete rankings. Agents of the same type have exactly the same preference order; mass is their population fraction. The chair deletes alternatives, not individual voters, so the model does not fractionalize the outcome or the intervention. It only replaces the explicit voter list by its aggregate distribution.

The discrete-to-continuous correspondence is exact. If a finite election has \(n_\rho\) voters of ranking type \(\rho\), set \(\mu_\rho=n_\rho/n\). For every candidate subset and every consensus ranking, the weighted Kemeny objective is the ordinary objective divided by \(n\): \(\sum_\rho \mu_\rho d_{\mathrm{KT}}(\pi,\rho)=\frac1n\sum_{v}d_{\mathrm{KT}}(\pi,v)\). Hence the optimal rankings, winner set, and every legal candidate-deletion solution are unchanged. The discrete Kemeny control instance is therefore a special case of the continuous problem.

I expect hardness to transfer, placing this mirror in Class B rather than Class A: the relevant combinatorics live in the candidate agenda and the competing consensus rankings, not in the multiplicity of individually named voters. In particular, the continuous problem is at least \(\Theta_2^p\)-hard under the direct embedding supplied by Theorem 2.4. The interesting follow-up questions are whether the weighted distributional version has the same upper bound, how its complexity depends on \(m\), the support size \(\tau\), and the bit length of \(\mu\), and whether approximation or parameterization by \(k\) changes the picture.

A second, more direct mirror of the paper’s hybridization result is Continuous Hybrid-Kemeny-Plurality Candidate-Deletion Control. This uses the paper’s hybrid scheme with two constituents: Kemeny as \(\election_0\) and plurality as \(\election_1\). On a candidate set \(C\), the rule uses weighted Kemeny if every candidate name is even; otherwise it uses weighted plurality. Plurality gives candidate \(a\) score \(\sum_{\rho:\operatorname{top}(\rho)=a}\mu_\rho\), and the maximum-score candidates win.

The instance and question are otherwise identical: given \((C,c,k,\mu)\), is there a set \(D\subseteq C\setminus\{c\}\) of at most \(k\) candidates whose deletion makes \(c\) the unique winner under this hybrid rule? The objective is again to minimize \(|D|\).

The anchor here is Theorem 3.3, proved in the paper. It says that for any of the twenty standard constructive or destructive control types, if at least one constituent is candidate-anonymous and resistant to that control type, then the hybrid is resistant as well. The proof maps every candidate name \(x\) to \(kx+i\), forcing the hybrid to route the instance to constituent \(\election_i\); this is a polynomial many-one reduction from the constituent’s control problem.

Kemeny is candidate-anonymous, and its candidate-deletion problem is \(\Theta_2^p\)-hard by Theorem 2.4 and susceptible—for example, deleting all competitors can leave the target alone. Thus it supplies the resistant constituent required by Theorem 3.3. Given any discrete Kemeny instance, relabel every candidate by twice its old name. Every remaining candidate is still even after deletion, so the continuous hybrid behaves exactly as weighted Kemeny. Consequently this hybrid mirror inherits at least the same \(\Theta_2^p\)-hardness, and certainly the NP-hardness asserted by Theorem 3.3.

The paper’s authors should recognize both questions as their problems: the voter model is their election model compressed into type masses, Kemeny is their underlying rule, candidate deletion is unchanged, and the second question uses their own modulo-based hybrid mechanism. This is not a collision with the paper, since the paper never makes the society itself continuous or studies rational population distributions.

The weak point is that the Kemeny mirror does not make control fractional: continuity compresses the electorate but leaves the hard candidate-level decision intact. An opposing analyst can fairly say that this demonstrates a high-multiplicity reformulation more than a new tractability phenomenon. The hybrid’s parity switch is also artificial. But those are limitations of the scope, not failures of the mirror. The programme explicitly allows Class B outcomes, and this example gives a precise, socially intelligible continuous-population question whose hardness survives for the principled reason that its combinatorics live in the alternatives rather than in named voters.