北京大学博弈论课件第3章-完全信息动态博弈.ppt
第三章完全信息动态博弈,在完全信息动态博弈中，博弈参与者的行动存在先后顺序。可以用博弈树表示完全信息动态博弈。可以通过逆向归纳法求解完全信息动态博弈的子博弈精炼纳什均衡，剔除不可置信的威胁。,第一节 完全信息动态博弈概述,一、完全信息动态博弈的定义 在完全信息静态博弈中，博弈参与者同时采取行动。但在完全信息动态博弈中，博弈参与者的行动存在先后顺序。从信息角度上，完全信息动态博弈与完全信息静态博弈类似，博弈参与者对博弈结构、博弈顺序、双方收益等信息都具备完全了解。,二、博弈树,在动态博弈中，由于博弈参与者的行动存在先后顺序，因此可以用更形象的方法来表示动态博弈：博弈树（Game Tree）。通过支付矩阵的形式表示的博弈通常被称为策略型或正则型博弈（Normal Form Game）。通过博弈树表示的博弈通常被称为扩展型博弈（Extensive Form Game）。,动态市场争夺战博弈的扩展型表达方式如图所示,“市场争夺战”博弈的扩展型表达形式,1博弈树的构成要素,（1）博弈参与者（2）行动顺序：在动态博弈中，博弈参与者的行动存在先后次序。（3）行动策略空间（Action Set）：指博弈参与者可以采取的所有可能策略。（4）信息集（Information Set）：指博弈参与者在博弈过程中所知道的信息。（5）支付函数指博弈参与者采用特定策略与所能得到的收益之间的关系。,2博弈树的结构,（1）博弈树的构造方法首先行动的一方位于博弈树的最上端，根据动态博弈过程中各方的行动顺序，博弈数自上至下延展。也有学者习惯自左至右构造博弈树。,横向博弈树,博弈树中包含若干“节点”，节点用小圆圈表示。位于博弈树最上端的节点称为“初始节点”。初始节点用空心小圆圈表示，其他节点均用实心小圆圈表示。在每个节点处均对应某个博弈参与者，将节点对应的博弈参与者标识在节点旁边。例如：在“市场争夺战”博弈中，因为潜在进入者先行动，因此初始节点处对应的博弈参与者为潜在进入者。将潜在进入者标识在博弈树初始节点旁边。当潜在进入者决策之后，轮到在位者进行决策。在位者所在的节点称为“后续节点”。在位者位于两个后续节点上。在位者都有两种策略选择：“斗争”和“默许”。,如果初始节点处的博弈参与者存在 N 种策略，那么就从初始节点处分出 N 条路径。路径用线段表示。在线段旁注明相应的策略。在“市场争夺战”博弈中，首先行动的潜在进入者可以采取两种策略：“不进入”和“进入”。因此，从初始节点处引出两条线段，在两条线段旁分别标识“不进入”和“进入”。当潜在进入者选择结束后，达到在位者的节点。在位者有两个选择：“斗争”和“默许”。因此，从在位者的节点处引出两条线段，在两条线段旁分别标识“斗争”和“默许”。,当博弈不再有后续节点时，需要将博弈的收益标识在博弈树末端。将博弈参与者的收益放在括号里。需要注意的是：各博弈参与者的收益需要按照各参与者行动顺序进行排列。先行动的博弈参与者的收益写在左边，依次类推，从左到右，最后行动的博弈参与者的收益写在最右边。各个博弈参与者的收益之间用逗号分割。,（2）博弈树与博弈顺序博弈树各节点之间存在顺序关系，博弈树由上至下的节点顺序表示各博弈参与者进行决策的顺序。,从博弈树的节点可以引出多条线段，但不能从博弈树多个节点共同到达博弈树下方同一个后续节点。,错误的博弈树构造方法,正确的博弈树构造方法,正确的博弈树构造方法,构造博弈树时只能按照由上至下的路径，而不能存在由下向上的路径，也不能形成循环路径。回溯路径唯一性在求解完全信息动态博弈时非常重要。因为在求解动态博弈均衡时，一个很重要的方法是“逆向归纳法（Backward Induction）”。只有首先确保从博弈树任何最终节点向上回溯时路径唯一，才能确保逆向归纳法的可操作性。,正确的博弈树构造方法,正确的博弈树构造方法,错误的博弈树构造方法,错误的博弈树构造方法,三、信息集与三人罢工博弈,在完全信息动态博弈中，如果将博弈树的多个节点用虚线连接起来，表明这多个节点位于同一个博弈信息集中。也就是说：博弈参与者不知道自己位于同一个信息中的哪个博弈节点上。可以通过“三人罢工博弈”来说明信息集的含义以及信息集在动态博弈中的重要性。,1三人罢工博弈的定义,三人罢工博弈的博弈树,2三人罢工博弈的策略选择与信息,员工 2 只有一个信息集的博弈树,员工 3 不能观察到员工 2 的决策策略,员工 3 不知道员工 1 的决策策略,员工 3 不知道员工 1 和员工 2 的决策策略,三名员工都只有一个信息集的博弈,四、博弈树与静态博弈,博弈树的方法不仅能表示动态博弈，还能表示静态博弈。所谓的“博弈先后顺序”，它主要是一个信息的概念，而不是一个纯时间先后的概念。,用博弈树表示囚徒困境,下面三种博弈表达方式所表达的博弈内涵相同,第二节 完全且完美信息动态博弈概述,在完全且完美信息动态博弈（Dynamic Game with Perfect and Complete Information）中，每个博弈参与者均知道在自己之前进行决策的参与者选择的策略和博弈结构。博弈树中每个节点都独立构成一个信息集，没有虚线连接两个或多个博弈树节点。求解完全且完美信息动态博弈的重要方法之一是：逆向归纳法。可以通过“海盗分宝博弈”这个生动有趣的故事对“逆向归纳法”进行一个直观介绍。,一、海盗分宝博弈,1海盗分宝博弈的规则五个海盗首先进行抽签，确定决策顺序。五个海盗按照决策顺序依次提出对 100 个金币的分配方案。第一个海盗提出一个分配方案，如超过半数的海盗（包括提出分配方案的海盗）同意第一个海盗的分配方案，即大于等于 3 名海盗同意第一个海盗的分配方案时，那么该方案被通过，博弈结束。如果第一个海盗提出的分配方案没有得到超过半数海盗的同意，那么第一个海盗将被扔到海里喂鲨鱼。接下来由第二个海盗提出分配方案，如果超过半数的海盗同意第二个海盗的分配方案时，那么该方案被通过，博弈结束。,如果第二个海盗提出的分配方案没有得到超过半数海盗的同意，那么第二个海盗也将被扔到海里喂鲨鱼。接下来由第三个海盗提出分配方案，如果超过半数的海盗，即大于等于 2 名海盗，同意第三个海盗的分配方案时，那么该方案被通过，博弈结束。如果第三个海盗提出的分配方案没有得到超过半数海盗的同意，那么第三个海盗也将被扔到海里喂鲨鱼。接下来由第四个海盗提出分配方案。如果超过半数的海盗同意第四个海盗的分配方案时，那么该方案被通过，博弈结束。,如果第四个海盗提出的分配方案没有得到超过半数海盗的同意，那么第四个海盗也将被扔到海里喂鲨鱼。这时就只剩下第五个海盗了，第五个海盗将独吞抢劫来的100个金币，博弈结束。在这种分配规则下，第一个海盗将提出怎样的分配方案？第一个海盗提出的分配方案需要满足两个条件。第一，保证超过半数的海盗同意第一个海盗的分配方案。第二：第一个海盗最大化自己能分到的金币。如果直接从第一个海盗的决策策略入手，此问题相对复杂。不妨从第五个海盗入手，然后按照从后向前的顺序依次逆向考察海盗的策略选择。,2求解海盗分宝博弈的均衡,第一个海盗将提出怎样的分配方案？此分配方案在保证能得到超过半数海盗同意的前提下应最大化第一个海盗的利益。,通过逆向归纳法推导出的财宝分配方案,3海盗分宝博弈的均衡,第一个海盗的分配方案可以有两种。分配方案 1：分配给自己 97 个金币，给第二个海盗 0 个金币，给第三个海盗 1 个金币，给第四个海盗 2 个金币，给第五个海盗 0 个金币。分配方案 2：分配给自己 97 个金币，给第二个海盗 0 个金币，给第三个海盗 1 个金币，给第四个海盗 0 个金币，给第五个海盗 2 个金币。如果第一个海盗提出分配方案 1，那么第二个海盗和第五个海盗将反对，而第一个、第三个和第四个海盗将同意，因此第一个海盗的提议将获得通过。如果第一个海盗提出分配方案 2，那么第二个海盗和第四个海盗将反对，而第一个、第三个和第五个海盗将同意，因此第一个海盗的提议将获得通过。,二、扩展形式博弈的策略表达方式,1将扩展形式的博弈改写为策略形式,动态博弈的扩展表达形式,错误的动态博弈策略表达形式,动态博弈的策略表达形式,动态博弈的扩展表达形式,动态博弈的策略表达形式,2扩展形式转化为策略形式时的规律,参与者 1 的纯策略空间为：参与者 2 的纯策略空间为：参与者 3 的纯策略空间为：,参与者 2 的纯策略空间为：参与者 1 的纯策略空间为：,第三节 子博弈与逆向归纳法,在图中，用虚线框起来的部分称作一个子博弈（Sub-Game）。,一、子博弈,子博弈是原始动态博弈的一部分。子博弈包含博弈所需的各种信息，能独立构成一个博弈。一个博弈的子博弈需要满足四个条件。1子博弈的起始节点不能是原来博弈的起始节点2子博弈不能分割信息集3有些博弈包含多个子博弈4有些博弈没有子博弈,二、逆向归纳法,1逆向归纳法的定义和求解方法 逆向归纳法指：在求解动态博弈时，首先找到博弈顺序在最后的子博弈，找到子博弈中博弈参与者的策略选择，然后按博弈顺序由后向前逆向归纳，直至博弈树的初始节点，从而找到博弈的均衡。,1逆向归纳法的定义和求解方法 逆向归纳法指：在求解动态博弈时，首先找到博弈顺序在最后的子博弈，找到子博弈中博弈参与者的策略选择，然后按博弈顺序由后向前逆向归纳，直至博弈树的初始节点，从而找到博弈的均衡。,2通过逆向归纳法求解博弈均衡实例,三、斯塔贝尔伯格寡头博弈,斯塔贝尔伯格博弈（Stackelberg Duopoly Game）是寡头博弈的一种常见形式，是一种完全信息动态博弈。1斯塔贝尔伯格寡头博弈的定义 斯塔贝尔伯格寡头博弈：市场中有两个厂商。厂商 1 先行动，选择自身产量。厂商 2 观察到厂商 1 选择的产量后，再决策自己的产量。厂商 1 通常被称为领先者，厂商 2 通常被称为跟随者。,2求解斯塔贝尔伯格寡头博弈,根据逆向归纳法，首先考虑厂商 2 如何选择自己的产量.作为领先者，厂商 1 在决定自己的产量时会考虑自己的决策产量对厂商 2 的影响。求解得到：作为领先者的厂商 1 的产量为：作为跟随者的厂商 2 的产量为：,3古诺寡头博弈与斯塔贝尔伯格寡头博弈,在古诺寡头博弈中，市场需求函数和厂商成本函数与斯塔贝尔伯格博弈均相同。二者的主要区别是：在古诺寡头博弈中，两家厂商同时进行决策，是一个完全信息静态博弈。在斯塔贝尔伯格寡头博弈中，厂商 1 先行动，厂商 2 后行动，是一个完全信息动态博弈。古诺寡头博弈的均衡是：斯坦贝尔伯格寡头博弈的均衡是：,斯塔贝尔博弈寡头博弈均衡示意图,第四节 子博弈精炼纳什均衡,泽尔滕（Selten）在 1965 年提出了“子博弈精炼纳什均衡（Subgame Perfect Nash Equilibrium）”的概念。子博弈精炼纳什均衡也被称为子博弈完美纳什均衡。子博弈精炼纳什均衡与纳什均衡不同。纳什均衡要求：给定其他参与者在均衡处的策略，任何一方博弈参与者在均衡处选择的策略都是自己所能选择的最优策略，没有博弈参与者有动机改变自己在均衡时的策略。子博弈精炼纳什均衡不仅要求均衡解是纳什均衡，而且要求均衡解在每一个信息集上都是最优解。,一、子博弈精炼纳什均衡的含义,通过逆向归纳法求解博弈树得到的均衡是子博弈精炼纳什均衡。纳什均衡仅需要在均衡处，每个博弈参与者没有动机改变自己的策略。子博弈纳什均衡不仅要求均衡满足纳什均衡要求的条件，还要求在动态博弈中，此均衡是每个子博弈的最优解。也就是说：纳什均衡只对均衡处的策略有要求。子博弈精炼纳什均衡不仅对均衡处的策略有要求，而且对到达均衡的路径有要求。要求从博弈初始节点开始，博弈参与者到达均衡处所经过的路径也必须是最优的。,在“市场争夺战”博弈中，如果在位者选择“斗争”，那么潜在进入者会选择“不进入”。如果在位者选择“默许”，那么潜在进入者会选择“进入”。对潜在进入者来说，在位者的“斗争”策略是一种不可置信的威胁（Noncredible Threat）或空洞的威胁（Empty Threat）。子博弈精炼纳什均衡就是把包含不可置信威胁的纳什均衡从可能的均衡中剔除出去。顾名思义，“子博弈精练纳什均衡”是对纳什均衡的“精练”。通过剔除包含不可置信威胁的纳什均衡，减少纳什均衡的数目。,二、不可置信的威胁,在很多完全信息动态博弈中，都存在不可置信的威胁。1“市场争夺战”博弈在“市场争夺战”博弈中，（潜在进入者不进入，在位者斗争）这个纳什均衡包含不可置信的威胁，因此不是一个子博弈精练纳什均衡。如果在位者把“斗争”变成一个可置信的威胁（Credible Threat），那么博弈的均衡就会不同。,2斯塔贝尔伯格寡头博弈,如果后行动的跟随者做出一个“威胁”：不管先行动的领先者选择何种产量，自己都会将产量定在对于领先者厂商来说，这是一个可置信的威胁如果跟随者在具有法律约束力的公证机构签署一项承诺：不管领先者选取何种产量水平，自己都会将产量定在，如果自己违反承诺，那么将自动捐出 的收益。跟随者厂商的承诺变为一个可置信的承诺。跟随者厂商不可置信的威胁不会影响到先行动的领先者厂商的产量决策。然而跟随者可置信的威胁的确会影响到先行动的领先者厂商的产量决策，进而影响博弈均衡。,三、逆向归纳法的扩展应用,逆向归纳法不仅在求解完全且完美信息动态博弈时非常有用，在某些完全但不完美信息动态博弈中，逆向归纳法也有一定用武之地。,完全且完美信息动态博弈,博弈的均衡路径是：参与者 1 选择策略 R，然后参与者 2 进行决策参与者 2 选择策略 T，博弈结束。参与者 1 得到收益 3、参与者 2 得到收益 1。,四、逆向归纳法的局限和“蜈蚣博弈”,虽然逆向归纳法是求解动态博弈子博弈精炼纳什均衡的有力工具，但根据逆向归纳法求解出的均衡有时却是和常理相悖的。或者说：通过逆向归纳法有时也会求解出“不合理”的均衡。经济学家罗森赛尔（Rosenthsal）提出的“蜈蚣博弈（Centipede Game）”就是这样一个典型例证。虽然通过逆向归纳法可以求出蜈蚣博弈的均衡解，但此均衡解的合理性受到了普遍挑战。因此，蜈蚣博弈有时也被称为“蜈蚣博弈悖论”，简称“蜈蚣悖论（Centipede Paradox）”。,1蜈蚣博弈的定义,假设有两名博弈参与者：参与者 1 和参与者 2。两名参与者轮流进行决策：首先由参与者 1 进行决策，然后是参与者 2，再次是博弈参与者 1，然后是博弈参与者 2，依次类推。在博弈的初始节点处，参与者 1 有两个策略可以选择：T 和 C。策略 T 表示结束博弈（Terminate），策略 C 表示继续（Continue）博弈。当参与者 1 选择策略 T 时，博弈结束。参与者 1 得到收益 1，参与者 2 得到收益1。当参与者 1 选择策略 C 时，轮到博弈参与者 2 进行决策。参与者 2 同样面临两个策略选择：策略 T 和策略 C。,当参与者 2 选择策略 T 时，博弈结束。参与者 1 得到收益 0，参与者 2 得到收益3。当参与者 2 选择策略 C 时，轮到博弈参与者 1 进行决策。参与者 1 同样面临两个策略选择：策略 T 和策略 C。如果参与者 1 选择策略 T，那么博弈结束。参与者 1 得到收益 2，参与者 2 得到收益 2。如果参与者 1 选择策略 C，那么轮到参与者 2 进行决策，依次类推。在蜈蚣博弈中，包含初始节点在内，共有 198 个博弈节点。,蜈蚣博弈的支付矩阵,参与者 1 和参与者 2 轮流决策。参与者 1 对应 98 个节点，参与者 2 也对应 98 个节点。即：在奇数节点上，都是参与者 1 进行决策。在偶数节点上，都是参与者 2 进行决策。,2蜈蚣博弈悖论,通过逆向归纳法可以求解出蜈蚣博弈的子博弈精炼纳什均衡。通过逆向归纳法求解出的蜈蚣博弈的子博弈精炼纳什均衡是：在初始节点处，参与者 1 选择策略 T，博弈结束。两名博弈参与者均得到收益 1。在“蜈蚣博弈”中，越是位置靠后的博弈节点对应的博弈收益普遍越高，对两名博弈参与者均如此。在实际生活中，蜈蚣博弈的参与者们往往通过各种努力使得博弈尽可能进行下去，而不是理性的在初始节点处就终止博弈。通过逆向归纳法求解出的蜈蚣博弈子博弈精炼纳什均衡与人们现实生活的普遍行为模式相悖，这是“逆向归纳法”这种博弈求解方法受到质疑的原因之一。,第五节 补充阅读,一、信息集的数学定义二、子博弈精炼纳什均衡的数学定义在动态博弈中，子博弈精炼纳什均衡一定是原始博弈纳什均衡，但原始博弈纳什均衡不一定都是子博弈精炼纳什均衡。所谓“精炼”，就是对原始博弈纳什均衡的一种“甄别”，将存在不可置信威胁的纳什均衡从均衡中剔除出去，减少均衡个数。,2023/3/11,金融,本章小结和习题,
