Election manipulation: the average-case

2012. január 4. szerda, 16:15

 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.