More than 20 years ago, a series of papers by Bartholdi, Tovey, and Trick started a line of intense study of the computational complexity of two types of attacks on elections--control and manipulation. In manipulation, one has non-manipulative voters, who come in with preferences, and one or a coalition of manipulative voters, who come in as blank slates; one asks if there is some setting of the manipulative voters such that a designated candidate wins the election (that is, wins under the given voting rule). Far more recently, a type of attack known as bribery was introduced [1], in which each voter comes in with preferences, and one asks whether by a given “amount” of bribing one can make a designated candidate win the election. Existing work studies both the case where the amount is the number of voters one bribes, and where one pays by adding up some notion of the distance of the change one made in each vote.

This paper in some sense connects these two lines of investigation. Like non-coalitional manipulation, it fixes as part of the input a single voter of interest. However, like bribery, that voter has an initial preference and the goal is highly distance sensitive. In particular, the question asked in this paper is whether the given voter has a vote that is not more than a certain distance from his or her initial vote, and that makes a certain designated candidate the winner.

The paper studies this problem for a number of election systems and for a number of notions of distance. The paper obtains polynomial-time algorithms, NP-completeness results, and inapproximability results (holding if P does not equal NP). In particular, the paper shows that this problem is computationally easy for scoring rules and for Bucklin elections, but gives intractability and inapproximability results for Copeland and maximin elections. The paper’s results are interesting, and its fresh direction is natural and attractive.