Article: 723 of sci.econ.research From: greg@dent.uchicago.edu (Greg Kuperberg) Subject: Precise statement of Arrow's theorem? Date: Sun, 6 Mar 1994 01:08:42 GMT Organization: Dept. of Mathematics I am interested in a precise statement of Arrow's theorem, a theorem to the effect that no voting system other than dictatorship makes complete sense. I read about the result in a popular mathematics book which I gave away. Recently I wondered if it is applicable to reconciliation of ordinals in figure skating, but the only mathematical assertions I could bring to bear on the question were either obviously true but inapplicable or were obviously false. To reiterate, what exactly is a voting system? Presumably it is a set of voters and a set of candidates and some sort of mathematical game that they play. And what are the hypotheses on voting systems in Arrow's theorem? I am also interested in generalizations of Arrow's theorem. ************************************************* Article: 731 of sci.econ.research From: mack13@panix.com () Date: Mon, 07 Mar 1994 21:23:53 -0500 Organization: PANIX Public Access Internet and Unix, NYC I quote from Liberalism Against Populism, by William H. Riker: "The essence of Arrow's theorem is that no method of amalgamating individual judgments can simultaneously satisfy some reasonable condition of fairness on the method and a condition of logicality on the result." Riker's book has a good discussion of Arrow's theorem, and I'm sure it's not the only such. If you'd like to go straight to the source, Kenneth Arrow's Social Choice and Individual Values is the ticket. ************************************************ Article: 753 of sci.econ.research From: "Jay Coggins" Date: Wed, 9 Mar 1994 00:25:35 CST Organization: Pol-Econ<==>Sci.Econ.Research Gateway X-Gateway-Source-Info: Mailing List March 6, 1994, Greg Kuperberg said: > I am interested in a precise statement of Arrow's theorem A nice and reasonably accesible treatment is in John Craven's 1992 Cambridge Press book entitled _Social Choice: A Framework for Collective Decisions and Individual Judgements_. Amartya Sen's chapter "Social Choice Theory" in volume III of the North-Holland _Handbook of Mathematical Economics_ (edited by Arrow and Intriligator) gives all the technical details concerning Arrow and related literature through about 1982. > Recently I wondered if it is applicable to reconciliation > of ordinals in figure skating, but the only mathematical assertions I > could bring to bear on the question were either obviously true but > inapplicable or were obviously false. Yes, it is applicable. The task facing skating judges is impossible in Arrow's sense. The term "ordinal" used in the skating world is unfortunate, because it is based upon cardinal information. Each judge's scores on artistic and technical merit are added together for each skater, and the skater who is ranked first by the most judges is declared the winner. I think that's right. But these scores are cardinal. The "ordinal" rankings violate independence of irrelevant alternatives (see below), which is a prohibition against the use of cardinal information in schemes like this. For a wonderful look at Arrow's theorem unified by a running example from athletics (the scoring system for the decathlon), see Alfred Mackay's Yale Press book entitled _Arrow's Theorem: (subtitle)_. > To reiterate, what exactly is a voting system? Presumably it is a set > of voters and a set of candidates and some sort of mathematical game > that they play. And what are the hypotheses on voting systems in > Arrow's theorem? Arrow's theorem starts with a finite set of outcomes (candidates for office or competitors in a decathlon), a finite set of voters (in the decathlon example, voters are the ten events), and their (well-behaved) individual preferences over outcomes. The search is for a rule that maps a collection of individual preferences (a profile) into a social ordering of the alternatives from first to last. IF (1) individual preferences can be anything at all (unrestricted domain), and the rule itself satisfies (2) the Pareto principle (if everyone prefers x to y, then x should be preferred to y in the social ordering) and (3) independence of irrelevant alternatives (roughly: only individuals' wishes concerning x and y should matter to whether x is preferred to y by society); THEN the rule is dictatorial (there is a person whose individual preferences will always agree precisely with the social preference ordering). The voting system in this rather abstract set-up is the rule for turning individual preferences into a social preference ordering. The best catalog of available voting systems that I know of is still Herve Moulin's 1983 North-Holland book _The Strategy of Social Choice_. Jay Coggins ph. (608) 262-0847 417 Taylor Hall fax (608) 262-4376 University of Wisconsin coggins@agecon.wisc.edu Madison WI 53706 ************************************************* From: H. Reiju Mihara Subject: Arrow's Theorem: precise statement and computability SUMMARY: I give a precise statement of Arrow's Theorem in Section 1. Section 2 gives some references. Final section is concerned with a recent development that I am working on---computability and Arrow's Theorem. greg@dent.uchicago.edu (Greg Kuperberg) wrote: Section 1 Theorem > I am interested in a precise statement of Arrow's theorem, a theorem to > the effect that no voting system other than dictatorship makes complete > sense. Assuming the writer is a mathematician who is not familiar with economic theory, I give a precise statement. (The following is written partially in LateX input language.) $I$ is a set of {\em individuals} (names of people), which is finite. $X$ is a set of {\em alternatives} (choices, options), which has at least three elements. $\P$ is the set of (strict) {\em preferences}, i.e., asymmetric and negatively transitive binary relations on $X$. (A preference R is intended to be interpreted: xRy means "x is preferred to y" or "x is chosen over y". A profile is a list of individual preferences, i.e., a function from the set of individuals to the set of preferences. A {\em social welfare function\/} is a function mapping a profile to a social preference. (Social preference is formally just a preference R. We interpret xRy to be "x is socially preferred to y" or "the society chooses x over y".) Note that it is implicit in this definition that any profile is allowed; so the function has to be well defined for any combination of individual preferences. Some writer emphasizes this aspect and call this condition universality. We list Arrow's conditions for social welfare functions: (Unanimity) For any x, y in X and for any profile, if x is preferred to y by all individuals, then x is socially preferred to y. (Independence) For any profiles p and p' and for any two element subsets Y of alternatives, if p and p' are identical on Y (i.e., the restrictions of p and p' to $Y \times Y$ are the same), then corresponding social preferences are the same on Y. (So, the in order for the society to decide whether x is better than y or not, the function only needs individuals' information concerning those particular two elements.) (Nondictatorship) There is no individual such that for all x, y and profiles, whenever she prefers x to y, so does the society. (That is, the case is ruled out in which social preference is always determined by a particular individual, called a "dictator"). Finally, Arrow's Theorem: Let F be a social welfare function satisfying Unanimity and Independence. Then F violates Nondictatorship. Note. Suppose the set I of individuals is infinite (contrary to above). If F satisfies Unanimity and Independence, then there exists an ultrafilter on I such that for all profiles and and all x and y: if the set of individuals that prefers x to y belongs to the ultrafilter, then x is preferred to y by society. In a sense, such an ultrafilter is made up of "decisive" or "dictatorial" subsets of individuals. Since there is an nontrivial ultrafilter on an infinite set, this gives a positive result when I is infinite. Section 2 References Historically, the first edition (1951) of the following opened the industry, or paradigm, if you will, of social choice. title = {Social Choice and Individual Values}, publisher = yale, year = {1963}, author = {Arrow, Kenneth J.}, address = {New Haven and London}, edition = {2nd}. I didn't not follow the original formulation, for it contains a minor error. Today many slightly different versions of Arrow's Theorem are available, and the above is fairly standard. > I am also interested in generalizations of Arrow's theorem. There is an enormous literature. Kelly, JS (1978) _Arrow Impossibility Theorems_ is a book that contains a lot of attempts to weaken some of assumptions. Even assumptions are somewhat weakened general results are mostly negative. A good reference is the Harvard phiosopher & economist Sen's book which sets the results in contexts. A more recent survey includes Sen (1986): title = {Collective Choice and Social Welfare}, publisher = n-h, year = {1970}, author = {Sen, Amartya K.}, series = {Advanced Textbooks in Economics}, address = {Amsterdam} author = {Sen, Amartya K.}, title = {Social Choice Theory}, booktitle = {Handbook of Mathematical Economics}, year = {1986}, publisher = {Elsevier}, editor = {Arrow, Kenneth J. and Intriligator, Michael D.}, volume = {III}, chapter = {22}, pages = {1073--1181}, address = {Amsterdam} I don't know how social choice is popular in philosophy and political science, but in economics, it is not so popular anymore (and perhaps never really was). I guess the profession is a bit fed up with a series of "negative" or impossible results. Impossibility theorems do not have as much impact as it did when G\"odel's Incompleteness appeared. People is not as optimistic as it used to be in 1930s. Aside from generalization in which social choice theorists are busy modifying the existing conditions like Unanimity or Independence, there are lines of research to produce Arrow-like theorems from axioms that are different in spirit from the original axioms. This includes examinations of (i) the relation between efficiency and liberty (by Sen and Gibbard), (ii) rules free from manipulation, (iii) economic set of alternatives (i.e., topological vector spaces) and preferences, (iv) "implementation" of a social welfare function as an equilibrium of a game. These are more interesting to me than mere generalizations. Section 3 Arrow's Theorem, Turing computability, and oracles Arrow's book starts with noting that voting and the market mechanism are similar and both are democratic. On the other hand, a popular misunderstanding of Arrow's Theorem is that centralized decision making doesn't work. In an attempt to justify this misunderstanding, I regard that algorithmic computability is an essential requirement for centralized decisions such as voting but perhaps not crucial requirement for decentralized decision making like market mechanisms. This view is inspired by the socialist calculation debate among Mises, Hayek, Lange, and Lerner. My dissertation "Arrow's Theorem, Turing computability, and oracles" is motivated by this observation. It considers infinite set of individuals (to be interpreted for example as a set of people in different states of the world). The main result is that among the social welfare functions that satisfy Unanimity and Independence, only dictatorial ones are computable in the following sense: there is an algorithm to decide for all profiles and for all alternatives x and y, whether the society prefers x to y given a description of the coalition (subset of individuals) in which everybody prefers x to y. This suggests that centralized decisions perform poorly. On the other hand, if the oracle \emptyet'' or the second jump of the empty set is allowed (so that one can tell given a name of a coalition whether it is finite or not), then there exists a social welfare function satisfying all of Unanimity, Independence, and Nondictatorship. The paper is not in the final form, but is available as a LateX input file or a dvi file directly from the author at the e-mail address below. Reiju H. Reiju Mihara (miha0008@gold.tc.umn.edu) is a graduate student of normative economics. ******************************* From: sergei@guriev.niiros.msk.su (Sergei M. Guriev) Subject: Re: Precise statement of Arrow's theorem? On March 6, Greg Kuperberg wrote ("Precise statement of Arrow's theorem"): > I am interested in a precise statement of Arrow's theorem, a theorem to > the effect that no voting system other than dictatorship makes complete > sense. The best book I have ever read in this field is H.Moulin's "Axioms of cooperative decision making", Cambridge University Press 1988. You will see there how to obtain different results (incl. Arrow's) using different sets of "fair" requirements (i.e. axioms) to the voting systems. > I am also interested in generalizations of Arrow's theorem. All possible generalizations are also there. > > To reiterate, what exactly is a voting system? Presumably it is a set > of voters and a set of candidates and some sort of mathematical game > that they play. And what are the hypotheses on voting systems in > Arrow's theorem? Let us take for granted set of candidates, set of voters and linear orders of preferences of candidates for each voter. Then voting system is a mapping from combination of orders to the set of candidates that defines which candidate will be elected in case of such combination of the orders. Arrow's theorem deals with social welfare preordering (SWP) that is different than voting system. SWP gives social order using individual orders, i.e. defines not only the number one, but N2, N3 etc. In these terms it is easy to formulate various requirements-axioms-hypotheses. Arrow's theorem is based on so called "Arrow's independence of irrelevant alternatives" and unanimity (Pareto-compatibility). It states that for more than 2 candidates the only SWP satisfying these two conditions is dictatorial. Hope this helps, everything else you can find in Moulin's book or feel free to ask Sergei Guriev, M.Sc. Computing Center of Russian Academy of Science > I am also interested in generalizations of Arrow's theorem. > ********************************** From: cave@rand.org (Jonathan Cave) Subject: Re: Precise statement of Arrow's theorem? In article <1994Mar6.010842.17586@midway.uchicago.edu> greg@dent.uchicago.edu (Greg Kuperberg) writes: >I am interested in a precise statement of Arrow's theorem, a theorem to >the effect that no voting system other than dictatorship makes complete >sense. Given a set A of alternatives and a set N of people, each of whom has a complete, transitive, etc. preference ordering Ri on A, we seek a social preference ordering R on A. R must also be complete and transitive. Here, the binary relation R is complete if all pairs can be compared: for all a,b in A, either a R b or b R a (or both, indicating indifference). R is transitive if a R b and b R c imply a R c. Axioms: I. Pareto optimality: if a Ri b (a is weakly preferred to b) by all i in N, then a R b. II. Nondictatorship: there is no i s.t. for all a,b and all preferences Rj of the other members of N, a R b if and only if a Ri b. III. Universal Domain: this process should work for all A, all N and all preferences Ri of the members of N. IV. Independance of Irrelevant Alternatives: Given a subset B of A, and two alternative a and b in the smaller set B, the social ranking of a and b is the same regardless of whether A or B is used. Put slightly differently, if a is the "best" element in A (i.e., a R b for all b in A), and a is in the smaller set B, then a is the "best" element on B. Theorem: there is no social choice rule that satisfies the 4 axioms. Remarks: In some books (e.g., Varian's undergrad. text), Axioms I, III, and IV are stated, and violation of II is proved. Note that the theorem as stated may not be so gloomy, since we can relax any one of the axioms and "solve" the problem: relaxing I is what we often do - what the "free-market" types who abound here like to do about externalities and public goods, f'rinstance (flame bait). relaxing II may be OK if we consider a random dictatorship mechanism. Whenever there's a decision to be made, choose a member of N at random and let them choose. If you change dictators often enough this has a sort of fairness. If the US president had any power, this would describe our approximation of representative democracy (more flame bait). relaxing III is like: citizenship restrictions, guild membership qualifications, Constitutional provisions leaving certain decisions up to the states or individuals, or the fre-marketer's postulate that individual preferences depend only on that individual's consumption (no externalities). relaxing IV: is the domain of explicit social welfare functions like Bergsonian, Benthamite or Rawlsian ones. One can also abandon e.g. transitivity, following Buchanan and Plott, in favor of something like fairness (Kemp) Another cute version of this kind of result is Sen's "paretian Liberal" (not flamebait:-) Impossibility theorem. Consider Axiom I (Pareto Optimality), Axiom III (Universal domain) and the following: Axiom V: for every person i there are two alternatives a and b such that a R b if and only if a Ri b. note: this says that each individual is decisiove for one pair of alternatives, or, in Sen's words: "there are certain personal matters in which each person should be free to decide what should happen, and in choices over these things whatever he or she thinks is better must be taken to be better for society as a whole, no matter what others think. [Sen, A. "Liberty, Unanimity and Rights," Economica, Aug., 1976, p. 217. The result? Theorem: No social choice rule satisfies Axioms I, III and V. Jonathan A simple discussion is given in e.g. Vicrey ************************************** From: wang1@u.washington.edu (Jiahui Jeffrey Wang) Newsgroups: sci.econ.research I suggest you to read "Collective Choice and Socail Welfare" by Sen. Jeffrey Wang University of Washington