Arrow's impossibility theorem


In social choice theory, Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem stating that when voters have three or more distinct alternatives, no ranked voting electoral system can convert the ranked preferences of individuals into a community-wide ranking while also meeting a specified set of criteria: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives. The theorem is often cited in discussions of voting theory as it is further interpreted by the Gibbard–Satterthwaite theorem. The theorem is named after economist and Nobel laureate Kenneth Arrow, who demonstrated the theorem in his doctoral 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".
In short, the theorem states that no rank-order electoral system can be designed that always satisfies these three "fairness" criteria:
Cardinal voting electoral systems are not covered by the theorem, as they convey more information than rank orders. However, Gibbard's theorem extends Arrow's theorem for that case. The theorem can also be sidestepped by weakening the notion of independence.
The axiomatic approach Arrow adopted can treat all conceivable rules within one unified framework. In that sense, the approach is qualitatively different from the earlier one in voting theory, in which rules were investigated one by one. One can therefore say that the contemporary paradigm of social choice theory started from this theorem.
The practical consequences of the theorem are debatable: Arrow has said "Most systems are not going to work badly all of the time. All I proved is that all can work badly at times."

Statement

The need to aggregate preferences occurs in many 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 electoral systems, which are mechanisms for extracting a governance-related 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. Each individual in the society gives a particular order of preferences on the set of outcomes. We are searching for a ranked voting electoral system, called a social welfare function, which transforms the set of preferences into a single global societal preference order. 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:
; 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: For any set of individual voter preferences, the social welfare function should yield a unique and complete ranking of societal choices. Thus:
; Independence of irrelevant alternatives : The social preference between x and y should depend only on the individual preferences between x and y. More generally, changes in individuals' rankings of irrelevant alternatives should have no impact on the societal ranking of the subset. For example, if candidate x ranks socially before candidate y, then x should rank socially before y even if a third candidate z is removed from participation.
; Monotonicity, or positive association of social and individual values: 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.
A later version of Arrow's theorem replaced the monotonicity and non-imposition criteria with:
; Pareto efficiency, or unanimity: 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.
This later version is more general, having weaker conditions. The axioms of monotonicity, non-imposition, and IIA together imply Pareto efficiency, whereas Pareto efficiency and IIA together do not imply monotonicity.

Independence of irrelevant alternatives (IIA)

The IIA condition has three purposes :
;Normative: Irrelevant alternatives should not matter.
;Practical: Use of minimal information.
;Strategic: Providing the right incentives for the truthful revelation of individual preferences. Though the strategic property is conceptually different from IIA, it is closely related.
Arrow's death-of-a-candidate example suggests that the agenda shrinks from, say, X = to S = because of the death of candidate c. This example is misleading since it can give the reader an impression that IIA is a condition involving two agenda and one profile. The fact is that IIA involves just one agendum but two profiles. If the condition is applied to this confusing example, it requires this: Suppose an aggregation rule satisfying IIA chooses b from the agenda when the profile is given by, that is, individual 1 prefers c to a to b, 2 prefers c to b to a. Then, it must still choose b from if the profile were, say: ; ; ; or.
In different words, Arrow defines IIA as saying that the social preferences between alternatives x and y depend only on the individual preferences between x and y.

Formal statement of the theorem

Let be a set of outcomes, a number of voters or decision criteria. We shall denote the set of all full linear orderings of by.
A social welfare function is a function
which aggregates voters' preferences into a single preference order on.
An -tuple of voters' preferences is called a preference profile. In its strongest and simplest form, Arrow's impossibility theorem states that whenever the set of possible alternatives has more than 2 elements, then the following three conditions become incompatible:
; Unanimity, or weak Pareto efficiency: If alternative,, is ranked strictly higher than for all orderings, then is ranked strictly higher than by.
; Non-dictatorship: There is no individual, whose strict preferences always prevail. That is, there is no such that for all, ranked strictly higher than by implies ranked strictly higher than by, for all and.
; Independence of irrelevant alternatives: For two preference profiles and such that for all individuals, alternatives and have the same order in as in, alternatives and have the same order in as in.

Informal proof

Based on two proofs appearing in Economic Theory. For simplicity we have presented all rankings as if ties are impossible. A complete proof taking possible ties into account is not essentially different from the one given here, except that one ought to say "not above" instead of "below" or "not below" instead of "above" in some cases. Full details are given in the original articles.
We will prove that any social choice system respecting unrestricted domain, unanimity, and independence of irrelevant alternatives is a dictatorship. The key idea is to identify a pivotal voter whose ballot swings the societal outcome. We then prove that this voter is a partial dictator. Finally we conclude by showing that all of the partial dictators are the same person, hence this voter is a dictator.

