Complexity of Shift Bribery in Committee Elections
Abstract
We study the (parameterized) complexity of Shift Bribery for multiwinner voting rules. We focus on the SNTV, Bloc, k-Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule, since the original rule is NP-hard to compute. We show that Shift Bribery tends to be significantly harder in the multiwinner setting than in the single-winner one by showing settings where Shift Bribery is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. We show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin--Courant rule sometimes affects the complexity of Shift Bribery.
Cite
Text
Bredereck et al. "Complexity of Shift Bribery in Committee Elections." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10132Markdown
[Bredereck et al. "Complexity of Shift Bribery in Committee Elections." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/bredereck2016aaai-complexity/) doi:10.1609/AAAI.V30I1.10132BibTeX
@inproceedings{bredereck2016aaai-complexity,
title = {{Complexity of Shift Bribery in Committee Elections}},
author = {Bredereck, Robert and Faliszewski, Piotr and Niedermeier, Rolf and Talmon, Nimrod},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {2452-2458},
doi = {10.1609/AAAI.V30I1.10132},
url = {https://mlanthology.org/aaai/2016/bredereck2016aaai-complexity/}
}