Arrow's impossibility theorem

Arrow's original statement of the theorem included

A commonly-considered axiom of rational choice is independence of irrelevant alternatives (IIA), which says that when deciding between A and B, one's opinion about a third option C should not affect their decision.^[2]

• Independence of irrelevant alternatives (IIA) – the social preference between candidate A and candidate B should only depend on the individual preferences between A and B.
  • In other words, the social preference should not change from ${\displaystyle A\succ B}$ to ${\displaystyle B\succ A}$ if voters change their preference about whether ${\displaystyle A\succ C}$.^[3]
  • This is equivalent to the claim about independence of spoiler candidates when using the standard construction of a placement function.^[28]

IIA is sometimes illustrated with a short joke by philosopher Sidney Morgenbesser:^[30]

Morgenbesser, ordering dessert, is told by a waitress that he can choose between blueberry or apple pie. He orders apple. Soon the waitress comes back and explains cherry pie is also an option. Morgenbesser replies "In that case, I'll have blueberry."

Arrow's theorem shows that if a society wishes to make decisions while always avoiding such self-contradictions, it cannot use ranked information alone.^[30]

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.^[31] 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

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

${\displaystyle R}$

${\displaystyle A\times A}$

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 alternative ${\displaystyle \mathbf {b} }$. This situation is often denoted ${\displaystyle \mathbf {a} \succ \mathbf {b} }$ or ${\displaystyle \mathbf {a} R\mathbf {b} }$. Denote the set of all preferences on ${\displaystyle A}$ by ${\displaystyle \Pi (A)}$. Let ${\displaystyle N}$ be a positive integer. An ordinal (ranked) social welfare function is a function^[2]

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

which aggregates voters' preferences into a single preference on ${\displaystyle A}$. An ${\displaystyle N}$-tuple ${\displaystyle (R_{1},\ldots ,R_{N})\in \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:^[32]

Pareto efficiency

If alternative ${\displaystyle \mathbf {a} }$ is preferred to ${\displaystyle \mathbf {b} }$ for all orderings ${\displaystyle R_{1},\ldots ,R_{N}}$, then ${\displaystyle \mathbf {a} }$ is preferred to ${\displaystyle \mathbf {b} }$ by ${\displaystyle F(R_{1},R_{2},\ldots ,R_{N})}$.^[2]

Non-dictatorship

There is no individual ${\displaystyle i}$ whose preferences always prevail. That is, there is no ${\displaystyle i\in \{1,\ldots ,N\}}$ such that for all ${\displaystyle (R_{1},\ldots ,R_{N})\in \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},\ldots ,R_{N})}$.^[2]

Independence of irrelevant alternatives

For two preference profiles ${\displaystyle (R_{1},\ldots ,R_{N})}$ and ${\displaystyle (S_{1},\ldots ,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},\ldots ,R_{N})}$ as in ${\displaystyle F(S_{1},\ldots ,S_{N})}$.^[2]

Proof by showing there is only one pivotal voter

Proofs using the concept of the pivotal voter originated from Salvador Barberá in 1980. Economic Theory.[32][36] Setup Assume there are n voters. We assign all of these voters an arbitrary ID number, ranging from 1 through n, which we can use to keep track of each voter's identity as we consider what happens when they change their votes. Without loss of generality, we can say there are three candidates who we call A, B, and C. (Because of IIA, including more than 3 candidates does not affect the proof.) We will prove that any social choice rule respecting unanimity and independence of irrelevant alternatives (IIA) is a dictatorship. The proof is in three parts: We identify a pivotal voter for each individual contest (A vs. B, B vs. C, and A vs. C). Their ballot swings the societal outcome. We prove this voter is a partial dictator. In other words, they get to decide whether A or B is ranked higher in the outcome. We prove this voter is the same person, hence this voter is a dictator. Part one: There is a pivotal voter for A vs. B Consider the situation where everyone prefers A to B, and everyone also prefers C to B. By unanimity, society must also prefer both A and C to B. Call this situation profile[0, x]. 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 as the profile number increases, there must be some profile, number k, for which B first moves above A in the societal rank. We call the voter k 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 the pivotal voter for simplicity. We will show that the 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: Every voter in segment one ranks B above C and C above A. Pivotal voter ranks A above B and B above C. Every voter in segment two ranks A above B and B above C. Then by the argument in part one (and the last observation in that part), 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 (even all!) 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 (identified by applying parts one and two to the other pairs of candidates). First, the pivotal voter for B over C must appear earlier (or at the same position) 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 (for any two candidates X and Y), then we have shown kB/C ≤ kB/A ≤ kC/B. Now repeating the entire argument above with B and C switched, we also have kC/B ≤ kB/C. Therefore, we have kB/C = kB/A = kC/B and the same argument for other pairs shows that all the pivotal voters (and hence all the dictators) occur at the same position in the list of voters. This voter is the dictator for the whole election.

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

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

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."^[37][38]

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.^[30]

The first set of methods studied by economists are the

Unfortunately, as Condorcet proved, this rule can be intransitive on some preference profiles.[39] 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.^[31]

Unlike pluralitarian rules such as

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.^[15][16]

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.^[15][16][12]

The rule does not fully generalize from the political spectrum to the political compass, a result related to the

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.[12] 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.^[12]

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.^[44]

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

As shown above, the proof of Arrow's theorem relies crucially on the assumption of

Arrow's framework assumed individual and social preferences are orderings or rankings, i.e. statements about which outcomes are better or worse than others.^[50] Taking inspiration from the behavioralist approach, some philosophers and economists rejected the idea of comparing internal human experiences of well-being.^[51][30] 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.^[52]

Arrow originally agreed with these position, rejecting the meaningfulness of cardinal utilities,^[3][51] thus interpreting his theorem as a kind of proof for nihilism or egoism.^[30][50] However, he later stated that cardinal methods can provide additional useful information, and that his theorem is not applicable to them.^[37][53] 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.^[54]

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,^[55] with Hildreth pointing out that "any procedure that extends the partial ordering of [Pareto efficiency] must involve interpersonal comparisons of utility."^[56] 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).^[57]

In

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

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 (

Fishburn shows all of Arrow's conditions can be satisfied for uncountably infinite sets of voters given the axiom of choice;^[67] 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".^[68]

Arrow's theorem is not related to strategic voting, which does not appear in his framework,^[3][1] though the theorem does have important implications for strategic voting (being used as a lemma to prove Gibbard's theorem^[26]). The Arrovian framework of social welfare assumes all voter preferences are known and the only issue is in aggregating them.^[1]

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.^[1][69]

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