Eco514-Game Theory ecture 6: Interactive Epistemology(1) Marciano siniscalchi October 5. 1999 Introduction This lecture focuses on the interpretation of solution concepts for normal-form games. You will recall that, when we introduced Nash equilibrium and rationalizability, we mentioned numerous reasons why these solution concepts could be regarded as yielding plausible restric- tions on rational play, or perhaps providing a consistency check for our predictions about However, in doing so, we had to appeal to intuition, by and large. Even a simple assump- tion such as "Player 1 believes that Player 2 is rational" involves objects that are not part of the standard description of a game with complete information. In particular, recall that Bayesian rationality is a condition which relates behavior and beliefs: a player is "rational if and only if she chooses an action which is a best reply given her beliefs. But then, to say that Player 1 believes that Player 2 is rational implies that Player 1 holds a conjecture on oth Player 2's actions and her beliefs The standard model for games with complete information does not contain enough ure for us to formalize this sort of assumption. Players'beliefs are probability distributions n their opponents'action profiles But, of course, the model we have developed(following Harsanyi)for games with payoff uncertainty does allow us to generate beliefs about beliefs, and indeed infinite hierarchies of mutual beliefs The objective of this lecture is to present a model of interactive beliefs based on Harsanyi's ideas, with minimal modifications to our setting for games with payoff uncertainty. We shall then begin our investigation of "interactive epistemology"in normal-form games by looking at correlated equilibrium
Eco514—Game Theory Lecture 6: Interactive Epistemology (1) Marciano Siniscalchi October 5, 1999 Introduction This lecture focuses on the interpretation of solution concepts for normal-form games. You will recall that, when we introduced Nash equilibrium and Rationalizability, we mentioned numerous reasons why these solution concepts could be regarded as yielding plausible restrictions on rational play, or perhaps providing a consistency check for our predictions about it. However, in doing so, we had to appeal to intuition, by and large. Even a simple assumption such as “Player 1 believes that Player 2 is rational” involves objects that are not part of the standard description of a game with complete information. In particular, recall that Bayesian rationality is a condition which relates behavior and beliefs: a player is “rational” if and only if she chooses an action which is a best reply given her beliefs. But then, to say that Player 1 believes that Player 2 is rational implies that Player 1 holds a conjecture on both Player 2’s actions and her beliefs. The standard model for games with complete information does not contain enough structure for us to formalize this sort of assumption. Players’ beliefs are probability distributions on their opponents’ action profiles. But, of course, the model we have developed (following Harsanyi) for games with payoff uncertainty does allow us to generate beliefs about beliefs, and indeed infinite hierarchies of mutual beliefs. The objective of this lecture is to present a model of interactive beliefs based on Harsanyi’s ideas, with minimal modifications to our setting for games with payoff uncertainty. We shall then begin our investigation of “interactive epistemology” in normal-form games by looking at correlated equilibrium. 1
The basic idea Recall that, in order to represent payoff uncertainty, we introduced a set Q2 of states of the world, and made the players payoff functions depend on the realization w E Q, as well as on the profile(alien E Lien A; of actions chosen by the players This allowed us to represent hierarchical beliefs about the state of the world; however we are no more capable of describing hierarchical beliefs about actions(at least not without introducing additional information, such as a specification of equilibrium actions for each type of each player) Thus, a natural extension suggests itself. For simplicity, I will consider games without payoff uncertainty, but the extension should be obvious Definition 1 Consider a simultaneous game G=(N, (Ai, wi)ien)(without payoff uncer tainty). A frame for G is a tuple F=(Q, (Ti, alieN) such that, for every player iE N, Tiis a partition of Q2, and ai is a map a;: Q2- Ai such that (a1)≠0→a1(a)∈T Continue to denote by ti(w) the cell of the partition Ti containing w. Finally, a model forG is a tuple M=(F, (pilieN), where F is a frame for G and each P; is a probability distribution I distinguish between frames and models to emphasize that probabilistic beliefs convey additional information-which we wish to relate to solution concepts. The distintion is also often made in the literature le, The main innovation is the introduction of the functions ai (.). This is not so far-fetched er all, uncertainty about opponents' actions is clearly a form of payoff uncertainty--one that arises in any strategic situation. However, by making players ' choices part of the state of the world, it is possible to discuss the players' hierarchical beliefs about them. Ultimately, we wish to relate solution concepts to precisely such assumptions There is one technical issue which deserves to be noted. We are assuming that"actions e measurable with respect to types, to use a conventional expression; that is, whenever w, w'e ti E Ti, the action chosen by Player i at w has to be the same as the action she chooses at w. This is natural: after all, in any given state, a player only knows her type, so it would be impossible for her to implement a contingent action plan which specifies different choices at different states consistent with her type. Our definition of a frame captures this Putting the model to work sider one concrete example to fix ideas. Fi exhibits a game and a model for
The basic idea Recall that, in order to represent payoff uncertainty, we introduced a set Ω of states of the world, and made the players’ payoff functions depend on the realization ω ∈ Ω, as well as on the profile (ai)i∈N ∈ Q i∈N Ai of actions chosen by the players. This allowed us to represent hierarchical beliefs about the state of the world; however, we are no more capable of describing hierarchical beliefs about actions (at least not without introducing additional information, such as a specification of equilibrium actions for each type of each player). Thus, a natural extension suggests itself. For simplicity, I will consider games without payoff uncertainty, but the extension should be obvious. Definition 1 Consider a simultaneous game G = (N,(Ai , ui)i∈N ) (without payoff uncertainty). 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 map ai : Ω → Ai such that a −1 i (ai) 6= ∅ ⇒ a −1 i (ai) ∈ Ti . Continue to denote by ti(ω) the cell of the partition Ti containing ω. Finally, 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 ∆(Ω). I distinguish between frames and models to emphasize that probabilistic beliefs convey additional information—which we wish to relate to solution concepts. The distintion is also often made in the literature. The main innovation is the introduction of the functions ai(·). This is not so far-fetched: after all, uncertainty about opponents’ actions is clearly a form of payoff uncertainty—one that arises in any strategic situation. However, by making players’ choices part of the state of the world, it is possible to discuss the players’ hierarchical beliefs about them. Ultimately, we wish to relate solution concepts to precisely such assumptions. There is one technical issue which deserves to be noted. We are assuming that “actions be measurable with respect to types,” to use a conventional expression; that is, whenever ω, ω0 ∈ ti ∈ Ti , the action chosen by Player i at ω has to be the same as the action she chooses at ω 0 . This is natural: after all, in any given state, a player only knows her type, so it would be impossible for her to implement a contingent action plan which specifies different choices at different states consistent with her type. Our definition of a frame captures this. Putting the model to work Let us consider one concrete example to fix ideas. Figure 1 exhibits a game and a model for it. 2
L R t1(w) al(w) pl(w) t2(w)a2(w)p2(w t1 0 22 R 0.4 ,10.0 B0.0 tiT 0 L 0.5 B Figure 1: A game and a model for it The right-hand table includes all the information required by Definition 1. In particular note that it implicitly defines the partitions Ti, i=1, 2, via the possibility correspondences As previously advertised, at each state w E S2 in a model, players actions and beliefs are completely specified. For instance, at wl, the profile(t, R)is played, Player 1 is certain that Player 2 chooses L (note that this belief is incorrect), and Player 2 is certain that Player 1 chooses T(which is a correct belief). Thus, given their beliefs, Player 1 is rational (T is a best reply to L) and Player 2 is not(R is not a best reply to T c. Moreover, note that, at w2, Player 2 believes that the state is w2(hence, that Player 1 nooses T) with probability and that it is w(hence, that Player 1 chooses B with probability & At w2 Player 2 chooses L, which is her unique best reply given her beliefs Thus, we can also say that at wn Player 1 assigns probability one to the event that the state is really w2, and hence that (i) Player 2s beliefs about Player 1's actions are given b (T: 6. B); and that(i)Player 2 chooses L. Thus, at w Player 1 is"certain"that Player 2 is rational. Of course, note that at w/ Player 2 is really not rational We can push this quite a bit further. For instance, type t? of Player 2 assigns probability d to w3, a state in which Player 1 is not rational (she is certain that the state is w3, hence that Player 2 chooses L, but she plays B). Hence, at wl, Player 1 is"certain"that Player 2 assigns probability 6 to the"event "that she (i) believes that 2 chooses L, and (i) play B-hence. she is not rational. this is a statement involving three orders of beliefs it also corresponds to an incorrect belief: at wl, Player 2 is certain that Player 1 chooses T and is of type tl-hence, that she is rational! We are ready for formal definitions of "rationality"and"certainty "Recall that, given any belief a-i E A(A-i) for Player i, ri(a-i) is the set of best replies for i given a-i First, a preliminary notion Definition 2 Fix a game G=(N, (Ai, uiieN) and a model M=( Q, (Ti, ai, pilieN) for G The first-order beliefs function a-i: Q-A(A-i for Player i is defined by vu∈9,a-i∈A-:a-()(a-)=p1({u:Wj≠i,a(u)=a3H(u) That is, the probability of a profile a_i E A-i is given by the(conditional) probability of all states where that profile is played. Notice that the function a-i( is T--measurable, just like ai(). Also note that this is a belief about players jti, held by player i
L R T 1,1 0,0 B 0,0 1,1 ω t1(ω) a1(ω) p1(ω) t2(ω) a2(ω) p2(ω) ω1 t 1 1 T 0 t 1 2 R 0.4 ω2 t 1 1 T 0.5 t 2 2 L 0.5 ω3 t 2 1 B 0.5 t 2 2 L 0.1 Figure 1: A game and a model for it The right-hand table includes all the information required by Definition 1. In particular, note that it implicitly defines the partitions Ti , i = 1, 2, via the possibility correspondences ti : Ω ⇒ Ω. As previously advertised, at each state ω ∈ Ω in a model, players’ actions and beliefs are completely specified. For instance, at ω1, the profile (T,R) is played, Player 1 is certain that Player 2 chooses L (note that this belief is incorrect), and Player 2 is certain that Player 1 chooses T (which is a correct belief). Thus, given their beliefs, Player 1 is rational (T is a best reply to L) and Player 2 is not (R is not a best reply to T). Moreover, note that, at ω2, Player 2 believes that the state is ω2 (hence, that Player 1 chooses T) with probability 0.5 0.5+0.1 = 5 6 , and that it is ω3 (hence, that Player 1 chooses B) with probability 1 6 . At ω2 Player 2 chooses L, which is her unique best reply given her beliefs. Thus, we can also say that at ω1 Player 1 assigns probability one to the event that the state is really ω2, and hence that (i) Player 2’s beliefs about Player 1’s actions are given by ( 5 6 ,T; 1 6 ,B); and that (ii) Player 2 chooses L. Thus, at ω1 Player 1 is “certain” that Player 2 is rational. Of course, note that at ω1 Player 2 is really not rational! We can push this quite a bit further. For instance, type t 2 2 of Player 2 assigns probability 1 6 to ω3, a state in which Player 1 is not rational (she is certain that the state is ω3, hence that Player 2 chooses L, but she plays B). Hence, at ω1, Player 1 is “certain” that Player 2 assigns probability 1 6 to the “event” that she (i) believes that 2 chooses L, and (ii) plays B—hence, she is not rational. This is a statement involving three orders of beliefs. It also corresponds to an incorrect belief: at ω1, Player 2 is certain that Player 1 chooses T and is of type t 1 1—hence, that she is rational! We are ready for formal definitions of “rationality” and “certainty.” Recall that, given any belief α−i ∈ ∆(A−i) for Player i, ri(α−i) is the set of best replies for i given α−i . First, a preliminary notion: Definition 2 Fix a game G = (N,(Ai , ui)i∈N ) and a model M = (Ω,(Ti , ai , pi)i∈N ) for G. The first-order beliefs function α−i : Ω → ∆(A−i) for Player i is defined by ∀ω ∈ Ω, a−i ∈ A−i : α−i(ω)(a−i) = pi ({ω 0 : ∀j 6= i, aj (ω 0 ) = aj}|ti(ω)) That is, the probability of a profile a−i ∈ A−i is given by the (conditional) probability of all states where that profile is played. Notice that the function α−i(·) is Ti-measurable, just like ai(·). Also note that this is a belief about players j 6= i, held by player i. 3
Definition 3 Fix a game G=(N, (Ai, uiieN) and a model M=(Q, (Ti, ai, pilieN) for G A player i E I is deemed rational at state w E Q iff a(w)E_i(w)). Define the event Player i is rational"b R1={u∈9:a(u)∈r(a-l(u)} and the event, "Every player is rational"by R= nien ri This is quite straightforward. Finally, adapting the definition we gave last time Definition 4 Fix a game G=(N, (Ai, ui)ieN) and a model M=(@2, (Ti, ai, piie) for G Player i's belief operator is the map Bi: 23-22 defined by VEc9,B1(E)={∈9:(E|t(u)=1} Also define the event, "Everybody is certain that E is true "by B(e)=nien Bi(e) The following shorthand definitions are also convenient vi∈N,q∈△(A-):[a-i=q={u:a-(u)=q} which extends our previous notation, and vi∈N,a1∈A:[a;=al={u:a(u)=a} We now have a rather powerful and concise language to describe strategic reasoning in games. For instance, the following relations summarize our discussion of Figure 1 u1∈B1(a2=L])∩B2(a1=T); and also, more interestingly ∈R1;w∈R2;∈B1(B2) In fact ∈9\B2(B1);a1∈B1(9\B2(R1) Notice that we are finally able to give formal content to statements such as "Player 1 is certain that Player 2 is rational". These correspond to events in a given model, which in turn represents well-defined hierarchies of beliefs I conclude by noting a few properties of belief operators Proposition 0.1 Fix a game G=(N, (Ai, uiieN) and a model M=(Q2, (Ti, ai, pi)ieN)for G.Then, for every i∈N: (1)t=B2(t) (2)EC F implies Bi(E)C Bi(F); (3)B(EnF)=B(E)∩B(F) (4)Bi (E)C B(B(E)) and 2\ B(E)C Bi(Q\B(E)): (5)R2CB2(R)
Definition 3 Fix a game G = (N,(Ai , ui)i∈N ) and a model M = (Ω,(Ti , ai , pi)i∈N ) for G. A player i ∈ I is deemed rational at state ω ∈ Ω iff ai(ω) ∈ ri(α−i(ω)). 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 . This is quite straightforward. Finally, adapting the definition we gave last time: Definition 4 Fix a game G = (N,(Ai , ui)i∈N ) and a model M = (Ω,(Ti , ai , pi)i∈N ) for G. Player i’s belief operator is the map Bi : 2Ω → 2 Ω defined by ∀E ⊂ Ω, Bi(E) = {ω ∈ Ω : pi(E|ti(ω)) = 1}. Also define the event, “Everybody is certain that E is true” by B(E) = T i∈N Bi(E). The following shorthand definitions are also convenient: ∀i ∈ N, q ∈ ∆(A−i) : [α−i = q] = {ω : α−i(ω) = q} which extends our previous notation, and ∀i ∈ N, ai ∈ Ai : [ai = ai ] = {ω : ai(ω) = ai} We now have a rather powerful and concise language to describe strategic reasoning in games. For instance, the following relations summarize our discussion of Figure 1: ω1 ∈ B1([a2 = L]) ∩ B2([a1 = T]); and also, more interestingly: ω1 ∈ R1; ω2 ∈ R2; ω1 ∈ B1(R2). In fact: ω2 ∈ Ω \ B2(R1); ω1 ∈ B1(Ω \ B2(R1)). Notice that we are finally able to give formal content to statements such as “Player 1 is certain that Player 2 is rational”. These correspond to events in a given model, which in turn represents well-defined hierarchies of beliefs. I conclude by noting a few properties of belief operators. Proposition 0.1 Fix a game G = (N,(Ai , ui)i∈N ) and a model M = (Ω,(Ti , ai , pi)i∈N ) for G. Then, for every i ∈ N: (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). 4
Correlated Equilibrium As a first application of this formalism, I will provide a characterization of the notion of correlated equilibrium, due to R.Aumann I have already argued that the fact that players choose their actions independently of each other does not imply that beliefs should necessarily be stochastically independent(recall the " betting on coordination"game). Correlated equilibrium provides a way to allow for correlated beliefs that is consistent with the equilibrium approach Definition 5 Fix a game G=(N, (Ai, ui)ieN). A correlated equilibrium of G is a probability distribution a E A(A) such that, for every player iE N, and every function di: Ai ∑a2(a1-)a(a,a-)≥∑ (aa,a-a)∈A (aa,a-1)∈A The above is the standard definition of correlated equilibrium. However Proposition 0.2 Fix a game=(N, (Ai, ui)ieN) and a probability distribution a E A(A) Then a is a correlated equilibrium of G iff, for any player i E N and action a; E Ai such that a({a}×A-)>0, and for all a∈A, ∑(an,a-)a(a-la)≥∑ta,a-)a(a-lan) a-;∈A- a-;∈A- where a(a_ilai=a(ai,a-i] x A-i Proof: Fix a player i E N. Observe first that, for any function f: Ai-Ais ∑a2(f(a,a-)a(a12a-)=∑∑at(f(a),a-)a(a,a-)= (a1,a-)∈A a∈A1a-i∈A ∑a({a}×A-)∑at(f(a),a-)a(a-la aa({a}×A-i)>0 a-i∈A- Suppose first that there exists an action ai E Ai with adlai)x A-i)>0 such that ∑a∈A,1(a,a-)a(a-l|a)<∑a∈A,(,a-)a(a-la1). Then the function d,:A A: defined by di(ai)=a' and di(ai= ai for all ait a constitutes a profitable er-ante deviation(see the above observation), so a cannot be a correlated equilibrium Conversely, suppose that the above inequality holds for all ai and a; as in the claim Now consider any function d,:A→A; by assumption,∑a∈A,t(a2,a-)a(a-lan)≥ 2ai ea_ ui(di(ai),a-i)a(a-ilai)for any ai such that a(lai] x A-i)>0. The claim follows from our initial observation
Correlated Equilibrium As a first application of this formalism, I will provide a characterization of the notion of correlated equilibrium, due to R. Aumann. I have already argued that the fact that players choose their actions independently of each other does not imply that beliefs should necessarily be stochastically independent (recall the “betting on coordination” game). Correlated equilibrium provides a way to allow for correlated beliefs that is consistent with the equilibrium approach. Definition 5 Fix a game G = (N,(Ai , ui)i∈N ). A correlated equilibrium of G is a probability distribution α ∈ ∆(A) such that, for every player i ∈ N, and every function di : Ai → Ai , X (ai,a−i)∈A ui(ai , a−i)α(ai , a−i) ≥ X (ai,a−i)∈A ui(di(ai), a−i)α(ai , a−i) The above is the standard definition of correlated equilibrium. However: Proposition 0.2 Fix a game G = (N,(Ai , ui)i∈N ) and a probability distribution α ∈ ∆(A). Then α is a correlated equilibrium of G iff, for any player i ∈ N and action ai ∈ Ai such that α({ai} × A−i) > 0, and for all a 0 i ∈ Ai , X a−i∈A−i ui(ai , a−i)α(a−i |ai) ≥ X a−i∈A−i ui(a 0 i , a−i)α(a−i |ai) where α(a−i |ai) = α({ai , a−i}|{ai} × A−i). Proof: Fix a player i ∈ N. Observe first that, for any function f : Ai → Ai , X (ai,a−i)∈A ui(f(ai), a−i)α(ai , a−i) = X ai∈Ai X a−i∈A−i ui(f(ai), a−i)α(ai , a−i) = = X ai:α({ai}×A−i)>0 α({ai} × A−i) X a−i∈A−i ui(f(ai), a−i)α(a−i |ai) P Suppose first that there exists an action a¯i ∈ Ai with α({a¯i} × A−i) > 0 such that a−i∈A−i ui(¯ai , a−i)α(a−i |a¯i) < P a−i∈A−i ui(a 0 i , a−i)α(a−i |a¯i). Then the function di : Ai → Ai defined by di(¯ai) = a 0 i and di(ai) = ai for all ai 6= ¯a constitutes a profitable ex-ante deviation (see the above observation), so α cannot be a correlated equilibrium. Conversely, suppose that the above inequality holds for all ai and a 0 i as in the claim. Now consider any function di : Ai → Ai : by assumption, P a−i∈A−i ui(ai , a−i)α(a−i |ai) ≥ P a−i∈A−i ui(di(ai), a−i)α(a−i |ai) for any ai such that α({ai} × A−i) > 0. The claim follows from our initial observation. 5