7.1 Arrow's Impossibility Theorem
Introduction
We argued in the first part of this course that the choices an individual makes are based on their preferences, which could sometimes be represented by a utility function. But societies make choices too: do “societies” (or more practically, governments) have preferences and utility functions? If so, what should those preferences be?
Democratic theorists would argue that the government should do its utmost to support the welfare of the populace. Often, though, individuals disagree: some want higher taxes and more services, others want a more libertarian approach.
So how should we as a society make choices? Using our knowledge of individual choice theory (i.e. utility maximization), can we build up a theory of social choice which combines the individual ranked preferences of many voters into one collective social ranking?
Stanford’s own Kenneth Arrow showed that when there are at least three candidates one can vote for, no voting system can satisfy a few extremely reasonable fairness conditions simultaneously. This fundamental result—known as Arrow’s Impossibility Theorem—forms the basis of modern social choice theory. Incidentally, watching Eric Maskin give a lecture on this topic is what motivated me to study econ professionally.
The Social Welfare Function
Let $A$ be a finite set of alternatives (like candidates) with $\lvert A \rvert \ge 3$. Each voter $i \in \lbrace 1,\dots,n \rbrace$ has a preference relation $\succsim_i$ over $A$, assumed to be:
- complete: for all $x,y \in A$, either $x \succsim_i y$ or $y \succsim_i x$, or both ($x \sim_i y$)
- transitive: $x \succsim_i y$ and $y \succsim_i z$ implies $x \succsim_i z$.
Define the set of all such preference relations as $\Pi(A)$. A preference profile is a vector \(R = (\succsim_1,\dots,\succsim_n) \in \Pi(A)^n.\) If an element of $\Pi(A)$ is a person’s ballot, then a preference profile is a stack of ballots from all the voters. To speak coherently about elections, we want a way to take all those ballots and actually make a social choice, which would be the most prefered option under a social preference relation. We can model doing so with a function from the pile of ballots to a single ranking over candidates. That function, in essence, is what it means to run an abstract election.
Definition (Social Welfare Function): A social welfare function (SWF) is a map $F : \Pi(A)^n \to \Pi(A)$, which assigns to each profile of individual preference orderings a single social preference relation $\succsim^\star = F(R)$.
Understanding Arrow’s Theorem, and thereby understanding elections, comes down to understanding what properties $F$ can have.
Arrow’s Four Key Assumptions
Below we rewrite Arrow’s axioms about $F$ in formal mathematical notation alongside informal explanations.
Definition (Unrestricted Domain): A social welfare function $F$ satisfies Unrestricted Domain if $F$ is defined on all $R \in \Pi(A)^n$.
The SWF must accept every logically possible preference profile of complete and transitive individual rankings.
Informal: The voting system must handle any imaginable collection of voter preferences. It cannot refuse to give an answer just because the preferences look odd.
Definition (Pareto Efficiency): A social welfare function $F$ satisfies Pareto Efficiency if, for any candidates $x,y \in A$ and any profile $R = (\succsim_1,\dots,\succsim_n)$, having $x \succ_i y$ for all $i$ implies $x \succsim^\star y$, where $\succsim^\star = F(R)$.
Informal: If every voter thinks $x$ is better than $y$, then society must also rank $x$ above $y$. No fair rule should overturn unanimous agreement.
Definition (Non-Dictatorship): A social welfare function $F$ satisfies Non-Dictatorship if there does not exist a voter $i$ such that, for all profiles $R$ and all $x,y \in A$, $x \succ_i y$ implies $x \succsim^\star y$; that is, no single voter's preferences always determine society's ranking. We also require that all alternatives (candidates) are treated equally, so any permutation of alternatives results in the same maximizer (chosen candidate); this is sometimes called neutrality.
Informal: No “king voter.” A fair system cannot have one individual who always gets their way regardless of how anyone else feels.
Definition (Independence of Irrelevant Alternatives): A social welfare function $F$ satisfies Independence of Irrelevant Alternatives (IIA) if, whenever $A = \lbrace a_1, a_2, \dots, a_n \rbrace$ has $a_i \succsim^\star a_j$, then for $A' = \lbrace a_1, a_2, \dots, a_n, b \rbrace$ we still have $a_i \succsim^\star a_j$.
Informal: Changing opinions about a third option $z$ should not affect society’s ranking between $x$ and $y$. No “spoiler” candidates.
IIA is sometimes illustrated with a short joke by philosopher Sidney Morgenbesser. He’s 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.”
The Theorem
Arrow’s Impossibility Theorem. If $\lvert A \rvert \ge 3$, then no social welfare function $F : \Pi(A)^n \to \Pi(A)$ can simultaneously satisfy:
- Unrestricted Domain,
- Pareto Efficiency,
- Non-Dictatorship,
- Independence of Irrelevant Alternatives.
In plain language: There is no perfect ranked voting system. Any system must violate at least one of these super reasonable fairness criteria.
An Intuitive Argument: The Condorcet Cycle
Here are some formal proofs of the Impossibility Theorem using techniques like contradiction that we talked about in last week’s lecture. These are a bit too hard to cover in this class, but if any of you are interested I’d highly recommend you check these proofs out. Professor Makler also found this fun video explanation.
That said, we should still build some intuition for why the theorem holds. To see why these axioms clash, consider three candidates $A$, $B$, and $C$ and three voters with the following rankings:
| Voter | 1st | 2nd | 3rd |
|---|---|---|---|
| 1 | $A$ | $B$ | $C$ |
| 2 | $B$ | $C$ | $A$ |
| 3 | $C$ | $A$ | $B$ |
Suppose we want to do something like a “majority rules” voting system. Let’s look at the pairwise majority comparisons:
- $A$ vs. $B$: voters 1 and 3 prefer $A$ $\Rightarrow$ $A$ wins 2–1.
- $B$ vs. $C$: voters 1 and 2 prefer $B$ $\Rightarrow$ $B$ wins 2–1.
- $C$ vs. $A$: voters 2 and 3 prefer $C$ $\Rightarrow$ $C$ wins 2–1.
This produces the cycle: \(A \succ B, \qquad B \succ C, \qquad C \succ A.\) Even though each individual has transitive preferences, the majority relation is intransitive. This is the classic Condorcet Paradox. Arrow’s result shows that any SWF capable of handling all possible profiles must sometimes exhibit such contradictions or violate one of the fairness axioms.
Should we give up on democracy?
No.
Churchill famously said “Democracy is the worst system of government…except for the others.” Even if a voting system will fail to live up to some pretty basic criteria, voting will still be better for most people in all likelihood than just ignoring their preferences entirely.
If we’re willing to relax a few of the assumptions above, then we can get social choice functions (i.e. voting rules) which still look pretty good. Here are some examples:
- With just two candidates, we can get what we want from a voting system by doing most-votes-wins. This result is called May’s Theorem. A related result, the Median Voter Theorem, more precisely tells us that the winner of such an election is whoever the median voter prefers.
- We can relax the unrestricted domain assumption. For instance, if we think of politicians as just being a point on the liberal to conservative spectrum, and voters pick whoever is closest to their favorite point on that spectrum, then a social choice rule called Condorcet Voting gives us everything else we want.
- If we let voters give “points” to their favorite candidates instead of just putting them in order, a social choice rule called the Borda Count can work well.
The guys behind the last two options absolutely hated each other by the way.
Proving these results requires some serious measure theory, but it’s delightful and very pretty. If that sounds interesting, check out this paper.
Conclusion
Arrow’s Impossibility Theorem is an unfortunate fact, teaching us that no voting system can perfectly translate individual preferences into a collective ranking while satisfying some fairly basic fairness axioms. Real-world systems must therefore trade off among desirable properties. Rather than making perfect democracy impossible, Arrow’s Theorem highlights the fundamental tensions inherent in collective decision making.