博弈论 完全信息动态博弈(1)

1、第三章完全信息动态博弈（1）主要内容：一、博弈的扩展式表述二、扩展式表述博弈的纳什均衡三、子博弈精炼纳什均衡四、子博弈精炼纳什均衡应用举例五、重复博弈 一、博弈的扩展式表述1、一个例子：房地产开发博弈某市房地产市场需求有两种状态：高需求和低需求，两家房地产商决定是否进行小区开发。假设开发商的开发成本为4。在市场高需求状态下，若市场只有一个楼盘出售，则售价为8，开发商的利润为4；若市场同时有2个楼盘出售，则售价为6，每个开发商的利润均为2。在市场低需求状态下，若市场只有一个楼盘出售，则售价为5，此时开发商的利润为1；若市场同时有两个楼盘出售，则售价仅为3，开发商各亏损1。（1）高需求开发商B开发

2、不开发开发商A开发2, 24, 0不开发0, 40, 0（2）低需求开发商B开发不开发开发商A开发1, 11, 0不开发0, 10, 0博弈的收益矩阵博弈分类按开发商博弈的先后顺序分：静态博弈：两个开发商同时决策，或后决策者不能观察到先行动者的行动。动态博弈：博弈有先后顺序，且后决策者能观察到先行动者的行动后再行动。按开发商是否知道市场需求状态分：完全信息博弈：若两个开发商都知道市场需求状态（高需求或低需求）。不完全信息博弈：由自然决定市场的需求状态，两开发商不知道。共同知识：在市场各种可能状态和各开发商不同策略组合下的得益矩阵是双方的共同知识。四种博弈类型完全信息静态博弈：市场需求状态是共同

3、知识，两开发商都能观察到市场需求状态，并同时决策。完全信息动态博弈：两开发商都能观察到市场需求状态，开发商A先行动，开发商B在观察到A的行动后再行动。不完全信息静态博弈：两开发商都不能观察到自然决定的市场需求状态，且同时行动。不完全信息动态博弈：两开发商不知道自然决定的市场需求状态，开发商A先行动，开发商B观察到A的行动后再行动。（a）高需求开发商B开发不开发开发商A开发2, 24, 0不开发0, 40, 0（b）低需求开发商B开发不开发开发商A开发1, 11, 0不开发0, 10, 0（1）完全信息静态情形（2）不完全信息静态情形自然以p的概率选择高需求开发商B开发不开发开发商A开发2, 2

4、4, 0不开发0, 40, 0自然以1-p的概率选择低需求开发商B开发不开发开发商A开发1, 11, 0不开发0, 10, 0海萨尼转换自然以p的概率选择高需求，以1-p的概率选择低需求开发商B开发不开发开发商A开发3p1, 3p113p, 0不开发0, 13p0, 0（3）完全信息动态情形N A B情形：自然先确定市场需求状态：高需求或低需求；开发商A首先行动， 在观察到市场需求状态后决定是否开发；开发商B在观察到市场需求状态和A的决策后再决定是否开发。N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1

5、）（0,0）（0,0）完全信息动态博弈图示：N A B开发商A不清楚市场的需求状态，决定是否开发；开发商B 在观察到市场需求和A的决策后决定是否开发。（4）不完全信息动态情形：ANBA高需求低需求开发NB开发开发开发开发高需求不开发低需求不开发不开发不开发（2,2）（4,0）（1,0）（0,4）（0,0）（0,1）（-1,-1）（0,0）不开发ANB的等价表示N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）开发商A不清楚市场的需求状态，决定是否开发；开发商B 在观察到市场需求和A的

6、决策后决定是否开发。N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发p1-p不完全信息动态博弈的其他情形（1）思考：该博弈树代表哪种情形？N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发p1-p不完全信息动态博弈的其他情形（2）思考：该博弈树代表哪种情形？完全信息静态博弈的博弈树N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发不完全信息静态博弈的

7、博弈树铁矿石价格谈判铁矿石谈判的合同价格与现货价格不同，不完全由供求确定，供求双方博弈的主要是对未来需求的预期。完全信息情形下的博弈：高需求低需求不完全信息情形下的博弈：需求方的信号承诺长协价格从年度定价到季度定价2、博弈的扩展式表述的要素博弈的扩展式表述包含以下要素：（1）参与人集合：i=1，2，n。此外，用N代表虚拟参与人自然。（2）行动顺序：谁在什么时候行动。（3）参与人的行动空间：（4）参与人的信息集：（5）参与人的策略集：（6）参与人的支付函数：（7）外生事件的概率分布。扩展型博弈通常用博弈树来描述。要素详解参与人：博弈中的决策主体，有时包括“自然”作为“虚拟参与人”。行动：是参与人

