Mathematical Sciences Research Institute

Home » Election manipulation: the average-case


Election manipulation: the average-case April 18, 2012 (11:00 AM PDT - 12:00 PM PDT)
Parent Program: --
Location: MSRI: Simons Auditorium
Speaker(s) Miklos Racz
Description No Description
No Video Uploaded

The Gibbard-Satterthwaite theorem says that any non-dictatorial way of electing a winner among three or more candidates is subject to manipulation. Recently, there has been much work in finding robust quantitative versions of this theorem, in particular by Friedgut, Kalai, Keller and Nisan for elections with three candidates, and Isaksson, Kindler and Mossel for neutral functions with at least four candidates. I will talk about a quantitative version of the Gibbard-Satterthwaite theorem that holds for any number of (at least three) candidates and does not require the neutrality assumption. The proof combines several ideas from the two previous proofs and also crucially uses reverse hypercontractivity. This is joint work with Elchanan Mossel.

No Notes/Supplements Uploaded No Video Files Uploaded