Part one: There is a "pivotal" voter for B over A

Say there are three choices for society, call them A, B, and C. Suppose first that everyone prefers option B the least: everyone prefers A to B, and everyone prefers C to B. By unanimity, society must also prefer both A and C to B. Call this situation profile 0.
On the other hand, if everyone preferred B to everything else, then society would have to prefer B to everything else by unanimity. Now arrange all the voters in some arbitrary but fixed order, and for each i let profile i be the same as profile 0, but move B to the top of the ballots for voters 1 through i. So profile 1 has B at the top of the ballot for voter 1, but not for any of the others. Profile 2 has B at the top for voters 1 and 2, but no others, and so on.
Since B eventually moves to the top of the societal preference, there must be some profile, number k, for which B moves above A in the societal rank. We call the voter whose ballot change causes this to happen the pivotal voter for B over A. Note that the pivotal voter for B over A is not, a priori, the same as the pivotal voter for A over B. In part three of the proof we will show that these do turn out to be the same.
Also note that by IIA the same argument applies if profile 0 is any profile in which A is ranked above B by every voter, and the pivotal voter for B over A will still be voter k. We will use this observation below.

Part two: The pivotal voter for B over A is a dictator for B over C

In this part of the argument we refer to voter k, the pivotal voter for B over A, as pivotal voter for simplicity. We will show that pivotal voter dictates society's decision for B over C. That is, we show that no matter how the rest of society votes, if Pivotal Voter ranks B over C, then that is the societal outcome. Note again that the dictator for B over C is not a priori the same as that for C over B. In part three of the proof we will see that these turn out to be the same too.
In the following, we call voters 1 through k − 1, segment one, and voters k + 1 through N, segment two. To begin, suppose that the ballots are as follows:
Then by the argument in part one, the societal outcome must rank A above B. This is because, except for a repositioning of C, this profile is the same as profile k − 1 from part one. Furthermore, by unanimity the societal outcome must rank B above C. Therefore, we know the outcome in this case completely.
Now suppose that pivotal voter moves B above A, but keeps C in the same position and imagine that any number of the other voters change their ballots to move B below C, without changing the position of A. Then aside from a repositioning of C this is the same as profile k from part one and hence the societal outcome ranks B above A. Furthermore, by IIA the societal outcome must rank A above C, as in the previous case. In particular, the societal outcome ranks B above C, even though Pivotal Voter may have been the only voter to rank B above C. By IIA, this conclusion holds independently of how A is positioned on the ballots, so pivotal voter is a dictator for B over C.

Part three: There exists a dictator

In this part of the argument we refer back to the original ordering of voters, and compare the positions of the different pivotal voters. First, the pivotal voter for B over C must appear earlier in the line than the dictator for B over C: As we consider the argument of part one applied to B and C, successively moving B to the top of voters' ballots, the pivot point where society ranks B above C must come at or before we reach the dictator for B over C. Likewise, reversing the roles of B and C, the pivotal voter for C over B must be at or later in line than the dictator for B over C. In short, if kX/Y denotes the position of the pivotal voter for X over Y, then we have shown
Now repeating the entire argument above with B and C switched, we also have
Therefore, we have
and the same argument for other pairs shows that all the pivotal voters occur at the same position in the list of voters. This voter is the dictator for the whole election.

Interpretations

Although Arrow's theorem is a mathematical result, 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 deterministic preferential voting mechanism—that is, one where a preference order is the only information in a vote, and any possible set of votes gives a unique result—cannot comply with all of the conditions given above simultaneously.
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. It is the one breached in most useful electoral 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:
then the pairwise majority preference of the group is that A wins over B, B wins over C, and C wins over A: these yield rock-paper-scissors preferences for any pairwise comparison. In this circumstance, any aggregation rule that satisfies the very basic majoritarian requirement that a candidate who receives a majority of votes must win the election, will fail the IIA criterion, if social preference is required to be transitive. To see this, suppose that such a rule satisfies IIA. Since majority preferences are respected, the society prefers A to B, B to C, and C to A. Thus a cycle is generated, which contradicts the assumption that social preference is transitive.
So, what Arrow's theorem really shows is that any majority-wins electoral system 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.

Remark: 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 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.

