Palash Dey
Y. Narahari
ABSTRACT
We study manipulability in elections when the number of candidates is large. Elections with a large number of voters have been studied in the literature and the focus of this paper is on studying election with a large number of candidates. Manipulability, when the number of candidates is large, is significant in the context of computational social choice. Our investigation in this paper covers the impartial culture (IC) assumption as well as a new culture of society which we call impartial scores culture (ISC) assumption, where all score vectors of the candidates are equally likely. Under the IC and ISC models, we study asymptotic collusion-proofness for plurality, veto, k-approval, and Borda voting rules. We provide bounds for the fraction of manipulable profiles when the number of candidates is large. Our results show that the size of the coalition and the tie-breaking rule play a crucial role in determining whether or not a voting rule satisfies asymptotic collusion-proofness.
- J. Bartholdi and J. Orlin. Single transferable vote resists strategic voting. Social Choice and Welfare, 8(4):341--354, 1991.Google Scholar
Cross Ref
- J. Bartholdi, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3):227--241, 1989.Google ScholarCross Ref
- A. Gibbard. Manipulation of voting schemes: a general result. Econometrica: Journal of the Econometric Society, pages 587--601, 1973.Google ScholarCross Ref
- S. Nitzan. The vulnerability of point-voting schemes to preference variation and strategic manipulation. Public Choice, 47(2):349--370, 1985.Google ScholarCross Ref
- G. Pritchard and M. C. Wilson. Asymptotics of the minimum manipulating coalition size for positional voting rules under impartial culture behaviour. Mathematical Social Sciences, 58(1):35--57, 2009.Google ScholarCross Ref
- M. Satterthwaite. Strategy-proofness and arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187--217, 1975.Google ScholarCross Ref
- A. Slinko. On asymptotic strategy-proofness of classical social choice rules. Theory and Decision, 52(4):389--398, 2002.Google ScholarCross Ref
Index Terms
- Asymptotic collusion-proofness of voting rules: the case of large number of candidates
Recommendations
Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
We investigate manipulation of the Borda voting rule, as well as two elimination style voting rules, Nanson's and Baldwin's voting rules, which are based on Borda voting. We argue that these rules have a number of desirable computational properties. For ...
Lot-based voting rules
AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2The Internet Engineering Task Force develops and promotes Internet standards like TCP/IP. The chair of the Task Force is chosen by an election which starts with a set of voters being selected at random from the electorate of volunteers. Selecting ...
Obvious Manipulability of Voting Rules
Algorithmic Decision TheoryAbstractThe Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability that was proposed by Troyan ...
Comments