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