A tight quantitative version of Arrow’s impossibility theorem

Keller, 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 -