| paper | Multimode Control Attacks on Elections |
| authors | Piotr Faliszewski, E. Hemaspaandra, Lane A. Hemaspaandra |
| venue | IJCAI 2009 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given disjoint finite candidate sets \(C\) and \(A\), a target \(p\in C\), a budget \(k\), and a rational distribution \(\mu\) over complete rankings of \(C\cup A\), does there exist \(S\subseteq A\) with \(|S|\le k\) such that, after restricting every ranking to \(C\cup S\), \(p\) is the unique maximin winner, meaning \(\operatorname{mm}_{\mu,S}(p)>\operatorname{mm}_{\mu,S}(c)\) for every \(c\in(C\cup S)\setminus\{p\}\), where \(\operatorname{mm}_{\mu,S}(c)=\min_{d\ne c}\sum_t\mu_t\mathbf{1}[c\succ_t d]\)?
An anonymous high-multiplicity electorate in which complete ranking types \(t\) over \(C\cup A\) carry rational masses \(\mu_t\); the decision variable is the discrete spoiler set \(S\subseteq A\) with \(|S|\le k\), and the objective is unique maximin victory for \(p\).
The mirror directly covers Theorem 5.2 and provides related mass-action extensions of Theorems 6.2 and 5.5; it leaves the paper's remaining control classifications, vulnerability framework, FPT corollaries, and Dodgson connection untouched.
My lead mirror is a continuous-population version of constructive maximin control by adding candidates.
The anchor is Theorem 5.2, proved in this paper. It states that maximin is resistant to constructive AC control: given initial candidates \(C\), addable candidates \(A\), a finite collection of voters ranking \(C\cup A\), a preferred candidate \(p\in C\), and a bound \(k\), deciding whether at most \(k\) candidates from \(A\) can be added so that \(p\) becomes the unique maximin winner is NP-hard. The theorem also establishes susceptibility. Its proof reduces from X3C. For an instance with \(B=\{b_1,\ldots,b_{3k}\}\) and sets \(S_1,\ldots,S_n\), it creates spoiler candidates \(a_i\), and adding \(a_i\) lowers the maximin score of exactly the three element-candidates in \(S_i\). Thus \(p\) becomes the unique winner exactly when the chosen spoilers encode an exact cover.
I would call the continuous problem Continuous Maximin Spoiler Control. Its instance consists of disjoint candidate sets \(C\) and \(A\), a target \(p\in C\), an integer \(k\), and a rational population distribution \(\mu\) over complete rankings of \(C\cup A\). Here \(\mu_t\) is the fraction of society of ranking type \(t\), with \(\sum_t\mu_t=1\). For \(S\subseteq A\), \(|S|\le k\), restrict every ranking to \(C\cup S\), and define \(N_\mu^S(c,d)\) as the mass preferring \(c\) to \(d\). Candidate \(c\)'s maximin score is \(\operatorname{mm}_S(c)=\min_{d\neq c}N_\mu^S(c,d)\). The question is whether there exists \(S\) such that \(\operatorname{mm}_S(p)>\operatorname{mm}_S(c)\) for every other candidate \(c\). A solution is the selected spoiler set \(S\).
This is a genuine population continuization, not outcome-space continuity. Candidates, rankings, and the control action remain discrete because those are intrinsic parts of AC control; the electorate is the continuous object. A natural regime is a large election or party-primary electorate in which many voters share one of a relatively small number of complete ballot types. The same ranking type includes the same preferences and the same eligibility status. We can have \(N\gg\tau\), where \(N\) is the number of voters and \(\tau\) is the number of realized ranking types. The paper’s maximin rule is anonymous and uses voters only through pairwise counts, so this grouping is particularly faithful.
Theorem 5.2 transfers directly. Give each of the reduction’s \(2n+2\) voter patterns mass \(1/(2n+2)\). Every pairwise count is merely divided by \(2n+2\), so all strict maximin comparisons are unchanged. If desired, duplicate every type \(M\) times to obtain an arbitrarily high-multiplicity finite electorate without changing \(\mu\). The X3C combinatorics remain in the choice of spoiler candidates, not in population granularity. Therefore a polynomial algorithm for Continuous Maximin Spoiler Control would solve X3C. I expect this mirror to be Class B: hardness transfers.
This is also plausible as the authors’ problem. It keeps their maximin rule, their constructive unique-winner objective, their candidate-addition action, and their exact candidate budget. Only the anonymous voter profile is represented as masses. The paper itself already works with counts by ranking type in Section 6 and notes that its methods apply to succinct elections; that is supporting evidence that this high-multiplicity regime is meaningful, not a novelty collision.
A second, more genuinely mass-action mirror comes from Theorem 6.2, also proved here. The theorem states that for every anonymous election system whose unique-winner condition can be expressed by an integer linear program, constructive \(E\)-AC+DC+AV+DV+BV control is fixed-parameter tractable when parameterized by the total number of candidates. The action may add or delete candidates, add or delete voters, and bribe voters, with separate bounds on all five prongs. The paper’s proof enumerates the surviving candidate set and uses Lenstra’s algorithm on the resulting integer program.
For example, define Continuous Borda Full Control as follows. The instance has a rational initial mass distribution \(\mu\) over rankings, an addable mass reservoir \(\rho\), a target \(p\), candidate-addition and deletion budgets, and rational mass budgets for voter addition, deletion, and bribery. The controller chooses a surviving candidate set, adds and deletes allowed voter mass, and transfers at most the bribery budget between ranking types. The objective is to make \(p\) the unique Borda winner. For any fixed surviving candidate set, Borda scores are linear in the final type masses, so feasibility is an LP; enumerating candidate sets gives an FPT algorithm in the number of candidates. I therefore expect this mirror to be tractable in the paper’s parameterized sense, and potentially polynomial for fixed candidate agendas.
The main limitation is that my lead mirror leaves the population passive: the control action is still candidate-level. A critic could call it a conservative high-multiplicity restatement rather than a showcase for continuous optimization. I concede that. Its value is different: it shows that continuization need not dissolve hardness when the reduction’s combinatorics live in the agenda rather than in individual voter selection. The second mirror supplies the missing mass-action case.
The natural next question is the continuous analogue of Theorem 5.5, which proves NP-hardness for maximin control by adding voters. There one would choose real masses \(x_t\) from an addable reservoir, subject to \(0\le x_t\le\rho_t\) and \(\sum_t x_t\le\kappa\), to make \(p\) the unique maximin winner. The paper’s exact-cover gadget appears to collapse under fractional mass: arbitrarily small positive mass from suitable types can cover every element, so its discrete hardness does not transfer. Whether the full continuous maximin mass-control problem is polynomial, merely FPT, or continuum-specifically hard is an important boundary question rather than a reason to reject the mirror.
The strongest negative case is that the proponent has not identified a genuinely continuous computational phenomenon in either of the first two anchors. But that case is not ultimately strong enough to support the requested universal verdict.
For Theorem 5.2, the proposed mirror is undeniably a valid high-multiplicity problem. Maximin is anonymous, and the society can naturally consist of large cohorts sharing complete rankings. Normalizing the reduction’s voter counts preserves every pairwise comparison, so the exact-cover hardness transfers. The best criticism is that \(\mu\) is computationally passive: the whole population collapses to the pairwise matrix
\[
M_\mu(c,d)=\sum_t \mu_t\,\mathbf{1}[c\succ_t d].
\]
The control variable remains the discrete spoiler set \(S\subseteq A\). Thus this is a weighted or succinct version of candidate control, rather than a mass-transfer problem with an LP, a pricing oracle, or a new fractional feasibility phenomenon.
That makes the mirror scientifically modest, but it does not defeat it under ChoCo’s rules. The programme explicitly permits population continuization while candidates and control actions remain discrete, and the fact that the reduction’s combinatorics are preserved in the agenda is a legitimate Class B outcome. A dense encoding of all \((|C|+|A|)!\) rankings would also make the claimed polynomial hardness transfer fail on output-size grounds, but a sparse-support encoding repairs this—and is precisely the natural high-multiplicity representation. I cannot honestly turn this into a fatal objection.
Theorem 6.2 is more vulnerable, because the proposed continuous version is not actually the theorem’s problem. The paper proves FPT for integral voter additions, deletions, and bribes, using integer programming and Lenstra’s theorem. Replacing those decisions by divisible masses changes the feasible set. For Borda, the repaired mass problem is a sensible LP, but that is a new fractional relaxation; for a general integer-linear-program-implementable rule, the paper’s winner characterization is guaranteed only on integer assignments and does not automatically define the correct real-valued problem. A faithful mirror retains integer control and becomes essentially a succinct high-multiplicity restatement; a mass-native mirror is new and needs its own correctness and rounding analysis. This defeats the proponent’s claim that Theorem 6.2 transfers directly, but not the value of the resulting continuous problem.
Theorem 5.5 supplies the strongest objection to hardness transfer. Its X3C gadget depends on selecting whole addable voters. In the mass version, if each set type is available, one can assign a small positive mass \(\epsilon\) to every set covering a given element; choosing \(\epsilon\) sufficiently small makes the total mass fit the budget while defeating the exact-cover obstruction. The reduction therefore collapses under fractionalization. Restoring all-or-nothing cohorts or minimum activation masses restores the combinatorics only by reintroducing indivisibility or adding a new nonconvex constraint. The general continuous maximin-addition problem may still be difficult because unique maximin victory contains disjunctive bottleneck conditions, but that would be an open extension, not a consequence of Theorem 5.5.
So the negative case can successfully reject two overstatements: Theorem 6.2 is not a direct continuous theorem, and Theorem 5.5’s reduction does not survive divisible voter mass. It cannot, however, defeat Theorem 5.2. That mirror is a legitimate, natural high-multiplicity population model with a named computational result and a sound normalization argument. The honest negative conclusion is therefore weak: the paper offers a thin but real Class B mirror, plus a plausible mass-native extension. I would not recommend a universal “no worthwhile mirror” verdict.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.