A tight quantitative version of Arrow's impossibility theorem (Q713951)

A Generalized Social Welfare Function (GSWF) \(F\) by definition assigns to every profile of individual preferences (linear orderings) of the voters the preference of society amongst each pair of alternatives. In the special case that the output of \(F\) can be represented as a full linear ordering of the alternatives, \(F\) is called a social welfare function (SWF). A quantitative version of Arrow's theorem was formulated by Kalai: for any \(\epsilon > 0\) there exists a \(\delta\) such that if a GSWF on three or more alternatives satisfies the IIA (Independence of Irrelevant Alternatives) condition and its probability of a 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. The author defines the distance \(D_1(F)\) of a GSWF \(F\) on \(k\) alternatives from the class \(\mathcal{F}_k\) of GSWF's on \(k\) alternatives which satisfy IIA and whose output is always transitive as the minimal probability that \(F \neq G\), where \(G \in \mathcal{F}_k\). Next he shows that there exists an absolute constant \(C\) such that for any \(k\) and for any GSWF \(F\) on \(k\) alternatives that satisfies IIA, if the probability of a non-transitive outcome under \(F\) is at most \(\delta(\epsilon) = C(\epsilon/k^{2})^{3}\), then \(D_1(F) \leq \epsilon\). It is also shown that the dependence of \(\delta\) on \(\epsilon\) is tight, up to logarithmic factors in \(\epsilon\). A second distance definition \(D_2(F)\) is given for which a similar result is shown.