《完全信息动态博弈》PPT课件.ppt

《《完全信息动态博弈》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《完全信息动态博弈》PPT课件.ppt（32页珍藏版）》请在三一办公上搜索。

1、完全信息动态博弈,第一节 扩展型博弈第二节 子博弈完美均衡,凶残海盗的逻辑,凶残海盗的逻辑中有一个智力题海盗分金：5个海盗要分配抢来的100个金币，分配方式是第一个人提出分配方案，如果同意这种方案的达到半数，提议通过，否则提议的人扔进大海，由剩余的人再进行同样的过程。假设5个人的提议的次序已定，金币不能分割，而且海盗的本性让他们觉得，如果对自己的收益没有影响，则很乐意看到别人被扔进大海，这时理性结局应该如何？这种博弈局势和策略型博弈的不同之处在于：其中存在着局中人行动的先后次序，更多的信息意味着有可能利用这些信息形成更严格的均衡概念?对这种具有动态结构的决策形势进行研究的规范分析工具是扩展型博

2、弈。,第一节 扩展型博弈,扩展型博弈与策略型博弈的区别 1、其中存在着局中人行动的先后次序。2、它增加了对局中人行动次序与局中人行动 时所掌握信息的描述.3、策略型博弈中常常利用矩阵形式作为一种清晰的表现手段，而扩展型博弈则利用博弈树来表现多个人有限策略博弈。策略型博弈中各局中人同时一次性地选定策略，无法表现出他们选择的先后次序，如果我们要研究博弈的动态特征，就必须找到一种更适当的表述方式结果就得到所谓的扩展型博弈。,一：扩展型博弈的构成,1：局中人2：行动顺序，即谁在何时采取行动3：行动空间，它表示在每次行动时，局中人可以进行哪些选择4；信息集，它表示局中人进行选择时所知道的信息；5：支付函

3、数，即把局中人所获得的支付表示为其采取的行动的函数；6外生事件的概率分布，对此引入“自然”作为一个虚拟局中人，它在博弈中的作用只是在相应的地方在若干外生事件中根据一定概率分布随机选取，而没有自己的利益目标与支付函数。,二：博弈树,（一）博弈树的理解1、这个博弈开始于一个起始决策点。2、博弈树由一系列节点x 和它们之间的连线构成，这些节点之间存在着偏序关系。3、博弈树是全排序的，即从博弈树的起点到博弈树中的任何一点只有惟一一条路径.4、博弈的扩展式与博弈树是同义语。与博弈的基本式相比，博弈的扩展式特别善于描述复杂的博弈，博弈越复杂，博弈扩展式的优点就越突出。,博弈树,囚徒困境的扩展型博弈,象棋的

4、扩展式,（二）完美信息博弈与完美信息的违背,1、信息集：1、1定义：实际上是参与者决策节点集合的一个子集。信息集的定义是当博弈进行到某个阶段，轮到某个参与者行动时，他不知道自己位于哪一个节点，不能加以区分的节点的集合就称为信息集。参与者之所以不能对信息集中的节点进行区分，原因在于他对前面发生的其他参与者的(有些或全部)行动未能观察到。,囚徒困境的信息集 在图中，我们看到当博弈进行到囚徒2行动时，由于囚徒2未能观察到此前囚徒1的行动，所以囚徒2不能对节点X2和X3作出区分，也就是他不知道囚徒1到底选择的是什么策略。节点X2、X3的集合X2，X3即是囚徒2的一个信息集，集合X1即是囚徒1的信息集。

5、习惯上，我们通常把位于同一个信息集的节点用虚线连接起来或者用圆圈圈起来，只包含个节点的信息集就称为单点信息集,1、2、信息集的意义 第一，使用信息集可以清楚地描绘出当参与者行动时，他所处的“环境”和所有可能掌握的信息，因而能揭示出博弈的信息特征。第二，信息集的使用还可以使静态博弈转化为动态博弈在博弈的基本式和 扩展式之间架设了一道桥梁，博弈的扩展式成为能够描述所有博弈类型的有力工具。第三，利用信息集概念，可以表现复杂的信息结构，描述动态博弈局势中局中人在行动时知道的各种信息。我们还可以利用扩展型博弈表现静态博弈 1、3、信息集的规定：第一，在任意一个信息集中的每一个节点上，参与者一定有相同的行

