Arrow's impossibility theorem

From Wikipedia, the free encyclopedia

In social choice theory, Arrow’s impossibility theorem, or Arrow’s paradox, demonstrates that no voting system can convert the ranked preferences of individuals into a community-wide ranking while also meeting a certain set of reasonable criteria with three or more discrete options to choose from. These criteria are called unrestricted domain, non-imposition, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives. The theorem is often cited in discussions of election theory as it is further interpreted by the Gibbard–Satterthwaite theorem.

The theorem is named after economist Kenneth Arrow, who demonstrated the theorem in his Ph.D. thesis and popularized it in his 1951 book Social Choice and Individual Values. The original paper was titled "A Difficulty in the Concept of Social Welfare".^[1] Arrow was a co-recipient of the 1972 Nobel Prize in Economics.

[edit] Statement of the theorem

The need to aggregate preferences occurs in many different disciplines: in welfare economics, where one attempts to find an economic outcome which would be acceptable and stable; in decision theory, where a person has to make a rational choice based on several criteria; and most naturally in voting systems, which are mechanisms for extracting a decision from a multitude of voters' preferences.

The framework for Arrow's theorem assumes that we need to extract a preference order on a given set of options (outcomes). Each individual in the society (or equivalently, each decision criterion) gives a particular order of preferences on the set of outcomes. We are searching for a preferential voting system, called a social welfare function, which transforms the set of preferences into a single global societal preference order. The theorem considers the following properties, assumed to be reasonable requirements of a fair voting method:

Non-dictatorship

The social welfare function should account for the wishes of multiple voters. It cannot simply mimic the preferences of a single voter.

Unrestricted domain

(or universality) The social welfare function should account for all preferences among all voters to yield a unique and complete ranking of societal choices. Thus:

The voting mechanism must account for all individual preferences.
It must do so in a manner that results in a complete ranking of preferences for society.
It must deterministically provide the same ranking each time voters' preferences are presented the same way.

Independence of irrelevant alternatives (IIA): The social welfare function should provide the same ranking of preferences among a subset of options as it would for a complete set of options. Changes in individuals' rankings of irrelevant alternatives (ones outside the subset) should have no impact on the societal ranking of the relevant subset.
Positive association of social and individual values: (or monotonicity) If any individual modifies his or her preference order by promoting a certain option, then the societal preference order should respond only by promoting that same option or not changing, never by placing it lower than before. An individual should not be able to hurt an option by ranking it higher.
Non-imposition: (or citizen sovereignty) Every possible societal preference order should be achievable by some set of individual preference orders. This means that the social welfare function is surjective: It has an unrestricted target space.

Arrow's theorem says that if the decision-making body has at least two members and at least three options to decide among, then it is impossible to design a social welfare function that satisfies all these conditions at once.

A later (1963) version of Arrow's theorem can be obtained by replacing the monotonicity and non-imposition criteria with:

Pareto efficiency: if every individual prefers a certain option to another, then so must the resulting societal preference order. This, again, is a demand that the social welfare function will be minimally sensitive to the preference profile.

The later version of this theorem is stronger—has weaker conditions—since monotonicity, non-imposition, and independence of irrelevant alternatives together imply Pareto efficiency, whereas Pareto efficiency, non-imposition, and independence of irrelevant alternatives together do not imply monotonicity.

[edit] Formal statement of the theorem

Let $A$ be a set of outcomes, $N$ a number of voters or decision criteria. We shall denote the set of all full linear orderings of $A$ by $L(A)$ (this set is equivalent to the set $S | A |$ of permutations on the elements of $A$ ).

A (strict) social welfare function is a function $F : \mathrm{L(A)}^N \to \mathrm{L(A)}$ which aggregates voters' preferences into a single preference order on $A$ . The $N$ -tuple $(R_1, \ldots, R_N)$ of voter's preferences is called a preference profile. In its strongest and most simple form, Arrow's impossibility theorem states that whenever the set $A$ of possible alternatives has more than 2 elements, then the following three conditions become incompatible:

unanimity, or Pareto efficiency: If alternative a is ranked above b for all orderings $R_1 , \ldots, R_N$ , then a is ranked higher than b by $F(R_1, R_2, \ldots, R_N)$ . (Note that unanimity implies non-imposition).

