JournalsjemsVol. 14, No. 5pp. 1331–1355

A tight quantitative version of Arrow’s impossibility theorem

  • Nathan Keller

    Weizmann Institute of Science, Rehovot, Israel
A tight quantitative version of Arrow’s impossibility theorem cover
Download PDF

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\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 δ(ϵ)=exp(C/ϵ21)\delta(\epsilon)=\exp(-C/\epsilon^{21}), and generalized it to GSWFs with kk alternatives, for all k3k \geq 3. In this paper we show that the quantitative version holds with δ(ϵ)=Cϵ3\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 kk 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