How many candidates are needed to make elections hard to manipulate?
<|reference_start|>How many candidates are needed to make elections hard to manipulate?: 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 (Conitzer 2002), 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.<|reference_end|>
@article{conitzer2003how,
    title={How many candidates are needed to make elections hard to manipulate?},
    author={Vincent Conitzer, Jerome Lang, Tuomas Sandholm},
    journal={In Proceedings of the 9th Conference on Theoretical Aspects of
  Rationality and Knowledge (TARK-03), pp. 201-214, Bloomington, Indiana, USA,
  2003},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0307003},
    primaryClass={cs.GT cs.CC cs.MA}
}