Elections with Few Voters: Candidate Control Can Be Easy

Election control problems are concerned with affecting the result of an election by modifying the structure of the election. Such election modifications could be either introducing some new candidates or voters or removing some existing candidates or voters from the election or partitioning candidates or voters [2, 27, 32, 42, 56, 57, 34, 35, 62]. We focus on the computational complexity of election control by adding and deleting candidates (that is, candidate control), for the case where the election involves only a few voters. From the viewpoint of computational complexity, voter control with few voters has not received sufficient study. We focus on very simple, practical voting rules such as Plurality, Veto, andt-Approval, but discuss several more involved rules as well. To analyze the effect of allowing only a small number of voters, we use the formal tools of parameterized complexity theory [21, 23, 38, 60]. From the viewpoint of classical complexity theory, most of the candidate control problems for most of the typically studied voting rules are NPhard. Indeed, candidate control problems are NPhard even for the Plurality rule; nonetheless, there are some natural examples of candidate control problems with polynomialtime algorithms. It turns out that for the case of elections with few voters, that is, for control problems parameterized by the number of voters, the computational complexity landscape of candidate control is much more varied and sometimes quite surprising.