I pilfered this from Jim's Torg Website for ease of reference, but he deserves all credit for tracking it down on sci.econ.research. Interesting stuff.
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