A quantitative Gibbard-Satterthwaite theorem without neutrality

Elchanan Mossel, Miklós Z. Rácz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

Recently, quantitative versions of the Gibbard-Satterthwaite theorem were proven for k=3 alternatives by Friedgut, Kalai, Keller and Nisan and for neutral functions on k ≥ 4 alternatives by Isaksson, Kindler and Mossel. In the present paper we prove a quantitative version of the Gibbard-Satterthwaite theorem for general social choice functions for any number k ≥ 3 of alternatives. In particular we show that for a social choice function f on k ≥ 3 alternatives and n voters, which is ε-far from the family of nonmanipulable functions, a uniformly chosen voter profile is manipulable with probability at least inverse polynomial in n, k, and ε -1. Removing the neutrality assumption of previous theorems is important for multiple reasons. For one, it is known that there is a conflict between anonymity and neutrality, and since most common voting rules are anonymous, they cannot always be neutral. Second, virtual elections are used in many applications in artificial intelligence, where there are often restrictions on the outcome of the election, and so neutrality is not a natural assumption in these situations. Ours is a unified proof which in particular covers all previous cases established before. The proof crucially uses reverse hypercontractivity in addition to several ideas from the two previous proofs. Much of the work is devoted to understanding functions of a single voter, and in particular we also prove a quantitative Gibbard-Satterthwaite theorem for one voter.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages1041-1060
Number of pages20
DOIs
StatePublished - 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • computational social choice
  • gibbard-satterthwaite
  • isoperimetric inequalities
  • manipulation
  • reverse hypercontractivity
  • voting

Fingerprint Dive into the research topics of 'A quantitative Gibbard-Satterthwaite theorem without neutrality'. Together they form a unique fingerprint.

  • Cite this

    Mossel, E., & Rácz, M. Z. (2012). A quantitative Gibbard-Satterthwaite theorem without neutrality. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 1041-1060). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214071