完全信息动态博弈

2完全信息动态博弈扩展型博弈表述扩展型博弈的战略及纳什均衡子博弈精炼纳什均衡子博弈精炼纳什均衡应用举例2完全信息动态博弈动态博弈：参与人的行动有先后顺序，且后行动者能够观察到先行动者的行动(电信公司、电信用户及资费套餐）。先行动者的选择影响后行动者的选择空间，后行动者可以观察到先行动者做了什么选择，因此，为了做出最优的行动选择，每个参与人都必须这样思考问题：如果我如此选择，对方将如何应对？给定他的应对，什么是我的最优选择？(美女；帅哥）例：欺负他人可以获得快乐，你会欺负他人吗？不会。欺负他人会担心他人的报复，抵消了从欺负他人的行为中获得快乐。——先行动者在选择行动时要考虑自己的选择对后行动者的影响。一、动态博弈的扩展式表述I如何用扩展式表述（extensiveformrepresentation）来描述动态博弈？例1，解放初，美国总是寻找各种机会来侵犯我国。对此，毛主席提出了“人不犯我、我不犯人，人若犯我、我必犯人”的战略方针。该动态博弈的战略式表述局中人：美国、中国行动空间：美国“犯我”或“不犯我”，中国“犯人”或“不犯人”行动顺序：美国先行动，我国依美国的行动而后动支付：这样假设支付情况：若美国“犯我”，中国“犯人”，则支付向量为(-2,-2)；一、动态博弈的扩展式表述Ⅱn人有限战略的扩展式表述：博弈树（gametree）犯人犯我不犯我犯人不犯人不犯人美国我国我国(1,1)(3,-5)(2,-4)(-2,-2)若美国“犯我”，中国“不犯人”，则支付向量为(2,-4)；若美国“不犯我”，中国“犯人”，则支付向量为(3,-5)；若美国“不犯我”，中国“犯人”，则支付向量为(1,1)。2人有限博弈的战略式表述：支付矩阵决策结：行动的时点枝终点结参与人集合：，此外，虚拟参与人“自然”；参与人的行动顺序（theorderofmoves）：谁在什么时候行动；参与人的行动空间（actionset）：在每次行动时，参与人有些什么选择。参与人的信息集（informationset）：每次行动时，参与人知道些什么；参与人的支付函数；外生事件（即自然的选择）的概率分布扩展式表述的要素：ni,,1一、动态博弈的扩展式表述Ⅵ一、动态博弈的扩展式表述Ⅲ例2：两个房地产商A、B进行房地产开发博弈。市场需求大、小的概率各占50%。投入：1亿。假定市场上有两栋楼出售：需求大时，每栋售价1.4亿，需求小时，售价7千万；如果市场上只有一栋楼需求大时，可卖1.8亿需求小时，可卖1.1亿行动顺序：(1)开发商A首先行动，选择开发或不开发；(2)在A决策后，自然选择市场需求的大小；(3)开发商B在观测到A的决策和市场需求后，决定是否开发A开发不开发NN大小1/21/2大小1/21/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)房地产开发博弈（图2.1)注意：支付向量的顺序与博弈树上行动顺序是对应的！A开发不开发NN大小1/21/2大小1/21/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)B在决策时不确切地知道自然的选择;B的信息集由4个变为2个该参与人知道博弈进入该集合的某个决策结，但不知道自己究竟处于哪一个决策结A开发不开发NN大小1/21/2大小1/21/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)B知道自然的选择;但不知道A的选择(或A、B同时决策)房地产开发博弈信息集（informationset）的概念：是决策结集合的一个子集，该子集包括所有满足下列条件的决策结：每一个决策结都是同一参与人的决策结；该参与人知道博弈进入该集合的某个决策结，但不知道自己究竟处于哪一个决策结。只包含一个决策结的信息集称为单结信息集，如果博弈树的所有信息都是单结的，该博弈称为完美信息博弈。（博弈中没有任何参与人同时行动，且后行动者能观察到先行动者的行动，且所有参与人观察到N的行动）一、动态博弈的扩展式表述ⅣA开发不开发NN大小1/21/2大小1/21/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)表示B在行动前既观察不到A的行动，也观察不到N的行动房地产开发博弈N大小AA开发不开发开发不开发1/2BBBB开发不开发开发不开发开发不开发开发不开发(4,4)(8,0)(0,8)(0,0)(-3,-3)(1,0)(0,1)(0,0)不同的博弈树可能代表相同的博弈，但有一个基本准则一个参与人决策之前知道的事情必须出现在该参与人的决策结之前实际上是A先行动＞N＞B（图2.5)1/2静态博弈用扩展式表述。例囚徒困境博弈一、动态博弈的扩展式表述ⅤBAA坦白抵赖坦白抵赖坦白抵赖(-8,-8)(0，-10)(-10,0)(-1,-1)A坦白抵赖BB坦白抵赖坦白抵赖(-8,-8)(0，-10)(-10,0)(-1,-1)二、动态博弈中的战略令Hi为第i个参与人的信息集的集合,Ai=hiHiA(hi)为其行动集合，其中A(hi)是在信息集hi的行动集合。参与人i的一个纯战略是从信息集集合Hi到行动集Ai的一个映射，用Si：HiAi表示，其中，对于所有的hiHi,Si(hi)A(hi),参与人的纯战略空间Si就是所有的Si的集合，因为每一个纯战略都是从信息集到行动集的一个映射，Si可以表示为每一个信息集hi上的行动空间A(hi)的笛卡尔积：Si=hiHiA((hi)二、动态博弈中的战略战略是一个完备的行动计划：在博弈开始之前就规定出每一个决策点上的选择，即使这个决策点实际上不会出现。例1：房地产开发博弈(映射关系)AB不开发(0,0)(0,1)(1,0)B若A先行动，B在知道A的行动后行动，则A有一个信息集，两个可选择的行动，战略空间为:(开发，不开发）；B有两个信息集，2个可选择的行动，B有四个纯战略：开发策略：不论A开发不开发，我开发——{开发，开发}追随策略：A开发我开发，A不开发我不开发——{开发，不开发}；反向策略：A开发我不开发，A不开发我开发——{不开发，开发}；不开发策略:不论A开发不开发我不开发）——{不开发，不开发}；战略空间为：{开发，开发}、{开发，不开发}、{不开发，开发}（不开发，不开发}。A开发不开发BB开发不开发开发(-3,-3)(1，0)（0，1)(0,0)不开发xx’什么是参与人的战略？三、战略式表述下的纳什均衡Ⅰ开发不开发AB{开发,开发}-3，-3-3，-31，01，00，10，00，10，0{开发,不开发}{不开发,开发}{不开发,不开发}A（不开发,{开发,开发}）三个纯战略NE：（开发，{不开发，开发}）；（开发；{不开发，不开发}）；（不开发，{开发，开发}）问题：哪一个会出现呢？三、战略式表述下的纳什均衡ⅡNE(不开发,{开发,开发})：B威胁无论A是否开发自己都将开发，A相信了威胁，则最好选择不开发；如果A选择不开发，则B选择{开发,开发}是最优的。A会相信B的威胁吗？如果A选择了开发，B的最好选择不开发。——B的威胁是不可置信的(notcredible)：给定A选择了“开发”，“开发”不是B的最优选择。(不开发,{开发,开发})不会是该博弈合理的均衡。为什么？三、战略式表述下的纳什均衡Ⅲ纳什均衡假定每一个参与人在选择自己的最优战略时假定所有其他参与人的战略是给定的，即参与人并不考虑自己的选择对他人的影响。但是如果参与人的行动有先有后，后行动者的选择空间依赖于前行动者的选择，先行动者在选择时不可能不考虑自己的行动对后行动者的影响。NE(开发,{不开发,不开发})：{不开发，不开发}不是B一个合理的战略,因为如果A选择了不开发，B的最优选择是开发而非不开发。NE（开发，{不开发，开发}）：若A选择开发，B的最优选择是开发；若A选择不开发，则B选择开发。A预测到自己的选择对B产生的影响，选择开发。四、子博弈精炼纳什均衡IⅡⅢ不包含不可置信的行动的战略所组成的NE被称为“精炼纳什均衡”(PerfectNashequilibrium)；也就是说，不论过去发生了什么，构成精炼纳什均衡的战略，其所规定的行动在每一个决策点上都是最优的;首先必须是“纳什均衡”，但并非所有纳什均衡都是合理的；只有其战略不包含不可置信行动的纳什均衡才是合理的。子博弈。A开发不开发BB开发不开发开发不开发(-3,-3)（1,0)(0,1)(0,0)定义：一个扩展式博弈的子博弈G由一个决策结和所有该决策结的后续结T（x）组成，它满足下列条件：1、x是单结信息集，即h(x)=x;2、对于所有的x1T(x),如果x2h(x1),那么x2T(x)有几个子博弈？AUDBBLRLRCCCClrlrlrlr(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)o0四、子博弈精炼纳什均衡Ⅱ子博弈：由原博弈中某个决策点（信息集）开始的部分构成一个子博弈。原博弈不开发开发(0,0)(0,1)(1,0)(-3,-3)BAxx’x子博弈I(-3,-3)(1,0)x’子博弈Ⅱ(0,1)(0,0)开发不开发不开发开发四、子博弈精炼纳什均衡Ⅲ一个纳什均衡是精炼纳什均衡，当只当参与人的战略在每个子博弈中都构成纳什均衡，也就是说，组成精炼纳什均衡的战略必须在每一个子博弈中都是最优的。——泽尔腾（Selten）（1965）：子博弈精炼纳什均衡(SubgameperfectNashequilibrium,SPNE)序贯理性（sequentialrationality）：不管过去发生什么，参与人在每一个决策结上最优化自己的行动。例，房地产开发博弈：（不开发，{开发，开发}）在子博弈Ⅰ上不构成NE；（开发，{不开发，不开发}）在子博弈Ⅱ不构成NE；（开发，{不开发，开发}）在所有子博弈上都构成NE。四、子博弈精炼纳什均衡Ⅳ例UDLR(2,2)(3,1)(0,0)122，22，23，10，01UDLR2NE（U,R）在子博弈上不构成NE；NE（D,L)在子博弈上构成NE，所以为SPNE；四、子博弈精炼纳什均衡Ⅵ逆向归纳法(backwardinduction)求解有限博弈的精炼纳什均衡：从最后一个决策点开始，找出该子博弈的纳什均衡；然后再倒回到倒数第二个决策点，找出决策者的最优决策（假定最后一个决策者的决策是最优的；如此一直到初始决策点，所有子博弈上的最优选择就是精炼纳什均衡。又称“rollback”。逆向归纳法只适用于完美信息博弈。犯人犯我不犯我犯人不犯人不犯人美国我国我国(1,1)(3,-5)(2,-4)(-2,-2)例1：逆向归纳法找中美军事博弈的SPNE均衡为（不犯我，{犯人，不犯人}）例2：121（2，0）（5，0）（4，2）（1，1）UDRLU’D’均衡为（{U,U’}；L）,均衡结果为1选择U。四、子博弈精炼纳什均衡Ⅶ特定的纳什均衡下所经过的决策点和最优选择构成的路径，称为均衡路径（equilibriumpath);其他的路径是非均衡路径（off-equilibriumpath);SPNE与NE的实际区别：SPNE要求在每个子博弈上构成纳什均衡=构成SPNE的战略不仅在均衡路径的决策结上最优，而且在非均衡路径的决策结上也是最优的轮流出价的讨价还价模型两人分一块蛋糕,参与人1先出价,参与人2可以接受或拒绝.如果参与人2接受,博弈结束;如果参与人2拒绝,参与人2出价,参与人1此时必须接受.问此博弈的精炼的纳什均衡?用x表示参与人1的份额,(1-x)表示参与人2的份额,假定参与人1与参与人2的贴现因子分别为1,2乙112乙(1,-1)甲(-1,1