Eco514|Game Theory
Lecture 15,Sequential Equilibrium
Marciano Siniscalchi
November 11,1999
Introduction
The theory of extensive games is built upon a key notion,that of sequential rationality,and a
key insight,the centrality of o -equilibrium beliefs,The de nition of sequential equilibrium
brings both to the fore in a straightforward manner,and emphasizes their interrelation.
From subgame perfection to sequential rationality
.
Let us begin by considering a game with observed actions (but possibly simultaneous
moves),Fix a pro le s2S; according to the de nition,s is a subgame-perfect equilibrium of
i,for every history h2HnZ,the continuation strategy pro le sjh is a Nash equilibrium
of the subgame (h) beginning at h.
Equivalently,we can say that s is a SPE i,for every history h2HnZ,and every player
i 2 N,there is no strategy s0i 2 Si that yields a higher payo to Player i than si in the
subgame (h).
Moreover,we can actually restrict this requirement to subgames starting at histories
h 2 P 1(i),Consider a history h0 such that i 62 P(h0); then either Player i never moves
in the subgame (h0) (in which case si is trivially optimal),or there exists a collection of
historiesfh00gsuch that (i) h0 is a subhistory of every h00,and (ii) i2P(h00) for each such h00.
According to the pro le s i,exactly one of these histories,say h,will be reached starting
from h0,and by assumption sijh is a best reply to s ijh in (h),Therefore,sijh0 is also a best
reply to s ijh0 in (h0).
In other words,s is a SPE i each component strategy si is a best reply against s i
conditional upon reaching any history where Player i moves|including those histories that
are not generated by s,or perhaps explicitly excluded by si itself,This is precisely the notion
of sequential rationality.
1
There is little reason why this concept should not apply to general extensive games
as well,However,observe that,in games with observed actions,xing a strategy pro le
s is su cient to generate well-de ned beliefs in every subgame|i.e,well-de ned beliefs
conditional upon reaching any history,This is not the case in general extensive games (or
in Bayesian extensive games with observed actions,for that matter).
In some (very special) games,this does not really matter,For instance,consider Fig,1.
L2,2 1q
M
R
@
@
@
@@q
r
A
A
A
AA
0,0
l
3,1
q
1,1
A
A
A
AA
0,2
2
I2
Figure 1,A special game (OR 219.1)
Observe that (L;r) is a Nash equilibrium of this game; note also that,since Player 1
chooses L in this equilibrium,it is not clear what Player 2 should believe if the information
set I2 = f(M);(R)g is reached! Thus,the equilibrium strategy pro le is insu cient to pin
down players’ conditional beliefs.
Yet,in this particular game,this is essentially irrelevant,regardless of his beliefs about
Player 1’s actual choice,r is conditionally strictly dominated at I2,Whatever Player 2’s
beliefs,r cannot thus be sequentially rational,so (L;r) is \not a legitimate solution" to the
extensive game in Figure 1,On the other hand,(M;l) is.
In this simple game,Player 2’s beliefs about the strategy (action) actually chosen by
Player 1 is irrelevant as far as his choices are concerned,However,this is seldom the case:
consider Fig,2,which di ers from Fig,1 only in that the payo s at the terminal history
fM;rg have been modi ed.
Consider (L;r) again,Upon being reached,Player 2 must conclude that Player 1 did
not choose L; hence,he must adopt new,distinct from the equilibrium pro le,Suppose that
he thinks that Player 1 actually chose M,then r is indeed a sequential best reply! Suppose
instead that he thinks that Player 1 chose R,in this case r is not sequentially rational.
2
L2,2 1q
M
R
@
@
@
@@q
r
A
A
A
AA
0,2
l
3,1
q
1,1
A
A
A
AA
0,2
2
I2
Figure 2,A typical case (OR 220.1)
Formal de nitions
The simple games in the previous section emphasize that o -equilibrium beliefs matter,they
determine whether or not a given pro le is an equilibrium,Moreover,the putative equilibrium
pro le does not yield a complete speci cation of beliefs.
In particular,at any information set,a (behavioral) strategy pro le yields a complete
speci cation of continuation strategies,but may fail to provide information about past play|
precisely because,at information sets o the path of play generated by,it must necessarily
be the case that at least one player j made choices other than those prescribed by j! The
original pro le is clearly silent about such alternative choices.
Note that this problem does not arise in games with observed actions,precisely because
past play is observable (so there is no uncertainty about previous moves),However,it does
arise in Bayesian games with observed actions; see the next section for details.
Kreps and Wilson propose the following de nition.
De nition 1 Fix a general extensive game,A belief system is a map,Si2NIi !
(HnZ) such that,for every i2N and Ii2Ii,(Ii)(Ii) = 1.
It is most helpful to view a belief system as a summary representation of past play leading
to information sets,That is,informally speaking,one could imagine that,if the play reaches
an information set Ii (where Player i has to move) which is not consistent with the originally
expected behavioral strategy pro le,players conclude that a di erent pro le 0 is actually
being played,and base their inferences and forecasts on the latter.
However,based on simple consistency considerations,0 and should agree at least as
far as moves at information sets following I are concerned,But,if this is the case,then all
that is required in addition to in order to verify the sequential rationality of i at Ii is
the distribution over histories in Ii induced by 0|which is precisely the type of information
encoded in (I).
3
From now on,the basic unit of our analysis will be a pair ( ; ) consisting of a behavioral
strategy pro le and a belief system; such a pair is called an assessment.
Focus on games with perfect recall,In keeping with conventional usage,we de ne se-
quentially rational assessments,First,de ne the conditional outcome function O( ; jI) to
be the distribution over Z induced by the assessment ( ; ) conditional upon starting the
game at I,formally,for every z2Z,if no h2I is a subhistory of z,then O( ; jI)(z) = 0;
otherwise,by perfect recall,there can be only one such subhistory h (if there were two,then
one would have to be a subhistory of the other,and an information set cannot contain a pair
of nested histories),Thus,z = (h;a1;:::;aK),and we let
O( ; jI)(z) = (I)(h)
K 1Y
‘=1
P(h;a1;:::;a‘)(h;a1;:::;a‘)(a‘+1)
(recall that,with some abuse of notation,for h2Ii2Ii,i(h) = i(Ii)).
De nition 2 Fix a general extensive game,An assessment ( ; ) for is sequentially
rational i,for every player i 2 N,every information set Ii 2Ii,and every behavioral
strategy 0i2Bi,X
z2Z
Ui(z)O( ; jIi)
X
z2Z
Ui(z)O(( 0i; i) jIi)
It should be obvious that some relationship between belief systems and behavioral strate-
gies in an assessment ( ; ) should be maintained.
In particular,at least at information sets consistent with,should be derived from
by means of Bayes’ rule.
But we may reasonably require more than this,For instance,consider a modi cation of
the game in Figure 2 in which Player 1 chooses between L and C,and if 1 chooses C,a third
player 10 chooses between M and R; then Player 2 has to choose observing only Player 1’s
initial move,That is,Player 1’s choice among L,M and R is split between two players,1
and 10,choosing consecutively.
Consider a behavioral strategy pro le in which Player 1 chooses L and Player 10 chooses
M,Then,even after a deviation by Player 1,we would probably still want to require that
(f(C;M);(C;R)g)((C;M)) = 1; that is,a deviation by Player 1 should not a ect Player
2’s beliefs about the choices of Player 10,However,strictly speaking,Bayes’ rule does not
apply to this information set,because it lies o the path induced by the behavioral strategy
pro le under consideration.
[Note incidentally that if 1 and 10 were the same player,this argument would be less
convincing; one would have to invoke some kind of trembles or mistakes,whereas the argu-
ment in the case where 1 and 10 are distinct is essentially based on independence,As will
be clear,however,the standard de nition of sequential equilibrium does not discriminate
between these two cases.]
4
Kreps and Wilson suggest the following de nition.
De nition 3 Fix a nite general extensive game,An assessment ( ; ) is consistent
i there exists a sequence of assessments ( n; n) converging to ( ; ) and such that (i)
ni (Ii)(a) > 0 for every i2N,I2Ii and a2A(I); and (ii) n is derived from n via Bayes’
rule.
It is easy to see that this de nition captures the intended restrictions,Note that (ii)
makes sense because,since every action in the game receives positive probability,every
information set is also reached with positive probability,so Bayes’ rule always applies.
Myerson suggests the following argument,Almost all elements of the setB of behavioral
strategy pro les satisfy Condition (i) in De nition 3,that is,Condition (i) is generically
satis ed,Also,Condition (ii) is very reasonable,so we de nitely want all assessments ( ; )
such that satis es (i) to be deemed consistent if and only if is derived from by Bayes’
rule,Finally,it seems reasonable (and convenient) to assume that the set of consistent
assessments is closed; hence,it makes sense to de ne it to be precisely the closure of the set
of assessments satisfying (i) and (ii).
This may not appear to be a tremendously compelling argument; however,let me add
that,for certain classes of games,consistency is equivalent to much simpler conditions on
beliefs (when the latter are represented in an appropriate format),Also,consistency can
be characterized for general games in a manner that does not involve limits (although the
characterization is not tremendously appealing).
We are nally ready to de ne sequential equilibrium.
De nition 4 Fix a nite general extensive game,An assessment ( ; ) is a sequential
equilibrium of i it is consistent and sequentially rational.
Perfect Bayesian equilibrium
Some people nd the de nition of sequential equilibrium unwieldy (this refers in particular to
the consistency requirement),Also,consistency is only de ned for nite games,so sequential
equilibrium does not really apply to relatively simple games such as Bayesian extensive games
with observed actions where type sets are in nite.
In such games,just like in a Bayesian game with simultaneous moves,one must specify
a strategy for each payo -type of each player,That is,we must specify type-contingent
strategies,Hence,upon reaching a history h,players may be able to make inferences about
their opponents’ types based on the (equilibrium) strategy pro le,However,at histories
o the anticipated path of play,it is clear that the strategy pro le does not convey any
information about opponents’ types.
5
This is of course exactly the type of problem that beliefs system solve in general games.
Here,however,the situation is much simpler,because the domain of uncertainty (the sets of
payo types) are xed throughout the game.
In Perfect Bayesian equilibria (see OR for details),the information conveyed by strat-
egy pro les is complemented by measures i(h) 2 ( i) associated with each nonterminal
history.
In interpreting the de nitions,it is important to remember that,just like the probabilities
pi,i(h) represents the beliefs of players other than i about Player i’s type,These beliefs
are common to all players,which is reasonable,after all,the priors pi are common,and all
players observe exactly the same occurrences as the play progresses.
The key condition in the de nition of a PBE is the requirement that these beliefs be
action-determined,That is,if Player i does not move at a history h,then the beliefs about
her should not change at h; and if Player i does move,than beliefs about her should only be
a ected by her own action at h (not by somebody else’s action).
Just like the consistency requirement in SE,this complements Bayesian updating with
restrictions on beliefs following unexpected actions (i.e,on beliefs at o -equilibrium histo-
ries).
6
Lecture 15,Sequential Equilibrium
Marciano Siniscalchi
November 11,1999
Introduction
The theory of extensive games is built upon a key notion,that of sequential rationality,and a
key insight,the centrality of o -equilibrium beliefs,The de nition of sequential equilibrium
brings both to the fore in a straightforward manner,and emphasizes their interrelation.
From subgame perfection to sequential rationality
.
Let us begin by considering a game with observed actions (but possibly simultaneous
moves),Fix a pro le s2S; according to the de nition,s is a subgame-perfect equilibrium of
i,for every history h2HnZ,the continuation strategy pro le sjh is a Nash equilibrium
of the subgame (h) beginning at h.
Equivalently,we can say that s is a SPE i,for every history h2HnZ,and every player
i 2 N,there is no strategy s0i 2 Si that yields a higher payo to Player i than si in the
subgame (h).
Moreover,we can actually restrict this requirement to subgames starting at histories
h 2 P 1(i),Consider a history h0 such that i 62 P(h0); then either Player i never moves
in the subgame (h0) (in which case si is trivially optimal),or there exists a collection of
historiesfh00gsuch that (i) h0 is a subhistory of every h00,and (ii) i2P(h00) for each such h00.
According to the pro le s i,exactly one of these histories,say h,will be reached starting
from h0,and by assumption sijh is a best reply to s ijh in (h),Therefore,sijh0 is also a best
reply to s ijh0 in (h0).
In other words,s is a SPE i each component strategy si is a best reply against s i
conditional upon reaching any history where Player i moves|including those histories that
are not generated by s,or perhaps explicitly excluded by si itself,This is precisely the notion
of sequential rationality.
1
There is little reason why this concept should not apply to general extensive games
as well,However,observe that,in games with observed actions,xing a strategy pro le
s is su cient to generate well-de ned beliefs in every subgame|i.e,well-de ned beliefs
conditional upon reaching any history,This is not the case in general extensive games (or
in Bayesian extensive games with observed actions,for that matter).
In some (very special) games,this does not really matter,For instance,consider Fig,1.
L2,2 1q
M
R
@
@
@
@@q
r
A
A
A
AA
0,0
l
3,1
q
1,1
A
A
A
AA
0,2
2
I2
Figure 1,A special game (OR 219.1)
Observe that (L;r) is a Nash equilibrium of this game; note also that,since Player 1
chooses L in this equilibrium,it is not clear what Player 2 should believe if the information
set I2 = f(M);(R)g is reached! Thus,the equilibrium strategy pro le is insu cient to pin
down players’ conditional beliefs.
Yet,in this particular game,this is essentially irrelevant,regardless of his beliefs about
Player 1’s actual choice,r is conditionally strictly dominated at I2,Whatever Player 2’s
beliefs,r cannot thus be sequentially rational,so (L;r) is \not a legitimate solution" to the
extensive game in Figure 1,On the other hand,(M;l) is.
In this simple game,Player 2’s beliefs about the strategy (action) actually chosen by
Player 1 is irrelevant as far as his choices are concerned,However,this is seldom the case:
consider Fig,2,which di ers from Fig,1 only in that the payo s at the terminal history
fM;rg have been modi ed.
Consider (L;r) again,Upon being reached,Player 2 must conclude that Player 1 did
not choose L; hence,he must adopt new,distinct from the equilibrium pro le,Suppose that
he thinks that Player 1 actually chose M,then r is indeed a sequential best reply! Suppose
instead that he thinks that Player 1 chose R,in this case r is not sequentially rational.
2
L2,2 1q
M
R
@
@
@
@@q
r
A
A
A
AA
0,2
l
3,1
q
1,1
A
A
A
AA
0,2
2
I2
Figure 2,A typical case (OR 220.1)
Formal de nitions
The simple games in the previous section emphasize that o -equilibrium beliefs matter,they
determine whether or not a given pro le is an equilibrium,Moreover,the putative equilibrium
pro le does not yield a complete speci cation of beliefs.
In particular,at any information set,a (behavioral) strategy pro le yields a complete
speci cation of continuation strategies,but may fail to provide information about past play|
precisely because,at information sets o the path of play generated by,it must necessarily
be the case that at least one player j made choices other than those prescribed by j! The
original pro le is clearly silent about such alternative choices.
Note that this problem does not arise in games with observed actions,precisely because
past play is observable (so there is no uncertainty about previous moves),However,it does
arise in Bayesian games with observed actions; see the next section for details.
Kreps and Wilson propose the following de nition.
De nition 1 Fix a general extensive game,A belief system is a map,Si2NIi !
(HnZ) such that,for every i2N and Ii2Ii,(Ii)(Ii) = 1.
It is most helpful to view a belief system as a summary representation of past play leading
to information sets,That is,informally speaking,one could imagine that,if the play reaches
an information set Ii (where Player i has to move) which is not consistent with the originally
expected behavioral strategy pro le,players conclude that a di erent pro le 0 is actually
being played,and base their inferences and forecasts on the latter.
However,based on simple consistency considerations,0 and should agree at least as
far as moves at information sets following I are concerned,But,if this is the case,then all
that is required in addition to in order to verify the sequential rationality of i at Ii is
the distribution over histories in Ii induced by 0|which is precisely the type of information
encoded in (I).
3
From now on,the basic unit of our analysis will be a pair ( ; ) consisting of a behavioral
strategy pro le and a belief system; such a pair is called an assessment.
Focus on games with perfect recall,In keeping with conventional usage,we de ne se-
quentially rational assessments,First,de ne the conditional outcome function O( ; jI) to
be the distribution over Z induced by the assessment ( ; ) conditional upon starting the
game at I,formally,for every z2Z,if no h2I is a subhistory of z,then O( ; jI)(z) = 0;
otherwise,by perfect recall,there can be only one such subhistory h (if there were two,then
one would have to be a subhistory of the other,and an information set cannot contain a pair
of nested histories),Thus,z = (h;a1;:::;aK),and we let
O( ; jI)(z) = (I)(h)
K 1Y
‘=1
P(h;a1;:::;a‘)(h;a1;:::;a‘)(a‘+1)
(recall that,with some abuse of notation,for h2Ii2Ii,i(h) = i(Ii)).
De nition 2 Fix a general extensive game,An assessment ( ; ) for is sequentially
rational i,for every player i 2 N,every information set Ii 2Ii,and every behavioral
strategy 0i2Bi,X
z2Z
Ui(z)O( ; jIi)
X
z2Z
Ui(z)O(( 0i; i) jIi)
It should be obvious that some relationship between belief systems and behavioral strate-
gies in an assessment ( ; ) should be maintained.
In particular,at least at information sets consistent with,should be derived from
by means of Bayes’ rule.
But we may reasonably require more than this,For instance,consider a modi cation of
the game in Figure 2 in which Player 1 chooses between L and C,and if 1 chooses C,a third
player 10 chooses between M and R; then Player 2 has to choose observing only Player 1’s
initial move,That is,Player 1’s choice among L,M and R is split between two players,1
and 10,choosing consecutively.
Consider a behavioral strategy pro le in which Player 1 chooses L and Player 10 chooses
M,Then,even after a deviation by Player 1,we would probably still want to require that
(f(C;M);(C;R)g)((C;M)) = 1; that is,a deviation by Player 1 should not a ect Player
2’s beliefs about the choices of Player 10,However,strictly speaking,Bayes’ rule does not
apply to this information set,because it lies o the path induced by the behavioral strategy
pro le under consideration.
[Note incidentally that if 1 and 10 were the same player,this argument would be less
convincing; one would have to invoke some kind of trembles or mistakes,whereas the argu-
ment in the case where 1 and 10 are distinct is essentially based on independence,As will
be clear,however,the standard de nition of sequential equilibrium does not discriminate
between these two cases.]
4
Kreps and Wilson suggest the following de nition.
De nition 3 Fix a nite general extensive game,An assessment ( ; ) is consistent
i there exists a sequence of assessments ( n; n) converging to ( ; ) and such that (i)
ni (Ii)(a) > 0 for every i2N,I2Ii and a2A(I); and (ii) n is derived from n via Bayes’
rule.
It is easy to see that this de nition captures the intended restrictions,Note that (ii)
makes sense because,since every action in the game receives positive probability,every
information set is also reached with positive probability,so Bayes’ rule always applies.
Myerson suggests the following argument,Almost all elements of the setB of behavioral
strategy pro les satisfy Condition (i) in De nition 3,that is,Condition (i) is generically
satis ed,Also,Condition (ii) is very reasonable,so we de nitely want all assessments ( ; )
such that satis es (i) to be deemed consistent if and only if is derived from by Bayes’
rule,Finally,it seems reasonable (and convenient) to assume that the set of consistent
assessments is closed; hence,it makes sense to de ne it to be precisely the closure of the set
of assessments satisfying (i) and (ii).
This may not appear to be a tremendously compelling argument; however,let me add
that,for certain classes of games,consistency is equivalent to much simpler conditions on
beliefs (when the latter are represented in an appropriate format),Also,consistency can
be characterized for general games in a manner that does not involve limits (although the
characterization is not tremendously appealing).
We are nally ready to de ne sequential equilibrium.
De nition 4 Fix a nite general extensive game,An assessment ( ; ) is a sequential
equilibrium of i it is consistent and sequentially rational.
Perfect Bayesian equilibrium
Some people nd the de nition of sequential equilibrium unwieldy (this refers in particular to
the consistency requirement),Also,consistency is only de ned for nite games,so sequential
equilibrium does not really apply to relatively simple games such as Bayesian extensive games
with observed actions where type sets are in nite.
In such games,just like in a Bayesian game with simultaneous moves,one must specify
a strategy for each payo -type of each player,That is,we must specify type-contingent
strategies,Hence,upon reaching a history h,players may be able to make inferences about
their opponents’ types based on the (equilibrium) strategy pro le,However,at histories
o the anticipated path of play,it is clear that the strategy pro le does not convey any
information about opponents’ types.
5
This is of course exactly the type of problem that beliefs system solve in general games.
Here,however,the situation is much simpler,because the domain of uncertainty (the sets of
payo types) are xed throughout the game.
In Perfect Bayesian equilibria (see OR for details),the information conveyed by strat-
egy pro les is complemented by measures i(h) 2 ( i) associated with each nonterminal
history.
In interpreting the de nitions,it is important to remember that,just like the probabilities
pi,i(h) represents the beliefs of players other than i about Player i’s type,These beliefs
are common to all players,which is reasonable,after all,the priors pi are common,and all
players observe exactly the same occurrences as the play progresses.
The key condition in the de nition of a PBE is the requirement that these beliefs be
action-determined,That is,if Player i does not move at a history h,then the beliefs about
her should not change at h; and if Player i does move,than beliefs about her should only be
a ected by her own action at h (not by somebody else’s action).
Just like the consistency requirement in SE,this complements Bayesian updating with
restrictions on beliefs following unexpected actions (i.e,on beliefs at o -equilibrium histo-
ries).
6
