A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three Alternatives
Friedgut, Ehud, Kalai, Gil, Keller, Nathan, Nisan, Noam
–arXiv.org Artificial Intelligence
The Gibbard-Satterthwaite theorem states that every non-dictatorial election rule among at least three alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with a non-negligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range.
arXiv.org Artificial Intelligence
May-25-2011