Abstract

In their groundbreaking paper, Bartholdi, T ovey and Trick [1989] argued that many well-known vot-ing rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. An important as-sumption made in that paper is that the manipula-tor’s goal is to ensure that his preferred candidate is among the candidates with the maximum score,or, equivalently, that ties are broken in favor of the manipulator’s preferred candidate. In this pa-per, we examine the role of this assumption in the easiness results of[Bartholdi et al., 1989]. We ob-serve that the algorithm presented in [Bartholdi et al., 1989]extends to all rules that break ties accord-ing to a fixed ordering over the candidates. We then show that all scoring rules are easy to manipulate if the winner is selected from all tied candidates uni-formly at random. This result extends to Maximin under an additional assumption on the manipula-tor’s utility function that is inspired by the origi-nal model of [Bartholdi et al., 1989]. In contrast,we show that manipulation becomes hard when ar-bitrary polynomial-time tie-breaking rules are al-lowed, both for the rules considered in [Bartholdi et al., 1989], and for a large class of scoring rules