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 @math alternatives and n voters will be manipulable with probability at least @math , where @math is the minimal statistical distance between f and the family of dictator functions. Our results extend those of FrKaNi:08, which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in BarthOrline:91, ConitzerS03b, ElkindL05, ProcacciaR06 and ConitzerS06) cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.
Theorem considers the case of @math and more alternatives, compared to @math alternatives considered in @cite_3 . The two results are, however, difficult to compare: the result of @cite_3 counts the number of manipulation pairs @math , where @math is a manipulation point, and @math is the voting vector obtained from @math after one of the voters changed her vote to gain a more favorable outcome, while our result is stated in terms of the number of manipulations alone. Our proof actually shows a lower bound XXXIX
@cite_3
2070986136
The Gibbard-Satterthwaite theorem states that every non-trivial voting method among at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with non-negligible probability for every neutral voting method among 3 alternatives that is far from being a dictatorship.