Computer Science – Computer Science and Game Theory
Scientific paper
2003-07-02
In Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-03), pp. 201-214, Bloomington,
Computer Science
Computer Science and Game Theory
Scientific paper
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.
Conitzer Vincent
Lang Jérôme
Sandholm Tuomas
No associations
LandOfFree
How many candidates are needed to make elections hard to manipulate? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with How many candidates are needed to make elections hard to manipulate?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How many candidates are needed to make elections hard to manipulate? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-630685