Today I read a paper titled “How many candidates are needed to make elections hard to manipulate?”
The abstract is:
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.