Source-linked AI summary
Swap Bribery
E. Elkind, P. Faliszewski, A. Slinko
TL;DR
Bribery models often let a briber alter votes, but fixed prices do not capture how the requested change affects its cost. This paper defines swap bribery through priced adjacent swaps and analyzes its complexity across election systems. The results show that swap bribery is NP-hard for many systems, while several tractable cases and open algorithmic directions remain.
Problem
Fixed-price bribery does not capture settings where a voter’s price depends on the nature or extent of the requested vote change.
Source: §1 · p. 2Method
The paper models vote changes as sequences of adjacent-candidate swaps, each with its own price, and also studies shift bribery.
Source: §1 · p. 2Results
Swap bribery is NP-hard for many studied election systems, in contrast to easiness results for microbribery and nonuniform bribery in nonstandard voter models.
Source: §6 · p. 14Takeaways & Limitations
The paper’s results suggest that the hardness contrast is tied to the rational-voter setting rather than to flexible pricing alone.
Source: §1 · p. 3Identifying polynomial-time special cases and designing approximation algorithms for other voting rules and for swap bribery remain open research directions.
Source: §6 · p. 14
Abstract
from arXiv · showhide
In voting theory, bribery is a form of manipulative behavior in which an external actor (the briber) offers to pay the voters to change their votes in order to get her preferred candidate elected. We investigate a model of bribery where the price of each vote depends on the amount of change that the voter is asked to implement. Specifically, in our model the briber can change a voter's preference list by paying for a sequence of swaps of consecutive candidates. Each swap may have a different price; the price of a bribery is the sum of the prices of all swaps that it involves. We prove complexity results for this model, which we call swap bribery, for a broad class of election systems, including variants of approval and k-approval, Borda, Copeland, and maximin.
1 Introduction
The paper introduces swap bribery for rational voters, where each adjacent-candidate swap has its own price, and studies its computational complexity. It also treats shift bribery as a campaign-focused special case.
1 Introduction
- Earlier bribery models let the briber change a purchased vote arbitrarily at a fixed price, while nonuniform models had not addressed standard preference orders.Small changes may be more acceptable to voters than changing an entire vote.Source: §1 · p. 2
- Swap bribery prices sequences of adjacent-candidate swaps individually, making the total bribery cost the sum of their prices.The model adapts microbribery to rational voters and standard preference orders.Source: §1 · p. 2
- Shift bribery restricts paid changes to moving the preferred candidate upward, modeling campaigns focused on promoting that candidate.The paper presents it as a special case of swap bribery.Source: §1 · p. 2
- The paper seeks efficient algorithms and to locate the source of hardness; its results suggest hardness is tied to the voter model rather than flexible pricing.It frames identifying NP-hard bribery settings as a first step in studying resistance to manipulation.Source: §1 · pp. 2–3
2 Preliminaries
The preliminaries establish the paper’s election model and distinguish manipulation, possible-winner, and bribery problems. They also specify the standard complexity concepts used later.
2 Preliminaries
- An election consists of candidates and voters with strict linear preference orders, and an election system returns a set of winners.The paper uses the nonunique-winner model and considers point-based election systems.Source: §2 · p. 3
- Manipulation asks whether specified voters can be assigned preferences to make a preferred candidate win, while possible-winner asks whether partial votes can be completed to achieve that outcome.Manipulation is a special case of possible-winner.Source: §2 · p. 3
- Bribery asks whether votes can be modified within a budget so the preferred candidate wins, with voter prices specified as part of the instance.The paper uses P, NP, NP-completeness, and polynomial-time many-one reductions; many hardness proofs reduce from X3C.Source: §2 · p. 4
3 Swap Bribery
Swap bribery models vote changes as priced adjacent swaps and provides polynomial-time procedures for optimal vote transformations. The section also gives tractability conditions and reductions connecting swap bribery to other election problems.
3 Swap Bribery
- The paper motivates priced adjacent swaps as a practical way to specify nonuniform bribery without listing prices for all possible preference orders.There are m! possible votes with m candidates, making explicit price lists impractical.Source: §3 · p. 4
- Swap bribery forbids non-adjacent swaps as single operations, although such a swap can be simulated by a sequence of adjacent swaps.Each unit swap must involve candidates adjacent in the voter’s current preference order.Source: §3 · pp. 4–5
- A cheapest swap sequence converting one vote into another can be computed in polynomial time by swapping each inverted candidate pair once.The model prices each adjacent swap, and any vote can be transformed into any other by such swaps.Source: §3 · pp. 4–5
- For a fixed target multiset of votes, an optimal bribery can be found in polynomial time using a minimum-cost flow construction.The flow assigns input votes to target votes using their polynomial-time transformation costs.Source: §3 · pp. 5–6
- For anonymous rules with polynomial-time winner determination, optimal swap bribery is polynomial-time computable when the number of candidates is constant.The algorithm enumerates vote multisets, computes transformation costs, and selects the cheapest multiset making the preferred candidate win.Source: §3 · p. 6
- Possible-winner many-one reduces to swap bribery, and manipulation also reduces to swap bribery because it is a special case of possible-winner.The construction makes a preferred candidate winnable at cost zero exactly when the partial votes can be completed to make that candidate win.Source: §3 · pp. 6–7
- Shift bribery permits only moving the preferred candidate upward, and its price functions can be translated into swap-bribery prices while preserving the problem.The construction keeps the budget and sets other swap prices above it.Source: §3 · p. 7
- The possible-winner reduction does not automatically transfer to shift bribery, whose complexity remains worth studying even when possible-winner is hard.The section notes that shift bribery can be strictly easier than swap bribery, assuming P ≠ NP.Source: §3 · pp. 7–8
4 Case Study: Approval Voting
The approval-voting results sharply distinguish swap bribery from shift bribery and identify tractable cases by rule and input size. For k-approval, swap bribery is hard in several settings where shift bribery remains tractable.
4 Case Study: Approval Voting
- Plurality and veto swap bribery are in P, but for each fixed k ≥ 3 it is NP-complete even when swap costs lie in {0, 1, 2}.The proof reduces from X3C for fixed k ≥ 3.Source: §4 · p. 8
- For plurality, the algorithm computes the cost of replacing each voter’s top candidate with the preferred candidate, then applies a polynomial-time nonuniform-bribery algorithm.The paper states that veto is analogous to plurality.Source: §4 · p. 8
- The hardness construction for fixed k ≥ 3 uses X3C: spending one unit on a set’s voter can move its three elements out of the approved positions, while other changes cost at least two.The construction extends from 3-approval to larger fixed k by adding dummy candidates.Source: §4 · pp. 8–9
- Swap bribery for 2-approval is NP-complete, following from the known NP-completeness of its possible-winner problem.The section uses the possible-winner-to-swap-bribery result to obtain this case.Source: §4 · p. 9
- Shift bribery for k-approval is in P for every k < m, contrasting with swap-bribery hardness for many k-approval rules.In k-approval, voters award points to their top k candidates.Source: §4 · pp. 8–9
- For each fixed k, swap bribery for k-approval is in P when the number of voters is bounded by a constant.The algorithm considers possible top-k candidate sets for each voter and checks whether the resulting election makes the preferred candidate win.Source: §4 · p. 9
- When k is part of the input, swap bribery for k-approval is NP-complete even with a single voter.The hardness proof reduces from Balanced Biclique.Source: §4 · p. 10
5 Further Voting Rules and Shift Bribery
The section establishes NP-completeness results for shift bribery under Borda, maximin, and Copelandα, while also giving a polynomial-time 2-approximation for Borda-shift bribery.
5 Further Voting Rules and Shift Bribery
- Borda-swap bribery and Borda-shift bribery are both NP-complete.The swap-bribery result follows from the NP-completeness of Borda's possible-winner problem.Source: §5 · p. 11
- For Borda-shift bribery, bribing K voters corresponding to an X3C cover raises p’s score by 3K and lowers each member of B by 1, making all candidates tie.The reduction sets a budget of K and prices other voters beyond that budget.Source: §5 · p. 11
- A polynomial-time algorithm returns a Borda-shift bribery costing at most twice the optimal cost.A randomized algorithm for approximating Dodgson scores can also be adapted to Borda-shift bribery, but its log m approximation ratio is weaker.Source: §5 · pp. 11–12
- Shift bribery is NP-complete for maximin and for Copelandα at every rational α between 0 and 1.The maximin proof reduces from X3C, restricting affordable shifts to K voters; making p a winner within budget requires those voters to correspond to a cover of B.Source: §5 · pp. 12–14
- For irrational voters, microbribery is polynomial-time for Borda and maximin, and for Copeland0 and Copeland1, unlike the rational-voter hardness results here.The authors suggest that hardness may stem from handling preference orders rather than from the particular election systems.Source: §5 · pp. 11, 12, 14
6 Conclusions
Swap bribery adapts microbribery to rational voters, yet is NP-hard for many election systems. The paper leaves polynomial-time special cases and further approximation algorithms as open problems.
6 Conclusions
- Swap bribery and shift bribery are analyzed for plurality, k-approval, Borda, Copeland, and maximin.Swap bribery adapts the microbribery model to rational voters.Source: §6 · p. 14
- The authors contrast swap bribery’s hardness with easiness results for microbribery and nonuniform bribery in utility-based systems.They suggest that preference orders, rather than election-system design, may be a main source of hardness.Source: §6 · p. 14
- Open problems include finding polynomial-time optimal cases and approximation algorithms for other voting rules and for swap bribery.Theorem 5.2 is described as a first step toward approximation algorithms.Source: §6 · p. 14
A Swap Bribery in SP-AV
The section defines mixed bribery for sincere-strategy preference-based approval voting (SP-AV), allowing adjacent swaps and changes to approval counts. It proves NP-completeness even when only approval counts may change and their prices are linear, via a reduction from X3C.
A Swap Bribery in SP-AV
- The SP-AV mixed-bribery model lets the briber pay separately for adjacent swaps and changes in each voter's approval count.SP-AV voters provide a preference order and an approval count between 1 and m − 1.Source: A Swap Bribery in SP-AV · p. 16
- Mixed bribery remains hard when approval thresholds cannot change under either stated approval-count condition, and also when only linearly priced thresholds may change.The conditions are that all voters approve at least three candidates, or that one voter approves n/2 + 1 candidates.Source: A Swap Bribery in SP-AV · p. 16
- Mixed bribery for SP-AV is NP-complete even when swaps are forbidden and approval-count changes cost |k|.The restriction sets every swap price to infinity and each approval-threshold price to the absolute change.Source: A Swap Bribery in SP-AV · p. 16
- The reduction establishes that, in the constructed SP-AV election, p can become a winner via mixed bribery of cost at most 3K iff (B, S) is a yes-instance of X3C.To raise p’s score by K, bribery must include K set-corresponding voters, at cost 3 each, whose sets cover B.Source: A Swap Bribery in SP-AV · pp. 16–17
- Each bribed set voter raises p's score by one at cost 3, while also raising the scores of the members of its set.Thus the K voters needed to raise p's score by K must represent a cover of B without increasing any b_i's score by more than one.Source: A Swap Bribery in SP-AV · p. 17