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
Main Track. Pages 52-58.
https://doi.org/10.24963/ijcai.2021/8
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