AAAI Publications, Thirtieth AAAI Conference on Artificial Intelligence

Font Size: 
Complexity of Shift Bribery in Committee Elections
Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Nimrod Talmon

Last modified: 2016-03-03

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.

Keywords


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

Full Text: PDF