Algorithms for Destructive Shift Bribery

We study the complexity of Destructive Shift Bribery. In this problem, we are given an election with a set of candidates and a set of voters (ranking the candidates from best to worst, each), a despised candidate d (typically, one of the current winners), a budget B, and prices for shifting d down in voters’ rankings. The goal is to ensure that d is not a winner of the election. We show that this problem is polynomial-time solvable for all scoring protocols (encoded in unary) and the Maximin rule, but is NP-hard for the Copeland rule. This contrasts with the results for the constructive setting (known from the literature), for which the problem is polynomial-time solvable for k-Approval family of rules, but is NP-hard for the Borda, Copeland, and Maximin rules.

Authors

• Andrzej Kaczmarczyk AGH University
• Piotr Faliszewski AGH University

Keywords

• algorithms
• computational complexity
• voting
• campaign management
• bribery