Vincent Conitzer
Jérôme Lang
ABSTRACT
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.
- John J. Bartholdi, III and James B. Odin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341--354, 1991.Google Scholar
Cross Ref
- John J. Bartholdi, III, Craig A. Tovey, and Michael A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227--241, 1989.Google ScholarCross Ref
- John J. Bartholdi, III, Craig A. Tovey, and Michael A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6:157--165, 1989.Google ScholarCross Ref
- Vincent Conitzer and Tuomas Sandholm. Complexity of manipulating elections with few candidates. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 314--319, Edmonton, Canada, 2002. Google ScholarDigital Library
- Vincent Conitzer and Tuomas Sandholm. Vote elicitation: Complexity and strategy-proofness. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 392--397, Edmonton, Canada, 2002. Google ScholarDigital Library
- Eithan Ephrati and Jeffrey S Rosenschein. The Clarke tax as a consensus mechanism among automated agents. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 173--178, Anaheim, CA, 1991.Google Scholar
- Eithan Ephrati and Jeffrey S Rosenschein. Multi-agent planning as a dynamic search for social consensus. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI), pages 423--429, Chambery, France, 1993.Google Scholar
- A Gibbard. Manipulation of voting schemes. Econometrica, 41:587--602, 1973.Google ScholarCross Ref
- A Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45:665--681, 1977.Google ScholarCross Ref
- A Gibbard. Straightforwardness of game forms with lotteries as outcomes. Econometrica, 46:595--614, 1978.Google ScholarCross Ref
- Richard M Karp. Reducibility among combinatorial problems. In Raymond E Miller and James W Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, NY, 1972.Google ScholarCross Ref
- Andreu Mas-Colell, Michael Whinston, and Jerry R. Green. Microeconomic Theory. Oxford University Press, 1995.Google Scholar
- David M Pennock, Eric Horvitz, and C. Lee Giles. Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative filtering. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 729--734, Austin, TX, 2000. Google ScholarDigital Library
- M A Satterthwaite. Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10:187--217, 1975.Google ScholarCross Ref
- R Zeckhauser. Majority rule with lotteries on alternatives. Quarterly Journal of Economics, 83:696--703, 1969.Google ScholarCross Ref
Index Terms
- How many candidates are needed to make elections hard to manipulate?
Recommendations
When are elections with few candidates 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 ...
How hard is bribery in elections?
We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the election's winner? ...
Coercion-resistant electronic elections with write-in candidates
EVT/WOTE'12: Proceedings of the 2012 international conference on Electronic Voting Technology/Workshop on Trustworthy ElectionsIt is often argued in the e-voting community that in the presence of write-in candidates, forced abstention attacks are always possible. Therefore, write-in candidates are often excluded in existing definitions of coercion-resistance arguing that those ...
Comments