Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments

Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments

Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence

We study the parameterized complexity of counting variants of Swap- and Shift-Bribery, focusing on the parameterizations by the number of swaps and the number of voters. Facing several computational hardness results, using sampling we show experimentally that Swap-Bribery offers a new approach to the robustness analysis of elections.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting