Arrow's Impossibility Theorem

Why This Matters

Suppose you want to aggregate the preferences of multiple agents into a single group ranking. This arises in voting, committee decisions, multi-criteria optimization, and, increasingly, in ML: RLHF aggregates preferences from multiple human raters, ensemble methods combine ranked predictions from multiple models, and social welfare optimization tries to balance competing objectives.

Arrow's theorem says that no aggregation method can simultaneously satisfy a small set of reasonable fairness axioms when there are three or more alternatives. Something must give. This result constrains the design space for any preference aggregation system and forces explicit choices about which axiom to sacrifice.

Setup: Social Welfare Functions

Definition

Preference Order

A preference order (or linear order) on a set of alternatives $A = \{a_1, \ldots, a_m\}$ is a complete, transitive, antisymmetric binary relation $\succ$ on $A$. We write $a \succ b$ to mean "alternative $a$ is strictly preferred to alternative $b$." Let $\mathcal{L}(A)$ denote the set of all linear orders on $A$.

Definition

Social Welfare Function

A social welfare function (SWF) is a function $F: \mathcal{L}(A)^n \to \mathcal{L}(A)$ that maps a profile of $n$ individual preference orders to a single social preference order. Given individual rankings $(\succ_1, \ldots, \succ_n)$, the SWF produces a group ranking $\succ_F$.

The question is: what properties should $F$ satisfy to be "fair"?

Arrow's Axioms

Arrow proposed four axioms. Each individually seems unobjectionable.

Definition

Unrestricted Domain (U)

Unrestricted domain: The SWF $F$ is defined for every possible profile of individual preferences. No preference ranking is excluded. The domain of $F$ is all of $\mathcal{L}(A)^n$.

Definition

Pareto Efficiency (P)

Pareto efficiency (unanimity): If all individuals prefer $a$ to $b$ (i.e., $a \succ_i b$ for all $i$), then the social ranking must also prefer $a$ to $b$ (i.e., $a \succ_F b$).

Definition

Independence of Irrelevant Alternatives (IIA)

Independence of irrelevant alternatives: The social ranking of any two alternatives $a$ and $b$ depends only on the individual rankings of $a$ versus $b$. Adding, removing, or reranking a third alternative $c$ does not affect whether $a \succ_F b$ or $b \succ_F a$.

Definition

Non-Dictatorship (ND)

Non-dictatorship: There is no individual $i$ such that for every profile, the social ranking always agrees with $i$'s ranking. Formally, there is no $i$ such that $a \succ_i b$ implies $a \succ_F b$ for all alternatives $a, b$ and all profiles.

The Impossibility Result

Theorem

Arrow's Impossibility Theorem

Statement

If $|A| \geq 3$ and $n \geq 2$, no social welfare function $F: \mathcal{L}(A)^n \to \mathcal{L}(A)$ simultaneously satisfies:

1. Unrestricted domain (U)
2. Pareto efficiency (P)
3. Independence of irrelevant alternatives (IIA)
4. Non-dictatorship (ND)

Any SWF satisfying U, P, and IIA must be a dictatorship.

Intuition

The axioms create a logical trap. IIA says the social ranking of $a$ vs. $b$ can only depend on how individuals rank $a$ vs. $b$. Pareto says if everyone agrees, so does society. Together these force a rigid structure on the SWF. With three or more alternatives, this rigidity propagates: if a group of voters is "decisive" on one pair of alternatives, they become decisive on all pairs. Iterating this argument shrinks the decisive group to a single individual: a dictator.

Proof Sketch

Step 1: Define decisive sets. A set of voters $S$ is decisive for $a$ over $b$ if whenever all voters in $S$ prefer $a$ to $b$ (regardless of how voters outside $S$ rank $a$ and $b$), the social ranking has $a \succ_F b$.

Step 2: Field expansion lemma. If $S$ is decisive for $a$ over $b$ (one specific pair), then $S$ is decisive for every pair of alternatives. The proof uses IIA and the existence of a third alternative $c$: construct a profile where voters in $S$ rank $a \succ c \succ b$ and voters outside $S$ rank $c$ above both $a$ and $b$. Pareto forces $a \succ_F c$, decisiveness gives $a \succ_F b$, and IIA then shows $S$ is decisive for $a$ over $c$ and $c$ over $b$. Repeat for all pairs.

