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 listsEnterprise Tuesday 2012/2013 Faith and Peace 80000 Hours Cambridge## Other talksReconciling centennial-scale climate variation during the last millennium in reconstructions and simulations The Ethical and Legal Elements of Capacity and Consent Determining structures in situ using cryo-electron tomography:enveloped viruses and coated vesicles Project Management Quantifying Uncertainty in Turbulent Flow Predictions based on RANS/LES Closures Nuclear fuel manufacture at Westinghouse Springfields past, present and future |