Recent results have established that a variety of voting rules are computationally hard to manipulate in the worst-case; this arguably provides some guarantee of resistance to manipulation when the voters have bounded computational power. Nevertheless, it has become apparent that a truly dependable obstacle to manipulation can only be provided by voting rules that are average-case hard to manipulate. In this paper, we analytically demonstrate that, with respect to a wide range of distributions over votes, the coalitional manipulation problem can be decided with overwhelming probability of success by simply considering the ratio between the number of truthful and untruthful voters. Our results can be employed to significantly focus the search for that elusive average-case-hard-to-manipulate voting rule, but at the same time these results also strengthen the case against the existence of such a rule.
REF demonstrate that given certain assumptions regarding the distribution of votes in an election, it is possible to find voting rules that are average-case hard to manipulate.
Average-case tractability of manipulation in voting via the fraction of manipulators
In Proc. of AAMAS
Computer Science