d4-conf-ecai-2016-0354

The strongest case is that the paper’s control problems choose among many individual ballot records, while their continuous counterparts keep the same candidates, scoring rule, and winning condition and let the action operate on population mass. A plausible regime is a large primary or membership election with many repeated rankings: \(n\) is very large compared with the \(\tau\) ranking types actually present. For the bribery result, types also record whether a voter is reachable by the campaign. These are aggregate actions on genuinely large cohorts, not a change to the outcome space.

Lead anchor: Theorem 3.1. The paper states and proves its dichotomy for pure, polynomial-time uniform generators \(f\): both \(f\)-CCDV and \(f\)-bribery are in P if \(f\) is ultimately equivalent to one of five families—3-veto, 1-approval, 2-approval, \((0,\ldots,0,-\beta,-\alpha)\) for \(\alpha\ge\beta\ge0\), or \((2,1,\ldots,1,0)\)—and both are NP-complete otherwise. This is the paper’s own main result; some polynomial cases use earlier classifications, and the paper notes that many proof details appear in its full version [15]. For example, Borda is outside the listed families, so the theorem implies that Borda-CCDV is NP-complete.

I would mirror the CCDV part with Continuous Mass-CCDV. Fix a scoring generator \(f\). An instance gives candidates \(C\), a target \(p\), a rational budget \(\kappa\), and a list of \(\tau\) rankings \(\pi\), each with rational mass \(\mu_\pi>0\), where \(\sum_\pi\mu_\pi=1\). It asks whether one can delete mass \(d_\pi\) from each type, with \(0\le d_\pi\le\mu_\pi\) and \(\sum_\pi d_\pi\le\kappa\), so that \(p\) is a winner. A solution is the vector \(d\); the residual score is \(\sum_\pi(\mu_\pi-d_\pi)s_f(\pi,c)\) for each candidate \(c\). Normalizing the remaining mass does not affect who wins.

This is precisely the mass relaxation of discrete CCDV: if type \(\pi\) has \(n_\pi\) voters among \(n\), discrete deletion choices require \(d_\pi\) to be a multiple of \(1/n\); the continuous version removes that per-voter quantum. Its decision problem is a linear program with \(\tau\) variables and one score inequality per opponent, so it is polynomial in \(m,\tau,L\), including for Borda. The mirror covers the CCDV half of Theorem 3.1, not its bribery or manipulation results. It asks whether the hardness on the theorem’s hard side survives when deletions act on masses. A natural next question is when the LP solution can be rounded to discrete deletions with a controlled increase in cost and without changing the winner.

Second anchor: Theorem 3.2. The paper asserts that bribery for \((0,\ldots,0,-1,-2)\) becomes NP-complete when each voter has a bit saying whether they can be bribed. This result is asserted by the paper; its introduction says that most proof details are in the full version [15]. It is a useful anchor because Theorem 3.1 classifies ordinary bribery for this scoring family as polynomial-time solvable, while Theorem 3.2 identifies a specific added constraint that makes the discrete variant hard.

Its continuous mirror is Continuous Marked 2-Veto Bribery. The input is a rational distribution \(\mu_{\pi,e}\) over complete rankings \(\pi\) and eligibility types \(e\in\{0,1\}\), a target \(p\), and a budget \(\kappa\). Choose bribed mass \(d_\pi\le\mu_{\pi,1}\) from eligible ranking types, then assign that same mass to replacement rankings; ask whether \(p\) can be made a winner with total bribed mass at most \(\kappa\). A solution specifies the mass bribed from each eligible type and its replacement ballots. The eligibility bit remains part of the type throughout.

For this rule, only the last two positions of a replacement ballot affect scores. Let \(y_{a,b}\) be the replacement mass with \(a\) second-last and \(b\) last, for \(a\ne b\). Require \(y_{a,b}\ge0\) and \(\sum_{a\ne b}y_{a,b}=\sum_\pi d_\pi\). A replacement with this pair gives candidate \(c\) score \(s_{a,b}(c)=-\mathbf 1[c=a]-2\mathbf 1[c=b]\). Thus the final score is the initial score minus the score of the bribed ballots plus \(\sum_{a\ne b}y_{a,b}s_{a,b}(c)\), with one winner inequality for each opponent. Minimizing \(\sum_\pi d_\pi\) subject to these constraints is an LP with \(O(\tau+m^2)\) variables, so this continuous version is also in P. The mirror preserves the paper’s eligibility distinction while making each eligible type a cohort that can be partly bribed. A further question is whether similarly compact formulations survive when eligibility or bribe prices have more type-level categories.

My weakest point is the relaxation itself: it allows a fractional share of a ballot type to be deleted or bribed. In elections with many rare types, or interventions that must select whole individuals, that can produce an unattainable action and a different optimum. The case is strongest in the stated high-multiplicity regime, where many voters share each relevant type and mass is the intended unit of control. It proposes tractable continuous problems and a rounding question; it does not claim that the discrete NP-hardness disappears for every finite election.