Eco514—Game Theory
Lecture10:Extensive Games with(Almost)Perfect
Information
什么是母乳性黄疸Marciano Siniscalchi
October19,1999
Introduction
Beginning with this lecture,we focus our attention on dynamic games.The majority of games of economic interest feature some dynamic component,and most often payoffuncertainty as well.
The analysis of extensive games is challenging in veral ways.At the most basic level, describing the possible quences of events(choices)which define a particular game form is not problematic per ;yet,different formal definitions have been propod,each with its pros and cons.
Reprenting the players’information as the play unfolds is nontrivial:to some extent, rearch on this topic may still be said to be in progress.
The focus of this cour will be on solution concepts;in this area,subtle and unexpected difficulties ari,even in simple games.The very reprentation of players’beliefs as the play unfolds is problematic,at least in games with three or more players.There has been afierce debate on the“right”notion of rationality for extensive games,but no connsus ems to have emerged among theorists.
We shall investigate the issues in due cour.Today we begin by analyzing a particu-larly simple class of games,characterized by a natural multistage structure.I should point out that,perhaps partly due to its simplicity,this class encompass the vast majority of extensive games of economic interest,especially if one allows for payoffuncertainty.We shall return to this point in the next lecture.
Games with Perfect Information
Following OR,we begin with the simplest possible extensive-form game.The basic idea is as follows:play proceeds in stages,and at each stage one(and only one)player choos an
1
action.Sequences of actions are called histories;some histories are further
actions are taken,and players receive their payoffs.Moreover,at each stage every player
gets to obrve all previous actions.
Definition1An extensive-form game with perfect information is a tupleΓ=(N,A,H,P,Z,U)
where:
N is a t of players;
A is a t of actions;
H is a collection offinite and countable quences of elements from A,such that:
(i)∅∈H;
(ii)(a1,...,a k)∈H implies(a1,...,a )∈H for all <k;
(iii)If h=(a1,...,a k,...)and(a1,...,a k)∈H for all k≥1,then h∈H.
Z is the t of terminal histories:that is,(a1,...,a k)∈Z iff(a1,...,a k)∈H and
(a1,...,a k,a)∈H for all a∈A.Also let X=H\Z.All infinite histories are terminal.
寒鸦是什么意思P:X→N is the player function,associating with each non-terminal history h∈X the
player P(h)on the move after history h.
U=(U i)i∈N:Z→R is the payofffunction,associating a vector of payoffs to every
terminal history.
I differ from OR in two respects:first,Ifind it uful to specify the t of actions in
环境适应the definition of an extensive-form game.Second,at the expen of some(but not much!) generality,I reprent preferences among terminal nodes by means of a vN-M utility function.
Interpreting Definition1
A few comments on formal aspects are in order.First,actions are best thought of as move
labels;what really defines the game is the t H of quences.If one wishes,one can think of
A as a product very player gets her own t of move labels),but this is inesntial.
Histories encode all possible partial and complete plays of the gameΓ.Indeed,it is
precily by spelling out what the possible plays are that we fully describe the game under consideration!
Thus,consider the following game:N={1,2};A={a1,d1,a2,d2,A,D};H={∅,(d1),(a1),(a1,D),(a1, thus,Z={(d1),(a1,D),(a1,A,d2),(a1,A,a2)}and X={∅,(a1),(a1,A),};finally,P(∅)=
银行办理贷款P((a1,A))=1,P(a1)=2,and U((d1))=(2,2),U((a1,D))=(1,1),U((a1,A,d1))=(0,0),
U((a1,A,a2))=(3,3).ThenΓ=(N,A,H,Z,P,U)is the game in Figure1.
The empty history is always an element of H,and denotes the initial point of the game.
Part(ii)in the definition of H says that every sub-history of a history h is itlf a history in
its own right.Part(iii)is a“limit”definition of infinite histories.Note that infinite histories
are logically required to be terminal.
A key assumption is that,whenever a history h occurs,all players(in particular,Player
P(h))get to obrve it.
2
干锅土豆3,3r 12,2d 1a 1
r 2D A 1,1r 1d 2a 20,0
Figure 1:A perfect-information game
Strategies and normal form(s)
Definition 1is arguably a “natural”way of describing a dynamic game—and one that is at least implicit in most applications of the theory.
发红包英语According to our formulations,actions are the primitive objects of choice.However,the notion of a strategy ,i.e.a history-contingent plan,is also relevant:
Definition 2Fix an extensive-form game with perfect information Γ.For every history h ∈X ,let A (h )={a ∈A :(h,a )∈H }be the t of actions available at h .Then,for every player i ∈N ,a strategy is a function
s i :P −1(i )→A such that,for every h such that P (h )=i ,s i (h )∈A (h ).Denote by S i and S the t of strategies of Player i and the t of all strategy profiles.
Armed with this definition (to which we shall need to return momentarily)we are ready to extend the notion of Nash equilibrium to extensive games.
Definition 3Fix an extensive-form game Γwith perfect information.The outcome function O is a map O :S →Z defined by
fob怎么算∀h =(a 1,...,a k )∈Z, <k :a +1=s P ((a 1,...,a ))((a 1,...,a ))
The normal form of the game Γis G Γ=(N,(S i ,u i )i ∈N ),where u i (s )=U i (O (s )).
水果拼盘图片大全大图
The outcome function simply traces out the history generated by a strategy profile.The normal-form payofffunction u i is then derived from U i and O in the natural way.Finally:Definition 4Fix an extensive-form game Γwith perfect information.A pure-strategy Nash equilibrium of Γis a profile of strategies s ∈S which constitutes a Nash equilibrium of its normal form G Γ;a mixed-strategy Nash equilibrium of Γis a Nash equilibrium of the mixed extension of G Γ.
3
Thus,in the game of Figure1,both(a1a2,A)and(d1d2,D)are Nash equilibria.
Obrve that a strategy indicates choices even at histories which previous choices dictated by the same strategy prevent from obtaining.In the game of Figure1,for instance,d1a1is a strategy of Player1,although the history(a1,A)cannot obtain if Player1choos d1at∅.
It stands to reason that d2in the strategy d1d2cannot really be a description of Player 1’s action—she will never really play d2!
We shall return to this point in the next lecture.For the time being,let us provisionally say that d2in the context of the equilibrium(d1d2,D)reprents only Player2’s beliefs about Player1’s action in the counterfactual event that she choos a1at∅,and Player2follows it with A.
The key obrvation here is that this belief is crucial in sustaining(d1d2,D)as a Nash equilibrium.
Games with obrvable actions and chance moves
The beauty of the OR notation becomes manifest once one adds the possibility that more than one player might choo an action simultaneously at a given history.The resulting game is no longer one of perfect information,becau there is some degree of strategic uncertainty. Yet,we maintain the ass
umption that histories are obrvable:that is,every player on the move at a history h obrves all previous actions and action profiles which compri h.
The OR definition is a bit vague,so let me provide a rigorous,inductive one.I also add the possibility of chance enous uncertainty.
Definition5An extensive-form game with obrvable actions and chance moves is a tuple Γ=(N,A,H,P,Z,U,f c)where:
N is a t of players;Chance,denoted by c,is regarded as an additional player,so c∈N.
A is a t of actions
H is a t of quences who elements are points in i∈J A for some A⊂N∪{c};
Z and X are as in Definition1;
P is the player correspondence P:X⇒N∪{c}
U:Z→R N as in Definition1;
H satisfies the conditions in Definition1.Moreover,for every k≥1,(a1,...,a k)∈H implies that(a1,...,a k−1)∈H and a k∈ i∈P((a1,...,a k−1))A.
For every i∈N∪{c},let A i(h)={a i∈A:∃a−i∈ j∈P(h)\{i}(h,(a i,a−i))∈H}. Then f c:{h:c∈P(h)}→∆(A)indicates the probability of each chance move,and f c(h)(A i(h))=1for all h such that c∈P(h).
The definition is apparently complicated,but the underlying construction is rather nat-ural:at each stage,we allow more than one player(including Chance)to pick an action;the
4
chon profile then becomes publicly obrvable.We quite simply replace individual actions with action profiles in the definition of a history,and adapt the notation accordingly. Remark0.1Let A(h)={a∈ i∈P(h)A:(h,a)∈H}.Then A(h)= i∈P(h)A i(h).
The definition of a strategy needs minimal modifications:
Definition6Fix an extensive-form gameΓwith obrvable actions and chance moves. Then,for every player i∈N∪{c},a strategy is a function s i:{h:i∈P(h)}→A such that,for every h such that i∈P(h),s i(h)∈A i(h).Denote by S i and S the t of strategies of Player i and the t of all strategy profiles.
In the abnce of chance moves,Definition4applies verbatim to the new tting.You can think about how to generalize it with chance moves(we do not really wish to treat Chance as an additional player in a normal-form game,so we need to redefine the payofffunctions in the natural way).Finally,the definition of Nash equilibrium requires no change.
For tho of you who are ud to the traditional,tree-bad definition of an extensive game,note that you need to u information ts in order to describe games without perfect information,but with obrvable actions.That is,you need to u the full expressive power of the tree-bad notation in order to describe what is a slight and rather natural extension of perfect-information games.1
Most games of economic interest are games with obrvable actions,albeit possibly with payoffuncertainty;hence,the OR notation is sufficient to deal with most applied problems (payoffuncertainty is easily added to the basic framework,as we shall e).
1On the other hand,the OR notation is equivalent to the standard one for games with perfect information: just call histories“nodes”,actions“arcs”,terminal histories“leaves”and∅“root”.
5
