2009/05/24 by E. Elkind, P. Faliszewski, A. Slinko · 1 citation
Computer Science · #cs.GT #cs.AI
paper · pdf · doi:10.1007/978-3-642-04645-2_27
17 pages
arxiv created 2009/05/24 · arxiv updated 2015/05/13
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.