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

Boehmer, Niclas; Bredereck, Robert; Faliszewski, Piotr; Niedermeier, Rolf

doi:10.24963/ijcai.2021/8

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

Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 52-58.

https://doi.org/10.24963/ijcai.2021/8

Keywords

Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting

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.

Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, and Rolf Niedermeier. 2021. Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 52–58. https://doi.org/10.24963/ijcai.2021/8

@inproceedings{ijcai2021p8,
  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 = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {52--58},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/8},
  url       = {https://doi.org/10.24963/ijcai.2021/8},
}

TY  - CPAPER
TI  - Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments
AU  - Boehmer, Niclas
AU  - Bredereck, Robert
AU  - Faliszewski, Piotr
AU  - Niedermeier, Rolf
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 52
EP  - 58
DO  - 10.24963/ijcai.2021/8
UR  - https://doi.org/10.24963/ijcai.2021/8
ER  -