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

Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier

Abstract

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.
BibTeX
@inproceedings{boehmer2021winner,
  author = {Niclas Boehmer and Robert Bredereck and Piotr Faliszewski and Rolf Niedermeier},
  title = {{Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/8},
}

Loading related content...

Figure