Anyone But Them: The Complexity Challenge for A Resolute Election Controller

We study the voting problems where given is an election associated with a subset J of candidates, and the question is whether we can modify the election in a way so that none of the candidates in J wins the election. The modification operations include either adding some votes/candidates or deleting some votes/candidates. These problems are natural generalizations of destructive control problems where J is a singleton and capture many practical situations. We achieve a broad range of complexity results for a number of single-winner voting systems involving voting rules which are compositions of commonly used voting correspondences, such as Borda, Maximin and Copeland α , and three tie-breaking schemes, namely the fixed-order, random candidates and random votes. In particular, we achieve polynomial-time solvability results, NP-hardness results, fixed-parameter tractability results as well as XP results. In addition, we study other tie-breaking schemes and show that the complexity of the problems may depend on tie-breaking schemes.