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 listsLife Science Cambridge Review of International Affairs EPRG Energy and Environment (E&E) Series Easter 2012## Other talksHow to (Re)Use Big Data w/Prof Sabina Leonelli Cambridge-Lausanne Workshop 2018 - Day 2 Delivering The Promise of the Internet of Things. How IoT systems can benefit transport, logistics and infrastructure National crises, viewed in the light of personal crises w/ Prof Jared Diamond Deep Generative Models Forced Migration |