搜索
第二章完全信息动态博弈博弈的扩展式表述子博弈精炼纳什均衡子博弈精炼纳什均衡举例重复博弈和无名氏定理第一节博弈的扩展式表述完全信息动态博弈一般以扩展型式来表示：G=(N,H,P,I,U)，包括5要素：（1）局中人N；（2）历史H:博弈树是一个多环节与枝干的集合，从单一的起始环节，直到终结环节，代表博弈历史；（3）对每个环节的分配法则P:将每个环节（除终结环节外）分配给不同的局中人，并赋予行动时可选的策略；（4）局中人行动时的信息集合I；（5）对应局中人可能选择策略，各局中人在终结环节所得到的报酬U。122LLSSLS（2，2）（-1，-1）（-1，-1）（1，1）战略式表述(strategicformrepresentation)多用矩阵2,2-1,-1-1,-11,12LSLS1扩展式表述(extensiveformrepresentation)多用博弈树战略式与扩展式-3，-3-3，-31，01，00，10，00，10，0AB（进入，进入）进入不进入（进入，不进入）（不进入，进入）（不进入，不进入）市场进入博弈的标准式进入不进入ABB进入不进入不进入进入收益：AB-3，-31，00，10，0市场进入的扩展式在市场进入博弈中：A有两个行动：“进入”、“不进入”。由于是先行动者，只有两个战略：选择“进入”或“不进入”。B有两个行动：“进入”、“不进入”。但是，有4个战略：(1)若A选择“进入”，B选择“进入”，若A选择“不进入”，B选择“进入”，即（进入，进入）(2)若A选择“进入”，B选择“进入”，若A选择“不进入”，B选择“不进入”，即（进入，不进入）(3)若A选择“进入”，B选择“不进入”，若A选择“不进入”，B选择“不进入”，即（不进入，进入）(4)若A选择“进入”，B选择“不进入”，若A选择“不进入”，B选择“不进入”，即（不进入，不进入）博弈树的构成1．结(nodes)：结包括决策结(decitionnodes)和终点结(terminalnodes)两类。决策结是参与人采取行动的时点，终点结是博弈行动路径的终点。在博弈树中，“谁在什么时候行动”用在决策结旁边标注参与人的办法来表示。参与人的支付标注在博弈树终点结处。2．枝(branches)：在博弈树上，枝是从一个决策结到它的直接后续结的连线，每一个枝代表参与人的一个行动选择。3．信息集(informationsets)：博弈树上的所有决策结分割成不同的信息集。每一个信息集是决策结集合的一个子集。该子集包括所有满足下列条件的决策结：(1)每一个决策结都是同一参与人的决策结；(2)该参与人知道博弈进入该集合的的某个决策结，但不知道自己究竟处于哪一个决策结。122LLSSLS（2，2）（-1，-1）（-1，-1）（1，1）结nodes信息集分单节信息集和多节信息集；如果用虚线匡起来表示2知道自己位于信息集内，但不知道是哪一点，因为他没能观察到对手的行动；如果博弈树的所有信息集都是单结的，称为完美信息博弈122LLSSLS（2，2）（-1，-1）（-1，-1）（1，1）完美信息（perfectinformation）与不完美信息(imperfectinformation)122LLSSLS（2，2）（-1，-1）（-1，-1）（1，1）不完美信息：2不能区分1是采用了L还是S完美信息：2能区分1是选择了L还是S第二节子博弈精炼纳什均衡子博弈子博弈精炼纳什均衡求解方法：逆向归纳法承诺行动与子博弈精炼纳什均衡一、子博弈（sub-game）子博弈定义：在一个扩展型博弈中，如果一个博弈由它的一个决策结及其所有后续结构成，并满足（1）起始结是一个单结的信息结;（2）子博弈保留了原博弈的所有结构，则称它为原博弈的一个子博弈（子博弈）。（1）起始结是一个单结的信息结122LLSSLS（2，2）（-1，-1）（-1，-1）（1，1）122LLSSLS（2，2）（-1，-1）（-1，-1）（1，1）x1x2（2）子博弈保留了原博弈的所有结构：子博弈的信息集和支付向量都直接继承自原博弈122LLSSLSx1x23333进入不进入ABB进入不进入不进入进入收益：AB-3，-31，00，10，0抵赖坦白ABB抵赖坦白坦白抵赖-1，-1-9，00，-9-6，-6在市场进入博弈中，包含3个子博弈（包括原博弈）。而在囚徒博弈中，只有一个子博弈（？）二、子博弈精炼纳什均衡子博弈精炼纳什均衡定义：在博弈G中，如果s*=(s1,…,sn)是G的一个纳什均衡，并且对所有可能的子博弈而言仍是一个纳什均衡，则称s*=(s1,…,sn)为一个子博弈精炼纳什均衡市场进入博弈的纳什均衡进入不进入ABB进入不进入不进入进入收益：AB-3，-31，00，10，0-3，-3-3，-31，01，00，10，00，10，0AB（进入，进入）进入不进入（进入，不进入）（不进入，进入）（不进入，不进入）该博弈中有三个纳什均衡：不进入，（进入，进入）进入，（不进入，进入）进入，（不进入，不进入）前两个均衡的结果(进入，不进入)，即A进入，B不进入；第二个均衡结果是(不进入，进入)，即A不进入，B进入如果理论得到这样的结果，无助于预测博弈参与人的行为。此外，纳什均衡假定，每一个参与人选择的最优战略是在所有其他参与人的战略选择给定时的最优反应，即参与人并不考虑自己的选择对其他人选择的影响，因而纳什均衡很难说是动态博弈的合理解。必须在多个纳什均衡中剔除不合理的均衡解，即所谓“不可置信威胁”。子博弈精炼纳什均衡是对纳什均衡概念的最重要的改进。它的目的是把动态博弈中的“合理纳什均衡”与“不合理纳什均衡”分开。正如纳什均衡是完全信息静态博弈解的基本慨念一样，子博弈精炼纳什均衡是完全信息动态博弈解的基本概念。①{不进入，（进入，进入）}②{进入，（不进入，进入）}③{进入，（不进入，不进入）}进入不进入ABB进入不进入不进入进入收益：AB-3，-31，00，10，0前边得到的三个纳什均衡中，均衡①意味着当A不进入时，B选择进入；而当A选择进入时，B仍选择进入（B威胁无论如何都要进入市场）。显然，当A选择进入时，B仍选择进入是不合理的，如果A进入市场，B选择“不进入”比选择“进入”收益要更大，理性的B不会选择进入，而A知道B是理性的，因此也不会把该战略视为B会选择的战略。因此，B的战略（进入，进入）是不可置信威胁。均衡③意味着当A进入时，B选择不进入；而当A选择不进入时，B仍选择进入（B威胁无论如何都不进入市场）。显然，当A选择不进入时，B仍选择不进入是不合理的，B的战略是不可置信的。①{不进入，（进入，进入）}②{进入，（不进入，进入）}③{进入，（不进入，不进入）}只有均衡②是合理的：如果A进入，B不进入；如果A不进入，B进入。因为A是先行动者，理性的A会选择“进入”（他知道B是理性的，B不会选择“进入”），而理性的B选择“不进入”。观察博弈树上的三个均衡中，B的不可置信战略中的反应，在第二阶段B开始行动的两个子博弈中不是最优；而合理的纳什均衡中，B的战略在所有子博弈中都是最优的，与A的第一阶段可能选择的行动构成该子博弈的纳什均衡。进入不进入ABB进入不进入不进入进入收益：AB-3，-31，00，10，0①②③①②③只有当一个战略规定的行动规则在所有可能的情况下都是最优的时，它才是一个合理的、可置信的战略。子博弈精炼纳什均衡就是要剔除掉那些只在特定情况下是合理的而在其他情况下并不合理的行动规则。子博弈精炼纳什均衡：如果参与者的战略在每一个子博弈中都构成了纳什均衡，则称纳什均衡是子博弈精练的(泽尔滕，1965)。为简单起见，假定博弈有两个阶段，第一阶段参与人1行动，第2阶段参与人2行动，并且2在行动前观测到1的选择。令A1是参与人1的行动空间，A2是参与人2的行动空间。当博弈进入第二阶段，给定参与人1在第一阶段的选择为a1∈A1，参与人2面临的问题是：),(21max22aauAa显然参与人2的最优选择a2*依赖于参与人1的选择a1。用a2*＝R(a1)代表上述最优化问题的解(即2的反应函数)。因为参与人1应该预测到参与人2在博弈的第二阶段将按a2*＝R(a1)的规则行动，参与人1在第一阶段面临的问题是：))(,(11max11aRauAa令上述问题的最优解为a1*。那么，这个博弈的子博弈精炼纳什均衡为{a1*,R2(a1)}，均衡结果为{a1*,R2(a1*)}。(a1*,R2(a1*))是一个精炼均衡，因为a2*＝R2(a1)在博弈的第二阶段是最优的。除a2*＝R2(a1)之外，任何其他的行为规则都不满足精练均衡的要求。上述思路就是逆向归纳法寻找子博弈精炼纳是均衡的基本思路。甲乙（2，2）（1，0）（3，1）上下左右乙（2，1）左右乙{左，左}{左，右}{右，左}{右，右}2，22，22，12，11，03，11，03，1上下甲纳什均衡子博弈精炼纳什均衡三个纳什均衡：（上，{左，左}）（下，{左，右}）（下，{右，右}）排除（上，{左，左}），（下，{右，右}），只有（下{左，右}）是子博弈精炼纳什均衡三、求解方法：逆推法逆向归纳法求解子博弈精炼纳什均衡的过程，实质是重复剔除劣战略过程在扩展式博弈上的扩展：从最后一个决策结开始依次剔除掉每个子博弈的劣战略，最后生存下来的战略构成精炼纳什均衡。如同重复剔除的占优均衡要求“所有参与人是理性的”是共同知识一样，用逆向归纳法求解均衡也要求“所行参与人是理性的”是共同知识。122软软脆脆软脆（0，0）（10，20）（20，10）（0，0）逆推法：例1甲丙乙上东下西左右（4，2，3）（1，7，8）（5，3，4）（7，6，6）丙丙（2，1，9）（0，4，2）逆推法：例2进入者在位者（0，300）（40，50）（-10，0）不进入进入默许斗争0，3000，300不进入-10，040，50进入斗争默许进入者在位者支付逆推法：例3四、承诺行动（commitment）与子博弈精炼纳什均衡纳什均衡之所以不是精炼均衡，是因为不可置信的威胁存在，如父母与子女之间的博弈。如果参与人在博弈前采取措施改变行动空间或支付函数，原来不可置信威胁就变得可置信，博弈的精炼均衡就会改变；将改变博弈结果而采取的措施称为“承诺行动”完全承诺，如破釜沉舟、军事博弈不完全承诺，增加行动成本承诺行动与博弈结果春节前夕，某小镇上两个商铺主甲和乙同时看到一个赚钱机会：去城里贩一批鞭炮回来零售，购货款加上运输费用共5000元，如果没有竞争对手，这批货在小镇上能卖6000元；但如果另一家商铺同时在小镇上卖鞭炮，价格下跌使得这批鞭炮只能卖4000元。纳什均衡是什么？假设甲先行动，商铺乙看到对方的选择后再决定是否进货，子博弈精炼纳什均衡是什么？承诺行动与博弈结果如果甲先行动，但在博弈开始前商铺主乙有一次行动A的机会，利用子博弈精炼均衡概念分析下述两种情况下的博弈结果：（1）A：商铺主乙逢人便说自己一定要进货，无论对方如何行动他都不会改变这个决定；（2）A：商铺主乙与某个嘲笑他说大话的第三者丙打赌：如果自己到时不进货，向丙支付1500元；如果自己到时候进货，丙向他支付100元。并且，乙将这个赌局通知甲。甲乙乙进进不进不进进不进（-1000，-1000）（1000，0）（0，1000）（0，0）甲乙乙进进不进不进进不进（-1000，-900）（1000，-1500）（0，1100）（0，-1500）开金矿博弈的基本问题：甲在开采一价值4万元的金矿时缺1万元资金，而乙正好有1万元资金可以投资。设甲想说服乙将这1万元资金借给自己用于开矿，并许诺在采到金子后与乙对半分成，乙是否该将钱借给甲呢？假设金矿的价值是经过权威部门探测确认的，没必要怀疑。乙甲（0，4）（2，2）（1，0）不借借分不分开金矿博弈不借乙甲乙借不分分（1，0）不打打（0，4）（1，0）（2，2）有法律保障的开金矿博弈——分钱打官司都可信在一个重视自身利益的成员组成的社会中，完善公正的法律制度不但能保障社会的公平，而且还能提高社会经济活动效率，是实现最有效率的社会分工合作