text: Arrow's Impossibility Theorem states that any constitution which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a Dictator has to be non-transitive. In this paper we study quantitative versions of Arrow theorem. Consider @math voters who vote independently at random, each following the uniform distribution over the 6 rankings of 3 alternatives. Arrow's theorem implies that any constitution which satisfies IIA and Unanimity and is not a dictator has a probability of at least @math for a non-transitive outcome. When @math is large, @math is a very small probability, and the question arises if for large number of voters it is possible to avoid paradoxes with probability close to 1. Here we give a negative answer to this question by proving that for every @math , there exists a @math , which depends on @math only, such that for all @math , and all constitutions on 3 alternatives, if the constitution satisfies: The IIA condition. For every pair of alternatives @math , the probability that the constitution ranks @math above @math is at least @math . For every voter @math , the probability that the social choice function agrees with a dictatorship on @math at most @math . Then the probability of a non-transitive outcome is at least @math .
  @cite_5: 
  @cite_16: In this paper, we consider the question of determining whether a function f has property P or is e-far from any function with property P. A property testing algorithm is given a sample of the value of f on instances drawn according to some distribution. In some cases, it is also allowed to query f on instances of its choice. We study this question for different properties and establish some connections to problems in learning theory and approximation. In particular, we focus our attention on testing graph properties. Given access to a graph G in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has properties such as being bipartite, k -Colorable, or having a p -Clique (clique of density p with respect to the vertex set). Our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is independent of the size of the graph. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.
  @cite_12: The study of self-testing and self-correcting programs leads to the search for robust characterizations of functions. Here the authors make this notion precise and show such a characterization for polynomials. From this characterization, the authors get the following applications. Simple and efficient self-testers for polynomial functions are constructed. The characterizations provide results in the area of coding theory by giving extremely fast and efficient error-detecting schemes for some well-known codes. This error-detection scheme plays a crucial role in subsequent results on the hardness of approximating some NP-optimization problems.
summary: As noted in @cite_5 , there is an interesting connection between quantitative Arrow statements and the concept of testing introduced in @cite_12 @cite_16 which was studied and used extensively since. Roughly speaking a property of functions is testable if it is possible to perform a randomized test for the property such that if the probability that the function passes the test is close to @math , then the function has to be close to a function with the property (say in the hamming distance). In terms of testing, our result states that among all functions satisfying the IIA property, the Transitivity property is testable. Moreover, the natural test "works": i.e., in order to test for transitivity, one can pick a random input and check if the outcome is transitive.