2014/11/28 by Jiehua Chen, Piotr Faliszewski, Chen, Jiehua +5 · 2 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #F.1.3 #F.2.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.11 #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.1411.7812
openalex publication_date 2014/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.