Title :
Elections Can be Manipulated Often
Author :
Friedgut, Ehud ; Kalai, Gil ; Nisan, Noam
Author_Institution :
Hebrew Univ. of Jerusalem, Jerusalem
Abstract :
The Gibbard-Satterthwaite theorem states that every non-trivial voting method among 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 among 3 alternatives that is far from being a dictatorship.
Keywords :
government data processing; random processes; Gibbard-Satterthwaite theorem; neutral voting method; nontrivial voting method; random manipulation; Aggregates; Computer science; Gas insulated transmission lines; Nominations and elections; Voting; Computational game theory; elections; social choice;
Conference_Titel :
Foundations of Computer Science, 2008. FOCS '08. IEEE 49th Annual IEEE Symposium on
Conference_Location :
Philadelphia, PA
Print_ISBN :
978-0-7695-3436-7
DOI :
10.1109/FOCS.2008.87
