Complexity of Shift Bribery in Committee Elections
This addresses a problem in computational social choice for researchers and practitioners, providing theoretical insights into election manipulation, but it is incremental as it extends known single-winner complexity analyses to multiwinner settings.
The paper tackles the computational complexity of the SHIFT BRIBERY problem in multiwinner elections, showing that it tends to be harder than in single-winner cases, with specific rules like SNTV, Bloc, k-Borda, and Chamberlin-Courant exhibiting hardness or inapproximability results.
Given an election, a preferred candidate p, and a budget, the SHIFT BRIBERY problem asks whether p can win the election after shifting p higher in some voters' preference orders. Of course, shifting comes at a price (depending on the voter and on the extent of the shift) and one must not exceed the given budget. We study the (parameterized) computational complexity of S HIFT BRIBERY for multiwinner voting rules where winning the election means to be part of some winning committee. We focus on the well-established 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 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. Moreover, 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.