Abstract
We give evidence that Single Tranferable Vote (STV) is computationally resistant to manipulation: It is NP-complete to determine whether there exists a (possibly insincere) preference that will elect a favored candiate, even in an election for a single seat. Thus strategic voting under STV is qualitatively more difficult than under other commonly-used voting schemes. Furthermore, this resistance to manipulation is inherent to STV and does not depend on hopeful extraneous assumptions like the presumed difficulty of learning the preferences of the other voters. We also prove that it is NP-complete to recognize when an STV election violates monotonicity. This suggests that non-monotonicity in STV elections might be perceived as less threatening since it is in effect “hidden” and hard to exploit for strategic advantage.
Similar content being viewed by others
References
Anonymous (1989) Proportional Representation: Ballot Counting, Tally Sheets, and Background Information, prepared for the municipal election, Cambridge, Massachusetts, November 1989, FLM Cambridge, Research Division. Available from the Election Commission of the City of Cambridge, 362 Green Street, Cambridge, Massachusetts 02139
Austen-Smith D, Banks J (1990) Monotonicity in electoral systems. Manuscript, Department of Economics, University of Rochester, Rochester, NY. Polit Sci Rev (to appear)
Bartholdi JJ III, Tovey CA, Narasimhan L (1990) Recognizing majority-rule equilibrium in spatial voting games. Soc Choice Welfare 8: 183–197
Bartholdi JJ III, Tovey CA, Trick MA (1989) Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welfare 6: 157–165
Bartholdi JJ III, Tovey CA, Trick MA (1989) The computational difficulty of manipulating an election. Soc Choice Welfare 6: 227–241
Brams SJ (1982) The AMS nominating system is vulnerable to truncation of preferences. Notices Am Math Soc 29: 136–138
Brams SJ, Fishburn PC (1991) Alternative voting systems. Preprint from the Department of Politics, New York University, New York, NY 10003. In: Maisel LS (ed) Encyclopedia of American political parties and elections. Garland, New York
Chamberlin JR (1985) An investigation into the relative manipulability of four voting systems. Behav Sci 30: 195–203
Doron G, Kronick R (1977) Single transferable vote: an example of a perverse social choice function. Am J Polit Sci 21: 303–311
Dummet M (1984) Voting procedures. Clarendon Press, Oxford
Fishburn PC (1982) Monotonicity paradoxes in the theory of elections. Disc Appl Math 4: 119–134
Fishburn PC, Brams SJ (1983) Paradoxes of preferential voting. Math Mag 56: 207–214
Gärdenfors P (1976) Manipulation of social choice functions. J Econ Theory 13: 217–228
Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-compleness. WH Freeman, San Francisco
Gibbard A (1973) Manipulation of voting schemes. Econometrica 41: 587–601
Hill ID, wichmann BA, Woodall DR (1987) Single transferable vote by Meek's method. Comput J 30: 277–281
Holzman R (1989) To vote or not to vote: what is the quota? Disc Appl Math 22: 133–141
Janofsky M (1990) No clear favorite in search for site. NY Times (Sports Sect) September 16, 1990
Mill JS (1861) Considerations on Representative Government (1962 reprinting by Henry Regnery Company, Chicago of the original edition published in Londen by Parker, Son, and Bourn in 1861)
Moulin H (1988) Axioms of cooperative decision making. Cambridge University Press, Cambridge
Moulin H (1988) Condorcet's principle implies the no-show paradox. J Econ Theory 45: 53–64
Muller E, Satterthwaite MA (1977) The equivalence of strong positive associate and strategy-proofness. J Econ Theory 14: 412–418
Newland RA (1972) Only half a democracy. The electoral reform society of Great Britain and Ireland, London
Nitzan S (1985) The vulnerability of point-voting schemes to preference variation and strategic manipulation. Publ Choice 47: 349–370
Nurmi H (1990) Probability models in constitutional choice. Eur J Polit Econ 6: 107–117
Saari DG (1990) Susceptibility to manipulation. Publ Choice 64: 21–41
Saijo T (1987) On constant Maskin monotonic social choice functions. J Econ Theory 42: 382–386
Satterthwaite MA (1975) Strategy-proofness and Arrow's conditions. J Econ Theory 10: 187–217
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bartholdi, J.J., Orlin, J.B. Single transferable vote resists strategic voting. Soc Choice Welfare 8, 341–354 (1991). https://doi.org/10.1007/BF00183045
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00183045