Approximately Strategy-Proof Voting
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 20, 2011
- Accession Number
- ADA582553
Entities
People
- Eleanor Birrell
- Rafael Pass
Organizations
- Cornell University