第三章 完全信息动态博弈1.ppt

第三章完全信息动态博弈,一、博弈的扩展式表述二、扩展式表述博弈的NE三、逆向归纳法四、子博弈精练NE五、子博弈精练NE应用举例六、重复博弈和无名氏定理七、SWARM博弈仿真研究八、应用举例供应链的协调,一、博弈的扩展式表述,扩展式与战略式比较：战略式表述：参与人战略支付自然选择(高、低),一、博弈的扩展式表述,一、博弈的扩展式表述,自然选择(以概率分布来表达),二、扩展式表述博弈的NE,扩展式表述博弈：参与人是相机行事，即i“等待”G(博弈)到达自己的信息集h(i)后再决定如何行动；战略式表述博弈：参与人在博弈开始之前就制定出一个完全的相机行动计划，即“如果发生，我将选择”。,二、扩展式表述博弈的NE,A的行动空间（也即战略空间）：SA(开发，不开发)B的战略空间：SB(开发，开发，开发，不开发，不开发，开发，不开发，不开发),二、扩展式表述博弈的NE,1、扩展式表述可构造为战略式表述2、行为战略,1、扩展式表述可构造为战略式表述,2、行为战略,行为战略：在扩展式表述博弈中，混合战略被称为“行为战略”（behaviorstrategies）（1）特点：一个行为战略规定了对应每一个信息集的行动集合上的概率分布，且不同信息集上的概率分布是独立的。(若第i个参与人的信息集hij出现，我们将以A(hi)的概率选择行动集合A(hij)，j=1，2，3，4，)（2）符号表示：行动战略组合b=（b1，b2，bn）给出一个支付空间上的概率分布。混合战略组合=（1，2，n）,（3）混合战略集合不同于扩展式博弈的行为战略集合,卢斯与莱丰(LuceandRaiffa,1957)给出下述的类比来区别二者：,考虑下图：,参与人2有四个纯战略1选UDUDUDUD2选,令参与人2行为战略b2(1/2，1/2)(1/2，1/2)，即在每一个信息集上参与人2以1/2的概率选择一种行动。,结论：一个行为战略可能对应多个混合战略，但逆命题不成立，即一个混合战略只对应一个行为战略。（一个概率选择）,然而，库恩（Kuhn，1953）证明，在完美回忆博弈中，这两个概念是等价的，即任何混合战略i等价于一个唯一的行为战略bi（以概率为1选特定的行动），任何一个行为战略bi等价于每一个从该行为战略构造的混合战略i。“等价”的意思是，对于其他参与人的所有战略，i和bi在结果（支付）上定义了相同的概率分布。,三、逆向归纳法,定理(Zermelo,1913;Kuhn,1953)：一个有限完美信息博弈有一个纯战略纳什均衡。逆向归纳法：从最后的决策结集合(即倒数第二个结，即直接后续结是终点结)倒数第三倒数第四第一结(沿这一路径找到NE)。,三、逆向归纳法,三、逆向归纳法,若1选U，参与人2的信息集不能达到，我们说参与人2的信息集不在均衡路径上(outofequilibriumpath)，在这种情况下，参与人2无论选择什么对他的支付没有影响，因此，NE对参与人在非均衡信息集的选择没有限制。但是，一个参与人在非均衡信息集的战略可能影响其他参与人在均衡信息集上的选择(因为后者在评价他们可使用的其他战略的价值时，不得不考虑如果它们引起原先的非均衡信息集达到的话，什么将发生)。如均衡(U,R)，参与人1选择U而不是D，因为参与人2在非均衡信息集上选择R。若参与人2不是选择R而选择L，这时U就不是参与人1的最优选择。注1：逆向归纳法实际上是重复剔除劣战略在扩展式博弈的应用(每一步均为剔除劣战略)注2：不适用于无限博弈和不完美信息博弈。,四、子博弈精练NE(selten,1965),1、可置信的战略2、SPNE子博弈精练NE3、用逆向归纳法求解子博弈精练NE4、承诺行动与子博弈精练NE5、逆向归纳法与子博弈精练均衡存在的问题,1、可置信的战略,上一章指出：一个博弈可能有多个(甚至无穷多个)NE，究竟哪一个NE更为合理，博弈论没有一般的结论。但是，NE的多重性并不是NE存在的最严重的问题。最严重的问题是，NE假定每一个参与人在选择自己的最优战略时假定所有其他参与人的战略选择是给定的，就是说，参与人并不考虑自己的选择对其他人选择的影响。由于这个原因，NE很难是动态博弈的一个合理解，因为在动态博弈中，参与人的行动有先有后，后行动者的选择空间依赖于前行动者的选择，前行动者在选择自己的战略时不可能考虑自己的选择对后行动者选择的影响。NE这个缺陷促使博弈论专家从20世纪60年代开始就不断寻求改进(perfecting)和精练(refining)NE。,1、可置信的战略,三个NE：（不开发，开发，开发）（不开发，开发）（开发，不开发，开发）（开发，不开发，不开发）,1、可置信的战略,先看(不开发，开发，开发).若A相信B的威胁，不管A开发还是不开发，B都将选择开发，则不开发是A的最优战略。.假定A不开发，则开发，开发是B的最优战略。然而，A为什么要相信B的威胁呢？若A真的选择开发，B的信息集是x，此时，B选择开发得到-3的支付，选择不开发得到0的支付，显然B的最优选择是不开发。如果A知道B是理性的，A将选择开发，逼使B选择不开发，这时A可得支付为1，而不是选择不开发，让B开发，自己得到0的支付。用博弈论的语言来说，NE(不开发，开发，开发)是不可置信的(notcredible)，因为它依赖于B的一个不可置信的威胁战略；这是不可置信的，因为给定A选择开发，B不会实施这个威胁。,1、可置信的战略,再看(开发，不开发，不开发)尽管这个结果(A开发，B不开发)似乎是合理的，但均衡战略本身不开发，不开发是不合理的，若A选择开发，B的信息集是x，最优选择是不开发。但是，若A选择不开发，B对应的信息集是x，B的最优选择是开发而不是不开发。因此，不开发，不开发不是B的合理战略，或者说，不是一个可置信的战略。,1、可置信的战略,而（开发，不开发，开发）是一个合理的均衡。如果A选择开发，B的最优选择是不开发；如果A选择不开发，B的最优选择是开发。A预测到自己的选择对B选择的影响，开发是A的最优选择。均衡结果是，A选择开发，B选择不开发，A的支付为1，B的支付为0。事实上，（开发，不开发，开发）是这个博弈的唯一子博弈精练NE（SPNE）。,2、SPNE子博弈精练NE,目的是将那些包含不可置信威胁战略的NE从均衡中剔除，从而给出动态博弈结果的一个合理预测。(1)子博弈(2)定义(3)均衡路径(4)NE与SPNE的本质区别(5)序贯理性(6)SPNE就是要剔除那些只在特定情况下是合理的而在其他情况下并不合理的行动规则,（1）子博弈,子博弈,上述两条件：条件(1)，一个子博弈必须从一个单结信息集开始(换句话说，若一个信息集包含两个以上决策结，没有任何一个决策结可以作为子博弈的初始结)。显然，一个完美信息博弈的每一个决策结都开始一个子博弈(即每一个决策结和它的后续结构成一个子博弈),（1）子博弈,如上例原博弈是一个子博弈；,如下图x和x都不能作为子博弈的初始结,（1）子博弈,（1）子博弈,条件(2)说的是，子博弈的信息集和支付向量都直接继承自原博弈，即当且仅当x和x在原博弈中属于同一信息集时，它们在子博弈中才属于同一信息集；子博弈的支付函数只是原博弈支付函数留存在子博弈上的部分。特别地，条件(2)和条件(1)意味着子博弈不能切割原博弈的信息集。,（1）子博弈,要求子博弈满足上述两个条件的目的是保证子博弈对应于原博弈中可能出现的情况。若不满足这两个条件，参与人在原博弈中不知道的信息在子博弈中就变成知道的信息。于是，从子博弈中得出的结论对原博弈就没有意义。参与人2的信息集不能开始一个子博弈，因为否则的话，参与人3的信息集将被切割。图3.4和图3.5除原博弈外没有其他子博弈。,（2）定义,定义：扩展式博弈的战略组合是一个子博弈精练纳什均衡(SPNE)。它应满足两个条件：它是原博弈的NE；它在每一个子博弈(sp)上给出NE。,简单地说，一个战略组合是子博弈精练NE，当且仅当(包括原博弈)上都构成一个NE。(充要条件),若整个博弈是唯一的子博弈，(如图3.4,3.5)，纳什均衡与子博弈纳什均衡是相同的，若有其他子博弈存在，有些NE可能不构成SPNE。若唯一，有NESPNE；若不唯一，则有可能NESPNE。,（3）均衡路径,均衡路径：若一个博弈有个子博弈，一个特定的NE决定了原博弈树上唯一的一条路径，这条路径称为“均衡路径”(equilibriumpath)，博弈树上的其他路径称为非均衡路径。,如低需求（上图），开发商A不开发xB开发（0，1）是NE（不开发，开发，开发）的均衡路径，其余的路径都是该纳什均衡的非均衡路径。,（4）NE与SPNE的本质区别,NE仅要求其均衡战略在均衡路径的决策结上是最优的。定义(2)中，“在每一个子博弈上给出NE”意味着，构成SPNE的战略不仅在均衡路径的决策结上是最优的，而且在非均衡路径的决策结上也是最优的。如B的不开发，开发在任一路径上是最优的。,NE与SPNE的本质区别,NE仅在均衡路径的决策结上是最优,SPNE在所有路径（均衡和非均衡）的决策结上是最优的,（5）序贯理性(sequentialrationality),序贯理性指不论过去发生了什么，参与人应该在博弈的每一个时点上最优化自己的决策。SPNE要求正是参与人应该是序贯理性的。(一个合理、可置信的战略，其条件为一个战略规定的行动规则在所有可能的情况下都是最优的),（6）SPNE,检验及寻找SPNE在A开发，在(b)上，B的最优选择是不开发，1不符合2符合3符合在A不开发，在(c)上，B的最优选择是开发，1符合2符合3不符合故A开发，B不开发是唯一合理的均衡结果。,子博弈(b)、(c)属单人博弈(只有开发商B在决策)NE1(不开发，开发，开发)NE2(开发，不开发，开发)NE3(开发，不开发，不开发),（6）SPNE,3、用逆向归纳法求解子博弈精练NE,对于有限完美信息博弈，逆向归纳法是求解子博弈精练纳什均衡的最简便方法。(因为有限完美信息博弈的每一个决策结都是一个单独的信息集，每一个决策结都开始一个子博弈。因此，从最后一个子博弈逐步由后向前逆推，每一步均选最优，最后可得到子博弈精练NE)最后一个决策结，该决策结上行动的参与人有一个最优选择，这个最优选择就是该决策结开始的子博弈的NE(若最优行动多于一个，任选其中一个，若最后一个决策者有多个决策结，那么每一个决策结开始的子博弈都有一个NE)。然后，倒数第二个决策结(最后决策结的直接前列结)，找出倒数第二个决策者的最优选择；如此不断，直到初始结。“子博弈纳什均衡”SPNE。,3、用逆向归纳法求解子博弈精练NE,第三阶段1选U（30）第二阶段2选L(否则下阶段1选U造成01)第一阶段1选U(否则下阶段2选L造成12)这个博弈的子博弈精练NE均衡是(U,U,L)1选2选,3、用逆向归纳法求解子博弈精练NE,（1）实质是重复剔除劣战略过程在扩展式博弈上的扩展（2）重复剔除的占优均衡(IEDE)要求“所有参与人是理性的”是共同知识，逆向归纳法求解也有此要求。如上例：否则，若参与人1不认为参与人2是理性的，参与人1就不在第一阶段选U，而选D。而期待参与人2在第二阶段选R，从而参与人1可在第三阶段选U，获3单位支付。同样参与人2也会在第二阶段选R，期待参与人1在第三阶段选D，使其获得2单位支付。（3）逆向归纳法只适用于完美信息博弈例外情况：i、最后一个阶段所有参与人都有占优战略，以这一战略代替最后阶段的最优选择即可。ii、若不是i，有时逆向归纳法的逻辑也有助于我们找出精练均衡。,3、用逆向归纳法求解子博弈精练NE,3、用逆向归纳法求解子博弈精练NE,a、参与人2最后一个信息集没有一个优于其他选择(事实上，最后一个子博弈是零和博弈)(选L可能出现1选U，选R可能出现1选D),精练纳什均衡：用纳什均衡支付向量代替子博弈（从参与人1的第二个信息集开始的子博弈有唯一的混合战略NE，期望支付为0）。,3、用逆向归纳法求解子博弈精练NE,c、参与人2能猜透参与人1的3个战略U,U,D,U,D,D的某一个大于1/4的概率出现，否则参与人2不会在第一信息集上选R，再加上参与人2知道参与人1是理性的，故这种比参与人1更好的结果很难出现。参与人2在第1信息集上选L参与人1在第1信息集上选D这样的推论正是子博弈精练均衡的逻辑。,4、承诺行动与子博弈精练NE,（1）承诺行动(commitment)（2）法律上要胁诉讼(nuisancesuits),（1）承诺行动,承诺行动(commitment)：若参与人能在博弈之前采取某种措施改变自己的行动空间或支付函数，原来不可置信的威胁就可能变得可置信，博弈的精练均衡就会相应改变。措施称为“承诺行动”。,（1）承诺行动,(2)不完全承诺：毁约的成本代价有限,（2）法律上要胁诉讼,希望很小且需花成本，为什么要指控？原因是他知道被告辩护的成本很大，所以可能同意私了。如：小企业指控大企业对产品垄断指控当红的政治家曾与她有暧昧关系,（2）法律上要胁诉讼,c原告指控成本（交法庭）s原告需被告的赔偿金p原告的起诉成本（包括律师费用）d被告的辩护成本x原告赢得的支付原告赢得的概率,（2）法律上要