Arrow's impossibility theorem

Arrow's impossibility theorem is a key result in social choice showing that no rank-order decision procedure can behave rationally when there is more than one voter. Specifically, any such rule violates independence of irrelevant alternatives, the principle that a choice between ${\displaystyle A}$ and ${\displaystyle B}$ should not depend on the quality of a third, unrelated option ${\displaystyle C}$.

The result is most often cited in election science and voting theory, where ${\displaystyle C}$ is called a spoiler candidate. In this context, Arrow's theorem can be restated as showing that no ranked-choice voting rule can eliminate the spoiler effect.

The practical consequences of the theorem are debatable, with Arrow noting "Most [ranked] systems are not going to work badly all of the time. All I proved is that all can work badly at times." Some methods are more susceptible to spoilers than others. Plurality and instant-runoff in particular are highly sensitive to spoilers, often manufacturing them even in situations where they are not forced. By contrast, Condorcet methods uniquely minimize the possibility of spoilers, limiting them to rare situations called Condorcet paradoxes.

While originally overlooked by Arrow, rated methods are not affected by Arrow's theorem or IIA failures. Arrow initially asserted the information provided by these systems was meaningless, and therefore could not be used to prevent paradoxes. However, he and other authors would later recognize this to have been a mistake, with Arrow admitting systems based on cardinal utility (such as score and approval voting) are not subject to his theorem.

Background

Arrow's theorem falls under the branch of welfare economics and ethics called social choice. This field deals with aggregating preferences and information to make fair or accurate decisions. The goal is to create a social ordering function—a procedure that determines which of two outcomes or options is better, according to all members of a society—that satisfies the properties of rational behavior. Such a social ordering function can be any way for a group to make decisions; this can be a market, a voting system, a country's constitution, or even a moral or ethical framework. Arrow's theorem therefore generalizes the voting paradox discovered earlier by Condorcet, proving such paradoxes exist for any possible collective decision-making procedure that relies only on orderings of options.

History

Arrow's theorem is named after economist and Nobel laureate Kenneth Arrow, who demonstrated it in his doctoral thesis and popularized it in his 1951 book.

Arrow's work is remembered as much for its pioneering methodology as its direct implications. Arrow's axiomatic approach provided a framework for proving facts about all conceivable at once, contrasting with the earlier approach of investigating such rules one by one.

Among the most important axioms of rational choice is independence of irrelevant alternatives, which says that when deciding between ${\displaystyle A}$ and ${\displaystyle B}$, our opinion about some irrelevant option ${\displaystyle C}$ should not affect our decision. Arrow's theorem shows this is not possible without relying on further information, such as rated ballots (rejected by some strict behaviorists).

Non-degenerate systems

As background, it is typically assumed that any non-degenerate (that is, actually useful) voting system satisfies the principles of:

• Non-dictatorship—the system does not just ignore every voter except one. The principle can also be taken as defining the social choice function as a way to represent collective choices, not just individual ones, i.e. collective choices should not just be defined as some particular person's preferences.
• Non-nullity—the social choice function does not just ignore all the voters and always elect the same candidate. (At least one voter can affect the result.)

Most proofs use additional assumptions to simplify deriving the result, though Robert Wilson proved these to be unnecessary. Older proofs have taken as axioms:

• Non-negative response—increasing the rank of an outcome should not make them lose. In other words, a candidate should never lose as a result of winning "too many votes". While originally considered "obvious" for any practical system, instant-runoff fails this criterion. Arrow later gave another proof applying to systems with negative response.
• Non-imposition—it is possible for any candidate to win, given some combination of votes (the social choice function is onto).
  • This is a weaker form of neutrality, i.e. the requirement of a fair election where candidates are all treated equally. Non-imposition weakens this, requiring only that it be theoretically possible for any candidate to win.
• Pareto efficiency—if every voter agrees one candidate is better than another, the system will agree as well. (A candidate with unanimous support should win.) This assumption replaced non-negative response and non-imposition in Arrow's second proof.
• Majority rule in the two-candidate case—if most voters prefer ${\displaystyle A}$ to ${\displaystyle B}$, then ${\displaystyle A}$ should defeat ${\displaystyle B}$. This form was proven by the Marquis de Condorcet with his discovery of the voting paradox.
• Universal domain—some authors are explicit about the assumption that the social welfare function is a function over the domain of all possible preferences (not just a partial function).
  • In other words, the system cannot simply "give up" and refuse to elect a candidate for some sets of ballots.
  • Without this assumption, majority rule satisfies Arrow's criteria, and May's theorem shows it is the unique "sensible" social choice function that does so. This result is often cited as justification for Condorcet methods, which always elect a majority-preferred candidate if possible.

Independence of irrelevant alternatives (IIA)

The IIA condition is an important assumption governing rational choice. The axiom says that adding irrelevant—i.e. rejected—options should not affect the outcome of a decision. From a practical point of view, the assumption prevents electoral outcomes from behaving erratically in response to the arrival and departure of candidates.

Arrow defines IIA slightly differently, by stating that the social preference between alternatives ${\displaystyle A}$ and ${\displaystyle B}$ should only depend on the individual preferences between ${\displaystyle A}$ and ${\displaystyle B}$. In other words, we should not be able to go from ${\displaystyle A\succ B}$ to ${\displaystyle B\succ A}$ by changing preferences over some irrelevant alternative, e.g. whether ${\displaystyle A\succ C}$. This is equivalent to the above statement about independence of spoiler candidates, which can be proven by using the standard construction of a placement function.

Theorem

Intuitive argument

If we are willing to make the stronger assumptions that our voting system guarantees the principles of one vote one value and a free and fair election, the proof of Arrow's theorem becomes much simpler, and was given by Condorcet. May's theorem implies that under the assumptions above, the only Pareto-efficient rule for choosing between two candidates is a simple majority vote. Therefore, the requirement that all social preferences ${\displaystyle A\succ B}$ only depend on individual preferences ${\displaystyle A\succ _{i}B}$ effectively says that ${\displaystyle A\succ B}$ if and only if most voters prefer ${\displaystyle A}$ to ${\displaystyle B}$. Given these assumptions, the existence of the voting paradox is enough to show the impossibility of rational behavior for ranked-choice voting.

The above is sufficient to show Arrow's theorem for all "practical" voting systems, as systems that violate the above assumptions are unlikely to be considered meaningfully democratic. However, Arrow's theorem can be made substantially more general.

Formal statement

Let A be a set of outcomes, N a number of voters or decision criteria. We denote the set of all total orderings of A by L(A).

An ordinal (ranked) social welfare function is a function:

${\displaystyle \mathrm {F} :\mathrm {L} (A)^{N}\to \mathrm {L} (A)}$

which aggregates voters' preferences into a single preference order on A.

An N-tuple (R₁, …, R_N) ∈ L(A)^N of voters' preferences is called a preference profile. We assume two conditions:

Pareto efficiency

If alternative a is ranked strictly higher than b for all orderings R₁ , …, R_N, then a is ranked strictly higher than b by F(R₁, R₂, …, R_N). This axiom is not needed, but simplifies the proof by reducing the number of cases.

Non-dictatorship

There is no individual i whose strict preferences always prevail. That is, there is no i ∈ {1, …, N} such that for all (R₁, …, R_N) ∈ L(A)^N and all a and b, when a is ranked strictly higher than b by R_i then a is ranked strictly higher than b by F(R₁, R₂, …, R_N).

Then, this rule must violate independence of irrelevant alternatives:

Independence of irrelevant alternatives

For two preference profiles (R₁, …, R_N) and (S₁, …, 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₁, …, R_N) as in F(S₁, …, S_N).

Formal proof

Interpretation and practical solutions

Arrow's theorem establishes that no ranked voting rule can always satisfy independence of irrelevant alternatives, but it says nothing about the frequency of spoilers. This led Arrow to remark that "Most systems are not going to work badly all of the time. All I proved is that all can work badly at times."

Attempts at dealing with the effects of Arrow's theorem take one of two approaches: either accepting his rule and searching for the least spoiler-prone methods, or dropping his assumption of ranked voting to focus on studying rated voting rules.

Minimizing IIA failures: Majority-rule methods

The first set of methods economists have studied are the majority-rule methods, which limit spoilers to rare situations where majority rule is self-contradictory, and uniquely minimize the possibility of a spoiler effect among rated methods. Arrow's theorem was preceded by the Marquis de Condorcet's discovery of cyclic social preferences, situations where majority rule is logically inconsistent. Condorcet believed voting rules should satisfy both independence of irrelevant alternatives and the majority rule principle, i.e. if most voters rank Alice ahead of Bob, Alice should defeat Bob in the election.

Unfortunately, as Condorcet proved, this rule can be self-contradictory (intransitive), because there can be a rock-paper-scissors cycle with three or more candidates defeating each other in a circle. Thus, Condorcet proved a weaker form of Arrow's impossibility theorem long before Arrow, under the stronger assumption that a voting system in the two-candidate case will agree with a simple majority vote.

Condorcet methods avoid the spoiler effect in non-cyclic elections, where candidates can be chosen by majority rule. Political scientists have found such cycles to be empirically rare, suggesting they may be of limited practical concern. Spatial voting models also suggest such paradoxes are likely to be infrequent or even non-existent.

Left-right spectrum

Duncan Black showed his own remarkable result, the median voter theorem. The theorem proves that if voters and candidates are arranged on a left-right spectrum, Arrow's conditions are compatible, and all of them will be met by any rule satisfying Condorcet's majority-rule principle.

More formally, Black's theorem assumes preferences are single-peaked: a voter's happiness with a candidate goes up and then down as the candidate moves along some spectrum. For example, in a group of friends choosing a volume setting for music, each friend would likely have their own ideal volume; as the volume gets progressively too loud or too quiet, they would be increasingly dissatisfied.

If the domain is restricted to profiles where every individual has a single-peaked preference with respect to the linear ordering, then social preferences are acyclic. In this situation, Condorcet methods satisfy a wide variety of highly-desirable properties.

Unfortunately, the rule does not generalize from the political spectrum to the political compass, a result called the McKelvey-Schofield Chaos Theorem. However, a well-defined median and Condorcet winner do exist if the distribution of voters on the ideological spectrum is rotationally symmetric. In realistic cases, when voters' opinions follow a roughly-symmetric distribution such as a normal distribution or can be accurately summarized in one or two dimensions, Condorcet cycles tend to be rare.

Generalized stability theorems

The Campbell-Kelly theorem shows that Condorcet methods are the most spoiler-resistant class of ranked voting systems: whenever it is possible for some ranked voting system to avoid a spoiler effect, a Condorcet method will do so. In other words, replacing a ranked-voting method with its Condorcet variant (i.e. elect a Condorcet winner if they exist, and otherwise run the method) will sometimes prevent a spoiler effect, but never cause a new one.

In 1977, Ehud Kalai and Eitan Muller gave a full characterization of domain restrictions admitting a nondictatorial and strategyproof social welfare function. These correspond to preferences for which there is a Condorcet winner.

Holliday and Pacuit devised a voting system that provably minimizes the number of candidates who are capable of spoiling an election, albeit at the cost of occasionally failing vote positivity (though at a much lower rate than seen in instant-runoff voting).

Eliminating IIA failures: Rated voting

As shown above, the proof of Arrow's theorem relies crucially on the assumption of ranked voting, and is not applicable to rated voting systems. As a result, systems like score voting and graduated majority judgment pass independence of irrelevant alternatives. These systems ask voters to rate candidates on a numerical scale (e.g. from 0–10), and then elect the candidate with the highest average (for score voting) or median (graduated majority judgment).

While Arrow's theorem does not apply to graded systems, Gibbard's theorem still does: no voting game can be straightforward (i.e. have a single, clear always-best strategy), so the informal dictum that "no voting system is perfect" still has some mathematical basis.

Meaningfulness of cardinal information

Arrow's framework assumed individual and social preferences are orderings or rankings, i.e. statements about which outcomes are better or worse than others. Taking inspiration from the strict behaviorism popular in psychology, some philosophers and economists rejected the idea of comparing internal human experiences of well-being. Such philosophers claimed it was impossible to compare the strength of preferences across several people who disagreed; Sen gives as an example that it would be impossible to know whether Nero's choice to begin the Great Fire of Rome was right or wrong, because while it killed thousands of Romans, it had the positive effect of allowing Nero to expand his palace.

Arrow originally agreed with these positions and rejected cardinal utility, leading him to focus his theorem on preference rankings. However, he later reversed this opinion, admitting scoring methods can provide useful information that allows them to evade his theorem. Similarly, Amartya Sen first claimed interpersonal comparability is necessary for IIA, but later argued it would only require "rather limited levels of partial comparability" to hold in practice.

Balinski and Laraki dispute the necessity of any genuinely cardinal information for rated voting methods to pass IIA. They argue the availability of a common language with verbal grades is sufficient for IIA by allowing voters to give consistent responses to questions about candidate quality. In other words, they argue most voters will not change their beliefs about whether a candidate is "good", "bad", or "neutral" simply because another candidate joins or drops out of a race.

John Harsanyi noted Arrow's theorem could be considered a special case of his own theorem and other utility representation theorems like the VNM theorem, which generally show that rational behavior requires consistent cardinal utilities. Harsanyi and Vickrey each independently derived results showing such interpersonal comparisons of utility could be rigorously defined as individual preferences over the lottery of birth.

Kaiser and Oswald conducted an empirical review of four decades of research including over 700,000 participants who provided self-reported measures of utility, with the goal of identifying whether people "have a sense of an actual underlying scale for their innermost feelings". They found that responses to such questions were consistent with all expectations of a well-specified quantitative measure. Furthermore, they were highly predictive of important decisions (such as international migration and divorce), moreso than even standard socioeconomic variables such as income and demographics. Ultimately, the authors concluded "this feelings-to-actions relationship takes a generic form, is consistently replicable, and is fairly close to linear in structure. Therefore, it seems that human beings can successfully operationalize an integer scale for feelings".

These results have led to the rise of implicit utilitarian voting approaches, which model ranked-choice procedures as approximations of the utilitarian rule (i.e. score voting).

Nonstandard spoilers

Behavioral economists have shown individual irrationality involves violations of IIA (e.g. with decoy effects), suggesting human behavior might cause IIA failures even if the voting method itself does not. However, past research on similar effects has found their effects are typically small, and such psychological spoiler effects can occur regardless of the electoral system in use. Balinski and Laraki discuss techniques of ballot design that could minimize these psychological effects, such as asking voters to give each individual candidate a verbal grade (e.g. "bad", "neutral", "good", "excellent").

Esoteric solutions

In addition to the above practical resolutions, there exist unusual (less-than-practical) situations where Arrow's conditions can be satisfied.

Supermajority rules

Supermajority rules can avoid Arrow's theorem at the cost of being poorly-decisive (i.e. frequently failing to return a result). In this case, a threshold that requires a ${\displaystyle 2/3}$ majority for ordering 3 outcomes, ${\displaystyle 3/4}$ for 4, etc. does not produce voting paradoxes.

In spatial (n-dimensional ideology) models of voting, this can be relaxed to require only ${\displaystyle 1-e^{-1}}$ (roughly 64%) of the vote to prevent cycles, so long as the distribution of voters is well-behaved (quasiconcave). This can be seen as providing some justification for the common requirement of a ${\displaystyle 2/3}$ majority for constitutional amendments, which is sufficient to prevent cyclic preferences in most situations.

Uncountable voter sets

Fishburn shows all of Arrow's conditions can be satisfied for uncountable sets of voters given the axiom of choice; however, Kirman and Sondermann showed this requires disenfranchising almost all members of a society (eligible voters form a set of measure 0), leading them to refer to such societies as "invisible dictatorships".

Common misconceptions

Arrow's theorem is not related to strategic voting, which does not appear in his framework. The Arrovian framework of social welfare assumes all voter preferences are known and the only issue is in aggregating them.

Contrary to a common misconception, Arrow's theorem deals with the limited class of ranked-choice voting systems, rather than voting systems as a whole.

See also

• Condorcet paradox
• Gibbard–Satterthwaite theorem
• Gibbard's theorem
• Holmström's theorem
• Market failure
• Voting paradox
• Comparison of electoral systems

References

Further reading

• Campbell, D. E. (2002). "Impossibility theorems in the Arrovian framework". In Arrow, Kenneth J.; Sen, Amartya K.; Suzumura, Kōtarō (eds.). Handbook of social choice and welfare. Vol. 1. Amsterdam, Netherlands: Elsevier. pp. 35–94. ISBN 978-0-444-82914-6. Surveys many of approaches discussed in #Alternatives based on functions of preference profiles.
• Dardanoni, Valentino (2001). "A pedagogical proof of Arrow's Impossibility Theorem" (PDF). Social Choice and Welfare. 18 (1): 107–112. doi:10.1007/s003550000062. JSTOR 41106398. S2CID 7589377. preprint.
• Hansen, Paul (2002). "Another Graphical Proof of Arrow's Impossibility Theorem". The Journal of Economic Education. 33 (3): 217–235. doi:10.1080/00220480209595188. S2CID 145127710.
• Hunt, Earl (2007). The Mathematics of Behavior. Cambridge University Press. ISBN 9780521850124.. The chapter "Defining Rationality: Personal and Group Decision Making" has a detailed discussion of the Arrow Theorem, with proof.
• Lewis, Harold W. (1997). Why flip a coin? : The art and science of good decisions. John Wiley. ISBN 0-471-29645-7. Gives explicit examples of preference rankings and apparently anomalous results under different electoral system. States but does not prove Arrow's theorem.
• Sen, Amartya Kumar (1979). Collective choice and social welfare. Amsterdam: North-Holland. ISBN 978-0-444-85127-7.
• Skala, Heinz J. (2012). "What Does Arrow's Impossibility Theorem Tell Us?". In Eberlein, G.; Berghel, H. A. (eds.). Theory and Decision : Essays in Honor of Werner Leinfellner. Springer. pp. 273–286. ISBN 978-94-009-3895-3.
• Tang, Pingzhong; Lin, Fangzhen (2009). "Computer-aided Proofs of Arrow's and Other Impossibility Theorems". Artificial Intelligence. 173 (11): 1041–1053. doi:10.1016/j.artint.2009.02.005.

External links

• "Arrow's impossibility theorem" entry in the Stanford Encyclopedia of Philosophy
• A proof by Terence Tao, assuming a much stronger version of non-dictatorship