Gibbard–Satterthwaite theorem | history


The strategic aspect of voting is already noticed in 1876 by Charles Dodgson, a pioneer in social choice theory, also known as Lewis Carroll. His quote (about a particular voting system) was made famous by Duncan Black:[8]

This principle of voting makes an election more of a game of skill than a real test of the wishes of the electors.

During the 1950s, Robin Farquharson published influential articles on voting theory.[9] In an article with Michael Dummett,[10] he conjectures that deterministic voting rules with at least three issues face endemic tactical voting.[11] This Farquarson-Dummett conjecture is proven independently by Allan Gibbard and Mark Satterthwaite. In a 1973 article, Gibbard exploits Arrow's impossibility theorem to prove the theorem that now bears his name, and he then deduces the present result, which is an immediate consequence of it.[1] Independently, Satterthwaite proves the same result in his PhD dissertation in 1973, then publishes it in a 1975 article.[2] His proof is also based on Arrow's impossibility theorem, but he doesn't expose the more general version given by Gibbard's theorem. Later, several authors develop variants of the proof, generally shorter, either for the theorem itself or for the corollary and weakened versions we mentioned above.[4][5][6][12][13][14][15][16][17]