Parameterized Complexity of Shift Bribery in Iterative Elections

In an iterative voting system, candidates are eliminated in consecutive rounds until either the set of remaining candidates does not change or a fixed number of rounds is reached. In this paper, we consider four prominent iterative voting systems, which are all based on positional scoring rules. The Hare and Coombs systems are based on the plurality and veto rules, respectively, while the Baldwin and Nanson systems are based on the Borda rule. We study the resistance of these four systems against shift bribery. Hereby, we consider both constructive and destructive settings. It is known that all four iterative voting systems are resistant to shift bribery, that is, both constructive and destructive shift bribery problems are NP-hard for these voting systems. We complement these NPhardness results by examining parameterized complexity of the shift bribery problems with respect to some natural parameters. Our results provide further evidence for the observation that shift bribery problems for iterative voting systems are computationally harder than for the corresponding non-iterative cases. In addition, our reductions apply several techniques which might be useful for proving hardness results for other iterative voting systems.