Step 3: Group contraction. If a decisive set $S$ has more than one voter, split it into $S_1$ and $S_2$. Construct a profile that forces either $S_1$ or $S_2$ to be decisive (using the third alternative to create a cycle that only one subset can resolve). This strictly shrinks the smallest decisive set.

Step 4: Conclusion. By Pareto, the full set of voters $N$ is decisive. By repeated contraction, the smallest decisive set has exactly one voter. That voter is a dictator.

Why It Matters

The theorem is not about a specific voting system being bad. It says every possible aggregation rule must violate at least one axiom. This is a structural impossibility, not a design failure. Any system for aggregating preferences must make a conscious choice about which axiom to sacrifice. In practice:

• Majority rule drops transitivity (Condorcet cycles).
• Borda count drops IIA (adding a new candidate can change the winner).
• Dictatorships satisfy everything except ND.

Failure Mode

The theorem requires $|A| \geq 3$. With only two alternatives, majority rule satisfies all four axioms (May's theorem). The theorem also requires strict linear orders; with ties (weak orders), a version still holds but the statement becomes more technical. Restricting the domain (e.g., to single-peaked preferences) can avoid the impossibility; this is the Black-Median Voter theorem.

Escape Routes

Arrow's theorem is not the end of the story. Several relaxations restore possibility:

Restrict the domain. If preferences are single-peaked (there exists a linear ordering of alternatives such that each voter's preference decreases monotonically on each side of their peak), then majority rule is transitive and non-dictatorial. Black's Median Voter Theorem guarantees a Condorcet winner. Many political preferences are approximately single-peaked, which is why majority rule works tolerably well in practice.

Use cardinal information. Arrow's theorem assumes ordinal preferences (rankings). If voters can express cardinal utilities or preference intensities, aggregation becomes easier. Utilitarianism (sum of utilities) satisfies all Arrow axioms once you allow cardinal input. The cost is interpersonal utility comparisons, which raise their own philosophical problems.

Randomize. Random dictator (pick a voter uniformly at random and use their ranking) satisfies ex-ante symmetry and Pareto. It violates ND only in the deterministic sense; no voter is always the dictator.

Gibbard-Satterthwaite Theorem

Theorem

Gibbard-Satterthwaite Theorem

Statement

If $|A| \geq 3$, every social choice function (mapping preference profiles to a single winning alternative) that is surjective (every alternative can win) and strategy-proof (no voter can benefit from misreporting their preferences) must be a dictatorship.

Intuition

Arrow says you cannot aggregate preferences fairly. Gibbard-Satterthwaite says you cannot even ask people to report their preferences honestly, because any non-dictatorial system creates incentives to lie. This is a deeper problem: not only is the aggregation impossible, but the inputs are unreliable.

Proof Sketch

The proof connects to Arrow via the following observation. Given a strategy-proof social choice function $g$, define a SWF by: $a \succ_F b$ if $g$ selects $a$ when $a$ and $b$ are the only "viable" candidates (constructed by moving all other candidates to the bottom of every ranking). Show this SWF satisfies IIA and Pareto, so by Arrow it must be a dictatorship.

Why It Matters

In mechanism design, Gibbard-Satterthwaite motivates the study of restricted domains (e.g., single-peaked preferences) and payment-based mechanisms (e.g., VCG auctions) where truthfulness can be achieved via monetary transfers. In RLHF, if human raters know how their preferences will be aggregated, they may strategically misreport, and this theorem tells you the problem is structural.

Failure Mode

Strategy-proofness is a strong requirement: no voter can ever gain by lying, for any preference profile. Weaker notions (e.g., approximate strategy-proofness, strategy-proofness for "large" elections) can be achievable. The theorem also does not apply when the outcome is a probability distribution over alternatives (randomized mechanisms can be strategy-proof).

Connections to ML

RLHF preference aggregation. In RLHF, multiple human raters rank model outputs. The standard approach (Bradley-Terry model) implicitly uses cardinal information (preference strength). Arrow's theorem applies to ordinal aggregation: if you only have rankings from each rater, you cannot aggregate them into a single ranking that satisfies all fairness axioms. In practice, RLHF systems work because they either assume cardinal utilities or accept violations of IIA.

Ensemble methods. Bagging, boosting, and stacking combine predictions from multiple models. When each model produces a ranking (e.g., of candidate labels), the ensemble must aggregate these rankings. Borda count and plurality voting are common. Arrow's theorem says no rank-based aggregation is universally fair. In practice, the Condorcet jury theorem provides some comfort: if each model is better than random and errors are independent, majority vote converges to the truth.

Multi-objective optimization. When optimizing multiple conflicting objectives (accuracy vs. fairness, precision vs. recall), Arrow's theorem applies to the Pareto frontier. No single aggregation of objectives into a scalar can satisfy all natural desiderata. This is why practitioners resort to explicit scalarization (weighted sum), which sacrifices IIA.

Common Confusions

Watch Out

Arrow's theorem does not say democracy is impossible

The theorem says no rank-based aggregation satisfies all four axioms. It does not say that democratic decision-making is doomed. Majority rule violates transitivity but works well for two-candidate races. Approval voting and range voting use cardinal information and sidestep the theorem entirely. The practical lesson is about understanding tradeoffs, not about nihilism.

Watch Out

IIA is the most controversial axiom, not the most obvious

IIA sounds reasonable: the social ranking of $a$ vs. $b$ should not depend on $c$. But in practice, the presence of $c$ reveals information about preference intensity. If a voter ranks $a \succ c \succ b$ with $c$ close to $a$, that suggests $a$ and $c$ are similar and the voter only slightly prefers $a$. IIA forbids using this information. Borda count violates IIA precisely because it uses rank-position information.

Watch Out

Two alternatives are easy, three are hard

With $|A| = 2$, majority rule satisfies all axioms (May's theorem, 1952). The impossibility only kicks in at $|A| \geq 3$ because three alternatives allow Condorcet cycles ($a \succ b \succ c \succ a$), which make transitivity of the social ranking impossible under majority rule.

Exercises

ExerciseCore

Problem

Construct a Condorcet cycle. Three voters rank three alternatives $\{a, b, c\}$ as follows: Voter 1: $a \succ b \succ c$. Voter 2: $b \succ c \succ a$. Voter 3: $c \succ a \succ b$. Under pairwise majority rule, determine the social ranking of each pair. Show that the resulting social preference is cyclic.

Hint

Reveal Solution

ExerciseCore

Problem

Show that the Borda count violates IIA. Consider 3 voters and 3 alternatives $\{a, b, c\}$ with rankings: Voter 1: $a \succ b \succ c$. Voter 2: $a \succ b \succ c$. Voter 3: $b \succ c \succ a$. Compute Borda scores (2 points for first, 1 for second, 0 for third). Now add a fourth alternative $d$ ranked last by all voters and recompute. Does the social ranking of $a$ vs. $b$ change?

Hint

Reveal Solution

ExerciseAdvanced

Problem

Prove that with single-peaked preferences, majority rule produces a transitive social order. Consider $n$ voters (odd) with single-peaked preferences on a linearly ordered set of alternatives $a_1 < a_2 < \cdots < a_m$. Show that the median peak voter's preferred alternative is a Condorcet winner (beats every other alternative in pairwise majority).

Hint

Reveal Solution

ExerciseResearch

Problem

In an RLHF setting, $k$ human raters each produce a ranking of $m$ model outputs. The system must aggregate these into a single ranking to determine the reward model training signal. By Arrow's theorem, any ordinal aggregation must sacrifice at least one axiom. For each of the four axioms, describe what it would mean concretely to sacrifice that axiom in the RLHF context. Which sacrifice is most palatable in practice, and why?

Hint

Reveal Solution

References

Original:

• Arrow, Social Choice and Individual Values (2nd ed., 1963), Chapters 3-5

Textbook treatments:

• Mas-Colell, Whinston, and Green, Microeconomic Theory (1995), Chapter 21
• Austen-Smith and Banks, Positive Political Theory I (1999), Chapters 2-3

Gibbard-Satterthwaite:

• Gibbard, "Manipulation of Voting Schemes: A General Result," Econometrica 41(4), 1973
• Satterthwaite, "Strategy-proofness and Arrow's conditions," J. Economic Theory 10(2), 1975

Connections to ML:

• Conitzer, "Making Decisions Based on the Preferences of Multiple Agents," CACM 53(3), 2010

Next Topics

Directions from Arrow's theorem:

• Mechanism design: designing games and institutions that achieve desirable outcomes despite strategic behavior
• Game theory: the broader framework of strategic interaction where Arrow's impossibility lives