Generalized scoring rules and the frequency of coalitional manipulability
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.
