Duggan-Schwartz theorem
From Wikipedia, the free encyclopedia
The Duggan-Schwartz theorem is a result about voting systems designed to choose a nonempty set of winners from the preferences of certain individuals, where each individual ranks all candidates in order of preference. It states that, for three or more candidates, at least one of the following must hold:
- The system is not anonymous (some voters are treated differently from others), or
- The system is imposed (some candidates can never win), or
- Every voter's top preference is in the set of winners, or
- The system can be manipulated by an optimist or pessimist.
The first two conditions are considered forbidden in any fair election, and the third condition requires many candidates to "tie" for the win. The general conclusion, then, is the same as that usually given to the Gibbard-Satterthwaite theorem: voting systems can be manipulated. The result essentially holds even if ties are allowed in the ballots; in that case, there exists at least one "weak dictator" such that at least one of the candidates tied at the top of that voter's ballot is a winner.
The Gibbard-Satterthwaite theorem is a similar theorem that deals with voting systems that elect a single winner. Likewise, Arrow's theorem deals with voting systems that yield a complete preference order of the candidates, rather than only choosing winners.
[edit] References
- J. Duggan and T. Schwartz, "Strategic manipulability is inescapable: Gibbard-Satterthwaite without resoluteness", Working Papers 817, California Institute of Technology, Division of the Humanities and Social Sciences, 1992.
- J. Duggan and T. Schwartz, "Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized", Social Choice and Welfare, Vol. 17 (2000), pp. 85-93.
- Alan D. Taylor, "The manipulability of voting systems", The American Mathematical Monthly, April 2002.
- Alan D. Taylor, "Social Choice and the Mathematics of Manipulation", Cambridge University Press, 1st edition (2005), ISBN 0-521-00883-2. Chapter 4: Non-resolute voting rules.
