Eco514|Game Theory
Lecture 14,General Extensive Games
Marciano Siniscalchi
November 10,1999
Introduction
[By and large,I will follow OR,Chapters 11 and 12,so I will keep these notes to a minimum.]
Games with observed actions and payo uncertainty
Not all dynamic models of strategic interaction t within the category of games with observed
actions we have developed in the previous lectures,In particular,no allowance was made
for payo uncertainty.
On the other hand,it is very easy to augment the basic model to allow for it,I am going
to follow OR very closely here:
De nition 1 An extensive-form game with observed actions and incomplete information
(OR,a Bayesian extensive game with observed actions) is a tuple = (N;A;H;P;Z;( i;pi;Ui)i2N)
where:
N,is a set of players;
A is a set of actions;
H is a collection of nite and countable sequences of vectors of elements of A,such that:
(i) ;2H;
(ii) (a1;:::;ak)2H implies (a1;:::;a‘)2H for all ‘<k;
(iii) If h = (a1;:::;ak;:::) and (a1;:::;ak)2H for all k 1,then h2H.
Z is the set of terminal histories,that is,(a1;:::;ak) 2 Z i (a1;:::;ak) 2 H and
(a1;:::;ak;a)62H for all a2A,Also let X = HnZ,All in nite histories are terminal.
P,X)N is the player correspondence.
i is a set of payo types; write = Qi2N i.
pi is a probability distribution over i; for i6= j,pi and pj are independent.
U = (Ui)i2N,Z Qi2N i!R is the payo function,associating a vector of payo s to
every terminal history and every pro le of payo types.
1
Thus,the key innovations are the sets i and the measures pi,The former enter as
parameters in the payo functions,and thus capture payo uncertainty; note that Player j’s
payo s may depend on Player i’s payo type (i.e,values may be interdependent,using our
auction-theoretic terminology).
The probabilities pi determine a common prior over,This is not yet apparent,but it
will be when we de ne a solution concept that applies to such games.
The implicit assumption one makes is that,before the game begins,payo types are
drawn according to the probabilities p1;:::;pN; each player i 2 N learns her own payo
type i,and the product measure p i2 ( i) de ned by
p i( i) =
Y
j6=i
pj( j) 8 i = ( j) 6=i2 i
serves as her prior belief about her opponents’ payo types.
Two important comments are in order,First of all,one might visualize the selection
of payo types as a chance move,Clearly,to make things interesting,it must be the case
that this initial move by chance is not perfectly observed by all players,Hence,one needs a
model of extensive games without observed actions; this is precisely the model we are going
to develop in the next section.
Indeed,one might even say that games with incomplete information are the main reason
why the theory has traditionally focused on extensive games without observable actions,My
point here (shared by OR,as well as Fudenberg and Tirole) is that the general notion is
perhaps more than is strictly required to model dynamic games of economic interest.
I should also add that reducing a situation with incomplete information/payo uncer-
tainty to one with imperfect information (in particular,unobserved actions) is not an entirely
harmless assumption|chie y because doing so requires imposing the common-prior assump-
tion (can you see why?)
Second,note that I am deviating somewhat from our basic framework for interactive
decision making,First,I am incorporating probabilities in the description of the model,and
I am making the players’ priors over payo type pro les common,This is why I am using
the term \incomplete information" as opposed to \payo uncertainty"|in keeping with the
literature.
Second,for simultaneous-move games,the setup does not immediately reduce to the one
we adopt for static Bayesian games,However,to relate the two constructions,it is su cient
to note that is the counterpart of in our static Bayesian setting,and each i de nes a
partition of whose cells are of the form ff ig ig.
While the static Bayesian model is more general than this derived formulation (think
about a setting in which all players’ payo s depend on a single random draw which no
2
player observes),the two can be reconciled by introducing a dummy player in De nition 1.
This is not a particularly clean solution,of course,but it works.
I will return to Bayesian extensive games with observed actions when I discuss Perfect
Bayesian equilibrium,the \modal" solution concept for such games,For the time being,
let me point out that,while the model implicitly de nes each player i’s prior on i,it
stands to reason that,as the game progresses,Player i will update her prior beliefs about her
opponents’ payo types based on her observations (as well as the conjectured equilibrium).
These updated beliefs must somehow be part of the description of the equilibrium; also,
they must be subject to some sort of consistency condition|Bayes’ rule,for instance,We
shall see that identifying such conditions is the key problem in the formulation of extensive-
form solution concepts.
General Games with Incomplete Information
With the above discussion as a motivation of sorts,we are led to consider a notion of extensive
games which allows for partial observability of actions.
The basic idea is to start with a game with perfect information (i.e,without simultaneous
moves) and enrich it with a description of what players actually \know" when a given history
obtains.
Player i’s knowledge is modelled via a partition Ii of the set of histories at which they
are called upon to choose an action,i.e,P 1(i),This is exactly as in our model of payo
uncertainty in static games,in the interim stage,Player i learns,hence knows,that the
true state of the world ! is an element of the cell ti(!),but need not know that it is
exactly !,Similarly,at a history h,a player learns that the actual history belongs to some
set Ii(h) P 1(i),but not necessarily that it is h.
De nition 2 An extensive-form game with chance moves is a tuple = (N;A;H;P;Z;(Ui;Ii);fc)
where:
N is a set of players; Chance,denoted by c,is regarded as an additional player,so c62N.
A is a set of actions
H is a set of sequences whose elements are elements of A,such that
(i) ;2H;
(ii) (a1;:::;ak)2H implies (a1;:::;a‘)2H for all ‘<k;
(iii) If h = (a1;:::;ak;:::) and (a1;:::;ak)2H for all k 1,then h2H;
Z and X are the set of terminal and non-terminal histories;
P is the player function P,X!N[fcg
U,Z!RN is the payo vector function;
Ii is a partition of P 1(i).
3
For everyi2N[fcg,letAi(h) =fa2A,(h;a)2Hg,Thenfc,fh,c2P(h)g! (A)
indicates the probability of each chance move,and fc(h)(Ai(h)) = 1 for all h such that
c2P(h).
Note that we are not allowing for simultaneous moves at a given history,This can be
easily xed,but it is not necessary because simultaneous moves can be modelled exploiting
the fact that moves may be unobservable.
The cells of each partition Ii are called information sets.
Perfect Recall
Note that,in general,it may be the case that,for some sequences of actions h;h0,both h
and (h;h0) belong to the same information set,This represents a situation in which a player
forgets her own previous choices.
More generally,a player may forget that her opponents have chosen certain actions in
the past.
De nition 2 allows for both possibilities,However,it is conventional (and expedient)
to assume that players have perfect recall,they forget neither their own actions,nor their
previous observations.
To formulate this assumption rigorously,we rst de ne,for each player i2N,a collection
of sequences (Xi(h))h2X such that,for every h2X,Xi(h) includes all the actions Player i
has chosen and all the information sets in Ii she has visited in the partial history h.
Formally,let Xi(;) = ;; next,assuming that Xi(h) has been de ned for all histories of
length ‘,for every a2A(h),let:
Xi(h;a) = Xi(h)[fag[Ii(h;a) if P(h) = P(h;a) = i;
Xi(h;a) = Xi(h)[fag if P(h) = i6= P(h;a);
Xi(h;a) = Xi(h)[Ii(h;a) if P(h;a) = i6= P(h); and
Xi(h;a) = Xi(h) if P(h)6= i and P(h;a)6= i.
Then we say that an extensive game has perfect recall i,for every player i 2 N,
information set Ii2Ii,and histories h;h02Ii,Xi(h) = Xi(h0),Observe that Xi is de ned
at every history,but the notion of perfect recall imposes direct restrictions only at histories
where Player i moves.
Note that,in particular,perfect recall implies that it is never the case that,for some
history h and sequence of actions h0,both h and (h;h0) belong to the same information set.
4
Strategies
Pure and mixed strategies in general extensive games are easily de ned:
De nition 3 Fix an extensive game and a player i2N,A pure strategy for Player i is
a map si,Ii!A such that,for all Ii2Ii,si(Ii)2A(Ii).
Denote by Si,S i and S the sets of strategies of Player i,the set of strategy pro les of
i’s opponents,and the set of complete strategy pro les respectively,A mixed strategy for
Player i is a probability distribution i2 (Si).
The notion of randomization captured in De nition is as follows,at the beginning of the
game,players spin a roulette wheel to choose a pure strategy,and stick to that strategy
thereafter.
However,players could also randomize at each information set,This gives rise to a
di erent notion:
De nition 4 Fix an extensive game and a player i2N,A behavioral strategy for Player
i is a map i,Ii! (A) such that,for all Ii2Ii,i(Ii)(A(h)) = 1.
Denote byBi,B i andBthe sets of i’s behavioral strategies,of her opponents’ behavioral
strategy pro les,and of complete behavioral strategy pro les.
If this reminds you of our de nition of chance moves,it should,the function fc is simply
Chance’s behavioral strategy!
It is natural to ask whether the two notions of randomization are related,The answer
is that,of course,they are,To be precise about this,we rst de ne (with some abuse of
notation) the outcome functions O,B! (Z) and O,Qi2N (Si) ! (Z) to be the
maps which associate with each pro le of behavioral or mixed strategies a distribution over
terminal nodes (you should provide a formal de nition).
We then ask two distinct questions,First,given a behavioral strategy pro le 2B,can
we nd an outcome-equivalent mixed strategy pro le,i.e,some 2Qi2N (Si) such that
O( ) = O( )?
The answer is a rmative for all games which satisfy the following condition,for every
player i2N,information set Ii 2Ii,and histories h;h02Ii,it is never the case that h is
a subhistory of h0 or vice-versa,Hence,in particular,the answer is a rmative for all games
with perfect recall,OR provides an example (p,214) where this condition fails.
Second,given a mixed strategy pro le,can we nd an outcome-equivalent behavioral
strategy pro le? The answer is again a rmative,if we restrict ourselves to games with
perfect recall,This is Proposition 214.1 in OR,also known as Kuhn’s Theorem.
I conclude by noting that a Nash equilibrium of an extensive game is simply a Nash
equilibrium of (the mixed extension of) its normal form; you can think of a formal de nition,
using outcome functions.
5
Lecture 14,General Extensive Games
Marciano Siniscalchi
November 10,1999
Introduction
[By and large,I will follow OR,Chapters 11 and 12,so I will keep these notes to a minimum.]
Games with observed actions and payo uncertainty
Not all dynamic models of strategic interaction t within the category of games with observed
actions we have developed in the previous lectures,In particular,no allowance was made
for payo uncertainty.
On the other hand,it is very easy to augment the basic model to allow for it,I am going
to follow OR very closely here:
De nition 1 An extensive-form game with observed actions and incomplete information
(OR,a Bayesian extensive game with observed actions) is a tuple = (N;A;H;P;Z;( i;pi;Ui)i2N)
where:
N,is a set of players;
A is a set of actions;
H is a collection of nite and countable sequences of vectors of elements of A,such that:
(i) ;2H;
(ii) (a1;:::;ak)2H implies (a1;:::;a‘)2H for all ‘<k;
(iii) If h = (a1;:::;ak;:::) and (a1;:::;ak)2H for all k 1,then h2H.
Z is the set of terminal histories,that is,(a1;:::;ak) 2 Z i (a1;:::;ak) 2 H and
(a1;:::;ak;a)62H for all a2A,Also let X = HnZ,All in nite histories are terminal.
P,X)N is the player correspondence.
i is a set of payo types; write = Qi2N i.
pi is a probability distribution over i; for i6= j,pi and pj are independent.
U = (Ui)i2N,Z Qi2N i!R is the payo function,associating a vector of payo s to
every terminal history and every pro le of payo types.
1
Thus,the key innovations are the sets i and the measures pi,The former enter as
parameters in the payo functions,and thus capture payo uncertainty; note that Player j’s
payo s may depend on Player i’s payo type (i.e,values may be interdependent,using our
auction-theoretic terminology).
The probabilities pi determine a common prior over,This is not yet apparent,but it
will be when we de ne a solution concept that applies to such games.
The implicit assumption one makes is that,before the game begins,payo types are
drawn according to the probabilities p1;:::;pN; each player i 2 N learns her own payo
type i,and the product measure p i2 ( i) de ned by
p i( i) =
Y
j6=i
pj( j) 8 i = ( j) 6=i2 i
serves as her prior belief about her opponents’ payo types.
Two important comments are in order,First of all,one might visualize the selection
of payo types as a chance move,Clearly,to make things interesting,it must be the case
that this initial move by chance is not perfectly observed by all players,Hence,one needs a
model of extensive games without observed actions; this is precisely the model we are going
to develop in the next section.
Indeed,one might even say that games with incomplete information are the main reason
why the theory has traditionally focused on extensive games without observable actions,My
point here (shared by OR,as well as Fudenberg and Tirole) is that the general notion is
perhaps more than is strictly required to model dynamic games of economic interest.
I should also add that reducing a situation with incomplete information/payo uncer-
tainty to one with imperfect information (in particular,unobserved actions) is not an entirely
harmless assumption|chie y because doing so requires imposing the common-prior assump-
tion (can you see why?)
Second,note that I am deviating somewhat from our basic framework for interactive
decision making,First,I am incorporating probabilities in the description of the model,and
I am making the players’ priors over payo type pro les common,This is why I am using
the term \incomplete information" as opposed to \payo uncertainty"|in keeping with the
literature.
Second,for simultaneous-move games,the setup does not immediately reduce to the one
we adopt for static Bayesian games,However,to relate the two constructions,it is su cient
to note that is the counterpart of in our static Bayesian setting,and each i de nes a
partition of whose cells are of the form ff ig ig.
While the static Bayesian model is more general than this derived formulation (think
about a setting in which all players’ payo s depend on a single random draw which no
2
player observes),the two can be reconciled by introducing a dummy player in De nition 1.
This is not a particularly clean solution,of course,but it works.
I will return to Bayesian extensive games with observed actions when I discuss Perfect
Bayesian equilibrium,the \modal" solution concept for such games,For the time being,
let me point out that,while the model implicitly de nes each player i’s prior on i,it
stands to reason that,as the game progresses,Player i will update her prior beliefs about her
opponents’ payo types based on her observations (as well as the conjectured equilibrium).
These updated beliefs must somehow be part of the description of the equilibrium; also,
they must be subject to some sort of consistency condition|Bayes’ rule,for instance,We
shall see that identifying such conditions is the key problem in the formulation of extensive-
form solution concepts.
General Games with Incomplete Information
With the above discussion as a motivation of sorts,we are led to consider a notion of extensive
games which allows for partial observability of actions.
The basic idea is to start with a game with perfect information (i.e,without simultaneous
moves) and enrich it with a description of what players actually \know" when a given history
obtains.
Player i’s knowledge is modelled via a partition Ii of the set of histories at which they
are called upon to choose an action,i.e,P 1(i),This is exactly as in our model of payo
uncertainty in static games,in the interim stage,Player i learns,hence knows,that the
true state of the world ! is an element of the cell ti(!),but need not know that it is
exactly !,Similarly,at a history h,a player learns that the actual history belongs to some
set Ii(h) P 1(i),but not necessarily that it is h.
De nition 2 An extensive-form game with chance moves is a tuple = (N;A;H;P;Z;(Ui;Ii);fc)
where:
N is a set of players; Chance,denoted by c,is regarded as an additional player,so c62N.
A is a set of actions
H is a set of sequences whose elements are elements of A,such that
(i) ;2H;
(ii) (a1;:::;ak)2H implies (a1;:::;a‘)2H for all ‘<k;
(iii) If h = (a1;:::;ak;:::) and (a1;:::;ak)2H for all k 1,then h2H;
Z and X are the set of terminal and non-terminal histories;
P is the player function P,X!N[fcg
U,Z!RN is the payo vector function;
Ii is a partition of P 1(i).
3
For everyi2N[fcg,letAi(h) =fa2A,(h;a)2Hg,Thenfc,fh,c2P(h)g! (A)
indicates the probability of each chance move,and fc(h)(Ai(h)) = 1 for all h such that
c2P(h).
Note that we are not allowing for simultaneous moves at a given history,This can be
easily xed,but it is not necessary because simultaneous moves can be modelled exploiting
the fact that moves may be unobservable.
The cells of each partition Ii are called information sets.
Perfect Recall
Note that,in general,it may be the case that,for some sequences of actions h;h0,both h
and (h;h0) belong to the same information set,This represents a situation in which a player
forgets her own previous choices.
More generally,a player may forget that her opponents have chosen certain actions in
the past.
De nition 2 allows for both possibilities,However,it is conventional (and expedient)
to assume that players have perfect recall,they forget neither their own actions,nor their
previous observations.
To formulate this assumption rigorously,we rst de ne,for each player i2N,a collection
of sequences (Xi(h))h2X such that,for every h2X,Xi(h) includes all the actions Player i
has chosen and all the information sets in Ii she has visited in the partial history h.
Formally,let Xi(;) = ;; next,assuming that Xi(h) has been de ned for all histories of
length ‘,for every a2A(h),let:
Xi(h;a) = Xi(h)[fag[Ii(h;a) if P(h) = P(h;a) = i;
Xi(h;a) = Xi(h)[fag if P(h) = i6= P(h;a);
Xi(h;a) = Xi(h)[Ii(h;a) if P(h;a) = i6= P(h); and
Xi(h;a) = Xi(h) if P(h)6= i and P(h;a)6= i.
Then we say that an extensive game has perfect recall i,for every player i 2 N,
information set Ii2Ii,and histories h;h02Ii,Xi(h) = Xi(h0),Observe that Xi is de ned
at every history,but the notion of perfect recall imposes direct restrictions only at histories
where Player i moves.
Note that,in particular,perfect recall implies that it is never the case that,for some
history h and sequence of actions h0,both h and (h;h0) belong to the same information set.
4
Strategies
Pure and mixed strategies in general extensive games are easily de ned:
De nition 3 Fix an extensive game and a player i2N,A pure strategy for Player i is
a map si,Ii!A such that,for all Ii2Ii,si(Ii)2A(Ii).
Denote by Si,S i and S the sets of strategies of Player i,the set of strategy pro les of
i’s opponents,and the set of complete strategy pro les respectively,A mixed strategy for
Player i is a probability distribution i2 (Si).
The notion of randomization captured in De nition is as follows,at the beginning of the
game,players spin a roulette wheel to choose a pure strategy,and stick to that strategy
thereafter.
However,players could also randomize at each information set,This gives rise to a
di erent notion:
De nition 4 Fix an extensive game and a player i2N,A behavioral strategy for Player
i is a map i,Ii! (A) such that,for all Ii2Ii,i(Ii)(A(h)) = 1.
Denote byBi,B i andBthe sets of i’s behavioral strategies,of her opponents’ behavioral
strategy pro les,and of complete behavioral strategy pro les.
If this reminds you of our de nition of chance moves,it should,the function fc is simply
Chance’s behavioral strategy!
It is natural to ask whether the two notions of randomization are related,The answer
is that,of course,they are,To be precise about this,we rst de ne (with some abuse of
notation) the outcome functions O,B! (Z) and O,Qi2N (Si) ! (Z) to be the
maps which associate with each pro le of behavioral or mixed strategies a distribution over
terminal nodes (you should provide a formal de nition).
We then ask two distinct questions,First,given a behavioral strategy pro le 2B,can
we nd an outcome-equivalent mixed strategy pro le,i.e,some 2Qi2N (Si) such that
O( ) = O( )?
The answer is a rmative for all games which satisfy the following condition,for every
player i2N,information set Ii 2Ii,and histories h;h02Ii,it is never the case that h is
a subhistory of h0 or vice-versa,Hence,in particular,the answer is a rmative for all games
with perfect recall,OR provides an example (p,214) where this condition fails.
Second,given a mixed strategy pro le,can we nd an outcome-equivalent behavioral
strategy pro le? The answer is again a rmative,if we restrict ourselves to games with
perfect recall,This is Proposition 214.1 in OR,also known as Kuhn’s Theorem.
I conclude by noting that a Nash equilibrium of an extensive game is simply a Nash
equilibrium of (the mixed extension of) its normal form; you can think of a formal de nition,
using outcome functions.
5
