How many candidates are needed to make elections hard to manipulate?


Journal Article

In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally. The complexity of manipulating realistic elections where the number of candidates is a small constant was recently studied [4], but the emphasis was on the question of whether or not a protocol becomes hard to manipulate for some constant number of candidates. That work, in many cases, left open the question: How many candidates are needed to make elections hard to manipulate? This is a crucial question when comparing the relative manipulability of different voting protocols. In this paper we answer that question for the voting protocols of the earlier study: plurality, Borda, STV, Copeland, maximin, regular cup, and randomized cup. We also answer that question for two voting protocols for which no results on the complexity of manipulation have been derived before: veto and plurality with runoff. It turns out that the voting protocols under study become hard to manipulate at 3 candidates, 4 candidates, 7 candidates, or never.

Full Text

Duke Authors

Cited Authors

  • Conitzer, V; Lang, J; Sandholm, T

Published Date

  • June 20, 2003

Published In

  • Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, Tark 2003

Start / End Page

  • 201 - 214

Digital Object Identifier (DOI)

  • 10.1145/846241.846268

Citation Source

  • Scopus