Skip to main content
SpringerLink
Log in

The computational difficulty of manipulating an election

  • Published:
Social Choice and Welfare Aims and scope Submit manuscript

Abstract

We show how computational complexity might protect the integrity of social choice. We exhibit a voting rule that efficiently computes winners but is computationally resistant to strategic manipulation. It is NP-complete for a manipulative voter to determine how to exploit knowledge of the preferences of others. In contrast, many standard voting schemes can be manipulated with only polynomial computational effort.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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

    Google Scholar 

  2. Bartholdi JJ III, Tovey CA, Trick MA (1987) How hard is it to control an election? Econometrica (submitted)

  3. Bollobas, B (1979) Graph theory. Graduate Texts 63. Springer, Berlin Heidelberg New York

    Google Scholar 

  4. Gardenfors P (1976) Manipulation of social choice functions. J Econ Theory 13:217–228

    Google Scholar 

  5. Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman, San Francisco

    Google Scholar 

  6. Gibbard A (1973) Manipulation of voting schemes. Econometrica 41:587–601

    Google Scholar 

  7. Gottinger HW (1987) Choice and complexity. Math Soc Sci 14:1–17

    Google Scholar 

  8. Kazic B, Keene RD, Lim KA (eds) (1986) The official laws of chess. Maxmillan, New York

    Google Scholar 

  9. Lewis A (1985) On the effectively computable realizations of choice functions. Math Soc Sci 10: 43–80

    Google Scholar 

  10. Morrison M (ed) (1978) Official rules of chess, 2nd Edn. David McKay, New York

    Google Scholar 

  11. Niemi RG, Riker WH (1976) The choice of voting systems. Sci Am 234:21–27

    Google Scholar 

  12. Nurmi H (1983) Voting procedures: a summary analysis. Br J Polit Sci 13:181–208

    Google Scholar 

  13. Nurmi H (1986) Problems of finding optimal voting and representation systems. E J Oper Res 24:91–98

    Google Scholar 

  14. Satterthwaite MA (1975) Strategy-proofness and Arrow's conditions. J Econ Theory 10:187–217

    Google Scholar 

  15. Stearns R (1959) The voting problem. Am Math Mon 66:761–763

    Google Scholar 

  16. Tovey CA (1984) A simplified NP-complete satisfiability problem. Disc Appl Math 8:85–89

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332, Atlanta, GA, USA

    J. J. Bartholdi III, C. A. Tovey & M. A. Trick

Authors
  1. J. J. Bartholdi III
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. A. Tovey
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. A. Trick
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The authors appreciate many helpful comments and suggestions by the editor and three anonymous referees. We also thank Michel Balinski, Salvador Barbera, Jean-Pierre Barthelemy, and Peyton Young for stimulating discussions.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bartholdi, J.J., Tovey, C.A. & Trick, M.A. The computational difficulty of manipulating an election. Soc Choice Welfare 6, 227–241 (1989). https://doi.org/10.1007/BF00295861

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00295861

Keywords

Search

Navigation