THREE BRIEF PROOFS OF ARROW’S IMPOSSIBILITY THEOREM

John Geanakoplos*

Revised: August 1996

ABSTRACT

Arrow’s original proof of his impossibility theorem proceeded in two steps: showing the existence of a decisive voter, and then showing that a decisive voter is a dictator. Barbera replaced the decisive voter with the weaker notion of a pivotal voter, thereby shortening the first step, but complicating the second step. I give three brief proofs, all of which turn on replacing the decisive/pivotal voter with an extremely pivotal voter (a voter who by unilaterally changing his vote can move some alternative from the bottom of the social ranking to the top), thereby simplifying both steps in Arrow’s proof. My first proof uses almost no notation, while the second uses May’s notation and is extremely brief. The third proof is perhaps the most interesting, because along the way to proving the existence of an extremely pivotal voter, it shows that the Arrow axioms guarantee issue neutrality, that is, that every choice must be made by exactly the same process.

*I wish to thank Ken Arrow, Don Brown, Ben Polak, Herb Scarf, Chris Shannon, Lin Zhou, and especially Eric Maskin for very helpful comments and advice. I was motivated to think of reproving Arrow’s theorem when I undertook to teach it to George Zettler, a mathematician friend. After I presented this paper at MIT, a graduate student there named Luis Ubeda–Rives told me he had worked out the same neutrality argument as I give in my third proof while he was in Spain nine years ago. He said he was anxious to publish on his own and not jointly, so I encourage the reader to consult his forthcoming working paper.

1 Informal Statement and Proof of Arrow’s Theorem

Let A = {A, B, ..., C} be a finite set of at least three alternatives. A transitive preference over A is a ranking of the alternatives in A from top to bottom, with ties allowed. We consider a society with N individuals, each of whom has a (potentially different) transitive preference. A constitution is a function which associates with every N-tuple (or profile) of transitive preferences a transitive preference called the social preference.

A constitution respects unanimity if society puts alternative α above β whenever every individual puts α above β. The constitution respects independence of irrelevant alternatives if the social relative ranking (higher, lower, or indifferent) of two alternatives α and β depends only on their relative ranking by every individual. The constitution is a dictatorship by individual n if society strictly prefers α to β whenever n strictly prefers α to β.

ARROW’S THEOREM: Any constitution that respects transitivity, independence of irrelevant alternatives, and unanimity is a dictatorship.

FIRST PROOF: Let alternative B be chosen arbitrarily. We argue first that at any profile in which every voter puts alternative B at the top or bottom of his ranking of alternatives, society must as well (even if half the voters put B at the top and half put B at the bottom). Suppose to the contrary that for such a profile and for distinct A, B, C, the social preference put A ≥ B and B ≥ C. By independence of irrelevant alternatives, this would continue to hold even if every individual moved C above A, because that could be arranged without disturbing any AB or CB votes (since B occupies an extreme position in each individual’s ranking, as can be seen from the diagram). By transitivity the social ranking would then put A ≥ C, but by unanimity it would also put C > A, a contradiction.

We argue that there is a voter n^{∗} = n(B) who is extremely pivotal in the sense that by changing his vote at some profile he can move B from the bottom of the social ranking to the top. To see this, let each voter put B at the bottom of his (otherwise arbitrary) ranking of alternatives. By unanimity, society must as well. Now let the individuals from voter 1 to N successively move B from the bottom of their rankings to the top, leaving the other relative rankings in place. Let n^{∗} be the first voter whose change causes the social ranking of B to change. (By unanimity, a change must occur at the latest when n^{∗} = N.) Denoted by profile I the list of all voter rankings just before n^{∗} moves B, and denote by profile II the list of all voter rankings just after n^{∗} moves B to the top. Since in profile II B has moved off the bottom of the social ranking, we deduce from our first argument that the social preference corresponding to profile II must put B at the top.

