TY - GEN
T1 - Voting and Bribing in Single-Exponential Time
AU - Knop, Dusan
AU - Koutecký, Martin
AU - Mnich, Matthias
N1 - data source: no data used
PY - 2017
Y1 - 2017
N2 - 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 manipulated 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 for a 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 Cl rule. In particular, our result resolves the parameterized of R-SwAP BRIBERY for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al.Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.
AB - 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 manipulated 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 for a 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 Cl rule. In particular, our result resolves the parameterized of R-SwAP BRIBERY for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al.Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.
KW - parameterized algorithm
KW - swap bribery
KW - n-fold integer programming
U2 - 10.4230/LIPIcs.STACS.2017.46
DO - 10.4230/LIPIcs.STACS.2017.46
M3 - Conference article in proceeding
VL - 66
T3 - Leibniz International Proceedings in Informatics
SP - 46:1-46:14
BT - 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
PB - Schloss Dagstuhl
CY - Dagstuhl, Germany
ER -