Prices Matter for the Parameterized Complexity of Shift Bribery
Dipl.-Inf. Jiehua Chen (TU Berlin)
In the Shift Bribery problem, we are given an election (based on
preference orders), a preferred candidate p, and a budget. The goal is
to ensure that p wins by shifting p higher in some voters' preference
orders. However, each such a shift comes at a price, depending on the
voter and on the extent of the shift and we may not exceed the given
We study the parameterized complexity of Shift Bribery with respect to a number of parameters and several classes of price functions. If we parameterize by the number of positions by which p is shifted in total, then the problem is fixed-parameter tractable for Borda and Maximin voting rules, and is W-hard for Copeland voting rule. If we parameterize by the budget for the cost of shifting, then the results depend on the price function class. We also show that Shift Bribery tends to be easy when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic.
Back to the research colloquium site.