日本語English新規登録

## カウンタ

 COUNTER

2012/07/19

| by reiju

# Arrow’s impossibility theorem: One-shot proof made accessible

by H. Reiju Mihara
First version: July 19, 2012
Last revised: July 22, 2012

## 1. Introduction

Arrow's Theorem
(1963; the first edition 1951) is a fundamental result in economics.  It opened up the field of social choice theory.  This note gives a full proof of the theorem, without assuming strict preferences for individuals and the society.  The proof is largely based on Yu's (2012) recent proof, which attempts to improve on Geanakoplos (2005).  Yu's proof is one of the simplest and the shortest that I have ever seen.  I have tried to make it more accessible by filling in missing details.

Remark
.  I guess I am pretty qualified to discuss Arrow's Theorem, since I am one of the few contemporary social choice theorists that are still publishing papers on the theorem in outlets like Economic TheoryJournal of Mathematical Economics, and Social Choice and Welfare.  If you are a novice, you might be interested in watching a ten-minute introduction to the theorem on YouTube.  The video also contains a very short introduction to later developments.  You can find most of my papers mentioned in the video from the link above.  Finally, the FAQs contain more on Arrow's theorem.

## 2. Arrow's Theorem

Let  be the set of voters (individuals), where  is finite.  Let  be a set of at least three alternatives (candidates).  A preference is a complete and transitive (see the Remark below) binary relation on the set of alternatives.  A (preference) profile is an -tuple  of individual preferences.  We write  (read " prefers  to ") if (read " weakly prefers  to ") but not .  We write  (read " is indifferent between  and ") if  and .

Remark.   A binary relation  on is complete if for all  and , we have either  or .  It is transitive if for all , and  imply

(preference) aggregation rule (often called a social welfare function) is a function  that maps each profile  into a preference , called the group preference.  We write  (read " is ranked above " or "the group prefers  to ") if  but not .  (The Unrestricted Domain condition is incorporated in the definition of an aggregation rule; it requires the domain of the rule to contain all profiles.)

Arrow's Theorem asserts that there is no aggregation rule that satisfies the following three conditions:
• Unanimity (Weak Pareto).  If every voter prefers  to , then the group prefers  to .
• Independence (Independence of Irrelevant Alternatives).  Whether the group prefers  to  can depend only on the relative positions of  and  in each voter's preference.
• Nondictatorship.  There is no voter that can always determine the group's preference whatever the preferences of the others.  That is, there is no voter  such that whenever  prefers  to  the group prefers  to .  (Such an  is called a dictator, if there is one.)
Remark.  More formally, these conditions can be expressed as follows:
• Unanimity.  For any  and for any profile , if for all , then .
• Independence.  For any  and for any profiles  and , if  for all , then .
• Nondictatorship.  There is no  such that for all  and for all profiles  implies .

## 3. Proof

Suppose that an aggregation rule satisfies Unanimity and Independence.  We prove that there is a dictator.

We first give the following definitions:  A voter is decisive for (the ordered pair) if, whenever he prefers  to  the group prefers  to .  A voter is decisive for  (the set) if he is decisive for  and for .  So a dictator is a voter that is decisive for all pairs .

Consider an arbitrary profile  where  for all .  Swap the positions of  and sequentially from  to .  Because of Unanimity, we start with  ("the group prefers  to ") and end with .  Let  be the first voter (-pivotal voter) that causes the violation of  (the violation is written , "the group does not prefer  to ").  Note that this definition of  is independent of the profile  because of Independence.  (Verify this.)

Lemma.  Let be arbitrary distinct alternatives.  Then we have:
•  is decisive for  (the set).
• .
Proof of the Lemma.  Consider any profile in which
• voters  through   prefer to  to ; and
• voters   through  prefer to  to .
Then, we have , where the first relation is by the definition of  and the second by Unanimity.  Next, consider any profile in which
• voters 1 through   prefer bothand  to  but order and  in any way (they may be indifferent between and );
• voter  prefers  to  to ; and
• voters   through  prefer to both and  but order and  in any way.
Then, we have , where the first relation is by the definition of  and the second by Independence (individual preferences between and  are the same inand in ).  Since the positions of and  are arbitrary for each voter except  in , Independence implies the following
Claim 1.   is decisive for  (ordered pair).

We next prove the following
Claim 2.  .
• To show , suppose otherwise.  Then just after  swaps the positions of and  in the swapping process that defines  , we have .  Since  still prefers to  at this point, Claim 1 implies , a ontradiction.
• To show , suppose otherwise.  Then just after  swaps the positions of and  in the swapping process that defines  , we have  by Claim 1.  Since  still prefers  to  at this point, we have , a ontradiction.
Since are arbitrary and distinct, we can replace  in Claim 1 and Claim 2 by  (that is, we can exchange the roles of and  in the claims).  This gives
•  is decisive for  (ordered pair).
• .
Combining the second statement with Claim 2 gives the second assertion () of the lemma.  Combining the first statement with Claim 1 gives the first assertion ( is decisive for  (the set)) of the lemma, since .  [End of the proof of the Lemma]

Choose two distinct alternatives  and fix them for the rest of the proof.  Replace  in the Lemma by , where  is any alternative distinct from .   The following claim follows from the Lemma:
Claim 3.   is decisive for  and  .

We conclude by showing that  is a dictator; that is,  is decisive for all  satisfying .

Case 1: Both  and belong to .  By Claim 3,  is decisive for .  (Since   is decisive both for  and for , we can conclude that   is decisive for , whether  or .)

Case 2: Exactly one of  belongs to .
• If or , we can assume  without loss of generality.  Replacing  in the Lemma by , we conclude that  is decisive for   But  by Claim 3.
• If  or , we can assume  without loss of generality.  Replacing  in the Lemma by , we conclude that  is decisive for
Case 3: Neither  nor  belongs to .  Replacing  in the Lemma by , we conclude that  is decisive for   But  follows from replacing  in the Lemma by .

## References

Arrow, K. J. (1963). Social Choice and Individual Values (2nd ed.). New Haven: Yale University Press.
Geanakoplos, J. (2005). Three brief proofs of Arrow’s Impossibility Theorem. Economic Theory, 26(1), 211-215. doi:10.1007/s00199-004-0556-7

Kumabe, M. & Mihara, H. R. (2011). Preference Aggregation Theory Without Acyclicity: The Core Without Majority Dissatisfaction. Games and Economic Behavior, 72, 187--201. doi:10.1016/j.geb.2010.06.008 [working paper]

Mihara, H. R. (1997). Arrow’s Theorem and Turing Computability. Economic Theory, 10, 257-276. doi:10.1007/s001990050157 [working paper]

Mihara, H. R. (2008). Arrow's Impossibility Theorem and ways out of the impossibility. YouTube.
Yu, N. N. (2012). A one-shot proof of Arrow’s impossibility theorem. Economic Theory, 523-525. doi:10.1007/s00199-012-0693-3

### Keywords in Japanese and Korean

ケネス・アロー, アローの不可能性定理，アローの定理，アロウの定理，証明, 社会選択理論，投票理論，ランキング，実証政治理論，合理的選択，政治学，ミクロ経済学，厚生経済学，規範経済学，離散数学．三原麗珠．香川大学図書館．

애로우의 불가능성정리, 증명, 사회선택이론, 투표이론, 랭킹, 실증정치이론, 합리적 선택, 정치학, 미시경제학, 후생경제학, 규범경제학,이산수학. 미하라래주 (레이주). 카가와대학.