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 cancelingout 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.
Starting from different assumptions, Xia and Conitzer showed that a random manipulation would succeed with probability Ω( 1 n ) for 3 or more candidates for STV, for 4 or more candidates for any scoring rule and for 5 or more candidates for Copeland REF .
A sufficient condition for voting rules to be frequently manipulable
EC '08
Mathematics Computer Science