8、在博弈的某个时点的决策变量。行动组合：参与人的行动的有序集。行动顺序：静态博弈和动态博弈信息：是参与人有关博弈的知识，如有关“自然”的选择、其他参与人的特征和行动的知识等。完全信息（complete information）完美信息（perfect information）对称信息（symmetric information）确定信息（certain information）策略：是参与人在给定信息集情况下的行动规则，它规定参与人在什么时候选择什么行动。在静态博弈中，策略和行动是等价的。信息集、行动、策略支付：指在一个特定策略组合下参与人得到的确定（期望）效用水平。结果：均衡策略组合、均衡行动

9、组合、均衡支付组合均衡：是所有参与人最优策略的组合，通常记为 s*=(s1*,s2*,sn*)，即均衡策略。均衡结果3、博弈树的构造博弈树的基本元素有：结；枝；信息集1UDLRz13z2z3z4PQ21UDLRLR211（1）结结。包括：初始结：博弈的起点。决策结：参与人采取行动的时点。终点结：博弈行动路径的终点。记X表示所有结的集合，xX表示某特定结。定义X上的半序（偏序）关系“ ”：x x意味着x在x之前。半序“ ”满足：传递性：若x x且 x x，则有x x。反对称性：若有 x x，则不可能有 x x。 注意：有的书本是以“ ”来表示这一偏序关系。博弈树中不允许出现的情形xxx右图不满足

10、博弈树要求的半序关系：传递性和反对称性。前列集和后续集定义x的前列集为：P（x）xx x定义的x的后续集：T（x）xx x如果P（x），则称x为初始结（假定为唯一的）；如果T（x），则称x为终点结。称p(x)为x的直接前列结，若p(x)P（x），且对x P（x），xp(x)，有x p(x)。如果x是x的直接前列结，则x是x的直接后续结。通常假定x的前列集P（x）是全序的。这就是说，在博弈树中从初始结点到每一个结点都只有一条路。这意味着任何一个非初始结有且仅有一个直接前列结。博弈树中不允许出现的情形（2）x的前列集P（x）不满足全序假定。博弈树要求，除初始结点外，每一个节点有且仅有一个直接前列结

11、。xxx（2）枝（路径）定义函数i：XN，1，2，n，即i(x)表示在决策结x参与人i行动。设xX，记t(x)是x直接后续结集合，A(x)是在决策结x的行动集合。在传递性、反对称性和前列结全序假设下，有：对于一个给定的xX，存在一个一一对应的关系：A(x)t(x)，即当且仅当参与人i(x)选择不同的行动a(x)A(x)时，从一个给定的结x出发，博弈才会到达不同的直接后续结x t(x)。这就是说，从x达到它的每一个直接后续结x，都对应着i(x)的一个唯一行动a(x)。枝的图示枝是一个从决策结到它的直接后续结的连线，代表参与人的一个行动选择。枝：不但完整地描述了每一个决策结参与人的行动空间，而且给

12、出了从一个决策结到下一个决策结的路径。1UDLRz13z2z3z4PQ2（3）信息集博弈树上所有决策结分割成不同的信息集（记为hH），它是X的一个子集，满足：（1）每一个决策结都是同一参与人的决策结；（2）该参与人知道博弈进入该集合的某个决策结，但不知道究竟处于哪一个决策结。记h(x)是X中包含x的信息集，如果xh(x)，则满足：（1）xP(x)，且x P(x)；（2）i(x)=i(x)；（3）A(x)=A(x)。在此基础上，即可用A(h)表示给定信息集h下的行动集合。信息集的表示所有同一信息集的决策结（节点）都由一条虚线连结起来。右图中有几个信息集？1UDLRLR2114、完美信息与完全信息

13、只包含一个决策结的信息集称为单结信息集。如果一个博弈的所有信息集都是单结的，则称该博弈为完美信息博弈（perfectinformation）。完美信息博弈意味着博弈中没有任何两个参与人同时行动，并且所有后行动者能准确知道前行动者采取了什么行动，并且所有人观察到自然的行动。完全信息（completeinformation）是指有关参与人的特征、支付函数和纯策略空间均为博弈各方的共同知识，可以是完美的，也可以是不完美的，如完全信息静态博弈不具有完美信息。 N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（

