# A tight quantitative version of Arrow’s impossibility theorem

Journal of the European Mathematical Society (2012)

- Volume: 014, Issue: 5, page 1331-1355
- ISSN: 1435-9855

## Access Full Article

top## Abstract

top## How to cite

topKeller, Nathan. "A tight quantitative version of Arrow’s impossibility theorem." Journal of the European Mathematical Society 014.5 (2012): 1331-1355. <http://eudml.org/doc/277566>.

@article{Keller2012,

abstract = {The well-known Impossibility Theorem of Arrow asserts that any generalized social welfare function (GSWF) with at least three alternatives, which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a dictatorship, is necessarily non-transitive. In 2002, Kalai asked whether one can obtain the following quantitative version of the theorem: For any $\epsilon > 0$, there exists $\delta =\delta (\epsilon )$ such that if a GSWF on three alternatives satisfies the IIA condition and its probability of non-transitive outcome is at most $\delta $, then the GSWF is at most $\epsilon $-far from being a dictatorship or from breaching the Unanimity condition. In 2009, Mossel proved such quantitative version, with $\delta (\epsilon )=\texttt \{exp\}(-C/\epsilon ^\{21\})$, and generalized it to GSWFs with $k$ alternatives, for all $k\ge 3$. In this paper we show that the quantitative version holds with $\delta (\epsilon )=C\cdot \epsilon ^3$, and that this result is tight up to logarithmic factors. Furthermore, our result (like Mossel’s) generalizes to GSWFs with k alternatives. Our proof is based on the works of Kalai and Mossel, but uses also an additional ingredient: a combination of the Bonami-Beckner hypercontractive inequality with a reverse hypercontractive inequality due to Borell, applied to find simultaneously upper bounds and lower bounds on the “noise correlation” between Boolean functions on the discrete cube.},

author = {Keller, Nathan},

journal = {Journal of the European Mathematical Society},

keywords = {arrow's impossibility theorem; hypercontractivity; reverse hypercontractivity; algorithmic game theory; discrete Fourier analysis; Arrow's impossibility theorem},

language = {eng},

number = {5},

pages = {1331-1355},

publisher = {European Mathematical Society Publishing House},

title = {A tight quantitative version of Arrow’s impossibility theorem},

url = {http://eudml.org/doc/277566},

volume = {014},

year = {2012},

}

TY - JOUR

AU - Keller, Nathan

TI - A tight quantitative version of Arrow’s impossibility theorem

JO - Journal of the European Mathematical Society

PY - 2012

PB - European Mathematical Society Publishing House

VL - 014

IS - 5

SP - 1331

EP - 1355

AB - The well-known Impossibility Theorem of Arrow asserts that any generalized social welfare function (GSWF) with at least three alternatives, which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a dictatorship, is necessarily non-transitive. In 2002, Kalai asked whether one can obtain the following quantitative version of the theorem: For any $\epsilon > 0$, there exists $\delta =\delta (\epsilon )$ such that if a GSWF on three alternatives satisfies the IIA condition and its probability of non-transitive outcome is at most $\delta $, then the GSWF is at most $\epsilon $-far from being a dictatorship or from breaching the Unanimity condition. In 2009, Mossel proved such quantitative version, with $\delta (\epsilon )=\texttt {exp}(-C/\epsilon ^{21})$, and generalized it to GSWFs with $k$ alternatives, for all $k\ge 3$. In this paper we show that the quantitative version holds with $\delta (\epsilon )=C\cdot \epsilon ^3$, and that this result is tight up to logarithmic factors. Furthermore, our result (like Mossel’s) generalizes to GSWFs with k alternatives. Our proof is based on the works of Kalai and Mossel, but uses also an additional ingredient: a combination of the Bonami-Beckner hypercontractive inequality with a reverse hypercontractive inequality due to Borell, applied to find simultaneously upper bounds and lower bounds on the “noise correlation” between Boolean functions on the discrete cube.

LA - eng

KW - arrow's impossibility theorem; hypercontractivity; reverse hypercontractivity; algorithmic game theory; discrete Fourier analysis; Arrow's impossibility theorem

UR - http://eudml.org/doc/277566

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.