×

zbMATH — the first resource for mathematics

Voting schemes for which it can be difficult to tell who won the election. (English) Zbl 0672.90004
Summary: 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.

MSC:
91B14 Social choice
68Q25 Analysis of algorithms and problem complexity
91D99 Mathematical sociology (including anthropology)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barthelemy JP, Monjardet B (1981) The median procedure in cluster analysis and social choice theory. Math Soc Sci 1:235-267 · Zbl 0486.62057 · doi:10.1016/0165-4896(81)90041-X
[2] Bartholdi JJ III, Tovey CA, Trick MA (1989) The computational difficulty of manipulating an election. Soc Choice Welfare (in print) · Zbl 0682.90007
[3] Black D (1958) Theory of committees and elections. Cambridge University Press, Cambridge · Zbl 0091.15706
[4] Marquis de Condorcet (1785) Essai sur l’application de l’analyse a la probabilité des decisions rendues a la pluralité des voix. Paris
[5] Fishburn PC (1974) Paradoxes of voting. Am Pol Sci Rev 68:537-546 · doi:10.2307/1959503
[6] Fishburn PC (1977) Condorcet social choice functions. SIAM J Appl Math 33:469-489 · Zbl 0369.90002 · doi:10.1137/0133030
[7] Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Francisco · Zbl 0411.68039
[8] Grötschel M, Junger M, Reinelt G (1984) A cutting plane algorithm for the linear ordering problem. Oper Res 32:1195-1220 · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[9] Kelly JS (1974) Voting anomalies, the number of voters, and the number of alternatives. Econometrica 42:239-251 · Zbl 0289.90005 · doi:10.2307/1911974
[10] Kemeny J (1959) Mathematics without numbers Daedalus 88:571-591
[11] Kemeny J, Snell L (1960) Mathematical models in the social sciences. Ginn, Boston · Zbl 0256.92003
[12] Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math Oper Res 8:538-547 · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[13] Niemi RG, Riker WH (1976) The choice of voting systems. Sci Am 234:21-27 · doi:10.1038/scientificamerican0676-21
[14] Nurmi H (1983) Voting procedures: a summary analysis. Br J Polit Sci 13: 181-208 · doi:10.1017/S0007123400003215
[15] Stearns R (1959) The voting problem. Am Math Mon 66:761-763 · Zbl 0090.25101 · doi:10.2307/2310461
[16] Wakabayashi Y (1986) Aggregation of binary relations: algorithmic and polyhedral investigations. Doctoral dissertation, University of Augsburg (unpublished) · Zbl 0606.68036
[17] Young HP, Levenglick A (1978) A consistent extension of Condorcet’s election principle. SIAM J Appl Math 35:285-300 · Zbl 0385.90010 · doi:10.1137/0135023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.