Proceedings

Approximately Strategy-Proof Voting

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 67-71.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-023

© 2011 International Joint Conferences on Artificial Intelligence

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.

  1. [Bartholdi et al., 1989] J. Bartholdi, C. Tovey, and M. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227-241, 1989.
  2. [Conitzer and Sandholm, 2006] V. Conitzer and T. Sand- holm. Nonexistence of voting rules that are usually hard to manipulate. In Proc. 21st AAAI Conference, pages 627- 634, 2006.
  3. [Dwork et al., 2006] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In 3rd TCC, pages 265-284, 2006.
  4. [Friedgut et al., 2009] E. Friedgut, G. Kalai, and N. Nisan. Elections can be manipulated often. In Proc. 49th FOCS, pages 243-249, 2009.
  5. [Friend, 1956] Edward H. Friend. Sorting on electronic com- puter systems. J. ACM, 3:134-168, July 1956.
  6. [Gibbard, 1973] A. Gibbard. Manipulation of voting schemes: a general result. Econometrica, 41(4):587-601, 1973.
  7. [Gibbard, 1977] A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45:665-681, 1977.
  8. [Halpern and Pass, 2010] J. Halpern and R. Pass. Game the- ory with costly computation: Formulation and application to protocol security. In ICS, pages 120-142, 2010.
  9. [Isaksson et al., 2010] M. Isaksson, G. Kindler, and E. Mos- sel. The geometry of manipulation -a quantitative proof of the Gibbard Satterthwaite theorem. In Proc. 50th FOCS, 2010.
  10. [Kahn et al., 1988] Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions (extended abstract). In FOCS, pages 68-80, 1988.
  11. [McSherry and Talwar, 2007] F. McSherry and K. Talwar. Mechanism design via differential privacy. In Proc. 48th FOCS, 2007.
  12. [Moulin, 1980] H. Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437-455, 1980.
  13. [Procaccia, 2010] A. Procaccia. Can approximation circum- vent Gibbard-Satterthwaite? In Proc. 24th AAAI, pages 836-841, 2010.
  14. [Satterthwaite, 1975] M. Satterthwaite. Strategy-proofness and arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare func- tions. Journal of Economic Theory, 10:187-217, 1975.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards