Approximation and Hardness of Shift-Bribery
DOI:
https://doi.org/10.1609/aaai.v33i01.33011901Abstract
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.
Downloads
Published
2019-07-17
How to Cite
Faliszewski, P., Manurangsi, P., & Sornat, K. (2019). Approximation and Hardness of Shift-Bribery. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 1901-1908. https://doi.org/10.1609/aaai.v33i01.33011901
Issue
Section
AAAI Technical Track: Game Theory and Economic Paradigms