Other possibilities

In an attempt to escape from the negative conclusion of Arrow's theorem, social choice theorists have investigated various possibilities. These investigations can be divided into the following two:
This section includes approaches that deal with
Since these two approaches often overlap, we discuss them at the same time. What is characteristic of these approaches is that they investigate various possibilities by eliminating or weakening or replacing one or more conditions that Arrow imposed.

Infinitely many individuals

Several theorists point out that when one drops the assumption that there are only finitely many individuals, one can find aggregation rules that satisfy all of Arrow's other conditions.
However, such aggregation rules are practically of limited interest, since they are based on ultrafilters, highly non-constructive mathematical objects. In particular, Kirman and Sondermann argue that there is an "invisible dictator" behind such a rule. Mihara shows that such a rule violates algorithmic computability. These results can be seen to establish the robustness of Arrow's theorem.

Limiting the number of alternatives

When there are only two alternatives to choose from, May's theorem shows that only simple majority rule satisfies a certain set of criteria. On the other hand, when there are at least three alternatives, Arrow's theorem points out the difficulty of collective decision making. Why is there such a sharp difference between the case of less than three alternatives and that of at least three alternatives?
Nakamura's theorem gives an answer more generally. It establishes that if the number of alternatives is less than a certain integer called the Nakamura number, then the rule in question will identify "best" alternatives without any problem; if the number of alternatives is greater or equal to the Nakamura number, then the rule will not always work, since for some profile a voting paradox will arise. Since the Nakamura number of majority rule is 3, one can conclude from Nakamura's theorem that majority rule can deal with up to two alternatives rationally. Some super-majority rules can have a Nakamura number greater than 3, but such rules violate other conditions given by Arrow.

Pairwise voting

A common way "around" Arrow's 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 satisfying even Pareto efficiency, 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. This means that the person controlling the order by which the choices are paired has great control over the outcome. In any case, when viewing the entire voting process as one game, Arrow's theorem still applies.

Domain restrictions

Another approach is relaxing the universality condition, which means restricting the domain of aggregation rules. The best-known result along this line assumes "single peaked" preferences.
Duncan Black has shown that if there is only one dimension on which every individual has a "single-peaked" preference, then all of Arrow's conditions are met by majority rule. Suppose that there is some predetermined linear ordering of the alternative set. An individual's preference is single-peaked with respect to this ordering if he has some special place that 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.
If the domain is restricted to profiles in which every individual has a single peaked preference with respect to the linear ordering, then simple aggregation rules, which include majority rule, have an acyclic social preference, hence "best" alternative. In particular, when there are odd number of individuals, then the social preference becomes transitive, and the socially "best" alternative is equal to the median of all the peaks of the individuals. Under single-peaked preferences, the majority rule is in some respects the most natural voting mechanism.
One can define the notion of "single-peaked" preferences on higher-dimensional sets of alternatives. However, one can identify the "median" of the peaks only in exceptional cases. Instead, we typically have the destructive situation suggested by McKelvey's Chaos Theorem: for any x and y, one can find a sequence of alternatives such that x is beaten by x1 by a majority, x1 by x2, up to xk by y.

Relaxing transitivity

By relaxing the transitivity of social preferences, we can find aggregation rules that satisfy Arrow's other conditions. If we impose neutrality on such rules, however, there exists an individual who has a "veto". So the possibility provided by this approach is also very limited.
First, suppose that a social preference is quasi-transitive ; this means that the strict preference is transitive: if and, then. Then, there do exist non-dictatorial aggregation rules satisfying Arrow's conditions, but such rules are oligarchic. This means that there exists a coalition L such that L is decisive, and each member in L has a veto.
Second, suppose that a social preference is acyclic : there do not exist alternatives that form a cycle. Then, provided that there are at least as many alternatives as individuals, an aggregation rule satisfying Arrow's other conditions is collegial. This means that there are individuals who belong to the intersection of all decisive coalitions. If there is someone who has a veto, then he belongs to the collegium. If the rule is assumed to be neutral, then it does have someone who has a veto.
Finally, Brown's theorem left open the case of acyclic social preferences where the number of alternatives is less than the number of individuals. One can give a definite answer for that case using the Nakamura number. See [|limiting the number of alternatives].

Relaxing IIA

There are numerous examples of aggregation rules satisfying Arrow's conditions except IIA. The Borda rule is one of them. These rules, however, are susceptible to strategic manipulation by individuals.
See also Interpretations of the theorem above.