non-dictatorship: There is no individual i whose preferences always prevail. That is, there is no $i \in \{1, \ldots,N\}$ such that $\forall (R_1, \ldots, R_N) \in \mathrm{L(A)}^N, \quad F(R_1,R_2, \ldots, R_N) = R_i$ .

independence of irrelevant alternatives: For two preference profiles $(R_1, \ldots, R_N)$ and $(S_1, \ldots, S_N)$ such that for all individuals i, alternatives a and b have the same order in $R i$ as in $S i$ , alternatives a and b have the same order in $F(R_1,R_2, \ldots, R_N)$ as in $F(S_1,S_2, \ldots, S_N)$ .

[edit] Informal proof

Based on the proof by John Geanakoplos of Cowles Foundation, Yale University.^[2]

We wish to prove that any social choice system respecting unrestricted domain, unanimity, and independence of irrelevant alternatives (IIA) is a dictatorship.

[edit] Part one: there is a "pivotal" voter for B

Say there are three choices for society, call them A, B, and C. Suppose first that everyone prefers option B the least. That is, everyone prefers every other option to B. By unanimity, society must prefer every option to B. Specifically, society prefers A and C to B. Call this situation Profile 1.

On the other hand, if everyone preferred B to everything else, then society would have to prefer B to everything else by unanimity. So it is clear that, if we take Profile 1 and, running through the members in the society in some arbitrary but specific order, move B from the bottom of each person's preference list to the top, there must be some point at which B moves off the bottom of society's preferences as well, since we know it eventually ends up at the top.

We now want to show that, during this process, at the point when the pivotal voter $n$ moves B off the bottom of his preferences to the top, the society's B moves to the top of its preferences as well, not to an intermediate point.

To prove this, consider what would happen if it were not true. Then, after $n$ has moved B to the top (i.e., when voters $\{1,\dots,n-1\}$ have B at the bottom and voters $\{n,\dots,\}$ have B at the top) society would have some option it prefers to B, say A, and one less preferable than B, say C. (If otherwise, just swap A's and C's names).

Now if each person moves his preference for C above A, then society would prefer C to A by unanimity. By the fact that A is already preferred to B, C would now be preferred to B as well in the social preference ranking. But moving C above A shouldn't change anything about how B and C compare, by independence of irrelevant alternatives. That is, since B is either at the very top or bottom of each person's preferences, moving C or A around doesn't change how either compares with B. We have reached an absurd conclusion.

Therefore, when the voters $\{1,\dots,n\}$ have moved B from the bottom of their preferences to the top, society moves B from the bottom all the way to the top, not some intermediate point.

[edit] Part two: voter $n$ is a dictator for A–C

In the second part of the proof, we show how voter $n$ can be a dictator over society's decision between A and C. Call the case with all voters up to (not including) $n$ having B at the top of their preferences and the rest (including $n$ ) with B at the bottom Profile 2. Call the case with all voters up through (and including) $n$ having B at the top and the rest having B at the bottom Profile 3.

Now suppose everyone up to $n$ ranks B at the bottom, $n$ ranks B below A but above C, and everyone else ranks B at the top. As far as the A–B decision is concerned, this organization is just as in Profile 2, which we proved puts B below A (in Profile 2, B is actually at the bottom of the social ordering). C's new position is irrelevant to the B–A ordering for society because of IIA. Likewise, $n$ 's new ordering has a relationship between B and C that is just as in Profile 3, which we proved has B above C (B is actually at the top). Hence we know society puts A above B above C. And if person $n$ flipped A and C, society would have to flip its preferences by the same argument. Hence person $n$ gets to be a dictator over society's decision between A and C.

Since B is irrelevant (IIA) to the decision between A and C, the fact that we assumed particular profiles that put B in particular places doesn't matter. This was just a way of finding out, by example, who the dictator over A and C was. But all we need to know is that he exists.

[edit] Part three: there can be at most one dictator

Finally, we want to show that the dictator can also dictate over the A–B pair and over the C–B pair. Consider that we have proven that there are dictators over the A–B, B–C, and A–C pairs, but they are not necessarily the same dictator. However, if you take the two dictators who can dictate over A–B and B–C, for example, they together can determine the A–C outcome, contradicting the idea that there is some third dictator who can dictate over the A–C pair. Hence the existence of these dictators is enough to prove that they are the same person, otherwise they would be able to overrule one another, a contradiction.

[edit] Interpretations of the theorem

