A tight quantitative version of Arrow�s impossibility theorem

• Autores: Nathan Keller
• Localización: Journal of the European Mathematical Society, ISSN 1435-9855, Vol. 14, Nº 5, 2012, págs. 1331-1355
• Idioma: inglés
• DOI: 10.4171/jems/334
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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 d=d(?) such that if a GSWF on three alternatives satisfies the IIA condition and its probability of non-transitive outcome is at most d , 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 d(?)=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 d(?)=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.