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

Autor:	Noam Nisan, Ehud Friedgut, Nathan Keller, Gil Kalai
Rok vydání:	2011
Předmět:	Discrete mathematics Range (mathematics) General Computer Science General Mathematics Compactness theorem Algorithmic game theory Election rule Social choice theory Mathematical economics Arrow's impossibility theorem Gibbard–Satterthwaite theorem Mathematics
Zdroj:	SIAM Journal on Computing. 40:934-952
ISSN:	1095-7111 0097-5397
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::483f706e501109cbd3ed6e5eabf0d09f https://doi.org/10.1137/090756740 Zobrazit plný text záznamu