A tight quantitative version of Arrow%26apos;s impossibility theorem

作者：Keller Nathan^*

来源：Journal of the European Mathematical Society, 2012, 14(5): 1331-1355.

DOI：10.4171/JEMS/334

The well-known Impossibility Theorem of Arrow asserts that any generalized social welfare 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 %26gt; 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 away from being a dictatorship or from breaching the Unanimity condition. In 2009, Mossel proved such a quantitative version, with delta(epsilon) = exp(-C/epsilon(21)), and generalized it to GSWFs with k alternatives, for all k %26gt;= 3. %26lt;br%26gt;In this paper we show that the quantitative version holds with delta(epsilon) = C epsilon(3), and that this result is tight up to logarithmic factors. Furthermore, our result (like Mossel%26apos;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 %26quot;noise correlation%26quot; between Boolean functions on the discrete cube.

• 出版日期2012