Relaxing the Pareto criterion

Wilson shows that if an aggregation rule is non-imposed and non-null, then there is either a dictator or an inverse dictator, provided that Arrow's conditions other than Pareto are also satisfied. Here, an inverse dictator is an individual i such that whenever i prefers x to y, then the society prefers y to x.
Remark
offered both relaxation of transitivity and removal of the Pareto principle. He demonstrated another interesting impossibility result, known as the "impossibility of the Paretian Liberal". Sen went on to argue that this demonstrates the futility of demanding Pareto optimality in relation to voting mechanisms.

Social choice instead of social preference

In social decision making, to rank all alternatives is not usually a goal. It often suffices to find some alternative. The approach focusing on choosing an alternative investigates either social choice functions or social choice rules.
As for social choice functions, the Gibbard–Satterthwaite theorem is well-known, which states that if a social choice function whose range contains at least three alternatives is strategy-proof, then it is dictatorial.
As for social choice rules, we should assume there is a social preference behind them. That is, we should regard a rule as choosing the maximal elements of some social preference. The set of maximal elements of a social preference is called the core. Conditions for existence of an alternative in the core have been investigated in two approaches. The first approach assumes that preferences are at least acyclic. For this reason, it is closely related to [|relaxing transitivity]. The second approach drops the assumption of acyclic preferences. Kumabe and Mihara adopt this approach. They make a more direct assumption that individual preferences have maximal elements, and examine conditions for the social preference to have a maximal element. See Nakamura number for details of these two approaches.

Rated electoral system and other approaches

Arrow originally rejected cardinal utility as a meaningful tool for expressing social welfare, and so focused his theorem on preference rankings, but later stated that a cardinal score system with three or four classes "is probably the best".
Arrow's framework assumes that individual and social preferences are "orderings" on the set of alternatives. This means that if the preferences are represented by a utility function, its value is an ordinal utility in the sense that it is meaningful so far as the greater value indicates the better alternative. For instance, having ordinal utilities of 4, 3, 2, 1 for alternatives a, b, c, d, respectively, is the same as having 1000, 100.01, 100, 0, which in turn is the same as having 99, 98, 1,.997. They all represent the ordering in which a is preferred to b to c to d. The assumption of ordinal preferences, which precludes interpersonal comparisons of utility, is an integral part of Arrow's theorem.
For various reasons, an approach based on cardinal utility, where the utility has a meaning beyond just giving a ranking of alternatives, is not common in contemporary economics. However, once one adopts that approach, one can take intensities of preferences into consideration, or one can compare gains and losses of utility or levels of utility, across different individuals. In particular, Harsanyi gives a justification of utilitarianism, originating from Jeremy Bentham. Hammond gives a justification of the maximin principle, originating from John Rawls.
Not all voting methods use, as input, only an ordering of all candidates. Methods which don't, often called "rated" or "cardinal" electoral system, can be viewed as using information that only cardinal utility can convey. In that case, it is not surprising if some of them satisfy all of Arrow's conditions that are reformulated.
Range voting is such a method.
Whether such a claim is correct depends on how each condition is reformulated. Other rated electoral system which pass certain generalizations of Arrow's criteria include approval voting and majority judgment. Note that Arrow's theorem does not apply to single-winner methods such as these, but Gibbard's theorem still does: no non-defective electoral system is fully strategy-free, so the informal dictum that "no electoral system is perfect" still has a mathematical basis.
Finally, though not an approach investigating some kind of rules, there is a criticism by James M. Buchanan, Charles Plott, and others. It argues that it is silly to think that there might be social preferences that are analogous to individual preferences. Arrow answers this sort of criticism seen in the early period, which come at least partly from misunderstanding.
A multi-pronged refutation of Arrow's theorem was published by philosophy Professor Howard DeLong in 1991. He challenges the theorem on the basis that Arrow wrongly assumes Preference is transitive property and that Collective Preference is the same as summing up individual preferences. He also claims that Arrow's model fails to model democracy as it exists in the real world as the model ignores the possibility of consensual temporary dictatorships and the effect of allowing lotteries to decide tie breakers and to avoid the problem of the tyranny of the majority, the example used being a group of campers at a summer camp, 8 of whom prefer cake, 7 who prefer ice cream, but funds are limited to one choice or the other on a weekly basis. Under the collective preference of majority rule each week the group would select cake. By drawing lots the choices would more accurately reflect the preferences of the collective than the majority.