| paper | Frugal Bribery in Voting |
| authors | P. Dey, Neeldhara Misra, Y. Narahari |
| venue | AAAI 2016 |
| 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: The problem is in \(\mathrm P\) for every fixed \(k\ge3\), and also for input-dependent \(1\le k<m\), in time \((m+\tau+L+\log(k+1))^{O(1)}\) with an exponent independent of \(k\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Fix \(k\ge3\). Given candidates \(C\), complete-ranking voter types \(T\) with rational masses \(\mu_t\) summing to \(1\), source prices \(\kappa_t\in\{1,\infty\}\), target \(p\), a fixed tie-breaking order, and a rational per-capita budget \(B\), let \(w\) be the current \(k\)-approval winner and \(V=\{t:p\succ_{\rho_t}w\}\). Decide whether there exist transfers \(x_{t,\rho}\ge0\), for \(t\in V\) and \(\rho\in L(C)\), satisfying \(\sum_{\rho}x_{t,\rho}\le\mu_t\) and \(\sum_{t,\rho}\kappa_t x_{t,\rho}\le B\), such that replacing the transferred mass from ranking \(\rho_t\) by ranking \(\rho\) makes \(p\) win under \(k\)-approval.
A high-multiplicity \(k\)-approval frugal-budget bribery model with complete ranking-and-price types, population mass \(\mu\), transfer variables \(x_{t,\rho}\), source-capacity constraints, a linear mass budget, and \(p\)-winning as the feasibility condition.
Theorem 2 does not itself show that the arbitrary set-specific rankings in its reduction recur at high multiplicity, so the application naturalness rests on an added recurring-segment scenario rather than on the reduction alone.
fatal: False
The mirrors cover Theorems 1 and 2, including Borda frugal bribery and \(k\)-approval frugal-budget bribery. They leave the weighted maximin, STV, Copeland, Bucklin, plurality, veto, and other observations and corollaries unmirrored.
The strongest mirror is the same frugal campaign applied to a high-multiplicity population. Candidates remain discrete, and the winner remains an ordinary winner; only the electorate becomes a distribution over complete rankings.
Let \(C\) be the candidates and let each type \(t\) have a ranking \(\rho_t\). A society is \(\mu\), with \(\mu_t\) the mass of type \(t\). Let \(w\) be the current winner under the paper’s fixed tie-breaking rule, and let \(V=\{t:p\succ_{\rho_t}w\}\) be the vulnerable types. A campaign may transfer mass \(x_{t,\rho}\) from a vulnerable type \(t\) to any new ranking \(\rho\), subject to \(x_{t,\rho}\ge 0\) and \(\sum_\rho x_{t,\rho}\le\mu_t\). The resulting society must make \(p\) win. This is exactly the paper’s restriction—only \(p\)-vulnerable votes may change—except that a campaign can approach a fraction of a repeated voter segment.
A plausible regime is a large election with \(n\) in the millions but only a comparatively small number of recurring ballot-and-cost types: for example, polling segments with the same ranking, persuasion cost, and response profile. Thus \(n\gg |T|\). If two people have the same ranking but different prices, they are different types, exactly as the high-multiplicity interpretation requires. Mass means the proportion of such a segment, not a lottery over winners and not a fractional candidate outcome.
My lead anchor is Theorem 1, proved in this paper. It states that FRUGAL-BRIBERY is NP-complete for the Borda voting rule in unweighted elections. Given a profile and a preferred candidate \(p\), one may change only votes whose voters prefer \(p\) to the current winner, and one asks whether some such changes can make \(p\) win. The proof reduces from PERMUTATION SUM and uses only two vulnerable votes, whose rankings encode two permutations.
The corresponding continuous problem is:
Continuous Borda Frugal Bribery. Given \(C\), a rational society \(\mu\), a target \(p\), and a fixed Borda tie-breaking rule, compute the current winner \(w\), identify \(V=\{t:p\succ_{\rho_t}w\}\), and decide whether there is a mass transfer \(x_{t,\rho}\) from vulnerable types to rankings such that the resulting society \(\mu'\) has \(p\) as its Borda winner. A solution is the transfer plan \(x\); there is no budget.
This is recognisably the paper’s problem, not a softened campaign problem. Vulnerability is unchanged, arbitrary replacement rankings are unchanged, and \(p\) must still win a discrete election. What changes is only the indivisibility of voters.
I would expect this mirror to be Class A, although the exact input and separation model deserve formal treatment. Let \(a(\rho)\in\mathbb{R}^{m}\) be the Borda score vector of ranking \(\rho\), let \(y_t=\sum_\rho x_{t,\rho}\), and let \(Y=\sum_t y_t\). The final score vector has the form \(S'=S-\sum_{t\in V}y_ta(\rho_t)+z\), where \(z\) is the aggregate score vector of the newly created mass and \(z\in YP_{\mathrm{Borda}}\), with \(P_{\mathrm{Borda}}\) the convex hull of all Borda score vectors. This is the Borda permutahedron, which has efficient separation via majorization. Hence the problem appears to reduce to linear feasibility plus a polynomial separation routine.
That is precisely the kind of phenomenon the continuization programme is meant to expose: the paper’s NP-hardness comes from requiring two indivisible rankings to realize a permutation-sum witness, whereas a continuous campaign chooses a point in the convex hull of all rankings. The further questions are whether this gives a strongly polynomial algorithm, how well its solution rounds to an \(n\)-voter election, and whether hardness returns if the campaign must move whole cohorts rather than arbitrary submass.
A second worthwhile anchor is Theorem 2, also proved in this paper. It states that FRUGAL-\(\$BRIBERY\) is NP-complete for \(k\)-approval for every constant \(k\ge 3\), even when every vulnerable vote has price \(1\) or \(\infty\). The input includes prices and a budget; only vulnerable votes with finite price may be changed, and the question is whether \(p\) can be made the winner within budget. The proof reduces from EXACT-COVER-BY-3-SETS.
The continuous counterpart is:
Continuous \(k\)-Approval Frugal-\(\$\)Bribery. Fix \(k\ge3\). Given a rational society \(\mu\), target \(p\), fixed tie-breaking, a source-type price \(\kappa_t\in\{1,\infty\}\), and a per-capita budget \(B\), choose transfers \(x_{t,\rho}\) only from vulnerable types, with \(\sum_{t,\rho}\kappa_ty_t\le B\), so that \(p\) wins under \(k\)-approval. The objective is to minimize \(\sum_t\kappa_ty_t\), or equivalently decide whether it is at most \(B\). For a finite election with \(n\) voters and integer budget \(b\), the normalized budget is \(B=b/n\).
I would again expect Class A. A \(k\)-approval ranking contributes a \(0\)-\(1\) vector with exactly \(k\) ones. The convex hull of these vectors is the hypersimplex \(0\le z_c\le Y\), \(\sum_c z_c=kY\). The budget, source-capacity constraints, and \(p\)-winning inequalities are all linear. The exact-cover reduction relies on selecting whole set-votes; continuous mass permits fractional selection and therefore turns the combinatorial core into a fractional covering or flow problem. The important follow-up is whether the resulting LP remains tractable with richer destination-dependent prices, swap costs, or restrictions on which rankings a segment can adopt.
The scope is deliberately limited: these mirrors cover Theorem 1 and Theorem 2, not the paper’s weighted maximin, STV, Copeland, or Bucklin results. The paper is not prior art for the mirror: it studies finite elections, while these questions ask what happens when repeated voter types become mass.
The weakest point is that Theorem 1’s own reduction uses only two vulnerable votes, and Theorem 2’s reduction gives one vote per set. Neither theorem itself establishes a high-multiplicity regime. If one insists on reproducing those exact gadgets, the case is weak. The positive claim is instead that the underlying frugal-bribery problems have a natural repeated-segment interpretation, and that their discrete hardness is exactly worth testing against the convexification created by a continuous population.
The strongest case against these anchors is that neither theorem’s reduction actually exhibits a high-multiplicity phenomenon. Theorem 1 uses exactly two vulnerable votes; Theorem 2 uses one vulnerable vote per set in an exact-cover instance. Their hardness comes from coordinating rankings over candidates, not from having many interchangeable voters. If one simply duplicates those votes, the continuous version permits fractional changes and destroys precisely the indivisible gadget that proves hardness.
That objection is not enough, however. It attacks the reductions, not the underlying problems. Voting profiles are unusually well suited to high multiplicity: agents are already described by complete rankings, and the paper’s unweighted variants contain no identity-dependent objective. A plausible election can have millions of voters divided into recurring ranking-and-price segments. Taking type to include the ranking and, for Theorem 2, the price, satisfies the programme’s definition of high multiplicity exactly.
For Theorem 1, the best negative argument is that the proposed mirror ceases to be specifically about frugal bribery. Since every vulnerable type may be changed to any ranking at no cost, all destination choices can be pooled. The source profile contributes only capacities and the aggregate score vector of the moved mass. For Borda, the possible destination score vectors form the permutahedron, so the problem becomes a generic convex feasibility problem. The two-vote permutation-sum gadget has disappeared, and the “frugal” feature contributes little beyond a vulnerable-mass bound.
But that is a criticism of the likely answer, not of the question. It is exactly a legitimate Class A outcome: continuization reveals that the discrete hardness was caused by indivisible destination rankings. The resulting convexification is partly an outcome-space phenomenon, but it is forced by continuizing the population while retaining the paper’s arbitrary vote-change operation. The mirror remains a population distribution over rankings, and the question remains computationally meaningful.
Theorem 2 is harder to dismiss. Its exact-cover construction also relies on selecting whole votes, and fractional mass would indeed replace exact cover by a fractional covering condition. Yet that is precisely the high-multiplicity relaxation one would want to test. The source price \(1\) or \(\infty\) can be a property of a recurring voter segment, and the budget can naturally be normalized to a per-capita budget \(B=b/n\). Nothing in the problem tracks individual identity. Requiring whole cohorts would preserve the reduction but would no longer be a genuine continuum; allowing fractional cohort mass is the intended model.
One can say that the proponent has not yet proved the claimed polynomial algorithms, nor supplied the required encoding and rounding dictionary. That is a valid reservation about the strength of the positive case, but not an obstruction to the mirrors themselves.
So the honest negative case is weak. The reductions do not establish that these problems have an interesting high-multiplicity regime, and the continuous versions may collapse into fairly generic LPs. They do not establish that no worthwhile mirror exists. Both anchors survive the stronger objections: the paper studies a canonical aggregate voting model with no identity-sensitive objective, and its discrete hardness is exactly the sort of indivisibility phenomenon that a continuous mirror is designed to expose.
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.