---
title: "Approximately Strategy-Proof Voting"
authors:
  - "Eleanor Birrell"
  - "Rafael Pass"
doi: "10.5591/978-1-57735-516-8/IJCAI11-023"
url: "https://ijcai.org/proceedings/2011/23"
pdf: "https://ijcai.org/proceedings/2011/0023.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "67-71"
track: ""
keywords:
---

# Approximately Strategy-Proof Voting

Eleanor Birrell, Rafael Pass

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 67-71. DOI: [10.5591/978-1-57735-516-8/IJCAI11-023](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-023)

## 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.