The Gibbard-Pattanaik-Satterthwaite theorem
As previously noted the problem identified by Pliny was the problem of strategic voting. The general result on this topic was obtained independently by Allan Gibbard (1973) and Mark Satterthwaite (1975).
A fundamental contribution due to Dummett and Farquharson (1961), more than ten years before, in spite of being published in Econometrica went rather unnoticed. The major contributions of Prasanta Pattanaik (1973, 1978) have been neglected because Pattanaik’s framework was the traditional Arrovian framework of aggregation functions and, accordingly, strategic voting had to be defined in a more complicated way than in the framework chosen by Gibbard and Satterthwaite.We will assume that X, the set of social states, here, say, candidates, is finite and, for reasons of simplicity, that individual preferences are given by linear orders, denoted by si. This means that individuals rank the candidates without ties. A profile π will then be a list of individual rankings (s1,..., >n). A social choice function is a function f from the set of profiles into X. This means that rather than selecting a social preference as in the case of aggregation functions, a social choice function selects, given a profile, a candidate.
We will say that individual i manipulates the social choice function f in profile π = (s1,..., >n) if there is a profile π' which is identical to profile π except for the preference of individual i such thatf(π') si f(π). For simplicity, imagine that the profile π is a profile of sincere individual preferences. Individual i manipulates f if, by misrepresenting her preference (lying), she can force the function to generate a result that she prefers to the result that would have been obtained otherwise. We will assume that the social choice function is surjective: for any candidate x, there is a profile π such that x = f(π). This basically means that there is no fictitious candidate. A consequence is, of course, that if there are at least two candidates, the function cannot be a constant function.
A dictator for a social choice function f will be an individual i such that for all profiles π,f(π) si x, for all x ≠f(π).
Gibbard-Satterthwaite theorem Suppose that there are at least two individuals and three candidates, that all linear orderings (individual preferences) are permissible and that f is surjective and non-manipulable. Then there is a dictator.
This theorem has been at the origin of a tremendous number of contributions in social choice theory, but also in public economics, and is strongly related to implementation theory (Jackson 2001; Maskin and Sjδstrδm 2002).