カウンタ

COUNTER29185

ブログ

研究ブログ >> 記事詳細

2012/07/19

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

Tweet ThisSend to Facebook | 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 N=\{1, \ldots, n\} be the set of voters (individuals), where n \ge 2 is finite.  Let X 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 Xof alternatives.  A (preference) profile is an n-tuple \mathbf{R}=(R_1, \ldots, R_n) of individual preferences.  We write xP_iy (read "i prefers x to y") if xR_iy(read "i weakly prefers x to y") but not yR_ix.  We write xI_iy (read "i is indifferent between x and y") if xR_iy and yR_ix.

Remark.   A binary relation R on Xis complete if for all x and y, we have either xRy or yRx.  It is transitive if for all x,yzxRy and yRz imply xRz

(preference) aggregation rule (often called a social welfare function) is a function f that maps each profile \mathbf{R} into a preference R_N=f(\mathbf{R}), called the group preference.  We write xP_Ny (read "x is ranked above y" or "the group prefers x to y") if xR_Ny but not yR_Nx.  (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 x to y, then the group prefers x to y.
  • Independence (Independence of Irrelevant Alternatives).  Whether the group prefers x to y can depend only on the relative positions of x and y 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 i such that whenever i prefers x to y the group prefers x to y.  (Such an i is called a dictator, if there is one.)
Remark.  More formally, these conditions can be expressed as follows:
  • Unanimity.  For any x, y \in X and for any profile \mathbf{R}=(R_1, \ldots, R_n), if for all i\in NxP_iy, then xP_Ny.
  • Independence.  For any x, y \in X and for any profiles \mathbf{R}=(R_1, \ldots, R_n) and \mathbf{R}'=(R'_1, \ldots, R'_n), if R_i\cap \{x,y\}^2=R'_i\cap \{x,y\}^2 for all i\in N, then R_N\cap \{x,y\}^2=R'_N\cap \{x,y\}^2.
  • Nondictatorship.  There is no i\in N such that for all x, y \in X and for all profiles \mathbf{R}=(R_1, \ldots, R_n)xP_iy implies xP_Ny.

3. Proof


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

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

Consider an arbitrary profile \mathbf{R} where xP_iy for all i.  Swap the positions of x and ysequentially from 1 to n.  Because of Unanimity, we start with x\succ y ("the group prefers x to y") and end with y\succ x.  Let i_{xy} be the first voter ((x,y)-pivotal voter) that causes the violation of x\succ y (the violation is written y\succeq x, "the group does not prefer x to y").  Note that this definition of i_{xy} is independent of the profile \mathbf{R} because of Independence.  (Verify this.)

Lemma.  Let u,v,w\in Xbe arbitrary distinct alternatives.  Then we have:
  • i_{uv} is decisive for \{v,w\} (the set).
  • i_{uv}=i_{vw}=i_{wv}=i_{uw}.
Proof of the Lemma.  Consider any profile \mathbf{R}'in which 
  • voters 1 through i_{uv}-1  prefer vto w to u; and
  • voters i_{uv}  through n prefer uto v to w.
Then, we have uP'_NvP'_Nw, where the first relation is by the definition of i_{uv} and the second by Unanimity.  Next, consider any profile \mathbf{R}''in which 
  • voters 1 through i_{uv}-1  prefer bothvand w to u but order vand w in any way (they may be indifferent between vand w); 
  • voter i_{uv} prefers v to u to w; and
  • voters i_{uv}+1  through n prefer uto both vand w but order vand w in any way.
Then, we have vR''_NuP''_Nw, where the first relation is by the definition of i_{uv} and the second by Independence (individual preferences between uand w are the same in\mathbf{R}'and in \mathbf{R}'').  Since the positions of vand w are arbitrary for each voter except i_{uv} in \mathbf{R}'', Independence implies the following 
Claim 1.  i_{uv} is decisive for (v,w) (ordered pair).

We next prove the following
Claim 2.  i_{vw} \ge i_{uv} \ge i_{wv}.
  • To show i_{vw} \ge i_{uv}, suppose otherwise.  Then just after i_{vw} swaps the positions of vand w in the swapping process that defines  i_{vw}, we have w\succeq v.  Since i_{uv} still prefers vto w at this point, Claim 1 implies v\succ w, a ontradiction.
  • To show i_{uv} \ge i_{wv}, suppose otherwise.  Then just after i_{uv} swaps the positions of wand v in the swapping process that defines  i_{wv}, we have v\succ w by Claim 1.  Since i_{wv} still prefers w to v at this point, we have w\succ v, a ontradiction.
Since u,v,w\in Xare arbitrary and distinct, we can replace (u,v,w) in Claim 1 and Claim 2 by (u,w,v) (that is, we can exchange the roles of vand w in the claims).  This gives 
  • i_{uw} is decisive for (w,v) (ordered pair).
  • i_{wv} \ge i_{uw} \ge i_{vw}.  
Combining the second statement with Claim 2 gives the second assertion (i_{uv}=i_{vw}=i_{wv}=i_{uw}) of the lemma.  Combining the first statement with Claim 1 gives the first assertion (i_{uv} is decisive for \{v,w\} (the set)) of the lemma, since i_{uw}=i_{uv}.  [End of the proof of the Lemma]

Choose two distinct alternatives a, b \in X and fix them for the rest of the proof.  Replace (u,v,w) in the Lemma by (c,a,b), where c is any alternative distinct from a, b.   The following claim follows from the Lemma:
Claim 3.  i_{ca} is decisive for \{a,b\} and  i_{ca}=i_{ab}=i_{ba}.

We conclude by showing that i_{ab} is a dictator; that is, i_{ab} is decisive for all (x,y) satisfying x\ne y.

Case 1: Both x and ybelong to \{a,b\}.  By Claim 3, i_{ab} is decisive for \{a,b\}=\{x,y\}.  (Since  i_{ab} is decisive both for (a,b) and for (b,a), we can conclude that  i_{ab} is decisive for (x,y), whether (x,y)=(a,b) or (x,y)=(b,a).)

Case 2: Exactly one of x,y belongs to \{a,b\}.  
  • If x=aor y=a, we can assume x=a without loss of generality.  Replacing (u,v,w) in the Lemma by (b,a,y), we conclude that i_{ba} is decisive for \{a,y\}=\{x,y\}.  But i_{ba}=i_{ab} by Claim 3.
  • If x=b or y=b, we can assume x=b without loss of generality.  Replacing (u,v,w) in the Lemma by (a,b,y), we conclude that i_{ab} is decisive for \{b,y\}=\{x,y\}.
Case 3: Neither x nor y belongs to \{a,b\}.  Replacing (u,v,w) in the Lemma by (b,x,y), we conclude that i_{bx} is decisive for \{x,y\}.  But i_{bx}=i_{ab} follows from replacing (u,v,w) in the Lemma by (a,b,x).


4. Discussion

  • The assumption that n is finite is crucial for this proof.  In fact, when there are infinitely many voters, aggregation rules exist that satisfy the three conditions of Unanimity, Independence, and Nondictatorship.  However, Mihara (1997) shows that such rules violate algorithmic computability, thus strengthening Arrow's theorem.

  • The assumption that there are at least three alternatives is also crucial, since we need to pick three distinct alternatives in the Lemma.  In fact, when there are only two alternatives, simple majority rule, for example, satisfies the conditions.  More generally, one can assign a number \nu called the Nakamura number to each aggregation rule satisfying conditions such as neutrality (equal treatment of alternatives) and show that this number plays a similar role: when the number of alternatives is less than \nu, the rule can pick a "best" alternative rationally, but otherwise a voting paradox (a cycle such as a beats bb beats c, and c beats a) will arise for some profile.  Some super-majority rules (such as those requiring 2/3 of the votes) have a Nakamura number greater than 3, but such rules violate the conditions of Arrow's theorem.  Kumabe and Mihara (2011) extend the above result (Nakamura's theorem) in several directions.

  • I'm saying this again, but the FAQs contain more on Arrow's theorem.

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

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

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

トラックバックURLhttp://researchmap.jp/index.php?action=journal_action_main_trackback&post_id=16504
10:20 | 投票する | 投票数(22) | コメント(2) | トラックバック(53) | 研究
コメント
reiju2012/07/22 03:46:36
アローの定理の「一発証明」を詳しく解説した記事.
2012年7月19日記事投稿時の訪問回数カウンタは7.
7月20日参照 twitter 投稿時点までにカウンタ52.
20日のうちにカウントは1000前後まで上昇.
22日3:37 時点で 1114.投票数 14.
23日2:00 時点で 1231.投票数15.
26日11:30 ころ 1376. 投票数 16.
同日,@wiki と平凡助教授ブログからリンク.
29日3:10 ころ 1471. 投票数 16.
8月3日1000ころ 1569.
twitter で言及.
8月3日1100ころ 1600.

2013年1月26日11:40時点で 2927.

可能を不可能にする男 (Mihara 1997 より)
reiju2012/12/12 18:26:47
Arrow's Impossibility Theorem (Posted by Ian Hoppe) contains another proof:
http://www.polymathmoshpit.com/2012/11/arrows-impossibility-theorem.html