Generalized scoring rules and the frequency of coalitional manipulability

Published

Journal Article

We introduce a class of voting rules called generalized scoring rules. Under such a rule, each vote generates a vector of k scores, and the outcome of the voting rule is based only on the sum of these vectors - more specifically, only on the order (in terms of score) of the sum's components. This class is extremely general: we do not know of any commonly studied rule that is not a generalized scoring rule. We then study the coalitional manipulation problem for generalized scoring rules. We prove that under certain natural assumptions, if the number of manipulators is O(np) (for any p < 1/2), then the probability that a random profile is manipulable is O(np-1/2), where n is the number of voters. We also prove that under another set of natural assumptions, if the number of manipulators is Ω(np) (for any p > 1/2) and o(n), then the probability that a random profile is manipulable (to any possible winner under the voting rule) is 1 - O(e -Ω(n2p-1)). We also show that common voting rules satisfy these conditions (for the uniform distribution). These results generalize earlier results by Procaccia and Rosenschein as well as even earlier results on the probability of an election being tied. Copyright 2008 ACM.

Full Text

Duke Authors

Cited Authors

  • Xia, L; Conitzer, V

Published Date

  • December 1, 2008

Published In

  • Proceedings of the Acm Conference on Electronic Commerce

Start / End Page

  • 109 - 118

Digital Object Identifier (DOI)

  • 10.1145/1386790.1386811

Citation Source

  • Scopus