完全信息动态博弈.ppt

完全信息动态博弈：子博弈精炼纳什均衡,完全信息动态博弈指各博弈方先后行动，后行动者知道先行动者的具体行动是什么且各博弈方对博弈中各种策略组合情况下所有参与人相应的得益都完全了解的博弈。静态博弈只是博弈问题中的一类。现实中的许多决策活动往往是依次选择行为而不是同时选择行为，而且后选择行为者能够看到先选择行为者的选择内容。依次选择与一次性同时选择有很大差异，我们来关注这类博弈。,动态博弈的表示法动态博弈的基本特点可信性和纳什均衡的问题逆向归纳法,第一部分,一个动态博弈的扩展式表达应包含以下要素：参与人集合：i=1,n；参与人的行动顺序：谁在什么时候行动；参与人的行动空间：在每次行动时，参与人有些什么行动可供选择；参与人的信息集：每次行动时，参与人知道些什么；参与人的得益函数：在博弈结束后，每个参与人得到些什么；外生事件（即“自然”的选择）的概率分布。“博弈树”,一、动态博弈的表示法,设有一家企业的产品被另一家企业仿冒，如果被仿冒企业采取措施制止，仿冒企业就会停止仿冒，如果被仿冒企业不采取措施制止，仿冒企业就会继续仿冒。对被仿冒企业来说，被仿冒当然会造成经济损失，因此采取措施制止是符合自身利益的，但制止仿冒是有代价的，因此在遭仿冒时是否应该制止是需要研究的问题。对于仿冒企业来说，仿冒不被制止能获得很大利益，但如果被制止就会偷鸡不着蚀把米，因此是否仿冒也要仔细推敲。所以，这两个企业在仿冒和制止的问题上，存在着一个行为和利益相互依存的博弈问题。由于只有在已经遭到仿冒的情况下被仿冒企业才需要考虑是否制止，因此这是一个动态博弈问题。,例仿冒与反仿冒,A,仿冒,不仿冒,B,制止,不制止,A,(0,10),(-2,5),仿冒,不仿冒,B,制止,不制止,(5,5),(2,2),(10,4),博弈树,博弈树结构元件：结：包括决策结和终点结。所有旁边标注参与人的圆圈都是决策结，决策结是参与人采取行动的时点，其和旁边标注的参与人共同给出了该博弈的参与人和各参与人的行动顺序；下边标注各参与人得益的圆圈是终点结，表明博弈结束，并标明博弈的一个可能结果，并唯一地给出到达该结果的一条博弈路径。枝：枝是从一个决策结到其直接后续结的连线，每一个枝代表参与人的一个行动选择。枝旁标注该具体行动的代号。一般每个决策结下有多个枝，给出每次行动时参与人的行动空间。信息集：博弈树中某一决策者在某一行动阶段具有相同信息的所有决策结称为一个信息集。,进入者,进,不进,在位者,在位者,默许,打击,默许,打击,（40，50）,（-10，0）,（0，300）,（0，300）,结：包括决策结和终点结；枝：从一个决策结到其直接后续结的连线；信息集：博弈树中某一决策者在某一行动阶段具有相同信息的所有决策结称为一个信息集。,二、动态博弈的特点,动态博弈中，各个博弈方的行为不仅有先后之分，而且一个博弈方的选择可能有多次；并且在不同阶段的多次行为之间有内在联系，是不能分割的整体。因此，我们在动态博弈中研究的决策是各博弈方在整个博弈中轮到选择的每个阶段时、针对前面阶段的各种情况作相应选择和行为的完整计划，以及由不同博弈方的这种计划构成的组合。,动态博弈的策略,如：在仿冒和反仿冒博弈中，仿冒企业A“在第一阶段仿冒，如果在第二阶段B制止，则第三阶段就不仿冒，否则第三阶段继续仿冒”，被仿冒企业B“第一阶段A仿冒时第二阶段不制止，第三阶段A继续仿冒时第四阶段制止”，分别是两博弈方的各一个策略。,男方策略是两个：足球，芭蕾。女方是在知道男方决策后才行动的，其策略可以归纳为四个：追随策略（他选什么我就选什么）、对抗策略（他选什么我偏不选什么）、芭蕾策略（无论他选什么我都选芭蕾）、足球策略（无论他选什么我都选他喜欢的足球）。,男,足球,芭蕾,女,女,足球,芭蕾,足球,芭蕾,（2，1）,（-1，-1）,（1，2）,（0，0）,动态博弈中各博弈方的行动有先后次序，且后行为者能观察到此前选择行动博弈方的行动，因此动态博弈中各博弈方的地位是不对称的。一般来说，由于后行动的博弈方有更多的信息帮助自己选择行动，可减少决策的盲目性，因此处于较有利的地位。不过，后行动和具有较多信息并不总是有利的。,动态博弈的非对称性,甲,左,中,上,下,乙,右,甲有后动优势：如果让乙先行动，乙会消去中策略和右策略这两个劣策略，这样甲可以很有把握达到左上（4，12）这个均衡，得益4.而如果甲先行动，他只能消去下策略，乙只需在得益相同的左右两个策略中随便选择一个即可。,甲有先动优势：如果先选定下策略，可稳得10.而乙也最好让对方先行，自己得100.若乙为得100，先占了左策略的位置，则将自己处于不确定的位置。,甲,左,右,上,下,乙,三、可信性与纳什均衡的问题,可信性：在某一博弈中，一参与人承诺当某种情况发生时，比如其他参与人作出某一特定行动选择时，其将作出某种具体行动。而当该情况真的发生时，承诺人如果真的履行其承诺将会付出相当大的代价，而不履行则会受益更大，那么该承诺就是不可信的。,例开金矿博弈及其不同版本,甲在开采一价值4万元的金矿时缺1万元资金，而乙正好有1万元资金可以投资。甲想说服乙将这1万元资金借给自己用于开矿，并许诺在采到金子后与乙对半分成，乙是否该将钱借给甲呢？假设金矿的价值是经过权威部门探测确定的，没必要怀疑。则乙最需要关心的就是甲采到金子后是否会履行诺言跟自己平分。,甲“分”的许诺是不可信的，因此乙的合理选择是“不借”,乙,借,不借,甲,分,不分,(1,0),开金矿博弈,(0，4),(2，2),当博弈进行到第三阶段即甲选择“不分”时，乙的合理选择是“打”官司，这一威胁是可信的；则甲在第二阶段的合理选择是“分”，这一许诺是可信的；乙在第一阶段选择“借”是合理的。因此，乙的完整策略是“第一阶段选择借，若第二阶段甲选择不分，则第三阶段选择打官司”，甲的完整策略是“第二阶段选择分”，这就是这个博弈的解。,乙,借,不借,甲,分,不分,(1,0),有法律保障的开金矿博弈,(0，4),(2，2),(1,0),打,不打,乙,乙在第三阶段选择“打”官司的威胁是不可信的，因此甲在第二阶段将选择“不分”，“分”是不可信的，所以乙在第一阶段的合理选择是“不借”。,乙,借,不借,甲,分,不分,(1,0),法律保障不足的开金矿博弈,(0，4),(2，2),(-1,0),打,不打,乙,可信性问题最重要的意义在于，它对纳什均衡在动态博弈分析中的有效性提出了质疑。静态博弈下，各参与人同时选择，既无法知道别人的选择，也无暇对此作出反应。但动态博弈中，后行动者会根据先行动者的选择来调整自己的选择，而先行动者也会预期到这一点，所以会考虑自己的选择对其他参与人有什么影响，从而调整自己的策略。纳什均衡不能排除不可信的威胁（或承诺），因此在分析动态博弈时不能往往不能做出可靠的判断。因此，动态博弈的均衡概念除了要满足纳什均衡的基本要求外，还要能排除不可信的威胁和承诺。,可信性与纳什均衡,四、逆向归纳法,逻辑基础：动态博弈中先行动的博弈方，在前面阶段选择行为时必然会考虑后行为博弈方在后面阶段的选择，只有在博弈最后一个阶段选择的博弈方才能直接作出明确选择。而当后面阶段博弈方的选择确定后，前一阶段博弈方的行为也就容易确定了。一般方法：从动态博弈的最后一个阶段开始分析，每一次确定出所分析阶段博弈方的选择和路径，然后再确定前一个阶段博弈方的选择和路径，逐步向前逆推以求解出动态博弈均衡。,第二部分,子博弈子博弈精炼纳什均衡子博弈精炼纳什均衡求解方法承诺行动与子博弈精炼纳什均衡,一、子博弈,定义：由一个单结信息集开始的与所有该决策结的后续结（包括终点结）组成的能自成一个博弈的原博弈的一部分。,乙,借,不借,甲,分,不分,(1,0),法律保障不足的开金矿博弈,(0，4),(2，2),(-1,0),打,不打,乙,乙,借,不借,甲,分,不分,(1,0),法律保障不足的开金矿博弈,(0，4),(2，2),(-1,0),打,不打,乙,A,仿冒,不仿冒,B,制止,不制止,A,(0,10),(-2,5),仿冒,不仿冒,B,制止,不制止,(5,5),(2,2),(10,4),仿冒与反仿冒博弈,二、子博弈精炼纳什均衡,定义：如果在一个完全信息动态博弈中，各博弈方的策略构成的一个策略组合满足，在整个博弈及它的所有子博弈中都构成纳什均衡，那么这个策略组合称为该动态博弈的一个子博弈精炼纳什均衡。,以法律保障不足的开金矿博弈为例,策略组合“乙在第一阶段选择借，第三阶段选择打；甲在第二阶段选择分”，即（借，打），（分），虽然是整个博弈的一个纳什均衡，但这个策略组合中乙的策略要求乙在第三阶段的子博弈中选择的“打”，不是该子博弈的一个纳什均衡，因此这个策略组合不是子博弈精炼纳什均衡。而策略组合（不借，不打），（不分）则是该博弈的子博弈精炼纳什均衡。因为该策略组合的双方策略不仅在整个博弈中构成纳什均衡，而且在两级子博弈中也都构成纳什均衡（从而不存在任何不可信的威胁或承诺）。注意：当博弈方按上述子博弈精炼纳什均衡策略组合行动时，实际上不会进行到博弈的第二、三阶段，两博弈方在第二、三阶段的行为实际上不会发生。但作为完整策略的表达，在描述子博弈精炼纳什均衡的策略选择时，必须将其给出。,（不进），（打击，打击）和（进入），（默许，默许）都是纳什均衡,进入者,进,不进,在位者,在位者,默许,打击,默许,打击,（40，50）,（-10，0）,（0，300）,（0，300）,例市场进入博弈,（进入），（默许，默许）是子博弈精炼纳什均衡,三、子博弈精炼纳什均衡求解方法,逆向归纳法是求解子博弈精炼纳什均衡的最简便方法。完全信息动态博弈的每一个决策结都是一个单独的信息集，每一个决策结都开始一个子博弈。这样，可以从最后一个子博弈开始（即从最后一个决策结开始）逆推上去，求解子博弈精炼纳什均衡。,例求解下面三阶段博弈的子博弈精炼纳什均衡,子博弈精炼纳什均衡策略组合为（U，U），（L）。最后的均衡结果是参与人1在第一阶段选择结束博弈，参与人1、2得益分别为2、0。,1,(2,0),(1,2),2,1,(3,0),(1,3),四、承诺行动与子博弈精炼纳什均衡,前面已知，有些纳什均衡之所以不是精炼均衡，是因为它们包含了不可信威胁。这也意味着，如果参与人能在博弈之前采取某种措施改变自己的行动空间或支付函数，原来不可信的威胁就可能变得可信，博弈的均衡就会相应改变。将这些为改变博弈结果而采取的措施称为“承诺行动”。在许多情况下，承诺行动对当事人是很有价值的。特别的，有时一个参与人通过减少自己的选择机会使自己受益，原因在于保证自己不选择某些行动可以改变对手的最优选择。,例房地产开发博弈,有两个房地产开发商A和B分别决定在同一地段上开发一栋写字楼。由于市场需求有限，如果他们都开发，则在同一地段会有两栋写字楼，超过了市场对写字楼的需求，难以完全出售，空置房太多导致各自亏损1百万。当只有一家开发商在这个地段开发一栋写字楼时，它可以全部售出，赚得利润1百万。假定A先决策，B在看见A的决策后再决策是否开发写字楼。,房地产开发博弈,用“逆向归纳法”求解这个博弈。在B进行决策的2个决策结上，B在左边的决策结上选择“不开发”；而在右边的决策结上选择“开发”。即给定A开发，B就不开发；给定A不开发，B就开发。B应避免同时与A都选择开发而蒙受损失。在这种情况下，A在自己的决策结上当然选择“开发”。当B威胁A说：“不管你是否开发，我都会在这里开发写字楼。”倘若A将B的话当了真，A就不敢开发，让B单独开发写字楼占便宜。但是，B的威胁是“不可置信”的。当A不理会B的威胁而果断地开发出一栋写字楼时，B其实不会将事前的威胁付诸实施。因为“识时务者为俊杰”，在A已开发的情况下，B的最优决策是“不开发”而不是“开发”。,但是，如果在A决策之前，B与某个客户签订一个合同，规定B在一个特定的时刻交付客户若干面积的写字楼办公室，如果B不能履约，将赔偿客户2百万元。这时，博弈就变为：,称B的这种行动为“承诺行动”，它使原来不可置信的威胁变为可以置信。这时，A就不得不相信B一定要开发写字楼的威胁了，于是放弃开发写字楼的计划，让B如愿以偿单独开发写字楼。B不仅未向客户支付2百万元，反而净赚1百万。,例波音与空中客车的争斗,假定世界飞机市场容量有限，在一段时间内两个公司都开发新型飞机会因市场饱和而亏损，但若一家公司开发而另一家公司不开发时，则开发的那家公司会获巨额利润。,空中客车,开发,不开发,波音,开发,不开发,此时有两个纳什均衡，即一家开发而另一家不开发。两个公司竞争的结果，应该是先开发出新飞机的一方获利。实际情况是，欧洲有些国家对空中客车实行补贴。假定补贴是20亿美元，则博弈变为：,这时只有一个纳什均衡，即波音公司不开发和空中客车公司开发的均衡（不开发,开发），这有利于空中客车。在这里，国家对空中客车的补贴就是使空中客车一定要开发（无论波音是否开发）的威胁变得可信的一种“承诺行动”。,空中客车,开发,不开发,波音,开发,不开发,例中国电信业的竞争,1993年，国务院正式发文同意电子部、电力部和铁道部共同组建“中国联合通信有限公司”参与竞争，电信市场上一直占据垄断地位的部门和企业使尽浑身解数，必欲置这个潜在的对手于死地。,设想垄断企业一直可以卖高价赚取每年10亿元的利润。其他企业欲进入此行业需要4亿元的投资。新企业进入时，原有企业必须决策：容忍进入，收缩产量维持高价，则利润将为5亿元，对方利润也为5亿元，减去成本，净得1亿元；如果抵抗，加大产量降低价格，则利润降到2亿元，对方得2亿元，减去成本，亏损2亿元。对方不进入时也可以采取降价威胁策略，利润降为4亿元。,唯一的纳什均衡：潜在企业进入，原有企业容忍,进入企业,进入,不进,原有企业,容忍,抵抗,实际商战中，我们看到许多不惜亏本拼死抵抗的案例。原因在于原有垄断企业的着眼点不是当时利益，而是长远利益。新企业则更关注当年利益。在原有企业看来，博弈应该是：,进入企业,进入,不进,原有企业,容忍,抵抗,垄断企业的抵抗威胁，并非不可信。,第三部分重复博弈,重复博弈有限次重复博弈无限次重复博弈,一、重复博弈,前面讨论过的动态博弈都有一个基本特征，即参与人在前一阶段的行动选择决定了随后的子博弈结构，因此各个子博弈的结构一般是不同的。这样的动态博弈称为“序贯博弈”。而相对应的重复博弈则是同样结构的博弈要重复多次，其中每次博弈称为“阶段博弈”。如果重复的次数是有限的，称之为“有限次重复博弈”；如果重复次数是无限的，重复博弈不能在可预计的有限次数内结束则称之为“无限次重复博弈”。,重复博弈的基本特征,第一，阶段博弈之间无物质上的联系，也就是说，前一阶段的博弈不改变后一阶段博弈的结构；第二，所有参与人都观察到博弈过去的历史；第三，参与人关心的是整个博弈的总得益。,二、有限次重复博弈,给定一个博弈G，重复进行T次G，并且在每次重复之前各博弈方都能观察到以前博弈的结果，这样的博弈过程称为G的一个“T次重复博弈”，记为G(T)。而G称为G(T)的原博弈。G(T)的每次重复称为G(T)的一个阶段。,什么是有限次重复博弈？,连锁店悖论,考虑“市场进入博弈”的有限次重复。我们知道，在一次博弈中，如果进入者先行动，这个博弈唯一的子博弈精炼纳什均衡结果是进入者进入，在位者默许，分别得到40和50的得益。,进入者,进,不进,在位者,在位者,默许,打击,默许,打击,（40，50）,（-10，0）,（0，300）,（0，300）,（进入），（默许，默许）是子博弈精炼纳什均衡,现在假定有同样的市场20个（比如说在位者的20个连锁店），进入者每次考虑一个市场的进入，因此该博弈就成了20次重复博弈。在位者会如何反应呢？,出于保护20个市场的考虑，也许我们会想，从第一个市场开始，在位者就应选择打击。实际上，在有限次重复博弈中，打击并不是一个值得置信的威胁。这个博弈可以用“子博弈精炼纳什均衡”和“逆向归纳法”求解。从最后一个市场开始分析。因为是在最后阶段，打击没有任何威慑意义，在位者的最优选择是默许，进入者选择进入。在第19个市场上，因为进入者知道在第20个市场上在位者终将选择默许，故此阶段在位者的行动不会影响第20个市场的均衡结果，故其最优选择也只能是默许。,如此逆推，可以得到这个博弈的唯一的子博弈精炼纳什均衡是：在位者在每一个市场上都选择默许，进入者在每一个市场上都选择进入。,这就是泽尔腾在1978年提出的著名的“连锁店悖论”。,定理：令G是阶段博弈，G(T)是G重复T次的重复博弈。那么，如果G有唯一的纳什均衡，重复博弈G(T)的唯一子博弈精炼纳什均衡结果是阶段博弈G的纳什均衡重复T次（即每个阶段博弈出现的都是一次性博弈的均衡结果）。,三、无限次重复博弈,以小镇卖水为例设想在一个镇上只有两个居民杰克和吉尔拥有能生产饮用水的水井。每周六，杰克和吉尔决定抽取多少加仑水，带到镇上，并以市场所能承受的价格出售。为了简单起见，假设杰克和吉尔可以没有成本地