完全信息动态博弈

null完全信息动态博弈：子博弈精炼纳什均衡完全信息动态博弈：子博弈精炼纳什均衡 完全信息动态博弈指各博弈方先后行动，后行动者知道先行动者的具体行动是什么且各博弈方对博弈中各种策略组合情况下所有参与人相应的得益都完全了解的博弈。 静态博弈只是博弈问题中的一类。现实中的许多决策活动往往是依次选择行为而不是同时选择行为，而且后选择行为者能够看到先选择行为者的选择 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 。依次选择与一次性同时选择有很大差异，我们来关注这类博弈。第一部分动态博弈的表示法 动态博弈的基本特点 可信性和纳什均衡的问题 逆向归纳法第一部分一、动态博弈的表示法一、动态博弈的表示法一个动态博弈的扩展式表达应包含以下要素： 参与人集合：i=1,…,n； 参与人的行动顺序：谁在什么时候行动； 参与人的行动空间：在每次行动时，参与人有些什么行动可供选择； 参与人的信息集：每次行动时，参与人知道些什么； 参与人的得益 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数：在博弈结束后，每个参与人得到些什么； 外生事件（即“自然”的选择）的概率分布。 “博弈树” 例 仿冒与反仿冒 设有一家企业的产品被另一家企业仿冒，如果被仿冒企业采取 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 制止，仿冒企业就会停止仿冒，如果被仿冒企业不采取措施制止，仿冒企业就会继续仿冒。对被仿冒企业来说，被仿冒当然会造成经济损失，因此采取措施制止是符合自身利益的，但制止仿冒是有代价的，因此在遭仿冒时是否应该制止是需要研究的问题。对于仿冒企业来说，仿冒不被制止能获得很大利益，但如果被制止就会偷鸡不着蚀把米，因此是否仿冒也要仔细推敲。所以，这两个企业在仿冒和制止的问题上，存在着一个行为和利益相互依存的博弈问题。由于只有在已经遭到仿冒的情况下被仿冒企业才需要考虑是否制止，因此这是一个动态博弈问题。例 仿冒与反仿冒AA仿冒不仿冒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继续仿冒时第四阶段制止”，分别是两博弈方的各一个策略。null男方策略是两个：足球，芭蕾。女方是在知道男方决策后才行动的，其策略可以归纳为四个：追随策略（他选什么我就选什么）、对抗策略（他选什么我偏不选什么）、芭蕾策略（无论他选什么我都选芭蕾）、足球策略（无论他选什么我都选他喜欢的足球）。男●足球芭蕾●●女女足球芭蕾足球芭蕾●●●●（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)打不打乙可信性与纳什均衡可信性问题最重要的意义在于，它对纳什均衡在动态博弈 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 中的有效性提出了质疑。 静态博弈下，各参与人同时选择，既无法知道别人的选择，也无暇对此作出反应。但动态博弈中，后行动者会根据先行动者的选择来调整自己的选择，而先行动者也会预期到这一点，所以会考虑自己的选择对其他参与人有什么影响，从而调整自己的策略。 纳什均衡不能排除不可信的威胁（或承诺），因此在分析动态博弈时不能往往不能做出可靠的判断。 因此，动态博弈的均衡概念除了要满足纳什均衡的基本要求外，还要能排除不可信的威胁和承诺。可信性与纳什均衡四、逆向归纳法四、逆向归纳法逻辑基础：动态博弈中先行动的博弈方，在前面阶段选择行为时必然会考虑后行为博弈方在后面阶段的选择，只有在博弈最后一个阶段选择的博弈方才能直接作出明确选择。而当后面阶段博弈方的选择确定后，前一阶段博弈方的行为也就容易确定了。 一般方法：从动态博弈的最后一个阶段开始分析，每一次确定出所分析阶段博弈方的选择和路径，然后再确定前一个阶段博弈方的选择和路径，逐步向前逆推以求解出动态博弈均衡。第二部分第二部分子博弈 子博弈精炼纳什均衡 子博弈精炼纳什均衡求解方法 承诺行动与子博弈精炼纳什均衡一、子博弈一、子博弈定义：由一个单结信息集开始的与所有该决策结的后续结（包括终点结）组成的能自成一个博弈的原博弈的一部分。法律保障不足的开金矿博弈法律保障不足的开金矿博弈乙借不借甲分不分(1,0)(0，4)(2，2)(-1,0)打不打乙法律保障不足的开金矿博弈法律保障不足的开金矿博弈乙借不借甲分不分(1,0)(0，4)(2，2)(-1,0)打不打乙AA仿冒不仿冒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的决策后再决策是否开发写字楼。 房地产开发博弈 房地产开发博弈null 用“逆向归纳法”求解这个博弈。在B进行决策的2个决策结上，B在左边的决策结上选择“不开发”；而在右边的决策结上选择“开发”。即给定A开发，B就不开发；给定A不开发，B就开发。B应避免同时与A都选择开发而蒙受损失。 在这种情况下，A在自己的决策结上当然选择“开发”。当B威胁A说：“不管你是否开发，我都会在这里开发写字楼。”倘若A将B的话当了真，A就不敢开发，让B单独开发写字楼占便宜。但是，B的威胁是“不可置信”的。 当A不理会B的威胁而果断地开发出一栋写字楼时，B其实不会将事前的威胁付诸实施。因为“识时务者为俊杰”，在A已开发的情况下，B的最优决策是“不开发”而不是“开发”。null但是，如果在A决策之前，B与某个客户签订一个合同，规定B在一个特定的时刻交付客户若干面积的写字楼办公室，如果B不能履约，将赔偿客户2百万元。 这时，博弈就变为：nullnull称B的这种行动为“承诺行动”，它使原来不可置信的威胁变为可以置信。这时，A就不得不相信B一定要开发写字楼的威胁了，于是放弃开发写字楼的计划，让B如愿以偿单独开发写字楼。B不仅未向客户支付2百万元，反而净赚1百万。 例 波音与空中客车的争斗例 波音与空中客车的争斗假定世界飞机市场容量有限，在一段时间内两个公司都开发新型飞机会因市场饱和而亏损，但若一家公司开发而另一家公司不开发时，则开发的那家公司会获巨额利润。null空中客车开发不开发波音开发不开发 此时有两个纳什均衡，即一家开发而另一家不开发。两个公司竞争的结果，应该是先开发出新飞机的一方获利。 实际情况是，欧洲有些国家对空中客车实行补贴。假定补贴是20亿美元，则博弈变为： null 这时只有一个纳什均衡，即波音公司不开发和空中客车公司开发的均衡（不开发,开发），这有利于空中客车。 在这里，国家对空中客车的补贴就是使空中客车一定要开发（无论波音是否开发）的威胁变得可信的一种“承诺行动”。空中客车开发不开发波音开发不开发例 中国电信业的竞争 例 中国电信业的竞争 1993年，国务院正式发文同意电子部、电力部和铁道部共同组建“中国联合通信有限公司”参与竞争，电信市场上一直占据垄断地位的部门和企业使尽浑身解数，必欲置这个潜在的对手于死地。null设想垄断企业一直可以卖高价赚取每年10亿元的利润。其他企业欲进入此行业需要4亿元的投资。新企业进入时，原有企业必须决策：容忍进入，收缩产量维持高价，则利润将为5亿元，对方利润也为5亿元，减去成本，净得1亿元；如果抵抗，加大产量降低价格，则利润降到2亿元，对方得2亿元，减去成本，亏损2亿元。对方不进入时也可以采取降价威胁策略，利润降为4亿元。null唯一的纳什均衡：潜在企业进入，原有企业容忍进入企业进入不进原有企业容忍抵抗null实际商战中，我们看到许多不惜亏本拼死抵抗的案例。原因在于原有垄断企业的着眼点不是当时利益，而是长远利益。新企业则更关注当年利益。在原有企业看来，博弈应该是：进入企业进入不进原有企业容忍抵抗垄断企业的抵抗威胁，并非不可信。第三部分 重复博弈第三部分 重复博弈 重复博弈 有限次重复博弈 无限次重复博弈 一、重复博弈一、重复博弈前面讨论过的动态博弈都有一个基本特征，即参与人在前一阶段的行动选择决定了随后的子博弈结构，因此各个子博弈的结构一般是不同的。这样的动态博弈称为“序贯博弈”。而相对应的重复博弈则是同样结构的博弈要重复多次，其中每次博弈称为“阶段博弈”。如果重复的次数是有限的，称之为“有限次重复博弈”；如果重复次数是无限的，重复博弈不能在可预计的有限次数内结束则称之为“无限次重复博弈”。重复博弈的基本特征重复博弈的基本特征第一，阶段博弈之间无物质上的联系，也就是说，前一阶段的博弈不改变后一阶段博弈的结构； 第二，所有参与人都观察到博弈过去的历史； 第三，参与人关心的是整个博弈的总得益。二、有限次重复博弈二、有限次重复博弈给定一个博弈G，重复进行T次G，并且在每次重复之前各博弈方都能观察到以前博弈的结果，这样的博弈过程称为G的一个“T次重复博弈”，记为G(T)。而G称为G(T)的原博弈。 G(T)的每次重复称为G(T)的一个阶段。什么是有限次重复博弈？连锁店悖论连锁店悖论考虑“市场进入博弈”的有限次重复。我们知道，在一次博弈中，如果进入者先行动，这个博弈唯一的子博弈精炼纳什均衡结果是进入者进入，在位者默许，分别得到40和50的得益。进入者●进不进●●在位者在位者默许打击默许打击（40，50）●●●●（-10，0）（0，300）（0，300）｛（进入），（默许，默许）｝是子博弈精炼纳什均衡null现在假定有同样的市场20个（比如说在位者的20个连锁店），进入者每次考虑一个市场的进入，因此该博弈就成了20次重复博弈。在位者会如何反应呢？出于保护20个市场的考虑，也许我们会想，从第一个市场开始，在位者就应选择打击。实际上，在有限次重复博弈中，打击并不是一个值得置信的威胁。这个博弈可以用“子博弈精炼纳什均衡”和“逆向归纳法”求解。从最后一个市场开始分析。因为是在最后阶段，打击没有任何威慑意义，在位者的最优选择是默许，进入者选择进入。在第19个市场上，因为进入者知道在第20个市场上在位者终将选择默许，故此阶段在位者的行动不会影响第20个市场的均衡结果，故其最优选择也只能是默许。null如此逆推，可以得到这个博弈的唯一的子博弈精炼纳什均衡是：在位者在每一个市场上都选择默许，进入者在每一个市场上都选择进入。这就是泽尔腾在1978年提出的著名的“连锁店悖论”。定理：令G是阶段博弈， G(T)是G重复T次的重复博弈。那么，如果G有唯一的纳什均衡，重复博弈G(T)的唯一子博弈精炼纳什均衡结果是阶段博弈G的纳什均衡重复T次（即每个阶段博弈出现的都是一次性博弈的均衡结果）。三、无限次重复博弈三、无限次重复博弈以小镇卖水为例 设想在一个镇上只有两个居民——杰克和吉尔——拥有能生产饮用水的水井。每周六，杰克和吉尔决定抽取多少加仑水，带到镇上，并以市场所能承受的价格出售。为了简单起见，假设杰克和吉尔可以没有成本地想抽取多少水就抽取多少水。 镇上水的需求可以表示如下 小镇水需求情况小镇水需求情况null如果两人合作，结成卡特尔，则能够达到总收益的最大化。即两人总共生产60加仑（二人平均划分市场的话，每人将生产30加仑），以每加仑60美元的价格出售，总收益为3600美元，每人得到1800美元收益。 但是，追求私利的结果是两人将各生产40加仑，各获得收益1600美元。分析这个博弈（下面矩阵表示二者的博弈）分析这个博弈（下面矩阵表示二者的博弈）在一次博弈中，两人都没有遵守协议的激励，生产40加仑水是每个参与者的优势策略。吉尔40304030杰克null现在假设杰克和吉尔知道，他们每周将进行一次同样的博弈。作出保持低产量的协议时，他们还可以规定如何处理一方违约的情况。比如，他们可以达成协议，一旦有人违约生产了40加仑水，他们两人以后会永远生产40加仑水。这种惩罚是容易实施的，因为一方产量提高，另一方也有同样做的理由和能力。这种惩罚的威胁可能就是维持合作所需要的一切。每个人都知道，欺骗会使自己的利润从1800美元增加到2000美元。但这种利益只能维持一周。以后，利润将为1600美元，并停在这一水平上。只要参与者都非常关心未来的利润，他们就将放弃欺骗的一次性好处。因此，在多次进行的囚徒困境博弈中，两个参与者都可以很好地达到合作的结果。在无限次重复博弈中，怎样的策略是最优的呢？在无限次重复博弈中，怎样的策略是最优的呢？“一报还一报”策略：参与者从合作开始，然后上一次另一方怎么做自己这一次也怎么做。因此，实行这一策略的参与者会一直合作直到另一方违约为止；违约到另一方重新合作时为止。null如果博弈重复无穷次且每个人有足够的耐心，任何短期的机会主义行为的所得都是微不足道的，参与人有积极性为自己建立一个乐于合作的声誉，同时也有积极性惩罚对方的机会主义行为。所以，重复博弈更重要的意义在于参与人必须在长期与短期利益之间进行权衡，从而带来了合作的可能性。