Combinatorics Seminar

When: Sunday, May 1, 10am Where: Schreiber 309 Speaker: Nathan Keller, Weizmann Institute Title: A quantitative version of the Gibbard-Satterthwaite theorem for three alternatives

Abstract:

The well-known Gibbard-Satterthwaite theorem in Social Choice theory asserts that any election with at least three alternatives which is not a dictatorship can be manipulated. That is, there always exist situations in which some voter will "gain" from voting for another alternative instead of his preferred one. While the theorem shows that only a dictatorship is perfectly immune to manipulations, one may ask whether there exist election rules in which manipulation is possible so rarely that it can be practically neglected.

We answer this question on the negative. Specifically, we present a quantitative version of the Gibbard-Satterthwaite theorem: if an election on three alternatives is not very close to a dictatorship and the probability of each alternative to be elected is non-negligible, then even a random manipulation by a randomly chosen voter will succeed with a non-negligible probability.

Our proof uses the quantitative versions of Arrow's impossibility theorem (whose proof involves discrete harmonic analysis and hypercontractive inequalities), and a new directed isoperimetric inequality, which we prove using the FKG correlation inequality.

In the talk (which will assume no prior knowledge of neither social choice theory nor discrete harmonic analysis), we will present a sketch of our proof, and the application of the results to the field of Algorithmic game theory.

Joint work with Ehud Friedgut, Gil Kalai, and Noam Nisan.