Algorithms for swap and shift bribery in structured elections

Conference item

In computational social choice, shift bribery is the procedure of paying voters to shift the briber's preferred candidate forward in their preferences so as to make this candidate an election winner; the more general swap bribery procedure also allows one to pay voters to swap other candidates in their preferences. The complexity of swap and shift bribery is well-understood for many voting rules; typically, finding a minimum-cost bribery is computationally hard. In this paper we initiate the study of swap and shift bribery in the setting where voters' preferences are known to be single-peaked or single-crossing. We obtain polynomial-time algorithms for several variants of these problems for classic voting rules, such as Plurality, Borda and Condorcet-consistent rules.

Authors: Elkind, E; Faliszewski, P; Gupta, S; Roy, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: International Foundation for Autonomous Agents and Multiagent Systems
• Host title: AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems
• Pages: 366-374
• Publication date: 2020-01-01
• Event title: 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020)
• Event location: Auckland, New Zealand
• Event website: https://aamas2020.conference.auckland.ac.nz/
• Event start date: 2020-05-09
• Event end date: 2020-05-13
• EISSN: 1558-2914
• ISSN: 1548-8403
• ISBN: 9781450375184
• Language: English
• Keywords: single-peaked preferences; single-crossing preferences; FFR; shift bribery; swap bribery