We argue third that n^{∗} = n(B) is a dictator over any pair AC not involving B. To see this, choose one element, say A, from the pair AC. Construct profile III from profile II by letting n^{∗} move A above B, so that A >_{n^{∗}}> B >_{n^{∗}} C, and by letting all the agents n ≠ n^{∗} arbitrarily rearrange their relative rankings of A and C while leaving B in its extreme position. By independence of irrelevant alternatives, the social preferences corresponding to profile III would necessarily put A > B (since all individual AB votes are as in profile I where n^{∗} put B at the bottom), and B > C (since all individual BC votes are as in profile II where n^{∗} put B at the top). By transitivity, society must put A > C. By independence of irrelevant alternatives, the social preference over AC must agree with n^{∗} whenever A >_{n^{∗}} C.

We conclude by arguing that n^{∗} is also a dictator over every pair AB. Given any alternative A different from B, we can find a third distinct alternative C to put at the bottom in the above construction. From the above argument, there must be a voter n(C) who is an αβ dictator for any pair αβ not involving C, such as AB. But agent n^{∗} can affect society’s AB ranking, namely at profiles I and II, hence this AB dictator n(C) must actually be n^{∗}. □

2 Arrow’s Theorem Formally Stated

Let A = {A, B, C} be a set of three alternatives.^{1} A transitive preference π is a binary relation that specifies for each pair of alternatives αβ ∈ A × A whether the first is preferred to the second (which we write as π_{αβ} = 1) or the second is preferred to the first (which we write as π_{αβ} = 0) or the two are indifferent (which we write as π_{αβ} = \frac{1}{2}), and that has no cycles. Since π_{αβ} = 1 − π_{βα}, a preference π can be identified with a triple (π_{AB}, π_{BC}, π_{CA}) ∈ \{0, \frac{1}{2}, 1\} × \{0, \frac{1}{2}, 1\} × \{0, \frac{1}{2}, 1\}. For

example, (110) means AπB, BπC, and AπC, and corresponds to the ranking (\begin{matrix}A \\ B \\ C \end{matrix}).

The set of transitive preferences is Π = {abc ∈ {0, 1}^{3} : abc ≠ 000 and abc ≠ 111} ∪ \{abc ∈ \{0, \frac{1}{2}, 1\}^{3} : a + b + c = \frac{3}{2}\} = \{(abc) ∈ \{0, \frac{1}{2}, 1\}^{3} : abc = \frac{1}{2} \frac{1}{2} \frac{1}{2} or \{0, 1\} ⊂ {a, b, c}}.

1For the purposes of Arrow’s Impossibility Theorem, there is no loss of generality in restricting attention to three alternatives. If every subset of three alternatives is determined by a dictator, then because such sets overlap, Arrow’s axiom of independence of irrelevant alternatives guarantees that one dictator would determine all social preferences.

The set of agents n ∈ N is a finite set. We call Π^{N} the set of legal preferences. A constitution is a function (f_{1}, f_{2}, f_{3}) = f : Π^{N} → Π, which we denote

f(π) = f(π(1) ; ⋮ ; π(n) ; ⋮ ; π(N))= f[π_{AB}(1) π_{BC}(1) π_{CA}(1) ; ⋮ ; π_{AB}(n) π_{BC}(n) π_{CA}(n) ; ⋮ ; π_{AB}(N) π_{BC}(N) π_{CA}(N)]= f[π_{1}(1) π_{2}(1) π_{3}(1) ; ⋮ ; π_{1}(n) π_{2}(n) π_{3}(n) ; ⋮ ; π_{1}(N) π_{2}(N) π_{3}(N)]= f[π_{1} π_{2} π_{3}].

The rows of the matrix π represent individual preferences, and the columns represent all individual preferences over one pair of alternatives.

The constitution f satisfies independence of irrelevant alternatives (IIA) if for each i ∈ {AB, BC, CA}, f_{i} depends only on the ith column of π: f_{i}(π) = f_{i}(ω) whenever π_{i}(n) = ω_{i}(n) for all n ∈ N. We will often abuse notation and write f_{i}(π_{i}) or f_{i}(μ) where π_{i} = μ ∈ \{0, \frac{1}{2}, 1\}^{N} is just the ith column of π.

