A sufficient condition for voting rules to be frequently manipulable
The Gibbard-Satterthwaite Theorem states that (in unrestricted settings) any reasonable voting rule is manipulable. Recently, a quantitative version of this theorem was proved by Ehud Friedgut, Gil Kalai, and Noam Nisan: when the number of alternatives is three, for any neutral voting rule that is far from any dictatorship, there exists a voter such that a random manipulation - -that is, the true preferences and the strategic vote are all drawn i.i.d., uniformly at random - -will succeed with a probability of Ω(1/n), where n is the number of voters. However, it seems that the techniques used to prove this theorem can not be fully extended to more than three alternatives. In this paper, we give a more limited result that does apply to four or more alternatives. We give a sufficient condition for a voting rule to be randomly manipulable with a probability of Ω(1/n) for at least one voter, when the number of alternatives is held fixed. Specifically, our theorem states that if a voting rule r satisfies 1. homogeneity, 2. anonymity, 3. non-imposition, 4. a canceling-out condition, and 5. there exists a stable profile that is still stable after one given alternative is uniformly moved to different positions; then there exists a voter such that a random manipulation for that voter will succeed with a probability of Ω(1/n). We show that many common voting rules satisfy these conditions, for example any positional scoring rule, Copeland, STV, maximin, and ranked pairs. Copyright 2008 ACM.
