Eco514|Game Theory Lecture 7: Interactive Epistemology (2) Marciano Siniscalchi October 7, 1999 Introduction This lecture presents the two main contributions of \interactive epistemology" to the the- ory of normal-form games: a characterization of Nash equilibrium beliefs, and a full (i.e. behavioral) characterization of rationalizability. A review of the basic de nitions For your convenience, I summarize the essential de nitions pertaining to models of interactive beliefs; please consult the notes for Lecture 6 for details. We x a simultaneous game G = (N;(Ai;ui)i2N. A frame for G is a tuple F = ( ;(Ti;ai)i2N) such that, for every player i 2 N, Ti is a partition of , and ai is a Ti- mesurable map ai : !Ai. We denote by ti(!) the cell of the partition Ti containing !. A model for G is a tuple M = (F;(pi)i2N), where F is a frame for G and each pi is a probability distribution on ( ). Given any belief i 2 (A i) for Player i, ri( i) is the set of best replies for i given i. The rst-order beliefs function i : ! (A i) extracts Player i’s beliefs about A i from her beliefs about . Armed with this notation, we can de ne the event, \Player i is rational" by Ri =f!2 : ai(!)2ri( i(!))g and the event, \Every player is rational" by R = Ti2N Ri. De ne the belief operator Bi : 2 !2 by 8E ; Bi(E) =f!2 : pi(Ejti(!)) = 1g: 1 We read Bi(E) \Player i is certain that E is true." Also de ne the event, \Everybody is certain that E is true" by B(E) = Ti2N Bi(E). Beliefs operators satisfy the following properties: (1) ti = Bi(ti); (2) E F implies Bi(E) Bi(F); (3) Bi(E\F) = Bi(E)\Bi(F); (4) Bi(E) Bi(Bi(E)) and nBi(E) Bi( nBi(E)); (5) Ri Bi(Ri). Finally, a few shorthand de nitions: 8i2N; q2 (A i) : [ i = q] =f! : i(!) = qg and 8i2N;ai2Ai : [ai = ai] =f! : ai(!) = aig Nash Equilibrium I will provide two distinct epistemic characterizations of Nash equilibrium. The rst is behavioral, nonstandard, and rather trivial. The second is actually a characterization of equilibrium beliefs, but it is the standard one, and requires a modicum of work. Simple-minded characterization of Nash equilibrium You will recall from our past informal discussions that Nash equilibrium incorporates two key assumptions: (1) Players are Bauesian rational; (2) Their beliefs are correct: what they believe their opponents will do is exactly what they in fact do. We now have the machinery we need to formalize this statement. The key idea is that correctness of rst-order beliefs is easy to de ne in our model. De nition 1 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N) for G. For every i 2 N and ! 2 , Player i has correct rst-order beliefs at ! i there exists a i = (aj)j6=i2A i such that: (1) 8j6= i, aj(!) = aj; (2) i(!)(fa ig) = 1. Let CFBi denote the set of states where Player i’s rst-order beliefs are correct. That is, concisely, CFBi =f! : i(!) = (aj(!))j6=ig At every state in a model, players choose a single action|they do not randomize. If randomization is an actual strategic option, it must be modelled explicitly. The present approach only deals with pure Nash equilibria. 2 Proposition 0.1 Fix a game G = (N;(Ai;ui)i2N) and a pro le of actions a = (ai)i2N. (1) If there exists a modelM= ( ;(Ti;ai;pi)i2N) for G and a state ! in the model such that !2R\Ti2N CFBi and ai(!) = ai for all i2N, then a is a Nash equilibrium of G. (2) If a2A is a Nash equilibrium of G, there exists a model M= ( ;(Ti;ai;pi)i2N) for G and a state ! in the model such that !2R\Ti2N CFBi and ai(!) = ai for all i2N. Proof: (1) At !, ai = ai(!) 2ri( i(!)) = ri( a i) for all i2N; hence, a is a Nash equilibrium. (2) Consider a model with a single state ! (so that = f!g = ti(!) for all i2N) such that ai(!) = ai. Since a is a Nash equilibrium, ! 2R; since necessarily pi(!) = 1 for all i2N, !2CSBi for all i2N. You are authorized to feel cheated. This characterization does not add much to the de nition of Nash equilibrium. However, it does emphasize what is entailed by correctness of beliefs. I mentioned this in the informal language we had to make do with a while ago, but I can be more precise now. Player i’s beliefs at ! are correct if i(!) = (ai(!))i2N which is a condition relating one player’s beliefs with her opponents’ choices at a state. If at ! this is true for all players, and if players are rational, then the pro le (ai(!))i2N they play at ! must be a Nash equilibrium. On the other hand, if a pro le a is a Nash equilibrium, the assumption that there exists a state ! where players are rational and i(!) = (aj)j6=i for all i2N, but still it may be the case that ai(!) 6= ai for some i2N, and the pro le (ai(!))i2N that is actually played at ! may fail to be a Nash equilibrium. In some sense, the most interesting part of Proposition 0.1 is (2), because it states that the strong notion of correctness of rst-order beliefs is necessary if we are to interpret Nash equilibrium as yielding behavioral predictions. Equilibrium beliefs The \standard" approach, usually attributed to Aumann and Brandenburger, is intellectually more satisfying. Instead of asking what conditions imply that players’ behavior will be consistent with Nash equilibrium, Aumann and Brandenburger ask what conditions imply that their beliefs will be. The result is most transparent in two-player games. The idea is to consider a pair ( 1; 2) of (possibly degenerate) mixed actions as a pair of beliefs. Thus, 1, which is conventionally 3 interpreted as Player 1’s mixed action, is actually viewed as Player 2’s beliefs about Player 1’s actions; and similarly for 2. Then, instead of assuming that players are rational, we assume that they are certain that their opponent is rational. And, instead of assuming that their rst-order beliefs are correct, we assume that they are certain of their opponent’s rst-order beliefs. Roughly speaking, if Player 1 believes that Player 2 will choose an action a2 with positive probability (i.e. if 2(a2) > 0); if she is certain that he is rational; and if she is certain that his belief about her actions is given by 1, then it must be the case that a2 is a best reply to 1. A similar argument holds for Player 2’s beliefs about Player 1, and we can conclude that ( 1; 2) must be a Nash equilibrium. Let us state and prove the result; additional comments will follow. Proposition 0.2 Fix a two-player game G = (N;(Ai;ui)i2N), with N =f1;2g, and a pro le of mixed actions = ( i)i2N (A1) (A2). (1) If there exists a modelM= ( ;(Ti;ai;pi)i2N) for G and a state ! in the model such that !2B(R)\B([ 1 = 1]\[ 2 = 2]) then is a Nash equilibrium of (the mixed extension of) G. (2) If is a Nash equilibrium of (the mixed extension of) G, then there exists a model M = ( ;(Ti;ai;pi)i2N) for G and a state ! in the model such that ! 2B(R)\B([ 1 = 1]\[ 2 = 2]). We begin with two preliminary results. Lemma 0.3 For any event E , every Player i2N, and every state !2 : !2Bi(E) i supppi( jti(!)) E. Proof of Lemma 0.3: suppose !2Bi(E). Then pi(Ejti(!)) = 1. This requires that pi(!0jti(!)) > 0)!02E, so supppi( jti(!)) E. The converse is obvious. Lemma 0.4 For every player i2N, every ti 2Ti and every state ! 2 , ! 2Bi(ti) i ti = ti(!); hence, Bi([ai = ai]) = [ai = ai] and Bi([ i = q]) = [ i = q], and Bi(Ri) = Ri. Proof: For every !, pi(tijti(!)) = 1 if ti = ti(!), and pi(tijti(!)) = 0 otherwise. This proves the rst claim. Now ai( ) is Ti-measurable; hence, if !2[ai = ai], then ti(!) [ai = ai). and if !2Bi([ai = ai]), then necessarily !2ti(!) [ai = ai] (because otherwise we could not have pi([ai = ai]jti(!)) = 1); and similarly for [ i = q]. The second claim follows immediately. Finally, note that Ri =f! : ai(!)2ri( i(!))gmust clearly be Ti-measurable, and the third claim follows by the same argument as above. 4 Proof of Proposition 0.2: (1) Fix a1 2A1 such that 1(!)(a1) > 0; that is, consider an action which, at !, Player 2 expects Player 1 to choose with positive probability. This implies that there exists !0 such that a1(!0) = a1 and p2(!0jt2(!)) > 0. Our assumptions imply that ! 2B2(R1)\B2([ 2 = 2]) = B2(R1 \[ 2 = 2]) (here we are using a key property of B2: B2(E\F) = B2(E)\B2(F)). Hence, by Lemma 0.3, suppp2( jt2(!)) R1 \[ 2 = 2]. But then !0 2R1 \[ 2 = 2], which implies that a1 = a1(!0)2r1( 2(!0)) = r1( 2). Thus, every a1 such that 1(!)(a1) > 0 is a best reply to 2. To complete the proof, we must show that 1(!) = 1. Note that this is not part of our assumptions; however, our assumptions do imply that !2B2([ 1 = 1]), and by Lemma 0.4, the required equality follows. The proof of Part (1) is complete. (2) Construct a model as follows: let = Qi2N supp i and de ne via the possibility correspondence ti( ) by letting 8(a1;a2)2 ; ti(a1;a2) =faig supp i for i = 1;2. This is similar to (but simpler than) the construction we used to prove the \revelation principle" in the last lecture notes. States are pro les that have positive proba- bility in equilibrium, and each player is informed of her action at any state. This makes it is possible to de ne ai(a1;a2) = ai. Finally, we can use a common prior on to complete the de nition of a model: p1(a1;a2) = p2(a1;a2) = 1(a1) 2(a2). There is nothing special about this; the key point is that, for ev- ery (a1;a2) 2 , pi(a1;a2jti(a1;a2)) = i(a i) and therefore i(a1;a2) = i with these de nitions. Note that this implies in particular that [ i = i] = for i = 1;2; hence, clearly (a1;a2)2B([ 1 = 1]\[ 2 = 2]) at any state (a1;a2)2 . Now consider any state ! = (a1;a2). Then ai(!) = ai2ri( i) = ri( i(!)), so !2Ri; that is, R1 = R2 = (which is obvious, if you think about it!) and therefore, at any state !2 , !2B(R). We are done. Observe that, to prove (1), we do not actually need ! 2Bi(Ri). However, this comes almost for free in part (2). Also, the assumptions imply (via Lemma 0.4) that players are indeed rational at the state under consideration; this is not used in the proof of Part (1), but again it comes for free in part (2). A key observation is that Aumann and Brandenburger’s construction solves another key interpretational problem almost automatically. Mixed actions are viewed as beliefs: thus, one does not even need to invoke randomizations to justify them. Rationalizability We now turn to Tan and Werlang’s characterization of correlated rationalizability. Actually, I will again present the argument for two-player games, but here everything generalizes 5 readily, and it is easy to add stochastic independence as an explicit restriction on beliefs. Indeed, any restriction on rst-order beliefs can be easily added to the characterization. Let me remind you of the de nition rst. Let A0i = Ai for i = 1;2. Next, for k 1, say that ai2Aki i there exists i2 (A i) such that i(Ak 1 i ) = 1 and ai2ri( i). We now de ne a sequence of events: B0 = R; 8k 1;Bk = B(Bk 1) Thus, B1 = \Everybody is certain that everybody is rational"; B2 = \Everybody is certain that everybody is certain that everybody is rational"; and so on. Proposition 0.5 Fix a two-player game G = (N;(Ai;ui)i2N), with N =f1;2g, and a pro le of actions a = (a1;a2). (1) If there exists a modelM= ( ;(Ti;ai;pi)i2N) for G and a state ! in the model with ai(!) = ai for i = 1;2 such that !2 k‘=0 B‘ then a2Ak+1. Hence, if there is a model M and a state ! in that model with ai(!) = ai for i = 1;2 such that !2T1‘=0 B‘, then a is rationalizable. (2) If a2Ak (k 1), then there exists a modelM= ( ;(Ti;ai;pi)i2N) for G and a state ! in the model such that ai(!) = ai, i = 1;2 and !2Tk 1‘=0 B‘. If a is rationalizable, there exists a model M and a state ! such that ai(!) = ai, i = 1;2 and !2T1‘=0 B‘. Proof: Note rst that, for k 1, k‘=0 B‘ = Rk‘=1 B(B‘ 1) = R\B k 1‘=0 B‘ ! (1, k = 0) Fix !2B0 = R. Then trivially ai = ai(!)2ri( i(!)), so ai2A1i. (1, k> 0) By induction, suppose the claim is true for‘ = 0;:::;k 1. Fix!2Tk‘=0Bk; by the above decomposition, !2Ri and !2Bi T k 1 ‘=0 B ‘ . By Lemma 0.3, supppi( jti(!)) Tk 1 ‘=0 B ‘; but for all !0 2 Tk 1 ‘=0 B ‘, by the induction hypothesis a i(!0) 2 Ak 1 i . Hence, i(!)(Ak 1 i ) = 1, and we are done. The claim concerning rationalizable pro les follows from the fact that, since the game is nite, there exists K such that k K implies Aki = AKi for all i2N. (2) : left as an exercise for the interested reader. The characterization result is quite straightforward. I do point out that the assumption that ! 2Sk‘=0B‘ has behavioral implications: what players actually do at ! is consistent with k + 1 steps of the iterative procedure de ning rationalizability. As I have remarked many times, this is not the case with Nash equilibrium. 6