14、0,0）（0,0）完美信息博弈：N A B情形自然先确定市场需求状态：高需求或低需求；开发商A在观察到市场需求状态后决定是否开发；开发商B在观察到市场需求状态和A的决策后再决定是否开发。不完美信息博弈在房地产开发博弈中，不完美信息博弈有4种情形：（1）若参与人B知道自然的选择和A的选择，A不知道自然的选择。A为非完美信息，有一个信息集，B的信息集有四个。（2）若参与人B不知道自然的选择但知道A的选择，该博弈可分为两类：ANB（A为非完美信息，只有1个信息集）和NAB（A为完美信息，有两个信息集），B的信息集有两个。（3）若参与人B知道自然的选择但不知道参与人A的选择时，B有两个信息集。（4）若

15、参与人B既不知道自然的选择，也不知道参与人A的选择时，B只有一个信息集。不完美信息博弈：情形（1）N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）开发商A为非完美信息。不完美信息博弈：情形（2）若参与人B不知道自然的选择但知道A的选择，B的信息集有两个，针对A的信息集，可将该博弈分为两类：NAB：A为完美信息，有两个信息集ANB：A为非完美信息，只有1个信息集A为完美信息：N A B情形N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0

16、）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）A为不完美信息：A N B情形A高需求低需求开发NB开发开发开发开发高需求不开发低需求不开发不开发不开发（2,2）（4,0）（1,0）（0,4）（0,0）（0,1）（-1,-1）（0,0）不开发A为不完美信息的等价表示：N A B情形N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）不完美信息博弈：情形（3）若参与人B知道自然的选择但不知道参与人A的选择时，B有两个信息集。该博弈可分为两类：NAB：A为完美信息，有两个

17、信息集ANB：A为非完美信息，只有1个信息集A为完美信息： N A B情形N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）A为不完美信息： A N B情形A高需求低需求开发NB开发开发开发开发高需求不开发低需求不开发不开发不开发（2,2）（4,0）（1,0）（0,4）（0,0）（0,1）（-1,-1）（0,0）不开发不完美信息博弈：情形（4）若参与人B既不知道自然的选择，也不知道参与人A的选择时，B只有一个信息集。该博弈也有两类：NAB：A为完美信息，有两个信息集ANB：A为非完美

18、信息，只有1个信息集A为完美信息： N A B情形N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）A为不完美信息： A N B情形A高需求低需求开发NB开发开发开发开发高需求不开发低需求不开发不开发不开发（2,2）（4,0）（1,0）（0,4）（0,0）（0,1）（-1,-1）（0,0）不开发5、完美回忆完美回忆是指没有参与人会忘记自己以前知道的事情，并且所有参与人都知道自己以前的选择。通常，我们假定博弈满足“完美回忆”的要求。参与人不满足完美回忆要求1UDLRLR21A1UDLR

19、LR211参与人不满足完美回忆要求LRLR1122UDUD1NBLRLR1122UDUDN11确保博弈具有完美回忆的条件如果x2h(x1)，xP(x1)，i(x)=i(x1)成立，就存在一个x（可能是x本身），满足：（1）xh(x)（2）xP(x2)（3）在x点为达到x1的行动与在x为达到x2的行动是一样的。则该博弈具有完美回忆特征。完美回忆的实质就是 “同一信息集”假设和“同一行动”假设。LRLR22UDUDx1x2xx11不满足完美回忆的同一行动假设1UDLRLR21A1UDLRLR211不满足完美回忆的同一信息集假设LRLR1122UDUD1NBLRLR1122UDUDN116、博弈的扩

20、展式表述要素小结参与人集合：i=1，2，n。此外，用N代表虚拟参与人自然。行动顺序：i(x)参与人的行动空间：Ai(x)参与人的信息集：hi(x)参与人的策略集：策略表示从信息集到行动集上的映射支和路径参与人的支付函数：外生事件的概率分布：二、扩展式表述博弈的纳什均衡1、策略与纳什均衡2、行为策略 3、逆向归纳法 1、策略与纳什均衡令Hi为第i个参与人的信息集的集合，AihiHiA(hi)为其行动集合，其中A(hi)为在信息集hi的行动集合。参与人i的一个纯策略是从信息集Hi到行动集合Ai的一个映射si：HiAi，对所有的hiHi，满足si(hi)A(hi)。策略与行动纯策略指出了参与人在他的

