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 , 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 , and generalized it to GSWFs with alternatives, for all . In this paper we show that the quantitative version holds with , and that this result is tight up to logarithmic factors. Furthermore, our result (like Mossel's) generalizes to GSWFs with 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