AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Approximately Strategy-Proof Voting
Eleanor Birrell, Rafael Pass

Last modified: 2011-06-28


The classic Gibbard-Satterthwaite Theorem establishes that only dictatorial voting rules are strategy-proof; under any other voting rule, players have an incentive to lie about their true preferences. We consider a new approach for circumventing this result: we consider randomized voting rules that only approximate a deterministic voting rule and only are approximately strategy-proof. We show that any deterministic voting rule can be approximated by an approximately strategy-proof randomized voting rule, and we provide asymptotically tight lower bounds on the parameters required by such voting rules.

Full Text: PDF