  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 \ge 4$ alternatives and n voters will be manipulable with probability at
least $10^{-4} \eps^2 n^{-3} q^{-30}$, where $\eps$ 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.
