Complexity of Shift Bribery in Committee Elections

Authors

  • Robert Bredereck Technische Universität Berlin
  • Piotr Faliszewski AGH University of Science and Technology, Krakow
  • Rolf Niedermeier Technische Universität Berlin
  • Nimrod Talmon Technische Universität Berlin

DOI:

https://doi.org/10.1609/aaai.v30i1.10132

Keywords:

multiwinner elections, shift bribery, algorithms, parameterized complexity, campaign management, Chamberlin--Courant

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.

AAAI 2016 Proceedings Cover

Downloads

Published

2016-03-03

How to Cite

Bredereck, R., Faliszewski, P., Niedermeier, R., & Talmon, N. (2016). Complexity of Shift Bribery in Committee Elections. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10132

Issue

Vol. 30 No. 1 (2016): Thirtieth AAAI Conference on Artificial Intelligence

Section

Technical Papers: Multiagent Systems