Complexity of Shift Bribery in Iterative Elections

In iterative voting systems, candidates are eliminated in consecutive rounds until either a fixed number of rounds is reached or the set of remaining candidates does not change anymore. We focus on iterative voting systems based on the positional scoring rules plurality, veto, and Borda and study their resistance against shift bribery attacks. In constructive shift bribery, an attacker seeks to make a designated candidate win the election by bribing voters to shift this candidate in their preferences; in destructive shift bribery, the briber's goal is to prevent this candidate's victory. We show that many iterative voting systems, including those due to Hare (a.k.a. single transferable vote, instant-runoff voting, or alternative vote), Coombs, Baldwin, and Nanson, are resistant to these types of attack, i.e., the corresponding problems are NP-hard.