COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > A quantitative version of the Gibbard-Satterthwaite theorem

## A quantitative version of the Gibbard-Satterthwaite theoremAdd to your list(s) Download to your calendar using vCal - Kindler, G (HUJI)
- Friday 01 April 2011, 11:30-12:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis Consider an election between q alternatives, where each of the voters rank the different alternatives, and the winner is determined according to some predefined function of this voting profile. Such a social choice function is called manipulable, if a situation might occur where a voter who knows the rankings given by other voters can change her ranking in a way that does not reflect her true preference, but which leads to an outcome that is more desirable to her. Gibbard and Satterthwaite proved that any social choice function where more than two alternatives can be selected is manipulable, unless it is a dictatorship (where the outcome of the election only depends on the choices of one voter). In the case where the social choice function is neutral, namely when it is invariant under changing the names of the alternatives, we prove a lower bound on the fraction of manipulable preference profiles which is inverse polynomial in the number of voters and alternatives. Our proof in fact does not rely on discrete harmonic analysis – finding an analytic version of the proof would be the role of the audience. Joint work with Marcus Isaksson and Elchanan Mossel. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
Note that ex-directory lists are not shown. |
## Other listsStone Lectures Department of Geography - Book launch women@CL Speaker Lunch Series## Other talksAnonymity in Cryptocurrencies NK cells: in and out of the circulation The impact of parental traits on the phenotypes of children with genomic copy number variations Research frontiers and new therapeutic strategies in pancreatic cancer Jerrard Hayes - Title to Be Confirmed G I TAYLOR LECTURE - Waves in the airways: a carpet of microscopic rowers keeps us alive |