普林斯顿大学博弈论讲义10
更新时间:2023-06-06 02:28:01 阅读量: 实用文档 文档下载
- 普林斯顿大学博弈论推荐度:
- 相关推荐
普林斯顿大学博弈论讲义3-10
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 payo?uncertainty as well.
The analysis of extensive games is challenging in several ways.At the most basic level, describing the possible sequences of events(choices)which de?ne a particular game form is not problematic per se;yet,di?erent formal de?nitions have been proposed,each with its pros and cons.
Representing the players’information as the play unfolds is nontrivial:to some extent, research on this topic may still be said to be in progress.
The focus of this course will be on solution concepts;in this area,subtle and unexpected di?culties arise,even in simple games.The very representation of players’beliefs as the play unfolds is problematic,at least in games with three or more players.There has been a?erce debate on the“right”notion of rationality for extensive games,but no consensus seems to have emerged among theorists.
We shall investigate these issues in due course.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 encompasses the vast majority of extensive games of economic interest,especially if one allows for payo?uncertainty.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 chooses an
1
普林斯顿大学博弈论讲义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
普林斯顿大学博弈论讲义3-10
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)
De?nition 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:
De?nition 2Fix an extensive-form game with perfect information Γ.For every history h ∈X ,let A (h )={a ∈A :(h,a )∈H }be the set 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 set of strategies of Player i and the set of all strategy pro?les.
Armed with this de?nition (to which we shall need to return momentarily)we are ready to extend the notion of Nash equilibrium to extensive games.
De?nition 3Fix an extensive-form game Γwith perfect information.The outcome function O is a map O :S →Z de?ned by
?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 pro?le.The normal-form payo?function u i is then derived from U i and O in the natural way.Finally:De?nition 4Fix an extensive-form game Γwith perfect information.A pure-strategy Nash equilibrium of Γis a pro?le 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
普林斯顿大学博弈论讲义3-10
Thus,in the game of Figure1,both(a1a2,A)and(d1d2,D)are Nash equilibria.
Observe 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 Player1chooses 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)represents only Player2’s beliefs about Player1’s action in the counterfactual event that she chooses a1at?,and Player2follows it with A.
The key observation here is that this belief is crucial in sustaining(d1d2,D)as a Nash equilibrium.
Games with observable actions and chance moves
The beauty of the OR notation becomes manifest once one adds the possibility that more than one player might choose an action simultaneously at a given history.The resulting game is no longer one of perfect information,because there is some degree of strategic uncertainty. Yet,we maintain the assumption that histories are observable:that is,every player on the move at a history h observes all previous actions and action pro?les which comprise h.
The OR de?nition is a bit vague,so let me provide a rigorous,inductive one.I also add the possibility of chance moves,i.e.exogenous uncertainty.
De?nition5An extensive-form game with observable actions and chance moves is a tuple Γ=(N,A,H,P,Z,U,f c)where:
N is a set of players;Chance,denoted by c,is regarded as an additional player,so c∈N.
A is a set of actions
H is a set of sequences whose elements are points in i∈J A for some A?N∪{c};
Z and X are as in De?nition1;
P is the player correspondence P:X?N∪{c}
U:Z→R N as in De?nition1;
H satis?es the conditions in De?nition1.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}A s.t.(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 de?nition 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
普林斯顿大学博弈论讲义3-10
chosen pro?le then becomes publicly observable.We quite simply replace individual actions with action pro?les in the de?nition 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 de?nition of a strategy needs minimal modi?cations:
De?nition6Fix an extensive-form gameΓwith observable 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 set of strategies of Player i and the set of all strategy pro?les.
In the absence of chance moves,De?nition4applies verbatim to the new setting.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 rede?ne the payo?functions in the natural way).Finally,the de?nition of Nash equilibrium requires no change.
For those of you who are used to the traditional,tree-based de?nition of an extensive game,note that you need to use information sets in order to describe games without perfect information,but with observable actions.That is,you need to use the full expressive power of the tree-based 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 observable actions,albeit possibly with payo?uncertainty;hence,the OR notation is su?cient to deal with most applied problems (payo?uncertainty is easily added to the basic framework,as we shall see).
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
正在阅读:
普林斯顿大学博弈论讲义1006-06
2013清华大学接收外校推荐免试攻读博士(硕士)学位研究生拟预录取05-09
1 总产出及质量12-23
应用水田土壤防渗保水剂试验初报07-28
快乐体育论文03-19
《结构力学习题集》6-位移法12-14
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 普林斯顿大学
- 博弈论
- 讲义
- 材料力学教程习题解答-第八章
- 2009计财能手选拔考试试题及答案
- 黄金分割线使用方法
- 浅谈诊断和治疗中尿HCG假阳性及假阴性体会_姜东河
- 数控铣削中切削参数对加工质量的影响
- 美国教育简介American_education
- 《中国近中国近现代史纲要》各章重点列条
- Word 文档排版技巧
- 青少版新概念1Bunit 28
- 2013年福州市干部普法考试题目及答案
- 脚手架拆除应急预案
- 螺旋行槽曲线轴专机的电气_设计_与制造 电气自动化论文
- 美式乡村、法式田园、英式乡村风格装修的各自特点及设计基础
- 我国跨国公司国际避税行为研究_张想
- NB/T_47004-2009板式热交换器
- 第二章 Web系统开发架构及PHP6简介
- 一种新型共聚型阻燃剂的合成及性能测试
- 申报高级会计师资格材料要求
- 装饰公司安全生产管理制度
- 年产1000T碱性蛋白酶生产车间设计