Essays on the complexity of voting manipulation

In their groundbreaking paper, Bartholdi, Tovey and Trick [6] argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. Following the direction proposed by this paper we examine the influence of features to which attention was not paid previously, namely, tie-breaking rules, and additional constraints, namely, the distance to the manipulator’s true preferences, on the complexity of manipulating elections. In Chapter 3 we show that all scoring rules, (simplified) Bucklin and Plurality with Runoff are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator’s utility function that is inspired by the original model of [6]. In contrast, we show that manipulation under randomized tie-breaking is hard for Copeland, Maximin, STV and Ranked Pairs. In Chapter 4 we demonstrate that Plurality, Maximin, Copeland and Borda, as well as many families of scoring rules, become hard to manipulate if we allow arbitrary polynomial-time deterministic tie-breaking rules. In Chapter 5, we investigate the complexity of optimal manipulation, i.e., finding a manipulative vote that achieves the manipulator’s goal yet deviates as little as possible from her true ranking. We study this problem for three natural notions of closeness, namely, swap distance, footrule distance, and maximum displacement distance, and a variety of voting rules, such as scoring rules, Bucklin, Copeland, and Maximin. For all three distances, we obtain polynomial-time algorithms for all scoring rules and Bucklin and hardness results for Copeland and Maximin.DOCTOR OF PHILOSOPHY (SPMS