A Quantitative Version of the Gibbard–Satterthwaite Theorem for Three Alternatives

Abstract

The Gibbard–Satterthwaite theorem states that every nondictatorial 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 nonnegligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range.