北京大学博弈论课件第3章_完全信息动态博弈

POWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATEPOWERPOINTTEMPLATE2020/1/31金融第三章完全信息动态博弈在完全信息动态博弈中，博弈参与者的行动存在先后顺序。可以用博弈树表示完全信息动态博弈。可以通过逆向归纳法求解完全信息动态博弈的子博弈精炼纳什均衡，剔除不可置信的威胁。第一节完全信息动态博弈概述一、完全信息动态博弈的定义在完全信息静态博弈中，博弈参与者同时采取行动。但在完全信息动态博弈中，博弈参与者的行动存在先后顺序。从信息角度上，完全信息动态博弈与完全信息静态博弈类似，博弈参与者对博弈结构、博弈顺序、双方收益等信息都具备完全了解。二、博弈树在动态博弈中，由于博弈参与者的行动存在先后顺序，因此可以用更形象的方法来表示动态博弈：博弈树（GameTree）。通过支付矩阵的形式表示的博弈通常被称为策略型或正则型博弈（NormalFormGame）。通过博弈树表示的博弈通常被称为扩展型博弈（ExtensiveFormGame）。动态市场争夺战博弈的扩展型表达方式如图所示潜在进入者在位者不进入进入斗争默许（0,15）（-10,-10）（5,5）在位者斗争默许（0,20）“市场争夺战”博弈的扩展型表达形式1．博弈树的构成要素（1）博弈参与者（2）行动顺序：在动态博弈中，博弈参与者的行动存在先后次序。（3）行动策略空间（ActionSet）：指博弈参与者可以采取的所有可能策略。（4）信息集（InformationSet）：指博弈参与者在博弈过程中所知道的信息。（5）支付函数指博弈参与者采用特定策略与所能得到的收益之间的关系。2．博弈树的结构（1）博弈树的构造方法首先行动的一方位于博弈树的最上端，根据动态博弈过程中各方的行动顺序，博弈数自上至下延展。也有学者习惯自左至右构造博弈树。潜在进入者在位者不进入进入斗争默许（0,20）（-10,-10）（5,5）斗争默许（0,15）横向博弈树博弈树中包含若干“节点”，节点用小圆圈表示。位于博弈树最上端的节点称为“初始节点”。初始节点用空心小圆圈表示，其他节点均用实心小圆圈表示。在每个节点处均对应某个博弈参与者，将节点对应的博弈参与者标识在节点旁边。例如：在“市场争夺战”博弈中，因为潜在进入者先行动，因此初始节点处对应的博弈参与者为潜在进入者。将潜在进入者标识在博弈树初始节点旁边。当潜在进入者决策之后，轮到在位者进行决策。在位者所在的节点称为“后续节点”。在位者位于两个后续节点上。在位者都有两种策略选择：“斗争”和“默许”。如果初始节点处的博弈参与者存在N种策略，那么就从初始节点处分出N条路径。路径用线段表示。在线段旁注明相应的策略。在“市场争夺战”博弈中，首先行动的潜在进入者可以采取两种策略：“不进入”和“进入”。因此，从初始节点处引出两条线段，在两条线段旁分别标识“不进入”和“进入”。当潜在进入者选择结束后，达到在位者的节点。在位者有两个选择：“斗争”和“默许”。因此，从在位者的节点处引出两条线段，在两条线段旁分别标识“斗争”和“默许”。当博弈不再有后续节点时，需要将博弈的收益标识在博弈树末端。将博弈参与者的收益放在括号里。需要注意的是：各博弈参与者的收益需要按照各参与者行动顺序进行排列。先行动的博弈参与者的收益写在左边，依次类推，从左到右，最后行动的博弈参与者的收益写在最右边。各个博弈参与者的收益之间用逗号分割。（2）博弈树与博弈顺序博弈树各节点之间存在顺序关系，博弈树由上至下的节点顺序表示各博弈参与者进行决策的顺序。参与者1参与者2S1（a1,b1,c1）S2T1T2（a2,b2,c2）U1U2（a3,b3,c3）参与者3（a4,b4,c4）从博弈树的节点可以引出多条线段，但不能从博弈树多个节点共同到达博弈树下方同一个后续节点。（a4,b4,c4）参与者1参与者2S1（a1,b1,c1）S2U1U2（a3,b3,c3）参与者2参与者3V1V2（a2,b2,c2）V1V2错误的博弈树构造方法正确的博弈树构造方法参与者1参与者2S1（a1,b1,c1）S2参与者2V1V2（a2,b2,c2）V1V2参与者3（a4,b4,c4）U1U2（a3,b3,c3）参与者3（a6,b6,c6）U1U2（a5,b5,c5）正确的博弈树构造方法构造博弈树时只能按照由上至下的路径，而不能存在由下向上的路径，也不能形成循环路径。回溯路径唯一性在求解完全信息动态博弈时非常重要。因为在求解动态博弈均衡时，一个很重要的方法是“逆向归纳法（BackwardInduction）”。只有首先确保从博弈树任何最终节点向上回溯时路径唯一，才能确保逆向归纳法的可操作性。正确的博弈树构造方法正确的博弈树构造方法（a4,b4,c4）参与者1参与者2S1（a1,b1,c1）S2S1S2（a3,b3,c3）参与者1（a2,b2,c2）T1T2错误的博弈树构造方法错误的博弈树构造方法参与者1参与者2S1（a1,b1,c1）S2（a2,b2,c2）T1T2三、信息集与三人罢工博弈在完全信息动态博弈中，如果将博弈树的多个节点用虚线连接起来，表明这多个节点位于同一个博弈信息集中。也就是说：博弈参与者不知道自己位于同一个信息中的哪个博弈节点上。可以通过“三人罢工博弈”来说明信息集的含义以及信息集在动态博弈中的重要性。1．三人罢工博弈的定义3HO(2,2,0)(1,1,1)3HO(8,3,3)(2,0,2)3HO(3,8,3)(0,2,2)3HO(6,6,6)(3,3,8)2HO2HO1HO三人罢工博弈的博弈树2．三人罢工博弈的策略选择与信息3HO(2,2,0)(1,1,1)3HO(8,3,3)(2,0,2)3HO(3,8,3)(0,2,2)3HO(6,6,6)(3,3,8)2HO2HO1HO员工2只有一个信息集的博弈树3HO(2,2,0)(1,1,1)3HO(8,3,3)(2,0,2)3HO(3,8,3)(0,2,2)3HO(6,6,6)(3,3,8)2HO2HO1HO信息集1信息集2员工3不能观察到员工2的决策策略3HO(2,2,0)(1,1,1)3HO(8,3,3)(2,0,2)3HO(3,8,3)(0,2,2)3HO(6,6,6)(3,3,8)2HO2HO1HO信息集1信息集2员工3不知道员工1的决策策略3HO(2,2,0)(1,1,1)3HO(8,3,3)(2,0,2)3HO(3,8,3)(0,2,2)3HO(6,6,6)(3,3,8)2HO2HO1HO员工3不知道员工1和员工2的决策策略3HO(2,2,0)(1,1,1)3HO(8,3,3)(2,0,2)3HO(3,8,3)(0,2,2)3HO(6,6,6)(3,3,8)2HO2HO1HO三名员工都只有一个信息集的博弈四、博弈树与静态博弈博弈树的方法不仅能表示动态博弈，还能表示静态博弈。所谓的“博弈先后顺序”，它主要是一个信息的概念，而不是一个纯时间先后的概念。嫌疑人甲嫌疑人乙坦白不坦白坦白不坦白嫌疑人乙坦白不坦白(5,5)(1,10)(10,1)(2,2)用博弈树表示囚徒困境下面三种博弈表达方式所表达的博弈内涵相同嫌疑人甲嫌疑人乙坦白不坦白坦白不坦白嫌疑人乙坦白不坦白(5,5)(1,10)(10,1)(2,2)嫌疑人乙嫌疑人甲坦白不坦白坦白不坦白嫌疑人甲坦白不坦白(5,5)(1,10)(10,1)(2,2)嫌疑人乙坦白不坦白嫌疑人甲坦白（5，5）（1，10）不坦白（10，1）（2，2）第二节完全且完美信息动态博弈概述在完全且完美信息动态博弈（DynamicGamewithPerfectandCompleteInformation）中，每个博弈参与者均知道在自己之前进行决策的参与者选择的策略和博弈结构。博弈树中每个节点都独立构成一个信息集，没有虚线连接两个或多个博弈树节点。求解完全且完美信息动态博弈的重要方法之一是：逆向归纳法。可以通过“海盗分宝博弈”这个生动有趣的故事对“逆向归纳法”进行一个直观介绍。一、海盗分宝博弈1．海盗分宝博弈的规则五个海盗首先进行抽签，确定决策顺序。五个海盗按照决策顺序依次提出对100个金币的分配方案。第一个海盗提出一个分配方案，如超过半数的海盗（包括提出分配方案的海盗）同意第一个海盗的分配方案，即大于等于3名海盗同意第一个海盗的分配方案时，那么该方案被通过，博弈结束。如果第一个海盗提出的分配方案没有得到超过半数海盗的同意，那么第一个海盗将被扔到海里喂鲨鱼。接下来由第二个海盗提出分配方案，如果超过半数的海盗同意第二个海盗的分配方案时，那么该方案被通过，博弈结束。如果第二个海盗提出的分配方案没有得到超过半数海盗的同意，那么第二个海盗也将被扔到海里喂鲨鱼。接下来由第三个海盗提出分配方案，如果超过半数的海盗，即大于等于2名海盗，同意第三个海盗的分配方案时，那么该方案被通过，博弈结束。如果第三个海盗提出的分配方案没有得到超过半数海盗的同意，那么第三个海盗也将被扔到海里喂鲨鱼。接下来由第四个海盗提出分配方案。如果超过半数的海盗同意第四个海盗的分配方案时，那么该方案被通过，博弈结束。如果第四个海盗提出的分配方案没有得到超过半数海盗的同意，那么第四个海盗也将被扔到海里喂鲨鱼。这时就只剩下第五个海盗了，第五个海盗将独吞抢劫来的100个金币，博弈结束。在这种分配规则下，第一个海盗将提出怎样的分配方案？第一个海盗提出的分配方案需要满足两个条件。第一，保证超过半数的海盗同意第一个海盗的分配方案。第二：第一个海盗最大化自己能分到的金币。如果直接从第一个海盗的决策策略入手，此问题相对复杂。不妨从第五个海盗入手，然后按照从后向前的顺序依次逆向考察海盗的策略选择。2．求解海盗分宝博弈的均衡第一个海盗将提出怎样的分配方案？此分配方案在保证能得到超过半数海盗同意的前提下应最大化第一个海盗的利益。轮次分配方案提出者分配方案最后一轮海盗5自己独吞全部100个金币倒数第二轮海盗4任何分配方案都得不到通过倒数第三轮海盗3分配给第三个海盗100个金币，第四个海盗0个金币，第五个海盗0个金币。倒数第四轮海盗2分配给自己98个金币，第三个海盗0个金币，第四个海盗1个金币、第5个海盗1个金币。通过逆向归纳法推导出的财宝分配方案3．海盗分宝博弈的均衡第一个海盗的分配方案可以有两种。分配方案1：分配给自己97个金币，给第二个海盗0个金币，给第三个海盗1个金币，给第四个海盗2个金币，给第五个海盗0个金币。分配方案2：分配给自己97个金币，给第二个海盗0个金币，给第三个海盗1个金币，给第四个海盗0个金币，给第五个海盗2个金币。如果第一个海盗提出分配方案1，那么第二个海盗和第五个海盗将反对，而第一个、第三个和第四个海盗将同意，因此第一个海盗的提议将获得通过。如果第一个海盗提出分配方案2，那么第二个海盗和第四个海盗将反对，而第一个、第三个和第五个海盗将同意，因此第一个海盗的提议将获得通过。二、扩展形式博弈的策略表达方式1．将扩展形式的博弈改写为策略形式1L(a1,b1)22R(a2,b2)(a3,b3)(a4,b4)UVUV动态博弈的扩展表达形式参与者2UV参与者1L（a1，b1）（a2，b2）R（a3，b3）（a4，b4）错误的动态博弈策略表达形式参与者2（U，U）（U，V）（V，U）（V，V）参与者1L（a1，b1）（a1，b1）（a2，b2）（