1 Introduction1.1 Our results1.2 History and related work1.3 Techniques1.4 Organization of the paper2 Setup and notation3 Boundaries4 First Construction of Manipulation Paths5 Manipulation Points and First Proof6 Canonical Paths and Group Actions7 Refined Boundaries7.1 Manipulation points on refined boundaries7.2 Large Refined Boundaries8 Refined Construction of Manipulation Paths8.1 Proof of Theorem 1.79 Open problemsarXiv:0911.0517v4 [math.CO] 12 Apr 2010The Geometry of Manipulation - a Quantitative Proof of theGibbard Satterthwaite TheoremMarcus Isaksson∗Guy Kindler†Elchanan Mossel‡April 14, 2010AbstractWe prove a quantitative version of the Gibbard-Satterthwaite theorem. We show thata uniformly chosen voter profile for a neutral social choice function f of q ≥ 4 alternativesand n voters will be manipulable with probability at least 10−4ǫ2n−3q−30, whe re ǫ is theminimal statistical distance between f and the family of dictator functions.Our results extend those of [FKN09], which were obtained for the case of 3 alter-natives, and imply that the approach of masking manipulations behind computationalhardness (as considered in [BO91, CS03, EL05, PR06, CS06]) canno t hide manipulationscompletely.Our proof is geometric. More specifically it e xtends the method o f canonical paths toshow that the measure o f the profiles that lie on the interface of 3 o r mo re outcomes islarge. To the best of our knowledge o ur result is the first isoperimetric res ult to establishinterface of more than two bodie s.∗Chalmers University of Technology and G¨oteborg University, SE-41296 G¨oteborg, [email protected].†Incumbent of the Harry and Abe Sherman Lectureship Chair at the Hebrew Univeristy of Jerusalem.Supported by the Israel Science Foundation and by the Binational Science Foundation.‡Weizmann Institute and U.C. Berkeley [email protected]. Weizmann Institute of Science and U.C.Berkeley. Supported by DMS 0548249 (CAREER) award, by ISF grant 1300/08, by a Minerva Foundationgrant and by an ERC Marie Curie Grant 2008 239317.11 IntroductionSocial choice theory studies methods of collective decision making, and their interplay withsocial welfare and individual preference and behavior. Rigorous study of social choice datesback to the 18’th century, when Cond orcet discovered the following voting paradox: in a socialranking of three alternatives that is determined by the majority vote, an ‘irrational’ circularranking may occur where a candidate A is pr eferred over a candidate B, B is preferred overC, and C is preferred over A. Social choice theory in its modern form was established inthe 1950’s with the discovery of Arrow’s impossibility theorem [Arr50, Arr63], which showedthat all social ranking systems that satisfy a f ew reasonable conditions must either obtainirrational circular outcomes, or be dictatorships (a dictatorship is a system where the rankingis determined by just one voter).Manipulations. Many of the results in the study of social choice are negative, showing thatcertain desired properties of social choice schemes cannot be attained. One of the hallmarkexamples of such theorems was proved by Gibbard and Satterthwaite [Gib73, Sat75]. Theirtheorem considers a voting system where each of n voters rank q alternatives, and the winneris determined according to some pre-defin ed social choice function f : Lnq→ [q] of all thevoters’ rankings—here Lqdenotes the set of total orderin gs of the q alternatives.We say that a social choice function is manipulable, if a situation may occur where a voterwho knows the rank ings given by other voters can change her own ranking in a way that doesnot reflect her true preferences, but which leads to an outcome that is more desirable to her.FormallyDefinition 1.1 (Manipulation point). For a ranking x ∈ Lq, write ax> b to denote that thealternative a is preferred by x over b. A social choice function f : Lnq→ [q] is manipulable atx ∈ Lnqif there exist a y ∈ Lnqand i ∈ [n] such that x and y only differ in the i’th coordinateandf(y)xi> f(x) (1)In this case we also say that x is a m an ipulation point of f , and that (x, y) is a manipulationpair for f . We say that f is manipulable, if it is manipulable at some point x. We also saythat x is an r-manipulation point of f, if f has a manipulation pair (x, y) such that y isobtained from x by permuting (at most) r adjacent alternatives in one of the coordinates ofx.Gibbard and Satterthwaite proved that any social choice function which attains thr ee ormore values, and whose outcome d oes not depend on just one voter, must be manip ulable.Theorem 1.2 (Gibbard-Satterthwaite [Gib73, Sat75]). Any social choice function f : Lnq→[q] which takes at least three values and is not a dictator is manipulable.The Gibbard-Satterthwaite theorem has contributed significantly to the realization thatit is unlikely to expect truthfu lness in the context of voting. In a way, this and other resultsin social choice theory, contributed to the development of m echanism design, a field centeredaround developing social mechanisms that obtain desirable results even w hen each memberof the society acts selfishly.2Quantitative social choice. Theorem 1.2 is tight in the sense that monotone social choicefunctions which are dictators or only have two possible outcomes are indeed non-man ipulable(a function is non-monotone, and clearly manipulable, if for some set of rankings a votercan change the outcome from say a to b by moving a ahead of b in his preference). It isinteresting, however, to study manipulation quantitatively, asking not just wh ether a functionis manipulable but how many manipulations occur in it. To state results in quantitative socialchoice we need to define the distance between s ocial choice functions.Definition 1.3 (Distance between social choice functions). The distance D(f, g) between twosocial choice functions f, g : Lnq→ [q] is defined as the fraction of inputs on which they differ:D(f, g) = P[f(X) 6= g(X)], where X ∈ Lnqis uni formly selec ted. For a class G of socialfunctions, we write D(f, G) = ming∈GD(f, g).We also define some classes of functions that may not have any manipu lation points.Definition 1.4. We use the following three classes of functions, defined for parameters nand q that remain implicit (when used, the parameters will be obvious from the context):CONST = {f : Lnq→ [q] | f is constant }DICTi= {f : Lnq→ [q] | f only depend