Let 1 denote the vector of all 1’s, and 0 denote the vector of all 0’s. (The context will distinguish between 1 as vector and scalar.) Unanimity (U) requires f_{i}(1) = 1 and f_{i}(0) = 0 for i = 1, 2, 3.

If μ ∈ \{0, \frac{1}{2}, 1\}^{N}, then μ(−n) ∈ \{0, \frac{1}{2}, 1\}^{N−1} denotes the vector obtained by deleting μ(n) from μ, and \binom{a}{μ(−n)} ∈ \{0, \frac{1}{2}, 1\}^{N} denotes the vector obtained from μ by changing μ(n) to a. We say that a constitution f makes an agent n ∈ N pivotal in coordinate i at a particular μ(−n) ∈ \{0, \frac{1}{2}, 1\}^{N−1} if f_{i}\binom{1}{μ(−n)} = 1 and

f_{i}\binom{0}{μ(−n)} = 0. We say that f makes n a dictator iff f makes n pivotal in every coordinate i ∈ \{1, 2, 3\} at every μ(−n) ∈ \{0, \frac{1}{2}, 1\}^{N−1}.

ARROW’S IMPOSSIBILITY THEOREM: Let f : Π^{N} → Π be a constitution satisfying unanimity and independence of irrelevant alternatives, where Π is the set of all transitive preferences on a set of three or more alternatives. Then f makes some agent n ∈ N a dictator.

3 Second Proof ^{2}

LEMMA 1: Let π ∈ Π^{N} and suppose that f makes an agent n ∈ N pivotal in i at π_{i}(−n) and pivotal in j ≠ i at π_{j}(−n). Then f makes n pivotal in the third coordinate k ∉ {i, j} at π_{k}(−n).

PROOF OF LEMMA 1: WLOG, i = 1, j = 2. Since f \binom{110}{π(−n)} = (11a) ∈ Π,

a = 0. Similarly, \binom{001}{π(−n)} = (00b) ∈ Π, so b = 1. By IIA, n is also pivotal in the third coordinate. □

2Rather than repeating the first proof with the notation of the last section, we give a variation on the theme. In particular, we use the Condorcet triple to show the existence of an extremely pivotal voter.

LEMMA 2: Let π ∈ Π^{N} and suppose f makes n pivotal at π_{i}(−n) for all i = 1, 2, 3. Then n is a dictator.

PROOF OF LEMMA 2: Change one entry of one column of π(−n) legally. By IIA, n is still pivotal in the other two coordinates, hence by Lemma 1, in all three. By changing one entry at a time, one can move from π(−n) to any other ω(−n) ∈ Π^{N−1} without leaving Π^{N−1}. □

LEMMA 3: There exists n ∈ N and π ∈ Π^{N} such that f makes n pivotal in coordinate i at π_{i}(−n) for i = 1 and 2.

PROOF OF LEMMA 3: Let Δ ≡ {π ∈ Π^{N} : f(π) = 110, and for all n ∈ N, π(n) = 110 or 101 or 011\}.^{3} Note that by unanimity \left[{110 \atop 110}\right] ∈ Δ. Let π be any element of Δ with the fewest number of agents n with π(n) = 110. Note that there must be at least one such agent n, for if not, then by unanimity and IIA, f_{3}(π) = 1, contradicting π ∈ Δ.

Observe that by construction and IIA, f \left[{110 \atop π(−n)}\right] = 110, while f \left[{011 \atop π(−n)}\right] = a1c ≠

110 and f \left[{101 \atop π(−n)}\right] = 1bc ≠ 110. We must show a = b = 0. If c = 0, then a ≠ 1 and

b ≠ 1. But then by IIA, f \left[{001 \atop π(−n)}\right] = abc ≤ (\frac{1}{2} \frac{1}{2} 0), contradicting transitivity. So c ≥ \frac{1}{2}. Then a1c ∈ Π implies a = 0 and 1bc ∈ Π implies b = 0. □

4 Third Proof

