| paper | How Hard Is Bribery in Elections? |
| authors | Piotr Faliszewski, E. Hemaspaandra, Lane A. Hemaspaandra |
| venue | JAIR 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given candidates \(C=\{p,c\}\), a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), each type's ranking, per-agent voting weight \(w_t\), and per-agent bribe price \(\pi_t\), plus normalized budget \(K\), does there exist mass \(x_t\) for the types with \(c\succ_t p\), with \(0\le x_t\le\mu_t\), such that bribing that mass to report \(p\succ c\) costs \(\sum_t\pi_t x_t\le K\) and makes \(p\) a plurality winner, namely \(S_p+\sum_t w_t x_t\ge S_c-\sum_t w_t x_t\)?
A finite explicit type distribution \(\mu\), where each type carries a complete ranking, weight \(w_t\), and price \(\pi_t\). Decision variables \(x_t\) transfer mass from \(c\)-supporting types to the same voters reporting \(p\); the objective is to minimize \(\sum_t\pi_t x_t\), subject to mass bounds and the plurality-winning inequality.
Theorem 3.2's mirror is essentially fractional knapsack, and its naturalness depends on accepting a separate replicated cohort for each type-specific \((w_t,\pi_t)\); this bounds its novelty but does not invalidate the model.
fatal: False
The mirror covers the weighted priced-plurality and approval-bribery hardness results in Theorems 3.2 and 4.2, as well as the fixed-candidate algorithmic perspective of Theorem 5.2. It leaves the manipulation reductions, scoring-protocol dichotomies, Dodgson, Young, Kemeny, and artificial voting-system results without dedicated mirrors.
The strongest positive case is that the paper contains two natural hardness results whose hardness is plausibly caused by indivisible voters. Their continuous-population counterparts are not artificial simplifications: they preserve the voting rule, the bribery action, the target candidate, and the relevant costs, while replacing repeated individual agents by mass.
A plausible regime is a large referendum or platform election with \(N\) agents but only \(\tau\ll N\) behavioural types. A type records everything relevant to bribery: the complete preference or approval ballot, voting weight, and persuasion price where applicable. Repeated types arise from standardized membership tiers, organizational constituencies, automated accounts, or recurring policy templates. A mass \(\mu_t\) is the fraction of the population of type \(t\). Prices and weights being type attributes are not a distortion: that is precisely the high-multiplicity interpretation.
My lead anchor is Theorem 3.2, proved in this paper: weighted-\(\$\)-bribery for plurality is NP-complete, even with only two candidates. In the paper’s decision problem, voters have integer weights and prices, a target candidate \(p\), and a budget \(k\); the question is whether voters can be bribed, at total price at most \(k\), so that \(p\) becomes a winner. The proof reduces Partition: there are two candidates \(p,c\), every voter initially supports \(c\), voter \(i\) has weight and price \(s_i\), and the budget is \(S\), where \(\sum_i s_i=2S\). Making \(p\) a winner is possible exactly when some subset of the \(s_i\) sums to \(S\).
The corresponding continuous problem is:
Continuous Weighted-\(\$\)-Plurality Bribery\(_\infty\). An instance consists of candidates \(C=\{p,c\}\), a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), and for each type \(t\) a complete ranking, voting weight \(w_t\), and bribe price \(\pi_t\). Given a normalized budget \(K\), choose masses \(x_t\), where \(0\le x_t\le\mu_t\), to transfer from types supporting \(c\) to types supporting \(p\). The cost is \(\sum_t \pi_t x_t\). The question is whether the transfer can make \(p\) a plurality winner; equivalently, whether there are \(x_t\) satisfying \( \sum_t \pi_t x_t\le K \) and \( S_p+\sum_t w_t x_t\ge S_c-\sum_t w_t x_t \), where \(S_p,S_c\) are the initial weighted scores.
This is exactly the paper’s problem with a high-multiplicity electorate and fractional mass transfers. It is tractable: the required transferred voting weight is \( \max\{0,(S_c-S_p)/2\} \), and one fills that requirement by taking mass in increasing order of \( \pi_t/w_t \). Thus the Partition hardness disappears as indivisibility disappears. The expected classification is Class A. The result also generates natural extensions: more than two candidates, unique-winner constraints, destination-dependent prices, and type-to-type bribery costs. Those extensions become genuine pricing or LP questions rather than changes to the underlying problem.
The second anchor is Theorem 4.2, also proved here: unweighted approval bribery is NP-complete. The paper’s problem gives approval vectors, a target \(p\), and an integer \(k\), and asks whether at most \(k\) voters’ entire approval vectors can be changed so that \(p\) wins. The reduction is from X3C. There is one voter for each three-set \(S_i\), singleton-support voters ensuring every element candidate initially has \(m+1\) approvals, and \(m-t\) voters approving only \(p\). With budget \(t\), \(p\) can win exactly when \(t\) set-voters form an exact cover.
The continuous counterpart is:
Continuous Approval Bribery\(_\infty\). An instance consists of candidates \(C\), a target \(p\), rational masses \(\mu_A\) for approval types \(A\subseteq C\), and a mass budget \(\kappa\). Choose mass \(x_A\), \(0\le x_A\le\mu_A\), and change that mass’s approval vector to \(\{p\}\). The cost is \(\sum_A x_A\). The question is whether \(p\) can become a winner.
Changing to \(\{p\}\) is without loss of generality: it preserves \(p\)’s approval, removes approvals from every rival, and is at least as effective as any other new approval vector. Let \(a_c=\sum_A\mu_A\mathbf 1[c\in A]\). The problem is the LP with variables \(x_A\), constraints \(0\le x_A\le\mu_A\), \(\sum_Ax_A\le\kappa\), and, for every \(c\ne p\), \(a_p+\sum_{A:p\notin A}x_A\ge a_c-\sum_{A:c\in A}x_A\). It is solvable in time polynomial in \(m\), the number of represented types \(\tau\), and the encoding length.
Again, the expected classification is Class A. The X3C reduction relies on selecting whole set-voters. In the mirror, a type’s mass can be split, so the relevant object becomes a fractional covering LP. That is not a different social-choice question: it is still approval bribery, with the same complete ballot changes and the same winner condition. Only the population has been continuized.
These mirrors cover the paper’s core bribery questions, not merely its encodings. They also fit the paper’s own Section 5 perspective: Theorem 5.2, proved here, already shows that succinct fixed-candidate scoring bribery is polynomial-time solvable by grouping identical preference orders and using fixed-dimensional integer programming. The proposed mirrors extend that grouping from multiplicities represented by integers to population masses represented by rationals.
The weakest point is that a referee may insist that the paper’s NP-hardness results study indivisible bribery decisions, whereas the mirrors permit bribing a fraction of a type. That objection is valid—but it is exactly the continuization being tested. In both reductions, the combinatorics live primarily in selecting individual voters or set-voters. The continuous programme predicts that this population-driven hardness dissolves, while retaining the underlying bribery problem. That makes these unusually clean and defensible positive mirrors.
The strongest negative case is that both proposed mirrors are merely standard fractional relaxations of the paper’s reductions, not substantive continuous-population problems. That case is ultimately weak, however.
For Theorem 3.2, the hard instance has voters \(t_i=(c\succ p,s_i,s_i)\). Once weight and price are correctly included in the type, almost every voter is a singleton type: the Partition instance is encoded in type diversity, not in population multiplicity. The proposed variable \(x_t\) therefore permits a fraction of an indivisible Partition item to be purchased. Its sorting by \(\pi_t/w_t\) is just fractional knapsack. One could argue that this is a relaxation of the combinatorial problem rather than its high-multiplicity version.
That objection does not survive the stronger modelling choice, though. Replicate every \(t_i\) into a large cohort of interchangeable voters with the same weight and price. This is a plausible society of standardized constituencies or membership tiers, and the resulting mass-transfer problem is exactly the proposed LP. The programme explicitly treats such replication as legitimate high multiplicity. More elaborate versions with several candidates and type-to-type conversion costs remain natural LP or flow problems. The fact that the answer becomes tractable is not an objection under this programme; it is precisely the sort of Class A result the programme seeks.
The same issue arises for Theorem 4.2. The X3C reduction uses set-voters that are mostly unique, so its literal hard instances do not display much repeated type mass. But one can replicate each approval type into a large cohort without changing the social meaning. A fraction of the cohort approving \(S_i\) can be bribed to approve only \(p\), and the winner constraints become a genuine fractional covering problem. The approval vectors, target candidate, complete ballot changes, and budget all survive; only the population is continuized.
The best criticism is that this LP is mathematically routine. It is essentially the fractional relaxation of X3C, and with unit bribery costs it has little social-choice structure beyond aggregate approval margins. But “routine LP” is not a decisive objection here. The programme expressly values structural tractability results, and adding destination-dependent prices or general type-to-type transfer costs would produce a richer continuous model rather than invalidate the basic one.
Theorem 5.2 is a weaker anchor. With a fixed number of candidates, \(m!\) is constant, so replacing its integer multiplicity variables by rational masses is almost automatic. The resulting continuous problem contributes little beyond a finite-dimensional LP. If the candidate count varies, however, the type space becomes exponentially large and the continuous question is no longer just Theorem 5.2 with integrality removed; it becomes a genuine pricing or separation problem. Thus Theorem 5.2 should not carry the positive case by itself, but it also does not undermine the two bribery mirrors above.
Consequently, I cannot honestly defend the universal negative claim. The proposed mirrors may be elementary, but they are sensible high-multiplicity models, and both preserve a named computational problem from the paper. The negative case can downgrade their novelty and insist that the interesting continuization should use richer transfer costs or an implicit type space; it cannot show that no worthwhile mirror exists in any plausible scenario.
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.