Department of
Applied
Mathematics

Voting and Bribing in Single-Exponential Time (J. Matousek prize talk)

Martin Koutecký

Abstract

(joint work with D. Knop and M. Mnich)

We introduce a general problem about bribery in voting systems. In the R-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the perturbed election under the voting rule R. Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count to favour candidate.

As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules R, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized complexity of R-Swap-Bribery for all those voting rules, thereby solving a long-standing open problem and ``Challenge #2'' of the ``Nine Research Challenges in Computational Social Choice'' by Bredereck et al.

Further, our algorithm runs in single-exponential time for arbitrary costs; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the uniform-cost case for all scoring protocols, the maximin rule, and the Bucklin rule.