For any vector α ∈ \{0, \frac{1}{2}, 1\}^{K} for K = N or N − 1 or 3 or 1, we denote by ᾱ the vector obtained by changing each coordinate α_{i} into ᾱ_{i} = 1 − α_{i}. Thus ¯1 = 0 and ¯0 = 1.

LEMMA 1 (Strict individual preferences give strict and neutral social preferences): There is a function g : {0, 1}^{N} → {0, 1} such that for all i ∈ {1, 2, 3} and all μ ∈ {0, 1}^{N}, f_{i}(μ) = g(μ) = ḡ(μ̄). In other words, f_{AB}(μ) = f_{BC}(μ) = f_{CA}(μ) = f_{BA}(μ) ≡ f̄_{AB}(μ̄) = f_{CB}(μ) ≡ f̄_{BC}(μ̄) = f_{AC}(μ) ≡ f̄_{CA}(μ̄) ≠ \frac{1}{2}.

PROOF of LEMMA 1: Suppose f_{1}(μ) ≥ \frac{1}{2} and f_{2}(μ̄) ≥ \frac{1}{2} for some μ ∈ \{0, 1\}^{N}. Then [μμ̄1] is legal, since every row contains a 0 and 1, and f[μμ̄1] ≥ (\frac{1}{2} \frac{1}{2} 1), contradicting transitivity. We conclude that ∀μ ∈ \{0, 1\}^{N}, f_{1} = f̄_{2}(μ̄) ≠ \frac{1}{2}. Similarly, f_{3}(μ) = f̄_{2}(μ̄) ∀μ ∈ {0, 1}^{N}. Since the subscripts were arbitrary, the lemma is proved. □ LEMMA 2: Some agent is symmetrically doubly pivotal: there is n ∈ N and μ(−n) ∈ \{0, 1\}^{N−1} such that g\binom{1}{μ(−n)} = g\binom{1}{μ̄(−n)} = 1 and g\binom{0}{μ(−n)} = g\binom{0}{μ̄(−n)} = 0.

3The reader should recognize 110, 101, 011 as the Condorcet triple. Note that each preference in the Condorcet triple can be obtained from the next preference by moving the bottom alternative to the top.

PROOF OF LEMMA 2: By unanimity, g(1) = 1 and g(0) = 0. Change the coordinates one-by-one from 1 to 0; for some n, Lemma 1 assures us that g must switch all the way to 0. Take μ(−n) = ( \underbrace{0, ..., 0}_{1 to n−1}), \underbrace{0, ..., 0}_{n+1 to N})′. Then g\binom{1}{μ(−n)} = 1

and g\binom{0}{μ(−n)} = 0. From the neutrality part of Lemma 1, g\binom{0}{μ̄(−n)} = \overline{1} = 0 and

g\binom{1}{μ̄(−n)} = \overline{0} = 1. □

PROOF OF THEOREM: Take any η(−n) ∈ \{0, \frac{1}{2}, 1\}^{N−1}; then π ≡ [{1 \atop μ(−n)} {1 \atop μ̄(−n)} {0 \atop η(−n)}] is legal, since μ(−n) was constructed to lie in \{0, 1\}^{N−1}, so

that every row of π contains a 0 and a 1. By Lemma 2, f(π) = 11f_{3}\binom{0}{η(−n)} ∈ Π. We

conclude that f_{3}\binom{0}{η(−n)} = 0. Similarly, [{0 \atop μ(−n)} {0 \atop μ̄(−n)} {1 \atop η(−n)}] is legal, so f_{3}\binom{1}{η(−n)} = 1. Hence n is a dictator in issue 3; similarly, agent n is a dictator in issues 1 and 2. □

References

Arrow, Kenneth. 1951. Social Choice and Individual Values. New York: John Wiley and Sons.

Barbera, Salvador, 1980. “Pivotal Voters. A New Proof of Arrow’s Theorem,” Economics Letters, 6, 13–16.

May, K. 1952. “A Set of Independent, Necessary, and Sufficient Conditions for Simple Majority Decisions,” Econometrica, 20, 680–684.