The geometry of manipulation — A quantitative proof of the Gibbard-Satterthwaite theorem

摘要

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 ≥ 4 alternatives and n voters will be manipulable with probability at least 10−4∈2 n −3 q −30, where ∈ is the minimal statistical distance between f and the family of dictator functions.