On the Manipulablilty of Elections on Average

Bodhayan Roy
Friday, 15 Mar 2013, 14:30 to 16:00
A-212 (STCS Seminar Room)
Elections are a way of aggregating preferences made by individual voters and making a choice for the whole. Questions about how to make such a "social choice", or whether such a choice can be made have been well studied under the topic of social choice theory.  One of the staggering conclusions(known as the Arrows Imposibility theorem) derived very early was that, if we assume certain simple assumptions about elections, then the only way of making the social choice is a dictatorship. In this lecture, we will see a quantitative version of a similar theorem(Gibbard–Satterthwaite theorem). That is, for a random voting profile, with non trivial probability an assumption about manipulability of the election is violated if the election is very different from a dictatorship.

For the super interested, we will be covering the paper "The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem" by Isaksson, Mossel and Kindler. The proof is purely geometric, combinatorial and does not use discrete harmonic analysis.