Asymptotic Collusion-Proofness of Voting Rules: The Case of Large Number of Candidates

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 tiebreaking rule play a crucial role in determining whether or not a voting rule satisfies asymptotic collusion-proofness.