ARROWS IMPOSSIBILITY THEOREM OF SOCIAL CHOICE

HONI SANDERS

Abstract. A proof of Arrows Impossibility Theorem based on the ve conditions he imposed on the social-welfare function in his 1950 paper, A Diculty in the Concept of Social Welfare.

In order to make policy decisions, some algorithm must be used to choose one alternative out of all the available possibilities of action based on the preferences of the constituency. One might call this algorithm an election. The plurality election where the option with the most people preferring that option to any other is the one on which our mayorial, congressional, and most other elections are decided. One problem is that it could be that 30% of the population prefers a to b and b to c, 30% of the population prefers b to a and a to c, and 40% of the population prefers c to b and b to a. In this case, c would win, even though the majority of the population would rather anything but c. Many other election methods have been proposed as alternatives, but each either has outcomes that are unacceptable in certain cases or does not always give a winner. In his 1950 paper, A Diculty in the Concept of Social Welfare, Kenneth Arrow sets out guidelines for what he believes is a fair election method and proves that no such method exists. The social decision under consideration can be represented as a nite or innite set S, and the options are represented as the elements xk S. We can describe preference as a relation on the set. For an individual i, we will dene relations Ri and Pi . Denition 1. If individual i prefers xk to xj or is indierent between xk and xj , then xk Ri xj . Using this denition we can dene Pi in terms of Ri : Denition 2. xk Ri xj xj Pi xk The relations Ri and Pi on S are comparable to the relations and >, respectively, on Z, so Denition 2 is comparable to dening > in terms of : x y y > x. We assume that all individuals are rational and preference is based on relative utility, so preference and indierence are transitive. From the transitivity property of Ri and Pi , and following directly from the denition, we have (i) xk Ri xj , xj Ri xm xk Ri xm (ii) xk Pi xj , xj Ri xm xk Pi xm (iii) xk Pi xj xk Ri xj Our goal is to nd a social-welfare function, that is, an algorithm to determine relations R and P , representing the societal preference, on the set S given the relations {Ri }. Kenneth Arrow listed ve conditions that he thought one should expect the social-welfare function and the relations R and P that it produces to fulll.
1

HONI SANDERS

Condition 1. The social-welfare function must have an output R and P for any set of relations {Ri }. Condition 2. If {Ri } changes s.t. all xk Ri xj hold except for relations involving xm , and Ri , {xk |xm Ri xk before} {xk |xm Ri xk after} and {xk |xm Pi xk before} {xk |xm Pi xk after}, then {xk |xm P xk before} {xk |xm P xk after}. (That is, if people think more highly of xm and nothing else changes, then xm should not be thought of lower by society as a whole.) Condition 3 (Independence of Irrelevant Alternatives). C S with relation R on C ({Ri } are relations on C by transitivity), for xk , xj C, xk Rxj xk R xj . (The ordering of given options should not change with the presence of other options.) Condition 4 (Citizen Sovereignty). erence is allowed.) Condition 5 (Nondictatorship). xk , xj s.t. xk Rxj {Ri }. (Any societal pref-

individual i s.t. xk Pi xj xk P xj .

Arrow then proved that these ve conditions imply a contradiction. He used a society with two individuals and three elements in S. By Condition 3, disproving the existence of a social-welfare function on a set with three elements disproves it for all numbers of elements. He uses a mathematical wave of the hand on the generalizability of proofs involving societies with two individuals: The restriction to two individuals may be more serious; it is conceivable that there may be suitable social welfare functions which cab be dened for three individuals but not for two, for example. In fact, this is not so, and the results stated in this paper hold for any number of individuals. Lemma 1 (Pareto Eciency). xk Pi xj i xk P xj . Proof. Assume that xk Pi xj i xk P xj . Then, xk , xj s.t. xk Pi xj i but xj Rxk . Condition 4 is equivalent to the statement xk , xj {Ri } s.t. xk P xj . Take that {Ri }, which is not xk Pi xj i by assumption, and change only relations dealing with xk so that i and xm , xk Pi xm . We now have a {Ri } where xk Pi xj i. But by construction following Condition 2, because xk P xj before the change, it must be that xk P xj after the change, which contradicts the original assumption. It is at this point that Arrows proof begins to deal with only societies with two people. Lemma 2. If xk P1 xj , xj P2 xk , xk P xj , then xk P1 xj xk P xj . Proof. Take R1 where xk P1 xj and any R2 . Change R2 only with respect to xk to R2 so that xm , xm P2 xk , so xj P2 xk . With R1 and R2 , xk P xj by assumption. Change R2 back to R2 only by changing relations dealing with xk , which is a change following Condition 2, meaning that xk P xj . Lemma 3. xk P1 xj , xj P2 xk xk Rxj , xj Rxk Proof. Assume xk P1 xj , xj P2 xk xk Rxj , xj Rxk . That is, R1 , R2 where xk P1 xj , xj P2 xk and either xk P xj or xj P xk . With S = {a, b, c}, set xk = a, xj = b without loss of generality. We will prove

ARROWS IMPOSSIBILITY THEOREM OF SOCIAL CHOICE

a contradiction assuming aP b, and the case of bP a can be proved by the same process. By Lemma 2, we have (1) aP1 b aP b. Take R1 where aP1 b, bP1 c and R2 where bP2 c, cP2 a, bP2 a. aP b by (1), and bP c by Lemma 1, so aP c by transitivity. By Lemma 2, (2) aP1 c aP c. Take R1 where bP1 a, aP1 c and R2 where cP2 b, bP2 a. Then, bP a by Lemma 1 and aP c by (2); so by Lemma 2, (3) bP1 c bP c. Take R1 where bP1 c, cP1 a and R2 where cP2 a, aP2 b, cP a by Lemma 1 and bP c by (3); so by Lemma 2, (4) bP1 a bP a. Take R1 where cP1 b, bP1 a and R2 where aP2 c, cP2 b, cP b by Lemma 1 and bP a by (4); so by Lemma 2, (5) cP1 a cP a. Take R1 where cP1 a, aP1 b and R2 where aP2 b, bP2 c, aP b by Lemma 1 and cP a by (5); so by Lemma 2, (6) cP1 b cP b. Equations (1)-(6) can be summarized as xm , xn S, xm P1 xn xm P xn which establishes individual 1 as a dictator, and contradicts Condition 5. Now we can prove our main theorem: Theorem 1 (Arrows Impossibility Theorem). There is no social-welfare function which fullls Conditions 1-5 and produces a rational societal preference ordering. Proof. Take R1 where aP1 b, bP1 c and R2 where cP2 a, aP2 b. By Lemma 1, aP b. bP1 c, cP2 b bRc, cRb by Lemma 2, so aP c by (ii), but aP1 c, cP2 a aRc, cRa. References
[1] Kenneth J. Arrow. A Diculty in the Concept of Social Welfare. The Journal of Political Economy, Vol. 58, No. 4. August, 1950 pp. 328-346.