# A tight quantitative version of Arrow’s impossibility theorem

### Nathan Keller

Weizmann Institute of Science, Rehovot, Israel

## 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 $ϵ>0$, there exists $δ=δ(ϵ)$ such that if a GSWF on three alternatives satisfies the IIA condition and its probability of non-transitive outcome is at most $δ$, 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 $δ(ϵ)=exp(−C/ϵ_{21})$, and generalized it to GSWFs with $k$ alternatives, for all $k≥3$. In this paper we show that the quantitative version holds with $δ(ϵ)=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.

## Cite this article

Nathan Keller, A tight quantitative version of Arrow’s impossibility theorem. J. Eur. Math. Soc. 14 (2012), no. 5, pp. 1331–1355

DOI 10.4171/JEMS/334