普林斯顿大学博弈论讲义10(2)

普林斯顿大学博弈论讲义3-10

action.Sequences of actions are called histories;some histories are terminal,i.e.no further

actions are taken,and players receive their payo?s.Moreover,at each stage every player

gets to observe all previous actions.

De?nition1An extensive-form game with perfect information is a tupleΓ=(N,A,H,P,Z,U)

where:

N is a set of players;

A is a set of actions;

H is a collection of?nite and countable sequences 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 set of terminal histories:that is,(a1,...,a k)∈Z i?(a1,...,a k)∈H and

(a1,...,a k,a)∈H for all a∈A.Also let X=H\Z.All in?nite 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 payo?function,associating a vector of payo?s to every

terminal history.

I di?er from OR in two respects:?rst,I?nd it useful to specify the set of actions in

the de?nition of an extensive-form game.Second,at the expense of some(but not much!) generality,I represent preferences among terminal nodes by means of a vN-M utility function.

Interpreting De?nition1

A few comments on formal aspects are in order.First,actions are best thought of as move

labels;what really de?nes the game is the set H of sequences.If one wishes,one can think of

A as a product set(i.e.every player gets her own set of move labels),but this is inessential.

Histories encode all possible partial and complete plays of the gameΓ.Indeed,it is

precisely 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),};?nally,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 de?nition of H says that every sub-history of a history h is itself a history in

its own right.Part(iii)is a“limit”de?nition of in?nite histories.Note that in?nite 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 observe it.

2

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究普林斯顿大学博弈论讲义10(2)全文阅读和word下载服务。