6、动集合 原因非常简单，如果一个信息集中的两个节点包含的行动不一样，由于参与者在不同的节点具有不同的行动、因而他一定能对这两个节点作出区分。这就与信息集的定义相矛盾。第二，信息集不得违背完美回忆的假定。完美回忆假定当博弈中的参与者行动时，他对过去发生的一切情况都记得清清楚楚。显然完美回忆在现实生活中可能并不满足，因而我们把它看作一 种假定，但完美回忆在现实生活中也普遍存在，例如，打过桥牌的人就知道桥牌游戏就是一个典型的完美回忆。,（二）完美信息博弈与完美信息的违背,2、完美信息：指博弈中的每一个信息集只包含惟一一个节点。3、完美信息博弈：当每一个参与者行动时，他都能观察到他的 对手先前所有的行动

7、。这种博弈我们定义为完美信息博弈.这类特殊的完美信息博弈，其中所有的信息集都是单点集，在完美信息博弈中，一次只有一个局中人在行动而且他在行动时知道博弈的所有以往行动历史。博弈开始时，局中人1在两种行动U和D中进行选择，如果选择U则博弈结束，结局为X1；如果选择D，则由局中人2在L和R之间进行选择如果局中人2选L则博弈结局为X2，局中人2选R则局中人3在m相r中进行选择。（见博弈树 图）,4、不具备完美回忆的博弈 在经济学应用的绝大多数博弈模型中均假设博弈具有“完美回忆”即没有局中人会忘记自己所知道的信息，所有局中人不记得自己以往的行动选择。不具有完美回忆的例子如图所示，该博弈中，局中人1首先在

8、u与R两种行动中进行选择，局中人2随之行动，然后局中人1再行动，这时局中人1忘记了自己曾经在u与R中作出的选择，从而这一博弈不具有完美回忆。博弈理论研究的是完全理性的个人，因此涉及的博弈局势应该都具有完美回忆。,不具备完美回忆的博弈,在图中，参与者2忘记了他曾经知道的参与者1如何行动的信息。如果一个博弈不满足完美回忆的要求，实际上我们就不可能对该博弈进行分析，因为忘记，所以一切后果都可能出现。在博弈论中，完美回忆和博弈的结构是所有参与者的公共信息，是每一个博弈都必须满足的条件。,得到扩展型博弈的表述后，就需要考察它的解。在以扩展型博弈表述的完全信息动态博弈中，纳什均衡概念同样适用，然而需要加以

9、完善，最常用的解概念就是子博弈完美均衡。,第二节 子博弈完美均衡,子博弈通俗地说就是动态博弈的局部，只要是一个单点信息集，它后面的所有节点(信息集和结束点)连同它本身就构成了一个子博弈“子博弈精练纳什均衡”，该模型的中心思想是将纳什均衡中包含的不可置信的威胁剔除出去，使均衡战略不再包含不可置信的威胁。它要求参 与人的决策在任何时点上都是最优的，决策者“随机 应变”，而不是固守旧略。,X0、X1、X2、X3、X4共5个子博弈,一：扩展型博弈的纳什均衡,(一)策略与行为策略首先需要定义扩展型博弈中的纯策略。由于扩展型博弈中同一个局中人可能在多种场合行动，所以局中人的全局策略应该给出在每个需要决策的

10、地方(每个信息集处)局中人的行动选择。,例如，假设一种博弈局势分两个阶段进行，在第一阶段中，局中人1和2分别在U和D中同时进行选择，第一阶段的结果告诉两个局中人后，第二阶段局中人同时在L和R中进行选择。共有四个结果,这种穷举式策略表述方式比较罗嗦，因此常用更简单的方式来进行表示。例如，以上策略也可表示为：“第一阶段选U。如果对方也选U，则在第二阶段选L.否则，在其他情况下总选R,简化表述需要能对应完整表述的策略.例如，俗话说的“你不仁，我不义”就是更为熟悉的日常的策略表述方式，它表明，如果对方上次采取了对自己不利的行动，自己就在这次采取对对方不利的行动，而如果对方上次合作，那自己这次也合作。我

