- Technical Program
- Workshops & Tutorials
- At a glance
- Doctoral Consortium
- Opening & Reception
- Best Papers from Sister Conferences Track
- IJCAI Video Track
- Trading Agent Competion (TAC)
- IJCAI-11 Awards
- Funding Opportunities for International Research Collaborations
- General Game Playing Competition
- Banquet
- Ramon Llull Session
- Industry Day
- Closing Event
- List of Accepted Papers
- Poster Boards

Approximately Strategy-Proof Voting

Eleanor Birrell and Rafael Pass

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. Leveraging the notion of differential privacy, we show that any deterministic voting rule can be approximated by an approximately strategy-proof randomized voting rule. We also extend the Gibbard-Satterthwaite Theorem to provide asymptotically tight lower bounds on the parameters required by such voting rules.