Swap Bribery
arXiv:0905.3885 · doi:10.1007/978-3-642-04645-2_27
Abstract
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.
17 pages
Cited by in corpus (17)
- Determining Possible and Necessary Winners Given Partial Orders
- Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules
- Approximation Algorithms for Campaign Management
- Computational Aspects of Nearly Single-Peaked Electorates
- Algorithms for Destructive Shift Bribery
- Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules
- Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules
- On the Hardness of Bribery Variants in Voting with CP-Nets
- Multi-Party Campaigning
- On the Robustness of Winners: Counting Briberies in Elections
- Multivariate Analyis of Swap Bribery
- Local Distance Constrained Bribery in Voting
- Gerrymandering: A Briber's Perspective
- How Similar Are Two Elections?
- The Complexity of Online Bribery in Sequential Elections (Extended Abstract)
- Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges
- Manipulation Can Be Hard in Tractable Voting Systems Even for Constant-Sized Coalitions