The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem (Q452827)

The paper is concerned with the manipulability of social choice functions. A social choice function is a function that operates on the rankings of a number of alternatives (say \(q\)) given by a number of voters (say \(n\)). It is manipulable if there is a voter that given the votes of the other voters can change his vote such that the outcome of the social choice function changes in his favour. A known Theorem of \textit{A. Gibbard} [Econometrica 41, 587--601 (1973; Zbl 0325.90081)] and \textit{M. A. Satterthwaite} [J. Econ. Theory 10, 187--217 (1975; Zbl 0315.90088)] states that any social choice function taking at least three values and not being a dictator function (i.e. the result of the choice function does not depend solely on the ranking of one voter only) is manipulable. This still leaves open questions concerning the complexity of finding a manipulator. In this paper the authors restrict theirselves to neutral choice functions, i.e. choice functions where the result does not depend on the names of the alternatives. They give lower bounds on the number of manipulation points in a neutral social choice function operating on more than four alternatives that is bounded away from the set of dictators. A rough lower bound is obtained by applying the Gibbard-Satterthwaite Theorem in combination with the method of cannonical paths. By refining the arguments finally a lower bound is reached that is polynomial in \(1/q\) showing that it is not too difficult to find manipulation points.