Abstract
We show that a voting scheme suggested by Lewis Carroll can be impractical in that it can be computationally prohibitive (specifically, NP-hard) to determine whether any particular candidate has won an election. We also suggest a class of “impracticality theorems” which say that any fair voting scheme must, in the worst-case, require excessive computation to determine a winner.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barthelemy JP, Monjardet B (1981) The median procedure in cluster analysis and social choice theory. Math Soc Sci 1:235–267
Bartholdi JJ III, Tovey CA, Trick MA (1989) The computational difficulty of manipulating an election. Soc Choice Welfare (in print)
Black D (1958) Theory of committees and elections. Cambridge University Press, Cambridge
Marquis de Condorcet (1785) Essai sur l'application de l'analyse a la probabilité des decisions rendues a la pluralité des voix. Paris
Fishburn PC (1974) Paradoxes of voting. Am Pol Sci Rev 68:537–546
Fishburn PC (1977) Condorcet social choice functions. SIAM J Appl Math 33:469–489
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Francisco
Grötschel M, Junger M, Reinelt G (1984) A cutting plane algorithm for the linear ordering problem. Oper Res 32:1195–1220
Kelly JS (1974) Voting anomalies, the number of voters, and the number of alternatives. Econometrica 42:239–251
Kemeny J (1959) Mathematics without numbers Daedalus 88:571–591
Kemeny J, Snell L (1960) Mathematical models in the social sciences. Ginn, Boston
Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math Oper Res 8:538–547
Niemi RG, Riker WH (1976) The choice of voting systems. Sci Am 234:21–27
Nurmi H (1983) Voting procedures: a summary analysis. Br J Polit Sci 13: 181–208
Stearns R (1959) The voting problem. Am Math Mon 66:761–763
Wakabayashi Y (1986) Aggregation of binary relations: algorithmic and polyhedral investigations. Doctoral dissertation, University of Augsburg (unpublished)
Young HP, Levenglick A (1978) A consistent extension of Condorcet's election principle. SIAM J Appl Math 35:285–300
Author information
Authors and Affiliations
Additional information
The authors thank the editor and three anonymous referees for many helpful suggestions.
Rights and permissions
About this article
Cite this article
Bartholdi, J., Tovey, C.A. & Trick, M.A. Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welfare 6, 157–165 (1989). https://doi.org/10.1007/BF00303169
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00303169