Approximation and Hardness of Shift-Bribery

Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat

AAAI 2019 pp. 1901-1908

doi:10.1609/AAAI.V33I01.33011901 /aaai/2019/faliszewski2019aaai-approximation/

Abstract

In the SHIFT-BRIBERY problem we are given an election, a preferred candidate, and the costs of shifting this preferred candidate up the voters’ preference orders. The goal is to find such a set of shifts that ensures that the preferred candidate wins the election. We give the first polynomial-time approximation scheme for the case of positional scoring rules, and for the Copeland rule we show strong inapproximability results.

PDF AAAI Semantic Scholar

Cite

Text

Faliszewski et al. "Approximation and Hardness of Shift-Bribery." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33011901

Markdown

[Faliszewski et al. "Approximation and Hardness of Shift-Bribery." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/faliszewski2019aaai-approximation/) doi:10.1609/AAAI.V33I01.33011901

BibTeX

@inproceedings{faliszewski2019aaai-approximation,
  title     = {{Approximation and Hardness of Shift-Bribery}},
  author    = {Faliszewski, Piotr and Manurangsi, Pasin and Sornat, Krzysztof},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1901-1908},
  doi       = {10.1609/AAAI.V33I01.33011901},
  url       = {https://mlanthology.org/aaai/2019/faliszewski2019aaai-approximation/}
}