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

Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier

IJCAI 2021 pp. 52-58

doi:10.24963/IJCAI.2021/8 /ijcai/2021/boehmer2021ijcai-winner/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Boehmer et al. "Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/8

Markdown

[Boehmer et al. "Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/boehmer2021ijcai-winner/) doi:10.24963/IJCAI.2021/8

BibTeX

@inproceedings{boehmer2021ijcai-winner,
  title     = {{Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments}},
  author    = {Boehmer, Niclas and Bredereck, Robert and Faliszewski, Piotr and Niedermeier, Rolf},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {52-58},
  doi       = {10.24963/IJCAI.2021/8},
  url       = {https://mlanthology.org/ijcai/2021/boehmer2021ijcai-winner/}
}