Arrow's theorem is a mathematical result, but it is often expressed in a non-mathematical way with a statement such as "No voting method is fair", "Every ranked voting method is flawed", or "The only voting method that isn't flawed is a dictatorship". These statements are simplifications of Arrow's result which are not universally considered to be true. What Arrow's theorem does state is that a voting mechanism cannot comply with all of the conditions given above simultaneously for all possible preference orders.

Arrow did use the term "fair" to refer to his criteria. Indeed, Pareto efficiency, as well as the demand for non-imposition, seems trivial. Various theorists have suggested weakening the IIA criterion as a way out of the paradox. Proponents of ranked voting methods contend that the IIA is an unreasonably strong criterion, which actually does not hold in most real-life situations. Indeed, the IIA criterion is the one breached in most useful voting systems.

Advocates of this position point out that failure of the standard IIA criterion is trivially implied by the possibility of cyclic preferences. If voters cast ballots as follows:

7 votes for A > B > C
6 votes for B > C > A
5 votes for C > A > B

then the net preference of the group is that A wins over B, B wins over C, and C wins over A. In this circumstance, any system that picks a unique winner, and satisfies the very basic majoritarian rule that a candidate who receives a majority of all first-choice votes must win the election, will fail the IIA criterion. Without loss of generality, consider that if a system currently picks A, and B drops out of the race (as e.g. in a two-round system), the remaining votes will be:

7 votes for A > C
11 votes for C > A

Thus, C will win, even though the change (B dropping out) concerned an "irrelevant" alternative candidate who did not win in the original circumstance.

So, what Arrow's theorem really shows is that voting is a non-trivial game, and that game theory should be used to predict the outcome of most voting mechanisms. This could be seen as a discouraging result, because a game need not have efficient equilibria, e.g., a ballot could result in an alternative nobody really wanted in the first place, yet everybody voted for.

Note, however, that not all voting systems require (or even allow), as input, a strict ordering of all candidates. These systems may then trivially fail the universality criterion. Some systems may satisfy a version of Arrow's theorem with some reformulation of universality and independence of irrelevant alternatives; Warren Smith claims that range voting is such a system.

[edit] Other possibilities

The preceding discussion assumes that the "correct" way to deal with Arrow's paradox is to eliminate (or weaken) one of the criteria. The IIA criterion is the most natural candidate. Yet there are other "ways out".

Duncan Black has shown that if there is only one agenda by which the preferences are judged, then all of Arrow's axioms are met by the majority rule. Formally, this means that if we properly restrict the domain of the social welfare function, then all is well. Black's restriction, the "single-peaked preference" principle, states that there is some predetermined linear ordering P of the alternative set. Every voter has some special place he likes best along that line, and his dislike for an alternative grows larger as the alternative goes further away from that spot. For example, if voters were voting on where to set the volume for music, it would be reasonable to assume that each voter had their own ideal volume preference and that as the volume got progressively too loud or too quiet they would be increasingly dissatisfied. In such a restricted case, Arrow's theorem doesn't apply: in particular, it lacks an unrestricted domain.

Indeed, many different social welfare functions can meet Arrow's conditions under such restrictions of the domain. It has been proved, however, that under any such restriction, if there exists any social welfare function that adheres to Arrow's criteria, then the majority rule will adhere to Arrow's criteria.^[3] Under single-peaked preferences, then, the majority rule is in some respects the most natural voting mechanism.

Another common way "around" the paradox is limiting the alternative set to two alternatives. Thus, whenever more than two alternatives should be put to the test, it seems very tempting to use a mechanism that pairs them and votes by pairs. As tempting as this mechanism seems at first glance, it is generally far from meeting even the Pareto principle, not to mention IIA. The specific order by which the pairs are decided strongly influences the outcome. This is not necessarily a bad feature of the mechanism. Many sports use the tournament mechanism—essentially a pairing mechanism—to choose a winner. This gives considerable opportunity for weaker teams to win, thus adding interest and tension throughout the tournament. In effect, the mechanism by which the choices are limited to two candidates is best considered as a part of the balloting system, and hence Arrow's theorem applies.

There has developed an entire literature following from Arrow's original work which finds other impossibilities as well as some possibility results. For example, if we weaken the requirement that the social choice rule must create a social preference ordering which satisfies transitivity and instead only require acyclicity (if a is preferred to b, and b is preferred to c, then it is not the case that c is preferred to a) there do exist social choice rules which satisfy Arrow's requirements.

