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 restric-
tions 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 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
both Player 2’s actions and her beliefs.
The standard model for games with complete information does not contain enough struc-
ture for us to formalize this sort of assumption,Players’ beliefs are probability distributions
on their opponents’ action pro les.
But,of course,the model we have developed (following Harsanyi) for games with payo
uncertainty does allow us to generate beliefs about beliefs,and indeed in nite hierarchies of
mutual beliefs.
The objective of this lecture is to present a model of interactive beliefs based on Harsanyi’s
ideas,with minimal modi cations to our setting for games with payo 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 payo uncertainty,we introduced a set of states of the
world,and made the players’ payo functions depend on the realization !2,as well as
on the pro le (ai)i2N 2Qi2N 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 speci cation of equilibrium actions for each
type of each player).
Thus,a natural extension suggests itself,For simplicity,I will consider games without
payo uncertainty,but the extension should be obvious.
De nition 1 Consider a simultaneous game G = (N;(Ai;ui)i2N) (without payo uncer-
tainty),A frame for G is a tupleF = ( ;(Ti;ai)i2N) such that,for every player i2N,Ti is
a partition of,and ai is a map ai,!Ai such that
a 1i (ai)6=; ) a 1i (ai)2Ti:
Continue to denote by ti(!) the cell of the partition Ti containing !,Finally,a model for G is
a tupleM= (F;(pi)i2N),whereF 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 payo 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 2 ti 2 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 speci es di erent
choices at di erent states consistent with her type,Our de nition of a frame captures this.
Putting the model to work
Let us consider one concrete example to x ideas,Figure 1 exhibits a game and a model for
it.
2
L R
T 1,1 0,0
B 0,0 1,1
! t1(!) a1(!) p1(!) t2(!) a2(!) p2(!)
!1 t11 T 0 t12 R 0.4
!2 t11 T 0.5 t22 L 0.5
!3 t21 B 0.5 t22 L 0.1
Figure 1,A game and a model for it
The right-hand table includes all the information required by De nition 1,In particular,
note that it implicitly de nes the partitions Ti,i = 1;2,via the possibility correspondences
ti,),
As previously advertised,at each state !2 in a model,players’ actions and beliefs are
completely speci ed,For instance,at !1,the pro le (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:50:5+0:1 = 56,and that it is !3 (hence,that Player 1 chooses B)
with probability 16,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
(56,T; 16,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 t22 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,hencethat Player 2 chooses L,but she plays B),Hence,at !
1,Player 1 is \certain" that Player
2 assigns probability 16 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 t11|hence,that she is rational!
We are ready for formal de nitions of \rationality" and \certainty." Recall that,given
any belief i2 (A i) for Player i,ri( i) is the set of best replies for i given i.
First,a preliminary notion:
De nition 2 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N) for G.
The rst-order beliefs function i,! (A i) for Player i is de ned by
8!2 ; a i2A i,i(!)(a i) = pi (f!0,8j6= i;aj(!0) = ajgjti(!))
That is,the probability of a pro le a i2A i is given by the (conditional) probability of
all states where that pro le is played,Notice that the function i( ) is Ti-measurable,just
like ai( ),Also note that this is a belief about players j6= i,held by player i.
3
De nition 3 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N) for G.
A player i2I is deemed rational at state !2 i ai(!) 2ri( i(!)),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.
This is quite straightforward,Finally,adapting the de nition we gave last time:
De nition 4 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N) for G.
Player i’s belief operator is the map Bi,2 !2 de ned by
8E ; Bi(E) =f!2,pi(Ejti(!)) = 1g:
Also de ne the event,\Everybody is certain that E is true" by B(E) = Ti2N Bi(E).
The following shorthand de nitions are also convenient:
8i2N; q2 (A i),[ i = q] =f!,i(!) = qg
which extends our previous notation,and
8i2N;ai2Ai,[ai = ai] =f!,ai(!) = aig
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 2B1([a2 = L])\B2([a1 = T]);
and also,more interestingly:
!1 2R1; !2 2R2; !1 2B1(R2):
In fact:
!2 2 nB2(R1); !1 2B1( nB2(R1)):
Notice that we are nally 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-de ned hierarchies of beliefs.
I conclude by noting a few properties of belief operators.
Proposition 0.1 Fix a game G = (N;(Ai;ui)i2N) and a model M= ( ;(Ti;ai;pi)i2N) for
G,Then,for every i2N:
(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).
4
Correlated Equilibrium
As a rst 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.
De nition 5 Fix a gameG = (N;(Ai;ui)i2N),A correlated equilibrium ofGis a probability
distribution 2 (A) such that,for every player i2N,and every function di,Ai!Ai,
X
(ai;a i)2A
ui(ai;a i) (ai;a i)
X
(ai;a i)2A
ui(di(ai);a i) (ai;a i)
The above is the standard de nition of correlated equilibrium,However:
Proposition 0.2 Fix a game G = (N;(Ai;ui)i2N) and a probability distribution 2 (A).
Then is a correlated equilibrium of G i,for any player i2N and action ai 2Ai such
that (faig A i) > 0,and for all a0i2Ai,
X
a i2A i
ui(ai;a i) (a ijai)
X
a i2A i
ui(a0i;a i) (a ijai)
where (a ijai) = (fai;a igjfaig A i).
Proof,Fix a player i2N,Observe rst that,for any function f,Ai!Ai,
X
(ai;a i)2A
ui(f(ai);a i) (ai;a i) =
X
ai2Ai
X
a i2A i
ui(f(ai);a i) (ai;a i) =
=
X
ai,(faig A i)>0
(faig A i)
X
a i2A i
ui(f(ai);a i) (a ijai)
Suppose rst that there exists an action ai 2 Ai with (f aig A i) > 0 such thatP
a i2A iui( ai;a i) (a ij ai) <
P
a i2A iui(a
0
i;a i) (a ij ai),Then the function di,Ai !
Ai de ned by di( ai) = a0i and di(ai) = ai for all ai 6= a constitutes a pro table ex-ante
deviation (see the above observation),so cannot be a correlated equilibrium.
Conversely,suppose that the above inequality holds for all ai and a0i as in the claim.
Now consider any function di,Ai ! Ai,by assumption,Pa i2A iui(ai;a i) (a ijai) P
a i2A iui(di(ai);a i) (a ijai) for any ai such that (faig A i) > 0,The claim follows
from our initial observation.
5
Proposition 0.2 draws a connection between the notions of Nash and Correlated equi-
librium,recall that,in the former,an action receives positive probability i it is a best
response to the equilibrium belief,Note also that,if 2 (A) is an independent probability
distribution,(a ijai) = i(a i),the marginal of on A i,for all ai 2Ai,Thus,every
Nash equilibrium is a correlated equilibrium.
Moreover,Proposition 0.2 reinforces our interpretation of correlated equilibrium as an
attempt to depart from independence of beliefs,while remaining rmly within an equilibrium
setting.
The rst step in the epistemic characterization of correlated equilibrium is actually
prompted by a more basic question,The story that is most often heard to justify corre-
lated equilibrium runs along the following lines,the players bring in an outside observer
who randomizes according to the distribution and prescribes an action to each player.
De nition 5 then essentially requires that the players nd it pro table ex-ante to follow
the prescription rather than adopt any alternative prescription-contingent plan (i.e,\if the
observer tells me to do X,I shall do Y instead"),Proposition 0.2 shows that this is equivalent
to assuming that,upon receiving a prescription,players do not gain by deviating to any other
action.
The basic question that should have occurred to you is whether a richer \communication
structure" allows for more coordination opportunities|i.e,whether there exists expected
payo vectors which may be achieved using a richer structure,but may not be achieved when
messages are limited to action prescriptions.
The answer to this question is actually negative,as follows from a simple application
of the Revelation principle,However,the point is that frames may also be used to de ne
correlated equilibria in this extended sense.
De nition 6 Fix a game G = (N;(Ai;ui)i2N),An extended correlated equilibrium is a
tuple (F; ) where:
(1) F = ( ;(Ti;ai)i2N) is a frame for G;
(2) 2 ( ) is a probability over such that,for all i2N and ti2Ti,(ti) > 0;
(3) for every player i2N and ti2Ti,
X
!2
ui(ai(!);(aj(!))j6=i) (!jti)
X
!2
ui(a0i;(aj(!))j6=i) (!jti)
for all a0i2Ai.
The similarity between (3) and Proposition 0.2 should be obvious.
Note that the formal de nition of a frame in an extended correlated equilibrium is as in
De nition 1,However,the standard interpretation is di erent,the cells ti 2Ti represent
possible messages that the observer may send to Player i; since the action functions ai( ) are
6
Ti-measurable by the de nition of a frame,they represent message-contingent action plans;
nally,and model an abstract,general randomizing (or \correlating") device,The idea
is that,upon observing !2,the outside observer sends the message ti(!) to every Player
i2N.
It is clear that every correlated equilibrium according to De nition 5 can be interpreted
as an extended correlated equilibrium as per De nition 6,let = supp,i.e,the set of
action pro les that get played in equilibrium; then de ne type partitions indirectly,via the
possibility correspondence,assuming that,at each state ! = (ai;a i) 2,Player i is told
what her action must be:
ti(ai;a i) =faig fa0 i,(ai;a0 i)2supp g:
Since ti(ai;a i) actually depends on ai only,I denote this type by taii,Finally,let ai(ai;a i) =
ai and =,With these de nitions,note that,for every ai 2 Ai,and for every ! =
(ai;a i) 2 taii,ai(!) = ai and (!jtaii ) = (a ijai),This implies that (3) in De nition 6
must hold.
By the Revelation principle,the converse is also true,Intuitively,instead of sending the
message ti(!) to Player i whenever ! is realized,the outside observer could simply instruct
Player i to play ai(!),If it was unpro table to deviate from ai(!) in the original messaging
setting,then it must be unpro table to do so in the simpli ed game as well.
Formally,given an extended correlated equilibrium (F; ),de ne
(a) = (f!,8i2N;ai(!) = aig);
now observe that,for any ai2Ai,(faig A i) > 0 i there exists a (maximal) collection of
types t1i;:::;tKi 2Ti such that,at all states !2SKk=1 tki,ai(!) = ai,Now (3) in De nition
6 implies that
X
!2
ui(ai;(aj(!))j6=i) (!j
K[
k=1
tki )
X
!2
ui(a0i;(aj(!))j6=i) (!j
K[
k=1
tki )
for all a0i2Ai,because all types have positive probability,We can clearly rewrite the above
summations as follows:
X
a i2A i
ui(ai;a i) (
\
j6=i
[aj = aj]j
K[
k=1
tki )
X
a i2A i
ui(a0i;a i) (
\
j6=i
[aj = aj]j
K[
k=1
tki )
and since (Tj6=i[aj = aj]jSKk=1tki ) = (a ijai) by construction,is a correlated equilibrium
according to Proposition 0.2.
7
The bottom line is that we can actually take De nition 6 as our basic notion of correlated
equilibrium (OR does this,for example),there is no added generality.
But then we get an epistemic characterization of correlated equilibrium almost for free.
Observe that Condition (3) in De nition 6 implies that,at each state ! 2 ti,Player i’s
action ai(!) is a best response to her rst-order beliefs,given by i(!)(a i) = (f!0,8j6=
i;aj(!0) = ajgjti(!)),Hence,if we reinterpret an extended correlated equilibrium (F; ) as
a model M= (F;(pi)i2N) in which pi = for all i2N,we get:
Proposition 0.3 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N)
for G,If there exists 2 ( ) such that pi = for all i 2 N,and R =,then
(( ;(Ti;ai)i2N); ) is an extended correlated equilibrium of G.
Conversely,if is a correlated equilibrium ofG,there exists a modelM= ( ;(Ti;ai;pi)i2N)
for G in which = R.
The model alluded to in the second part of the Proposition is of course the one constructed
above,Observe that in that model is indeed a common prior.
You may feel a bit cheated by this result,After all,it seems all we have done is change
our interpretation of the relevant objects,This is of course entirely correct!
It is certainly the case that Proposition 0.3 characterizes correlated equilibrium beliefs.
More precisely,a distribution over action pro les is a correlated equilibrium belief if it is a
common prior in a model with the feature that every player is rational at every state.
As I have mentioned several times,this may or may not have any behavioral implications,
but at least Proposition 0.3 provides an arguably more palatable rationale for correlated
equilibrium beliefs than the \outside observer" story.
8
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 restric-
tions 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 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
both Player 2’s actions and her beliefs.
The standard model for games with complete information does not contain enough struc-
ture for us to formalize this sort of assumption,Players’ beliefs are probability distributions
on their opponents’ action pro les.
But,of course,the model we have developed (following Harsanyi) for games with payo
uncertainty does allow us to generate beliefs about beliefs,and indeed in nite hierarchies of
mutual beliefs.
The objective of this lecture is to present a model of interactive beliefs based on Harsanyi’s
ideas,with minimal modi cations to our setting for games with payo 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 payo uncertainty,we introduced a set of states of the
world,and made the players’ payo functions depend on the realization !2,as well as
on the pro le (ai)i2N 2Qi2N 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 speci cation of equilibrium actions for each
type of each player).
Thus,a natural extension suggests itself,For simplicity,I will consider games without
payo uncertainty,but the extension should be obvious.
De nition 1 Consider a simultaneous game G = (N;(Ai;ui)i2N) (without payo uncer-
tainty),A frame for G is a tupleF = ( ;(Ti;ai)i2N) such that,for every player i2N,Ti is
a partition of,and ai is a map ai,!Ai such that
a 1i (ai)6=; ) a 1i (ai)2Ti:
Continue to denote by ti(!) the cell of the partition Ti containing !,Finally,a model for G is
a tupleM= (F;(pi)i2N),whereF 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 payo 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 2 ti 2 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 speci es di erent
choices at di erent states consistent with her type,Our de nition of a frame captures this.
Putting the model to work
Let us consider one concrete example to x ideas,Figure 1 exhibits a game and a model for
it.
2
L R
T 1,1 0,0
B 0,0 1,1
! t1(!) a1(!) p1(!) t2(!) a2(!) p2(!)
!1 t11 T 0 t12 R 0.4
!2 t11 T 0.5 t22 L 0.5
!3 t21 B 0.5 t22 L 0.1
Figure 1,A game and a model for it
The right-hand table includes all the information required by De nition 1,In particular,
note that it implicitly de nes the partitions Ti,i = 1;2,via the possibility correspondences
ti,),
As previously advertised,at each state !2 in a model,players’ actions and beliefs are
completely speci ed,For instance,at !1,the pro le (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:50:5+0:1 = 56,and that it is !3 (hence,that Player 1 chooses B)
with probability 16,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
(56,T; 16,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 t22 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,hencethat Player 2 chooses L,but she plays B),Hence,at !
1,Player 1 is \certain" that Player
2 assigns probability 16 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 t11|hence,that she is rational!
We are ready for formal de nitions of \rationality" and \certainty." Recall that,given
any belief i2 (A i) for Player i,ri( i) is the set of best replies for i given i.
First,a preliminary notion:
De nition 2 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N) for G.
The rst-order beliefs function i,! (A i) for Player i is de ned by
8!2 ; a i2A i,i(!)(a i) = pi (f!0,8j6= i;aj(!0) = ajgjti(!))
That is,the probability of a pro le a i2A i is given by the (conditional) probability of
all states where that pro le is played,Notice that the function i( ) is Ti-measurable,just
like ai( ),Also note that this is a belief about players j6= i,held by player i.
3
De nition 3 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N) for G.
A player i2I is deemed rational at state !2 i ai(!) 2ri( i(!)),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.
This is quite straightforward,Finally,adapting the de nition we gave last time:
De nition 4 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N) for G.
Player i’s belief operator is the map Bi,2 !2 de ned by
8E ; Bi(E) =f!2,pi(Ejti(!)) = 1g:
Also de ne the event,\Everybody is certain that E is true" by B(E) = Ti2N Bi(E).
The following shorthand de nitions are also convenient:
8i2N; q2 (A i),[ i = q] =f!,i(!) = qg
which extends our previous notation,and
8i2N;ai2Ai,[ai = ai] =f!,ai(!) = aig
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 2B1([a2 = L])\B2([a1 = T]);
and also,more interestingly:
!1 2R1; !2 2R2; !1 2B1(R2):
In fact:
!2 2 nB2(R1); !1 2B1( nB2(R1)):
Notice that we are nally 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-de ned hierarchies of beliefs.
I conclude by noting a few properties of belief operators.
Proposition 0.1 Fix a game G = (N;(Ai;ui)i2N) and a model M= ( ;(Ti;ai;pi)i2N) for
G,Then,for every i2N:
(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).
4
Correlated Equilibrium
As a rst 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.
De nition 5 Fix a gameG = (N;(Ai;ui)i2N),A correlated equilibrium ofGis a probability
distribution 2 (A) such that,for every player i2N,and every function di,Ai!Ai,
X
(ai;a i)2A
ui(ai;a i) (ai;a i)
X
(ai;a i)2A
ui(di(ai);a i) (ai;a i)
The above is the standard de nition of correlated equilibrium,However:
Proposition 0.2 Fix a game G = (N;(Ai;ui)i2N) and a probability distribution 2 (A).
Then is a correlated equilibrium of G i,for any player i2N and action ai 2Ai such
that (faig A i) > 0,and for all a0i2Ai,
X
a i2A i
ui(ai;a i) (a ijai)
X
a i2A i
ui(a0i;a i) (a ijai)
where (a ijai) = (fai;a igjfaig A i).
Proof,Fix a player i2N,Observe rst that,for any function f,Ai!Ai,
X
(ai;a i)2A
ui(f(ai);a i) (ai;a i) =
X
ai2Ai
X
a i2A i
ui(f(ai);a i) (ai;a i) =
=
X
ai,(faig A i)>0
(faig A i)
X
a i2A i
ui(f(ai);a i) (a ijai)
Suppose rst that there exists an action ai 2 Ai with (f aig A i) > 0 such thatP
a i2A iui( ai;a i) (a ij ai) <
P
a i2A iui(a
0
i;a i) (a ij ai),Then the function di,Ai !
Ai de ned by di( ai) = a0i and di(ai) = ai for all ai 6= a constitutes a pro table ex-ante
deviation (see the above observation),so cannot be a correlated equilibrium.
Conversely,suppose that the above inequality holds for all ai and a0i as in the claim.
Now consider any function di,Ai ! Ai,by assumption,Pa i2A iui(ai;a i) (a ijai) P
a i2A iui(di(ai);a i) (a ijai) for any ai such that (faig A i) > 0,The claim follows
from our initial observation.
5
Proposition 0.2 draws a connection between the notions of Nash and Correlated equi-
librium,recall that,in the former,an action receives positive probability i it is a best
response to the equilibrium belief,Note also that,if 2 (A) is an independent probability
distribution,(a ijai) = i(a i),the marginal of on A i,for all ai 2Ai,Thus,every
Nash equilibrium is a correlated equilibrium.
Moreover,Proposition 0.2 reinforces our interpretation of correlated equilibrium as an
attempt to depart from independence of beliefs,while remaining rmly within an equilibrium
setting.
The rst step in the epistemic characterization of correlated equilibrium is actually
prompted by a more basic question,The story that is most often heard to justify corre-
lated equilibrium runs along the following lines,the players bring in an outside observer
who randomizes according to the distribution and prescribes an action to each player.
De nition 5 then essentially requires that the players nd it pro table ex-ante to follow
the prescription rather than adopt any alternative prescription-contingent plan (i.e,\if the
observer tells me to do X,I shall do Y instead"),Proposition 0.2 shows that this is equivalent
to assuming that,upon receiving a prescription,players do not gain by deviating to any other
action.
The basic question that should have occurred to you is whether a richer \communication
structure" allows for more coordination opportunities|i.e,whether there exists expected
payo vectors which may be achieved using a richer structure,but may not be achieved when
messages are limited to action prescriptions.
The answer to this question is actually negative,as follows from a simple application
of the Revelation principle,However,the point is that frames may also be used to de ne
correlated equilibria in this extended sense.
De nition 6 Fix a game G = (N;(Ai;ui)i2N),An extended correlated equilibrium is a
tuple (F; ) where:
(1) F = ( ;(Ti;ai)i2N) is a frame for G;
(2) 2 ( ) is a probability over such that,for all i2N and ti2Ti,(ti) > 0;
(3) for every player i2N and ti2Ti,
X
!2
ui(ai(!);(aj(!))j6=i) (!jti)
X
!2
ui(a0i;(aj(!))j6=i) (!jti)
for all a0i2Ai.
The similarity between (3) and Proposition 0.2 should be obvious.
Note that the formal de nition of a frame in an extended correlated equilibrium is as in
De nition 1,However,the standard interpretation is di erent,the cells ti 2Ti represent
possible messages that the observer may send to Player i; since the action functions ai( ) are
6
Ti-measurable by the de nition of a frame,they represent message-contingent action plans;
nally,and model an abstract,general randomizing (or \correlating") device,The idea
is that,upon observing !2,the outside observer sends the message ti(!) to every Player
i2N.
It is clear that every correlated equilibrium according to De nition 5 can be interpreted
as an extended correlated equilibrium as per De nition 6,let = supp,i.e,the set of
action pro les that get played in equilibrium; then de ne type partitions indirectly,via the
possibility correspondence,assuming that,at each state ! = (ai;a i) 2,Player i is told
what her action must be:
ti(ai;a i) =faig fa0 i,(ai;a0 i)2supp g:
Since ti(ai;a i) actually depends on ai only,I denote this type by taii,Finally,let ai(ai;a i) =
ai and =,With these de nitions,note that,for every ai 2 Ai,and for every ! =
(ai;a i) 2 taii,ai(!) = ai and (!jtaii ) = (a ijai),This implies that (3) in De nition 6
must hold.
By the Revelation principle,the converse is also true,Intuitively,instead of sending the
message ti(!) to Player i whenever ! is realized,the outside observer could simply instruct
Player i to play ai(!),If it was unpro table to deviate from ai(!) in the original messaging
setting,then it must be unpro table to do so in the simpli ed game as well.
Formally,given an extended correlated equilibrium (F; ),de ne
(a) = (f!,8i2N;ai(!) = aig);
now observe that,for any ai2Ai,(faig A i) > 0 i there exists a (maximal) collection of
types t1i;:::;tKi 2Ti such that,at all states !2SKk=1 tki,ai(!) = ai,Now (3) in De nition
6 implies that
X
!2
ui(ai;(aj(!))j6=i) (!j
K[
k=1
tki )
X
!2
ui(a0i;(aj(!))j6=i) (!j
K[
k=1
tki )
for all a0i2Ai,because all types have positive probability,We can clearly rewrite the above
summations as follows:
X
a i2A i
ui(ai;a i) (
\
j6=i
[aj = aj]j
K[
k=1
tki )
X
a i2A i
ui(a0i;a i) (
\
j6=i
[aj = aj]j
K[
k=1
tki )
and since (Tj6=i[aj = aj]jSKk=1tki ) = (a ijai) by construction,is a correlated equilibrium
according to Proposition 0.2.
7
The bottom line is that we can actually take De nition 6 as our basic notion of correlated
equilibrium (OR does this,for example),there is no added generality.
But then we get an epistemic characterization of correlated equilibrium almost for free.
Observe that Condition (3) in De nition 6 implies that,at each state ! 2 ti,Player i’s
action ai(!) is a best response to her rst-order beliefs,given by i(!)(a i) = (f!0,8j6=
i;aj(!0) = ajgjti(!)),Hence,if we reinterpret an extended correlated equilibrium (F; ) as
a model M= (F;(pi)i2N) in which pi = for all i2N,we get:
Proposition 0.3 Fix a game G = (N;(Ai;ui)i2N) and a model M = ( ;(Ti;ai;pi)i2N)
for G,If there exists 2 ( ) such that pi = for all i 2 N,and R =,then
(( ;(Ti;ai)i2N); ) is an extended correlated equilibrium of G.
Conversely,if is a correlated equilibrium ofG,there exists a modelM= ( ;(Ti;ai;pi)i2N)
for G in which = R.
The model alluded to in the second part of the Proposition is of course the one constructed
above,Observe that in that model is indeed a common prior.
You may feel a bit cheated by this result,After all,it seems all we have done is change
our interpretation of the relevant objects,This is of course entirely correct!
It is certainly the case that Proposition 0.3 characterizes correlated equilibrium beliefs.
More precisely,a distribution over action pro les is a correlated equilibrium belief if it is a
common prior in a model with the feature that every player is rational at every state.
As I have mentioned several times,this may or may not have any behavioral implications,
but at least Proposition 0.3 provides an arguably more palatable rationale for correlated
equilibrium beliefs than the \outside observer" story.
8
