2015/04/09 by Leung, Samantha, Lui, Edward, Pass, Rafael
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1504.02514
The classic Gibbard-Satterthwaite theorem says that every strategy-proof voting rule with at least three possible candidates must be dictatorial. In \citeMcL11, McLennan showed that a similar impossibility result holds even if we consider a weaker notion of strategy-proofness where voters believe that the other voters' preferences are i.i.d.~(independent and identically distributed): If an anonymous voting rule (with at least three candidates) is strategy-proof w.r.t.~all i.i.d.~beliefs and is also Pareto efficient, then the voting rule must be a random dictatorship. In this paper, we strengthen McLennan's result by relaxing Pareto efficiency to ε-Pareto efficiency where Pareto efficiency can be violated with probability ε, and we further relax ε-Pareto efficiency to a very weak notion of efficiency which we call ε-super-weak unanimity. We then show the following: If an anonymous voting rule (with at least three candidates) is strategy-proof w.r.t.~all i.i.d.~beliefs and also satisfies ε-super-weak unanimity, then the voting rule must be O(ε)-close to random dictatorship.