Elections Can be Manipulated Often

Authors: 
Ehud Friedgut, Gil Kalai and Noam Nisan
Abstract: 

The Gibbard-Satterthwaite theorem states that every non-trivial voting method between at least 3 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 non-negligible probability for every neutral voting method between 3 alternatives that is far from being a dictatorship.

Date: 
April, 2008
Published in: 
Number: 
481