Weighted electoral control

The strongest positive case is a high-multiplicity version of weighted constructive control by deleting voters under \(2\)-approval. I would call it Continuous \(2\)-Approval Weighted Voter Deletion.

The paper’s anchor is Theorem 4.13, proved in this paper. It states that WCCAV for \(2\)-veto and \(3\)-approval, and WCCDV for \(2\)-approval and \(3\)-veto, are NP-complete when the number of candidates is unbounded. Its proof gives the stronger restriction that WCCDV for \(2\)-approval remains NP-complete when every voter weight belongs to \(\{a,b\}\), for any fixed \(1\le a<b\); in particular, the reduction works with weights \(\{1,2\}\). The reduction is from \(X3C'\), and is proved here rather than cited.

The mirror is natural in a large weighted delegate election. Suppose a national association, cooperative, or shareholder-like organization has \(N\) delegates, where \(N\) is much larger than the number of recurring ballot and weight classes. A delegate type consists of a voting entitlement \(w_t\in\{1,2\}\) and a \(2\)-approval set \(A_t\subseteq C\), \(|A_t|=2\). Delegates of the same type have the same approved candidates and the same voting weight. Thus there may be millions of delegates but only

\[ \tau\le 2\binom{m}{2} \]

types. This is a genuine high-multiplicity regime: the agents are still individually present, but many are indistinguishable for the problem.

Let \(\mu_t\in\mathbb{Q}_{\ge 0}\) be the fraction of registered delegates of type \(t\), with \(\sum_t\mu_t=1\). Let \(p\in C\) be the preferred candidate and let \(\kappa\in\mathbb{Q}_{\ge0}\) be the maximum fraction of delegates that may be prevented from voting. A control action is a vector \(x\), where \(x_t\) is the mass of type \(t\) removed. The remaining weighted \(2\)-approval score of candidate \(c\) is

\[ \operatorname{sc}_{\mu-x}(c) = \sum_{t\in T} w_t(\mu_t-x_t)\mathbf{1}[c\in A_t]. \]

The decision problem asks whether there exists \(x\) satisfying

\[ 0\le x_t\le \mu_t,\qquad \sum_t x_t\le \kappa, \]

such that \(p\) is a co-winner:

\[ \operatorname{sc}_{\mu-x}(p) \ge \operatorname{sc}_{\mu-x}(c) \qquad \text{for every }c\in C. \]

The optimization version minimizes \(\sum_t x_t\). The output is a rational mass-removal vector, not a set of named voters. Importantly, this preserves the paper’s distinction between voting weight and control cost: \(w_t\) affects electoral scores, while the objective counts removed voter mass rather than removed voting weight.

This is recognizably the authors’ problem. The rule is still \(2\)-approval; the action is still constructive deletion of registered voters; the target is still a co-winner under the paper’s nonunique-winner convention; and the chair still pays per voter controlled, not per unit of electoral weight. Only the population representation has changed from a list of individual voters to a distribution over repeated voter types.

I expect this mirror to be Class A. Its optimization problem is the linear program

\[ \begin{aligned} \text{minimize}\quad &\sum_{t\in T}x_t\\ \text{subject to}\quad &0\le x_t\le \mu_t &&(t\in T),\\ &\sum_t w_t(\mu_t-x_t)\mathbf{1}[c\in A_t] \le \sum_t w_t(\mu_t-x_t)\mathbf{1}[p\in A_t] && (c\ne p). \end{aligned} \]

For the \(\{1,2\}\)-weight regime used in the proof of Theorem 4.13, there are only \(O(m^2)\) relevant types. Hence the continuous problem is solvable exactly in polynomial time by rational linear programming. More generally, with an explicitly listed finite type catalogue, it is polynomial in \(m\), \(\tau\), and the encoding length of the masses and weights.

The contrast with Theorem 4.13 is informative. Its \(X3C'\) reduction needs the chair to select whole voters. The exact-cover structure is encoded in which indivisible voters are deleted. Once a large cohort can be removed by an arbitrary mass \(x_t\), the covering constraints become linear inequalities and the integrality obstruction disappears. This is precisely the sort of discrete hardness that a continuous population can dissolve.

The high-multiplicity interpretation is not merely formal. If all masses and the optimum \(x\) are rational, clearing denominators produces a finite election with \(N\) individual voters and whole-voter deletions realizing exactly the same mass plan. Thus \(x_t\) should be understood as deleting a large number of ordinary delegates of type \(t\), not as casting fractional ballots. The continuous problem is the limiting, compressed version in which one controls percentages rather than one-person increments.

This mirror covers the \(2\)-approval WCCDV branch of Theorem 4.13, not every result in the paper. It generates several worthwhile follow-up questions: how large can the finite-population rounding gap be; do the \(3\)-approval and \(3\)-veto branches also reduce to compact LPs; what happens when \(t\) is part of the input and the approval-type catalogue becomes large; and can type-dependent deletion costs, campaign budgets, or robustness requirements create a genuinely continuum-specific hardness boundary?

The weakest point is clear: the original NP-hardness is driven substantially by the requirement that voters be deleted integrally, whereas the mirror allows fractional cohort mass. An opponent can therefore say that this is a relaxation of voter control rather than the same problem. I think that objection identifies the scientific content rather than defeating the mirror. In the programme’s high-multiplicity regime, mass is the honest control quantity, and the paper itself treats the number of targeted voters—not their total weight—as the resource. The proposed problem preserves that semantics at population scale while revealing exactly what the continuous formulation changes: the \(X3C'\) integrality barrier vanishes, leaving a compact and exactly solvable control problem.