Eco514-Game Theory ecture 7: Interactive Epistemology(2 Marciano siniscalchi October 7. 1999 Introduction This lecture presents the two main contributions of "interactive epistemology"to thethe- 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 definitions For your convenience, I summarize the essential definitions pertaining to models of interactive beliefs; please consult the notes for Lecture 6 for details (92, (Ti, ai)ieN) such that, for every player i E/a). A frame for G is a tuple F We fix a simultaneous game G=(N, (Ai is a partition of Q2, and a; is a Ti- mesurable map a1:→A We denote by ti(w)the cell of the partition Ti containing w A model for G is a tuple M=(F, (piie), where F is a frame for G and each pi is a probability distribution on A() Given any belief a-i E A(A-i) for Player i, rila_i) is the set of best replies for i given -i. The first-order beliefs function a-i: S-A(A-i) extracts Player i's beliefs about A-i from her beliefs about n Armed with this notation, we can define the event, "Player i is rational "by R1={u∈9:a(u)∈r(a-(∞)} nd the event, "Every player is rational"by r=nien Ri Define the belief operator Bi: 23-2 by VECQ, Bi(E)=WwE: pi(eti(w=1
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 theory of normal-form games: a characterization of Nash equilibrium beliefs, and a full (i.e. behavioral) characterization of rationalizability. A review of the basic definitions For your convenience, I summarize the essential definitions pertaining to models of interactive beliefs; please consult the notes for Lecture 6 for details. We fix a simultaneous game G = (N,(Ai , ui)i∈N . A frame for G is a tuple F = (Ω,(Ti , ai)i∈N ) such that, for every player i ∈ N, Ti is a partition of Ω, and ai is a Timesurable map ai : Ω → Ai . We denote by ti(ω) the cell of the partition Ti containing ω. A model for G is a tuple M = (F,(pi)i∈N ), where F is a frame for G and each pi is a probability distribution on ∆(Ω). Given any belief α−i ∈ ∆(A−i) for Player i, ri(α−i) is the set of best replies for i given α−i . The first-order beliefs function α−i : Ω → ∆(A−i) extracts Player i’s beliefs about A−i from her beliefs about Ω. Armed with this notation, we can define the event, “Player i is rational” by Ri = {ω ∈ Ω : ai(ω) ∈ ri(α−i(ω))} and the event, “Every player is rational” by R = T i∈N Ri . Define the belief operator Bi : 2Ω → 2 Ω by ∀E ⊂ Ω, Bi(E) = {ω ∈ Ω : pi(E|ti(ω)) = 1}. 1
We read Bi (E)"Player i is certain that E is true. Also define the event, "Everybody is certain that e is true”byB(E)=∩eNB2( Beliefs operators satisfy the following properties (1)t=B2(t); (2)E C F implies B(E)C Bi(F); (3)B(E∩F)=B(E)∩B(F); (4)Bi (E)C Bi (B(E))and Q2\B(E)C B(Q\B(E); (5)R2CB2(R2) Finally, a few shorthand definitions vi∈N,q∈△(A-): and vi∈N,a1∈A:[a1=al]={u:a(u)=a} Nash equilibrium I will provide two distinct epistemic characterizations of Nash equilibrium. The first 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 first-order beliefs is easy to define in our model Definition 1 Fix a game G=(N, (Ai, ui)ieN)and a model M=(Q, (Ti, ai, pi)ien) for G For every i E N and w E Q, Player i has correct first-order beliefs at w iff there exists a-i=(a1)≠∈A- i such that (1)≠,a(u)=a; 2)a-(u)({a-})=1 Let CFBi denote the set of states where Player i's first-order beliefs are correct. That is, concisely. CFB1={:a-(u)=6a)≠ 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
We read Bi(E) “Player i is certain that E is true.” Also define the event, “Everybody is certain that E is true” by B(E) = T i∈N 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 Ω \ Bi(E) ⊂ Bi(Ω \ Bi(E)); (5) Ri ⊂ Bi(Ri). Finally, a few shorthand definitions: ∀i ∈ N, q ∈ ∆(A−i) : [α−i = q] = {ω : α−i(ω) = q} and ∀i ∈ N, ai ∈ Ai : [ai = ai ] = {ω : ai(ω) = ai} Nash Equilibrium I will provide two distinct epistemic characterizations of Nash equilibrium. The first 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 first-order beliefs is easy to define in our model. Definition 1 Fix a game G = (N,(Ai , ui)i∈N ) and a model M = (Ω,(Ti , ai , pi)i∈N ) for G. For every i ∈ N and ω ∈ Ω, Player i has correct first-order beliefs at ω iff there exists a−i = (aj )j6=i ∈ A−i such that: (1) ∀j 6= i, aj (ω) = aj ; (2) α−i(ω)({a−i}) = 1. Let CFBi denote the set of states where Player i’s first-order beliefs are correct. That is, concisely, CFBi = {ω : α−i(ω) = δ(aj (ω))j6=i } 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=(N, (Ai, lilieN) and a profile of actions a=(alieN 1)If there exists a model M=(Q, (Ti, ai, piie) for G and a state w in the model such that u∈Rn∩ CFBi and a1(u)= ai for all i∈N, then a is a Nash equilibrium of G 2)If a E A is a Nash equilibrium of G, there exists a model M=(Q, (Ti, ai, piie)for G and a state w in the model such that w E RnneN CFB; and ai(w)=ai for all N Proof: (1)At w, ai=ai(w)Eri(a-i(w))=ri(sa-i)for all i E N; hence, a is a Nash equilibrium.(2)Consider a model with a single state w(so that Q= w= ti(w)for all i E N) such that ai( w)=ai. Since a is a Nash equilibrium, W E R; since necessarily D2(u)=1 for all i∈N,w∈CSB; for all i∈N.■ You are authorized to feel cheated. This characterization does not add much to the definition 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 w are correct if a-i(w)=d(a (w ieN which is a condition relating one player's beliefs with her opponents choices at a state. If at w this is true for all players, and if players are rational, then the profile(ai ( w))ien they play at w must be a Nash equilibrium On the other hand. if a profile a is a Nash equilibrium. the assumption that there exists a state w where players are rational and a-(u)=6(a)≠ (ai(w))ien that is actually played at w may fail to be a Nash equilibrium. ,and the profile for all iE N, but still it may be the case that ai( w)t ai for In some sense, the most interesting part of Proposition 0.1 is(2), because it states that the strong notion of correctness of first-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 b The result is most transparent in two-player games. The idea is to consider a pair(o1, 2) of (possibly degenerate) mixed actions as a pair of beliefs. Thus, 1, which is conventionally
Proposition 0.1 Fix a game G = (N,(Ai , ui)i∈N ) and a profile of actions a = (ai)i∈N . (1) If there exists a model M = (Ω,(Ti , ai , pi)i∈N ) for G and a state ω in the model such that ω ∈ R ∩ T i∈N CFBi and ai(ω) = ai for all i ∈ N, then a is a Nash equilibrium of G. (2) If a ∈ A is a Nash equilibrium of G, there exists a model M = (Ω,(Ti , ai , pi)i∈N ) for G and a state ω in the model such that ω ∈ R ∩ T i∈N CFBi and ai(ω) = ai for all i ∈ N. Proof: (1) At ω, ai = ai(ω) ∈ ri(α−i(ω)) = ri(δa−i ) for all i ∈ N; hence, a is a Nash equilibrium. (2) Consider a model with a single state ω (so that Ω = {ω} = ti(ω) for all i ∈ N) such that ai(ω) = ai . Since a is a Nash equilibrium, ω ∈ R; since necessarily pi(ω) = 1 for all i ∈ N, ω ∈ CSBi for all i ∈ N. You are authorized to feel cheated. This characterization does not add much to the definition 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(ω))i∈N 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 profile (ai(ω))i∈N they play at ω must be a Nash equilibrium. On the other hand, if a profile a is a Nash equilibrium, the assumption that there exists a state ω where players are rational and α−i(ω) = δ(aj )j6=i for all i ∈ N, but still it may be the case that ai(ω) 6= ai for some i ∈ N, and the profile (ai(ω))i∈N 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 first-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 1s mixed action, is actually viewed as Player 2' s beliefs about Player 1's actions; and similarly for o2 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 first-order beliefs are correct we assume that they are certain of their opponent's first-order beliefs Roughly speaking, if Player 1 believes that Player 2 will choose an action a2 with positi 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, lilieN), with N=(1, 2, and a profile of mixed actions=()ieNC△(A1)×△(A2) (1)If there exists a model M=(Q2, (Ti, ai, pilieN) for G and a state w in the model such that B(fB)∩B(a1=]n then o is a Nash equilibrium of (the mixed extension of)G (2)If o is a Nash equilibrium of (the mixed extension of)G, then there exists a model M=(9,(T,a,n)l∈N) for G and a state w in the model such that w∈B(B)∩B(a1 ]∩a2=c2 We begin with two preliminary results Lemma 0.3 For any event E C Q, every Player i N, and every state w E Q2: WE Bi(E) iff supppi ((ti(w))CE Proof of Lemma 0.3: suppose w E B (E). Then pi( Et(w))= l. This requires that D2(u|t(∞)>0→∈E, so supp pi(|t1(u)cE. The converse is obvious.■ Lemma0.4 For every player i∈N, every t;∈T; and every state w∈9,w∈Bl(t;)诳 ti=ti(u); hence, B (a;=ai])=ai=ai and Bi(a-i=q))=[a-i=g, and B (R=Ri Proof: For every w, pi(t:( w))=l if ti=ti(w), and Pi(titi w)=0 otherwise. This proves the first claim. Now ai is T-measurable; hence, if w ai=ail, then t(w)c [ ai ai). and if w E Bi(a;=ail), then necessarily w E ti(w)c ai=ail( because otherwise we could not have pi(la;=aillti ())=1); and similarly for a-i=q]. The second claim follows immediately. Finally, note that r i=w: aiw)Eri(a-iw)) must clearly be Ti -measurable, and the third claim follows by the same argument as above. l
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 first-order beliefs are correct, we assume that they are certain of their opponent’s first-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)i∈N ), with N = {1, 2}, and a profile of mixed actions φ = (φi)i∈N ⊂ ∆(A1) × ∆(A2). (1) If there exists a model M = (Ω,(Ti , ai , pi)i∈N ) for G and a state ω in the model such that ω ∈ B(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)i∈N ) for G and a state ω in the model such that ω ∈ B(R) ∩ B([α1 = φ1] ∩ [α2 = φ2]). We begin with two preliminary results. Lemma 0.3 For any event E ⊂ Ω, every Player i ∈ N, and every state ω ∈ Ω: ω ∈ Bi(E) iff supp pi(·|ti(ω)) ⊂ E. Proof of Lemma 0.3: suppose ω ∈ Bi(E). Then pi(E|ti(ω)) = 1. This requires that pi(ω 0 |ti(ω)) > 0 ⇒ ω 0 ∈ E, so supp pi(·|ti(ω)) ⊂ E. The converse is obvious. Lemma 0.4 For every player i ∈ N, every ti ∈ Ti and every state ω ∈ Ω, ω ∈ Bi(ti) iff ti = ti(ω); hence, Bi([ai = ai ]) = [ai = ai ] and Bi([α−i = q]) = [α−i = q], and Bi(Ri) = Ri . Proof: For every ω, pi(ti |ti(ω)) = 1 if ti = ti(ω), and pi(ti |ti(ω)) = 0 otherwise. This proves the first claim. Now ai(·) is Ti-measurable; hence, if ω ∈ [ai = ai ], then ti(ω) ⊂ [ai = ai). and if ω ∈ Bi([ai = ai ]), then necessarily ω ∈ ti(ω) ⊂ [ai = ai ] (because otherwise we could not have pi([ai = ai ]|ti(ω)) = 1); and similarly for [α−i = q]. The second claim follows immediately. Finally, note that Ri = {ω : ai(ω) ∈ ri(α−i(ω))} must clearly be Ti-measurable, and the third claim follows by the same argument as above. 4
Proof of Proposition 0. 2: (1)Fix a1 E A1 such that al(w(a1)>0; that is, consider an action which, at w, Player 2 expects Player 1 to choose with positive probability. This implies that there exists w such that al(w)= a1 and p2(wt2(w))>0 Our assumptions imply that w E B2(R1)n B2([a2=2 ) B2(Rin a2= o2])(here B2:B2(E∩F)=B2(E)∩B2(F). Hence,by 0.3, supp p2((t2(w))C R1 n(a2=o2]. But then w'E R1n(a2=p2l, which implies that a1=a1(u/)∈r1(a2(u/)=r1(2) Thus, every al such that aw(ai>0 is a best reply to 2. To complete the proof, show that a(w)=1. Note that this is not part of our assumptions; however, our assumptions do imply that w E B2(a1=o1]), and by Lemma 0.4, the required equality follows. The proof of Part(1)is complete (2)Construct a model as follows: let s= lien supp oi and define via the possibility correspondence ti( by lettin v(a1,a2)∈9,t(a1,a2)={a}×supp 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 profiles that have positive proba bility in equilibrium, and each player is informed of her action at any state. This makes it is possible to define ai( Finally, we can use a common prior on S to complete the definition of a model: Pi(a1,a2 P2(a1, a2)=o1(alo(a2). There is nothing special about this; the key point is that, for ev- ery(a1, a2)E Q, Pi(a1, a2 ti (a1,a2))=o-i(a-i) and therefore a-i(a1, a2)=o-i with these definitions. Note that this implies in particular that Ja-i=p-i=@ for i= 1, 2; hence, clearly(a1,a2)∈B(a1=o1]∩[a2=l]) at any state(a1,a2)∈92 Now consider any state w=(a1, a2). Then ai( w)=aiErio-i=ri(a-i(w)), SoWE Ri that is, R1= R2=Q(which is obvious, if you think about it! and therefore, at any state u∈9,u∈B(). We are done■ Observe that, to prove (1), we do not actually need w E Bi(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 ne 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
Proof of Proposition 0.2: (1) Fix a1 ∈ A1 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(ω 0 |t2(ω)) > 0. Our assumptions imply that ω ∈ B2(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, supp p2(·|t2(ω)) ⊂ R1 ∩ [α2 = φ2]. But then ω 0 ∈ R1 ∩ [α2 = φ2], which implies that a1 = a1(ω 0 ) ∈ r1(α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 ω ∈ B2([α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 Ω = Q i∈N supp φi and define via the possibility correspondence ti(·) by letting ∀(a1, a2) ∈ Ω, ti(a1, a2) = {ai} × 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 profiles that have positive probability in equilibrium, and each player is informed of her action at any state. This makes it is possible to define ai(a1, a2) = ai . Finally, we can use a common prior on Ω to complete the definition 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 every (a1, a2) ∈ Ω, pi(a1, a2|ti(a1, a2)) = φ−i(a−i) and therefore α−i(a1, a2) = φ−i with these definitions. Note that this implies in particular that [α−i = φ−i ] = Ω for i = 1, 2; hence, clearly (a1, a2) ∈ B([α1 = φ1] ∩ [α2 = φ2]) at any state (a1, a2) ∈ Ω. Now consider any state ω = (a1, a2). Then ai(ω) = ai ∈ ri(φ−i) = ri(α−i(ω)), so ω ∈ Ri ; that is, R1 = R2 = Ω (which is obvious, if you think about it!) and therefore, at any state ω ∈ Ω, ω ∈ B(R). We are done. Observe that, to prove (1), we do not actually need ω ∈ Bi(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