11、们可以把它转化为具体扩展型博弈中的完整策略。,这个例子也表现了扩展型博弈转换为策略型时的一种现象，完整的纯策略给出了每个信息集处局中人的选择，但这有时是不必要的。在示例中，局中人1第一阶段决定选择U，那么实际上第一阶段的结局不可能是(D，U)和(D，D)，只可能是(U，U)或U，D)，所以策略中只要考虑后两种结局处自己的选择就可以了。,(二)扩展型博弈和策略型博弈的关系,1、扩展型博弈可用策略型博弈的形式来表现 在以上定义的基础上，可以建立扩展型博弈与策略型博弈的对应关系，通过扩展型博弈的纯策略定义与相应期望支付函数的建立，可以将扩展型博弈用策略型博弈的形式来表现,2、扩展型博弈的策略型表述,

12、3、二者的关系,扩展型博弈与对应的策略型表述具有相同的纯策略空间，但是行为策略与对应策略型表述的混合策略在概念上并不完全相同。行为策略中，局中人在各信息集处采用不同的随机机制在对应行动集中选择。对此一个常用的比喻是：一种纯策略是一本指令书，每一页说明在特定的信息集处如何行动，纯策略空间就是由这些书组成的图书馆；混合策略是这些书上的一种概率分布，即根据一定机制随机地在这些书中进行选择；一种行为策略则是一本书其中每一页说明了对应的若干行动中的随机选择。,二、子完美博弈均衡,（一）纳什均衡的缺陷空洞威胁 策略型可以用来表述任意复杂的扩展型博弈，从而拓展了纳什均衡概念应用的范围。但是纳什均衡有些是不合

13、理的(泽尔滕指出，在扩展型博弈的纳什均衡中有些是不合理的).扩展型博弈中的纳什均衡的实现依赖于局中人不合理的“空洞威胁”，需要加以剔除，从而形成了子博弈完美均衡的概念。,空洞威胁,空洞威胁：发出威胁的局中人并不会真正实施这种策略，因为这种策略对他来说不是最佳策略。如果你对竞争者说：你不给我馅饼市场的一半的话我就在今后一年中免费发放馅饼，让你一个都卖不出去，对手是不会相信你的这种威胁的因为实施威胁行动对威胁者自己来说损失巨大，得不偿失。,（二）子博弈完美均衡的定义,为了剔除依赖空洞威胁的纳什均衡，要求均衡策略在每个信息集上都是对于对手策略的最佳反应，这样就避免了局中人利用非最佳反应策略来实施空洞

14、威胁的情况，从而得出的均衡就是子博弈完美均衡。,（三）子博弈完美均衡的求解逆向归纳法,第一步，从扩展式博弈(博弈树)的终点开始，找到每一个最后子博弈(它不再饱含任何其他更小的子博弈)的纳什均衡，并计算出相应的收益。第二步，将每一个最后子博弈的起始点变成结束点，将计算出的每一个最后子博弈在纳什均衡下的收益写在其下方、我们就获得了一个新的扩展式博弈(或新的博弈树)，称为压缩的扩展式博弈。这样经过一次压缩，就剔除)，最后子博弈。第三步，重复第一步和第二步，并重新得到一个压缩式博弈和相应的纳什均衡。这个过程一直进行到最后只剩下唯一一个子博弈为止，这时根据在逆推过程中找到的一系列子博弈的纳什均衡组合(表

15、明在不同信息集下的行动指南)就是扩展式博弈的一个完美均衡。第四步，如果在逆推过程中没有遇到多重均衡，那么这个策略组合就是惟一的完美均衡；如果遇到了多重均衡，就需要对子博弈中每一个可能的均衡重复以上步骤，从而得出所有的完美均衡。比如，一个扩展式博弈有两个子博弈分别存在2个和3个纳什均衡，其他子博弈只有1个纳什均衡，那么该博弈就有2x 36个完美均衡。,例 海盗分金的逆向归纳法,用i1，5表示按顺序先后提议的五个局中人，Xi表示每个人获得的金币数。1、如果只剩下两个人(4和5)，则4会建议X4100，X5=0，自己同意，即便剩下的那个人反对也达到半数，所以这一提议肯定会得到通过。2、倒推到剩下三个人的情形，考虑到后续的均衡结局，提议的人3会建议X399，X40，X51，从而赢得3的支持(否则后续子博弈中5只能得到0)，提案通过。3、倒推到剩四个人的情形，提议的2会建议X299，X30，X41，X50，这样可得到4的支持，从而通过方案。4、倒推到博弈开始，1会建议X198，X20，X31，X40，X51，从而赢得3和5的支持，就此结束博弈，这就是这一博弈局势中的子博弈完美均衡。,