Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter for a neutral social choice function f of q>3 alternatives and n voters will be manipulable with probability at least $10^{-4}epsilon^2n^{-3}q^{-30}$, where $epsilon$ is the minimal statistical distance between f and the family of dictator functions.

Our results extend those of Friedgut Kalai and Naor [FKN09], which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in [BO91, CS03, EL05, PR06, CS06]) cannot hide manipulations completely.

Questions and Answers

You need to be logged in to be able to post here.