Gibbard-Satterthwaite theorem

[Steve Eppley]

Mike O. asked for someone to post the Gibbard-Satterthwaite theorem
about manipulability (voters gaining by misrepresenting their
preferences).  Here's the version in Ordeshook's book.

I'd better include some definitions of terms:

   O is the set of possible outcomes

   Ri is the preference order of person i

   R is the group's preference profile (R1, R2, ... Ri, ... Rn)

   G(R,O) is the social choice function (i.e., the tally method)

   "x Pi y" means "x is preferred more than y by person i"


   Manipulability
   --------------
   The social choice function G(R,O) is manipulable if there exists 
   a preference profile R = (R1, ..., Rn) for the group
   and at least one person i such that for some preference order Ri'
   G((R1, ... Ri-1, Ri', Ri+1, ..., Rn), O)  Pi  G(R,O)


   Gibbard-Satterthwaite
   ---------------------
   If O contains more than two elements, and if G is nonmanipulable 
   and yields a single outcome as the social choice, 
   then G is a dictatorship.

The theorem is a consequence of Arrow's theorem.  Proof is left as an 
exercise for the reader.  :-)

---Steve     (Steve Eppley    seppley at alumni.caltech.edu)