A quantitative Gibbard-Satterthwaite theorem without neutrality

Elchanan Mossel, Miklós Z. Rácz

Research output: Contribution to journalArticlepeer-review

7 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. 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. 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)
Pages (from-to)317-387
Number of pages71
JournalCombinatorica
Volume35
Issue number3
DOIs
StatePublished - Apr 21 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • 05A05

Fingerprint

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

Cite this