Sunday, January 24, 2010

Quantitative Gibbard–Satterthwaite Theorem

This is a talk I gave in a few places- the last one is the Algorithmic Game Theory Seminar at Hebrew University on Jan 16, 2010.

The topic is a new new Quantitative proof of the Gibbard–Satterthwaite Theorem. This is based on a joint paper with Marcus Isaksson and Guy Kindler.
The talk can be found here (the previous version on google-doc is for some reason not accessible)

The paper can be found here:

See also the blog by Noam Nisan:

http://agtb.wordpress.com/2009/12/23/new-paper-average-case-manipulation-of-elections/

Finally here is the abstract from the Arxiv:

arXiv:0911.0517 (November 2009)
The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem
Marcus Isaksson, Guy Kindler and Elchanan Mossel
Received. 03 November 2009 Last updated. 08 January 2010
Abstract. We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function $f$ of $q geq 4$ alternatives and $n$ voters will be manipulable with probability at least $10^{-7} eps^2 n^{-3} q^{-32}$, where $eps$ is the minimal statistical distance between $f$ and the family of dictator functions. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.
Categories. math.CO math.PR





No comments:

Post a Comment