21、每一个信息集上如何选择行动，而行动只是度量了他在某一个特定信息集上如何选择。参与人i的纯策略空间Si就是所有纯策略的集合，即：)(iHhihASii 一般地，参与人i的纯策略空间的纯策略数目为：iiHhiihAS)(#*),(maxarg*iiiSsissusii混合策略是纯策略空间上的一概率分布。每一个策略组合决定了一个支付向量u=(u1,u2,un)。策略组合s*是扩展式博弈的一个纳什均衡，如果对所有的i，si*最大化ui(si,s-i*)。即： 纯策略和混合策略解释用Luce和Raiff的比喻来说，参与人i的每一个纯策略si相当于一本指导说明书，书中的每一页表示到了一个特定的信息集hi，

22、在该页上（到达该信息集的一个决策结）告诉参与人i在该信息集上如何行动。Si则表示书架上书的全体，混合策略则表示参与人以一定的概率分布从书架上随机抽取一本书。 N A B情形的纯策略自然需求是共同信息，开发商A先行动，开发商B在观察到A的决策后行动。 B有两个信息集A开发，A不开发，在每个信息集上有两个可供选择的行动开发，不开发，则B有四个纯策略：（开发，开发），（开发，不开发），（不开发，开发）和（不开发，不开发）开发不开发AB开发开发不开发不开发N A B情形的混合策略若在房地产开发博弈中，若B在观察到市场需求状态和A的行动后再决策。A的纯策略空间SA开发，不开发B的纯策略空间SB（开发，开

23、发），（开发，不开发），（不开发，开发），（不开发，不开发）。B的混合策略是纯策略空间SB上的概率分布。2、行为策略 行为策略：是指每一个参与人在每一个信息集上随机的选择行动。令（A(hi)）为定义在行动集合A(hi)上的概率分布，bi是参与人i的一个行为策略，则： )(iHhihAbii行为策略理解一个行为策略规定了对应每一个信息集的行动集合上的概率分布，且不同信息集上的概率分布是独立的。纯策略可理解为行为策略的特例（概率分布退化）。每一个行为策略组合给出一个支付空间上的概率分布。称b*=(b1*, b2*, , bn*)是一个行为策略纳什均衡，如果没有任何参与人可以通过选择其他行为策略增加

24、自己的期望效用 。行为策略解释纯策略与混合策略纯策略指出了参与人在他的每一个信息集上如何选择行动，行为策略则指示参与人在他的每一个信息集上如何随机地选择行动。类似于纯策略和混合策略的解释，行为策略相当于一本百科全书，参与人i翻到某一页，也就是到达信息集hi的一个决策结，这一页上列举了基于该信息集hi的所有行动A(hi)，并告诉他随机地从A(hi)中选取一个行动。这就是说，读这本书就相当于从书架上随机地取书。 在房地产开发博弈中，若开发商2（开发商B）在观察到市场需求和A的行动后再决策，则2有两个信息集A开发，A不开发，在每个信息集上有两个可供选择的行动开发，不开发，则：纯策略空间S2（开发，开

25、发），（开发，不开发），（不开发，开发），（不开发，不开发）。混合策略空间222=(21，22，23，24)是S2上的概率。行为策略空间B2b2b2=（(p, 1-p)，(q, 1-q)），这里p、q分别表示在信息集A开发和信息集A不开发条件下开发商2选择开发的概率。等价性在完美回忆博弈中，行为策略与混合策略这两个概念是等价的，即任何混合策略等价于一个唯一的行为策略，任何一个行为策略等价于每一个从该行为策略中构造的混合策略，等价意味着对于其他参与人的所有策略，在支付（结果）上定义了相同的概率分布。由于通常只考虑完美回忆博弈，因而可用混合策略代替行为策略。 等价性例子B的纯策略空间SB(开发，开

26、发)，(开发，不开发)，(不开发，开发)，(不开发，不开发)，考虑其行为策略b2=（(p, 1-p)，(q, 1-q)），混合策略2=(21,22,23,24)，则以下条件满足时，该行为策略和混合策略在结果上定义了相同的概率分布。开发不开发AB开发开发不开发不开发p=21+221-p=23+24q=21+231-q=22+243、博弈的扩展式表述与标准式表述的转换若在房地产开发博弈中，自然选择的需求是参与人的共同知识，A先行动，B在观察到A的行动后再决策。 A只有一个信息集，其行动空间也即策略空间SA开发，不开发，但B有两个信息集，在每个信息集上有两个可供选择的行动，故B有四个纯策略SB（开发

27、，开发），（开发，不开发），（不开发，开发），（不开发，不开发）。高需求情形开发商B（开发，开发）（开发，不开发）（不开发，开发）（不开发，不开发）开发商A开发2, 22, 24, 04, 0不开发0, 40, 00, 40, 0低需求情形开发商B（开发，开发）（开发，不开发）（不开发，开发）（不开发，不开发）开发商A开发-3, -3-3, -31, 01, 0不开发0, 10, 00, 10, 0在高需求状态下，有两个纯策略纳什均衡：（开发，（开发，开发）和（开发，（开发，不开发），纳什均衡结果为（开发，开发）；在低需求状态下，有三个纯策略纳什均衡：（开发，（不开发，开发）、（开发，（不开发

28、，不开发）和（不开发，（开发，开发），均衡结果为（开发，不开发）或（不开发，开发）。在扩展式博弈中，每一个策略组合给出了一条博弈路径，每一个纯策略纳什均衡则给出了一条均衡路径。 开发不开发（1）高需求（2）低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）AB4、逆向归纳法 如果一个扩展式博弈有有限个信息集，每个信息集上参与人有有限个行动选择，则称为有限博弈。由纳什均衡存在性定理，有限博弈存在混合策略纳什均衡。特别地有：定理：一个有限完美信息博弈存在一个纯策略纳什均衡。 逆向归纳法思想分析：有限博弈一

29、定存在一个最后的决策结（其直接后续结是终点结）的集合，在该决策结上行动的参与人将选择一个最大化自己的支付的行动；给定这个参与人的行动，倒数第二个决策结上的参与人将选择一个可行的行动最大化自己的支付；如此类推，直至初始结。该倒推过程完成时得到了一条路径，该路径给出了每一个参与人的一个特定的策略，它是一个纳什均衡（子博弈精炼纳什均衡）。逆向归纳法实质是重复剔除严格劣策略方法在扩展式博弈中的运用。 逆向归纳法要求“所有参与人是理性的”是共同知识，它只适用于完美信息博弈。但其逻辑方法亦可用于某些非完美信息博弈。完全信息动态条件下的房地产开发博弈求解：N开发不开发高需求低需求AB开发开发开发开发开发不开

30、发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）N A B情形（0）（-1,-1）（0,1）N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（1,0）（0,0）（0,0）N A B情形（1）N A B情形（2）N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）（2,2）（2,2）（0,1）（1,0）（0,4）（1,0）三、子博弈精炼纳什均衡 1、子博弈精炼纳什均衡

31、2、用逆向归纳法求解子博弈精炼纳什均衡3、子博弈精炼纳什均衡存在的问题 1、子博弈精炼纳什均衡 子博弈：一个扩展式博弈的子博弈G由一个决策结x和所有该决策结的后续结T(x)（包括终点结）组成，它满足：（1）x是一个单结信息集，即h(x)=x；（2）对于所有的xT(x)，如果xh(x)，则xT(x)。条件（1）是指子博弈必须从一个单结信息集开始；条件（2）说明子博弈的信息集和支付向量直接承自原博弈。这意味着子博弈不能切割原博弈的信息集。同时，任何博弈是它自身的子博弈。 各有几个子博弈？1UDLRLR21LRLR1122UDUDN111子博弈精炼（完美）纳什均衡：扩展式博弈的策略组合s*=(s1*

32、, s2*, , sn*)是一个子博弈精炼纳什均衡，如果：（1）它是原博弈的纳什均衡；（2）它在每一个子博弈上给出纳什均衡。 一个特定的纳什均衡决定了原博弈树上唯一的一条路径，称为均衡路径，博弈树上的其它路径称为非均衡路径。纳什均衡只要求均衡策略在均衡路径上是最优的，构成子博弈精炼纳什均衡的策略则意味着不仅在均衡路径的决策结上是最优的，而且在非均衡路径的决策结上也是最优的。N A B情形下的子博弈精炼纳什均衡N开发不开发高需求低需求AB开发开发开发开发开发不开发不开发不开发不开发不开发（2,2）（4,0）（0,4）（-1,-1）（1,0）（0,1）（0,0）（0,0）（2,2）（2,2）（0,1）（1,0）（0,4）（1,0）在高需求状态下，有两个纯策略纳什均衡：（开发，（开发，开发）和（开发，（开发，不