Economist and Nobel prize winner Amartya Sen has suggested at least two other alternatives^[4]. He has offered both relaxation of transitivity and removal of the Pareto principle. He has shown the existence of voting mechanisms which comply with all of Arrow's criteria, but supply only semi-transitive results.

Also, he has demonstrated another interesting impossibility result, known as the "impossibility of the Paretian Liberal". (See liberal paradox for details). Sen went on to argue that this demonstrates the futility of demanding Pareto optimality in relation to voting mechanisms.

Advocates of approval voting consider unrestricted domain to be the best criterion to weaken. In approval voting, voters can only vote 'for' or 'against' each candidate, preventing them from making distinctions between their favored candidates and merely acceptable ones.

Advocates of range voting also consider unrestricted domain to be the best criterion to violate—but instead of limiting voter options like approval voting, range voting increases the number of voter options beyond what Arrow's Theorem allows.

[edit] Scalar rankings from a vector of attributes and the IIA property

The IIA property might not be satisfied in human decision-making of realistic complexity because the scalar preference ranking is effectively derived from the weighting—not usually explicit—of a vector of attributes (one book dealing with the Arrow theorem invites the reader to consider the related problem of creating a scalar measure for the track and field decathlon event—e.g. how does one make scoring 600 points in the discus event "commensurable" with scoring 600 points in the 1500 m race) and this scalar ranking can depend sensitively on the weighting of different attributes, with the tacit weighting itself affected by the context and contrast created by apparently "irrelevant" choices. Edward MacNeal discusses this sensitivity problem with respect to the ranking of "most livable city" in the chapter "Surveys" of his book MathSemantics: making numbers talk sense (1994).

[edit] See also

[edit] Notes

^ Arrow, K.J., "A Difficulty in the Concept of Social Welfare", Journal of Political Economy 58(4) (August, 1950), pp. 328–346.
^ Three Brief Proofs of Arrow’s Impossibility Theorem
^ Campbell, D.E., Kelly, J.S., "A simple characterization of majority rule", Economic Theory 15 (2000), pp. 689–700.
^ Sen, Amartya. 1979. Personal Utilities and Public Judgements: Or What's Wrong With Welfare Economics. The Economic Journal, 89, 537-588.

[edit] References

The Mathematics of Behavior by Earl Hunt, Cambridge University Press, 2007. The chapter "Defining Rationality: Personal and Group Decision Making" has a detailed discussion of the Arrow Theorem, with proof. URL to CUP information on this book
Why flip a coin? : the art and science of good decisions by Harold W. Lewis, John Wiley, 1997. Gives explicit examples of preference rankings and apparently anomalous results under different voting systems. States but does not prove Arrow's theorem. ISBN 0-471-29645-7

[edit] External links

[0] Arrow, K.J., "A Difficulty in the Concept of Social Welfare", Journal of Political Economy 58(4) (August, 1950), pp. 328–346.

[1] Three Brief Proofs of Arrow’s Impossibility Theorem

[2] Campbell, D.E., Kelly, J.S., "A simple characterization of majority rule", Economic Theory 15 (2000), pp. 689–700.

[3] Sen, Amartya. 1979. Personal Utilities and Public Judgements: Or What's Wrong With Welfare Economics. The Economic Journal, 89, 537-588.

[1]

[2]

[3]

[4]

Arrow's impossibility theorem

From Wikipedia, the free encyclopedia

Contents

[edit] Statement of the theorem

[edit] Formal statement of the theorem

[edit] Informal proof

[edit] Part one: there is a "pivotal" voter for B

[edit] Part two: voter $n$ is a dictator for A–C

[edit] Part three: there can be at most one dictator

[edit] Interpretations of the theorem

[edit] Other possibilities

[edit] Scalar rankings from a vector of attributes and the IIA property

[edit] See also

[edit] Notes

[edit] References

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages

Arrow's impossibility theorem

From Wikipedia, the free encyclopedia

Contents

[edit] Statement of the theorem

[edit] Formal statement of the theorem

[edit] Informal proof

[edit] Part one: there is a "pivotal" voter for B

[edit] Part two: voter n is a dictator for A–C

[edit] Part three: there can be at most one dictator

[edit] Interpretations of the theorem

[edit] Other possibilities

[edit] Scalar rankings from a vector of attributes and the IIA property

[edit] See also

[edit] Notes

[edit] References

[edit] External links

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages

[edit] Part two: voter $n$ is a dictator for A–C