On the Complexity of Destructive Bribery in Approval-Based Multi-winner Voting

After more than two decades of extensive study on the complexity of single-winner voting problems, the computational social choice community has recently shifted its primary focus to multiwinner voting, given its generality and broad applications. In particular, many variants of manipulation, control, and bribery problems for approval-based multiwinner voting rules (ABM rules for short) have been studied from a complexity point of view (see e.g., [2, 27, 48, 55]). Existing works in this line of research predominantly concern the constructive model of these problems, which models scenarios where a strategic agent attempts to elevate a single distinguished candidate to winner status, or make a committee a winning committee. However, the destructive counterparts of these problems have not been adequately studied in the literature so far. This paper studies the complexity and the parameterized complexity of several destructive bribery problems for ABM rules. These problems are designed to capture scenarios where an election attacker (or briber) aims to prevent multiple distinguished candidates from winning by making changes to the votes (e.g., by bribing some voters to alter their votes) under certain budget constraints. The attacker's motivation may stem from these distinguished candidates being rivals (e.g., having completely different political views from the attacker), or the attacker attempting to make them lose to increase the winning chance of her preferred candidates. We consider five bribery operations categorized into two classes: atomic operations and vote-level operations.