A tight quantitative version of Arrow’s impossibility theorem

Nathan Keller

Journal of the European Mathematical Society (2012)

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

Access Full Article

top

 http://dx.doi.org/10.4171/JEMS/334

Abstract

top

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 $ϵ>0$, there exists $\delta =\delta \left(ϵ\right)$ 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 $ϵ$-far from being a dictatorship or from breaching the Unanimity condition. In 2009, Mossel proved such quantitative version, with $\delta \left(ϵ\right)=\mathrm{𝚎𝚡𝚙}(-C/{ϵ}^{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 \left(ϵ\right)=C·{ϵ}^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.

How to cite

top

• MLA
• BibTeX
• RIS

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 -

NotesEmbed ?

top

You must be logged in to post comments.

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

Language to use for this widget. български (bg) čeština (cs) Deutsch (de) ελληνικά (el) English (en) español (es) français (fr) italiano (it) lietuvių kalba (lt) polski (pl) português (pt) română (ro) русский (ru) slovenčina (sk)

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Number of notes per page 5 10 15 20

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.

OK