BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A quantitative version of the Gibbard-Satterthwaite theorem - Kind
 ler\, G (HUJI)
DTSTART:20110401T103000Z
DTEND:20110401T113000Z
UID:TALK30513@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Consider an election between q alternatives\, where each of th
 e voters rank the different alternatives\, and the winner is determined ac
 cording to some predefined function of this voting profile. Such a social 
 choice function is called manipulable\, if a situation might occur where a
  voter who knows the rankings given by other voters can change her ranking
  in a way that does not reflect her true preference\, but which leads to a
 n outcome that is more desirable to her. \n\nGibbard and Satterthwaite pro
 ved that any social choice function where more than two alternatives can b
 e selected is manipulable\, unless it is a dictatorship (where the outcome
  of the election only depends on the choices of one voter). In the case wh
 ere the social choice function is neutral\, namely when it is invariant un
 der changing the names of the alternatives\, we prove a lower bound on the
  fraction of manipulable preference profiles which is inverse polynomial i
 n the number of voters and alternatives. Our proof in fact does not rely o
 n discrete harmonic analysis - finding an analytic version of the proof wo
 uld be the role of the audience. \n\nJoint work with Marcus Isaksson and E
 lchanan Mossel.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR