Arrow's impossibility theorem

Theorem

Intuitive argument

Condorcet's example is already enough to see the impossibility of a fair ranked voting system, given stronger conditions for fairness than Arrow's theorem assumes. Suppose we have three candidates (${\displaystyle A}$, ${\displaystyle B}$, and ${\displaystyle C}$) and three voters whose preferences are as follows:

If ${\displaystyle C}$ is chosen as the winner, it can be argued any fair voting system would say ${\displaystyle B}$ should win instead, since two voters (1 and 2) prefer ${\displaystyle B}$ to ${\displaystyle C}$ and only one voter (3) prefers ${\displaystyle C}$ to ${\displaystyle B}$. However, by the same argument ${\displaystyle A}$ is preferred to ${\displaystyle B}$, and ${\displaystyle C}$ is preferred to ${\displaystyle A}$, by a margin of two to one on each occasion. Thus, even though each individual voter has consistent preferences, the preferences of society are contradictory: ${\displaystyle A}$ is preferred over ${\displaystyle B}$ which is preferred over ${\displaystyle C}$ which is preferred over ${\displaystyle A}$.

Because of this example, some authors credit Condorcet with having given an intuitive argument that presents the core of Arrow's theorem. However, Arrow's theorem is substantially more general; it applies to methods of making decisions other than one-person-one-vote elections, such as markets or weighted voting, based on ranked ballots.

Formal statement

Let ${\displaystyle A}$ be a set of alternatives. A voter's preferences over ${\displaystyle A}$ are a complete and transitive binary relation on ${\displaystyle A}$ (sometimes called a total preorder), that is, a subset ${\displaystyle R}$ of ${\displaystyle A\times A}$ satisfying:

1. (Transitivity) If ${\displaystyle (\mathbf{a},\mathbf{b})}$ is in ${\displaystyle R}$ and ${\displaystyle (\mathbf{b},\mathbf{c})}$ is in ${\displaystyle R}$, then ${\displaystyle (\mathbf{a},\mathbf{c})}$ is in ${\displaystyle R}$,
2. (Completeness) At least one of ${\displaystyle (\mathbf{a},\mathbf{b})}$ or ${\displaystyle (\mathbf{b},\mathbf{a})}$ must be in ${\displaystyle R}$.

The element ${\displaystyle (\mathbf{a},\mathbf{b})}$ being in ${\displaystyle R}$ is interpreted to mean that alternative ${\displaystyle \mathbf{a}}$ is preferred to or indifferent to alternative ${\displaystyle \mathbf{b}}$. This situation is often denoted ${\displaystyle \mathbf{a}\succsim \mathbf{b}}$ or ${\displaystyle \mathbf{a}R\mathbf{b}}$. The symmetric part of ${\displaystyle R}$ yields the indifference relation ${\displaystyle I}$. This is written as ${\displaystyle \mathbf{a}\sim \mathbf{b}}$ or ${\displaystyle \mathbf{a}I\mathbf{b}}$ if and only if ${\displaystyle (\mathbf{a},\mathbf{b})}$ and ${\displaystyle (\mathbf{b},\mathbf{a})}$ are both in ${\displaystyle R}$. The asymmetric part of ${\displaystyle R}$ yields the (strict) preference relation ${\displaystyle P}$. This is written as ${\displaystyle \mathbf{a}\succ \mathbf{b}}$ or ${\displaystyle \mathbf{a}P\mathbf{b}}$ if and only if ${\displaystyle (\mathbf{a},\mathbf{b})}$ is in ${\displaystyle R}$ and ${\displaystyle (\mathbf{b},\mathbf{a})}$ is not in ${\displaystyle R}$. In the following, preference of one alternative over another denotes strict preference.

Denote the set of all preferences on ${\displaystyle A}$ by ${\displaystyle \mathrm{\Pi }(A)}$. Equivalently, ${\displaystyle \mathrm{\Pi }(A)}$ is the set of rankings of the alternatives in ${\displaystyle A}$ from top to bottom, with ties allowed. Let ${\displaystyle N}$ be a positive integer. An ordinal (ranked) social welfare function is a function

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

which aggregates voters' preferences into a single preference on ${\displaystyle A}$. An ${\displaystyle N}$-tuple ${\displaystyle (R_1,\dots ,R_N)\in \mathrm{\Pi }(A{)}^N}$ of voters' preferences is called a preference profile.

Arrow's impossibility theorem: If there are at least three alternatives, then there is no social welfare function satisfying all three of the conditions listed below:

Pareto efficiency

If alternative ${\displaystyle \mathbf{a}}$ is preferred to ${\displaystyle \mathbf{b}}$ for all orderings ${\displaystyle R_1,\dots ,R_N}$, then ${\displaystyle \mathbf{a}}$ is preferred to ${\displaystyle \mathbf{b}}$ by ${\displaystyle F(R_1,R_2,\dots ,R_N)}$.

Non-dictatorship

There is no individual ${\displaystyle i}$ whose preferences always prevail. That is, there is no ${\displaystyle i\in \{1,\dots ,N\}}$ such that for all ${\displaystyle (R_1,\dots ,R_N)\in \mathrm{\Pi }(A{)}^N}$ and all ${\displaystyle \mathbf{a}}$ and ${\displaystyle \mathbf{b}}$, when ${\displaystyle \mathbf{a}}$ is preferred to ${\displaystyle \mathbf{b}}$ by ${\displaystyle R_i}$ then ${\displaystyle \mathbf{a}}$ is preferred to ${\displaystyle \mathbf{b}}$ by ${\displaystyle F(R_1,R_2,\dots ,R_N)}$.

Independence of irrelevant alternatives

For two preference profiles ${\displaystyle (R_1,\dots ,R_N)}$ and ${\displaystyle (S_1,\dots ,S_N)}$ such that for all individuals ${\displaystyle i}$, alternatives ${\displaystyle \mathbf{a}}$ and ${\displaystyle \mathbf{b}}$ have the same order in ${\displaystyle R_i}$ as in ${\displaystyle S_i}$, alternatives ${\displaystyle \mathbf{a}}$ and ${\displaystyle \mathbf{b}}$ have the same order in ${\displaystyle F(R_1,\dots ,R_N)}$ as in ${\displaystyle F(S_1,\dots ,S_N)}$.

Formal proof

Stronger versions

Arrow's impossibility theorem still holds if Pareto efficiency is weakened to the following condition:

Non-imposition

For any two alternatives a and b, there exists some preference profile R₁ , …, R_N such that a is preferred to b by F(R₁, R₂, …, R_N).

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 one or more of his assumptions, such as by focusing on rated voting rules.

Minimizing 'independence of irrelevant alternatives' failures: Majority-rule methods

The first set of methods studied by economists are the majority-rule, or Condorcet, methods. These rules limit spoilers to situations where majority rule is self-contradictory, called Condorcet cycles, and as a result uniquely minimize the possibility of a spoiler effect among ranked rules. (Indeed, many different social welfare functions can meet Arrow's conditions under such restrictions of the domain. It has been proven, however, that under any such restriction, if there exists any social welfare function that adheres to Arrow's criteria, then Condorcet method will adhere to Arrow's criteria.) 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 intransitive on some preference profiles. 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.

Unlike pluralitarian rules such as instant-runoff voting or plurality voting, 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 fairly 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

Soon after Arrow published his theorem, 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 all fully compatible, and all 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, including being fully spoilerproof.

The rule does not fully generalize from the political spectrum to the political compass, a result related to the McKelvey-Schofield chaos theorem. However, a well-defined Condorcet winner does exist if the distribution of voters is rotationally symmetric or otherwise has a uniquely-defined median. In most realistic situations, where voters' opinions follow a roughly-normal distribution or can be accurately summarized by one or two dimensions, Condorcet cycles are rare (though not unheard of).

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 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 can never create 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).

Rated social choice

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. 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). This opens up the possibility of finding another social choice procedure that satisfies independence of irrelevant alternatives. Arrow's theorem can thus be considered a special case of Harsanyi's utilitarian theorem and other utility representation theorems like the VNM theorem, which show rational behavior requires consistent cardinal utilities.

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).

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 behavioralist approach, 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 people who disagreed; Sen gives as an example that it would be impossible to know whether the Great Fire of Rome was good or bad, because despite killing thousands of Romans, it had the positive effect of letting Nero expand his palace.

Arrow originally agreed with this position, rejecting the meaningfulness of cardinal utilities, and thus interpreting his theorem as a kind of proof for nihilism or egoism. However, he later reversed this view, arguing cardinal methods can provide additional useful information, and that his theorem is not applicable to them. Similarly, Amartya Sen first claimed interpersonal comparability is necessary for IIA, but later came to argue in favor of cardinal methods for assessing social choice, arguing they would only require "rather limited levels of partial comparability" to hold in practice.

Other scholars have noted that interpersonal comparisons of utility are not unique to cardinal voting, but are instead a necessity of any non-dictatorial choice procedure, with cardinal voting rules making these comparisons explicit. David Pearce identified Arrow's original nihilist interpretation with a kind of circular reasoning, with Hildreth pointing out that "any procedure that extends the partial ordering of [Pareto efficiency] must involve interpersonal comparisons of utility." Similar observations have led to implicit utilitarian voting approaches, which attempt to make the assumptions of ranked procedures more explicit by modeling them as approximations of the utilitarian rule (or score voting).

In psychometrics, there is a general consensus that self-reported ratings (e.g. Likert scales) are meaningful and provide more information than pure rankings, as well as showing higher validity and reliability. Cardinal rating scales (e.g. Likert scales) provide more information than rankings alone. A review by Kaiser and Oswald found that ratings were more predictive of important decisions (such as international migration and divorce) than even standard socioeconomic predictors like income and demographics, writing that "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".

Nonstandard spoilers

Behavioral economists have shown individual irrationality involves violations of IIA (e.g. with decoy effects), suggesting human behavior can cause IIA failures even if the voting method itself does not. However, past research has typically found such effects to be fairly small, and such psychological spoilers can appear regardless of electoral system. Balinski and Laraki discuss techniques of ballot design derived from psychometrics that minimize these psychological effects, such as asking voters to give each candidate a verbal grade (e.g. "bad", "neutral", "good", "excellent") and issuing instructions to voters that refer to their ballots as judgments of individual candidates. Similar techniques are often discussed in the context of contingent valuation.

Esoteric solutions

In addition to the above practical resolutions, there exist unusual (less-than-practical) situations where Arrow's requirement of IIA 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). These results provide some justification for the common requirement of a two-thirds majority for constitutional amendments, which is sufficient to prevent cyclic preferences in most situations.

Infinite populations

Fishburn shows all of Arrow's conditions can be satisfied for uncountably infinite sets of voters given the axiom of choice; however, Kirman and Sondermann demonstrated 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, though the theorem does have important implications for strategic voting (being used as a lemma to prove Gibbard's theorem). The Arrovian framework of social welfare assumes all voter preferences are known and the only issue is in aggregating them.

Monotonicity (called positive association by Arrow) is not a condition of Arrow's theorem. This misconception is caused by a mistake by Arrow himself, who included the axiom in his original statement of the theorem but did not use it. Dropping the assumption does not allow for constructing a social welfare function that meets his other conditions.

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.