博弈论 第6讲2013学习专业资料

上次内容回顾帕累托占优风险占优聚点均衡防共谋均衡两个拆迁博弈12动态博弈的概念一类博弈行为通常需要参与人多步决策才能完成，具有明显的阶段性。博弈的结局、各参与人的收益由多阶段决策结果确定。各参与人的决策有一定的顺序。3

Thekeyfeaturesofadynamicgameofcompleteandperfectinformationarethat(ⅰ)themovesoccurinsequence,(ⅱ)allpreviousmovesareobservedbeforethenextmoveischosen,and(ⅲ)theplayers’payoffsfromeachfeasiblecombinationofmovesarecommonknowledge.4动态博弈的概念由于动态博弈各参与人进行决策具有明显的阶段性、行动次序性，通常用扩展式(extensiveform)表述法描述这些信息。5博弈的扩展式表示参与人集合：i=1,…,N。用N表示虚拟参与人“自然”；自然的含义是某些外生的客观概率分布事件参与人的行动顺序(theorderofmoves):描述各参与人在什么时候行动；参与人的行动空间(actionset)：在每次行动时，参与人可选择的行动集合；6博弈的扩展式表示参与人的信息集(informationset)：每次行动时参与人知道什么；参与人的收益函数：在行动结束之后，每个参与人得到些什么。自然选择的概率分布（假定自然状态是共同知识）。对于有限博弈，博弈树是常用的表述方式。7扩展式表述简例图2-1就是一个商品仿冒和反仿冒动态博弈的扩展型描述。ABAB制止不仿冒仿冒不制止不仿冒仿冒制止不制止图2-1仿冒和反仿冒博弈扩展型表述(0,10)(-2,5)(2,2)(10,4)(5,5)8扩展式表述简例图2-2是包括自然选择的博弈扩展式表述图2-2房地产开发博弈ANB大(1/2)不开发开发小(1/2)(8,0)(1,0)NBB大(1/2)小(1/2)B(4,4)(-3,-3)(0,8)(0,0)(0,1)(0,0)9博弈树若动态博弈是有限博弈，则可用博弈树表示该博弈。这里有限的含义是各阶段各参与人的行动数目有限博弈的阶段数有限10博弈树博弈树的基本结构为结点(nodes)。包括决策结及终点结。决策结是参与人采取行动的时点；终点结是博弈行动路径的终点。枝（branches）。从一个决策结到它的直接后续结的连线，每一个枝代表参与人的一个行动选择。11节点nodes决策节点（decisionnodes）终点节点（terminalnodes）枝branches：每一条树枝代表一个行动信息集informationsets：参与人在决策节点选择行动时，需要有关信息；对此前博弈过程的一个全部而明确的认识就构成一个信息集。信息集的定义：12DefinitionAninformationsetforaplayerisacollectionofdecisionnodessatisfying:(ⅰ)theplayerhasthemoveateverynodeintheinformationset,and(ⅱ)whentheplayofthegamereachesanodeintheinformationset,theplayerwiththemovedoesnotknowwhichnodeintheinformationsethas(orhasnot)beenreached.

对完美信息动态博弈的博弈树来说，一个信息集只包含一个决策结，对不完美信息动态博弈，则一个信息集包含多个决策结。13博弈树信息集：是决策结集合的一个子集。将博弈树中某一决策者在某一行动阶段具有相同信息的所有决策结称为一个信息集。每个决策结都是同一个参与人的决策结。该参与人知道博弈进入该集合的某个决策结，但不知道自己究竟出于哪一个决策结（若该信息集有两个或两个以上元素）。14completeinformation(i.e.,gamesinwhichtheplayers’payofffunctionsarecommonknowledge).Weanalyzedynamicgamesthathavenotonlycompletebutalsoperfectinformation,bywhichwemeanthatateachmoveinthegametheplayerwiththemoveknowsthefullhistoryoftheplayofthegamethusfar.

151617博弈树对于有限动态博弈，若参与人对彼此在各决策结点的行动集合，彼此的效用函数，历史的行动有着完全的了解，则称这样的博弈为完全信息动态博弈。如果博弈树的所有信息集都是单元素集，称该博弈为完美信息博弈(gameofperfectinformation)。上述两个定义的差别在于对自然行动信息的描述。1819博弈树实例注意，扩展式表述也可以用于分析静态博弈，如图2-5的囚徒问题。ABB坦白抵赖坦白抵赖抵赖坦白(-5,-5)(0,-8)(-8,0)(-1,-1)图2-5囚徒问题的扩展式表述20一些说明一般假定博弈满足“完美回忆”(perfectrecall)要求。“完美回忆”的概念完美回忆是指没有任何参与人会忘记自己以前知道的事情，所有参与人都知道自己以前的选择。可以利用信息集概念描述完美回忆。21一些说明图2-6描述了不完美回忆现象。图2-6不具有完美回忆的例子ABLDUBAALRARA不能区分（D,L）和(D,R)是正常的，因为参与人1可能没有观察到B是选择了L还是选择了R。但A不能区分（U,R）和(D,L)则说明A忘记了在开始博弈时选择了U行动还是D行动，因而不具有完美回忆。22一些说明现实中不具完美回忆的一个例子是扑克比赛。在扑克比赛中，参与人常常忘记别人曾出过些什么牌。23一些说明需要注意的是，若有些动态博弈的阶段很多乃至无限，或者参与人在一个阶段有许多可以选择的行为，这时采用博弈树表述将变得很困难，或者不可行。如下棋等。此时应用文字描述或用数学抽象形式表述。24动态博弈的策略式表述相机选择(contingentplay)动态博弈中参与人的策略是各自预先设定的，在博弈的各阶段，针对各种情况做出相应决策。即“等待”博弈到达自己的信息集（包含一个或多个决策结）后再决定如何行动。在策略式表述博弈中，参与人似乎是博弈开始之前就制定出了一个完全的相机选择，即“如果……发生，我将选择……”。25从扩展式表述构造战略式表述假定开发商A先决策，开发商B观测到A的选择后决策。那么博弈的扩展式表述如图2-8表述。ABB开发不开发开发不开发不开发开发(-3,-3)(1，0)(0,1)(0,0)图2-8房地产开发博弈动态博弈的策略式表述26这是一个完美信息博弈（每个参与人的信息集是单结的）。A只有一个信息集，两个可选择行动，因而A的行动空间也就是A的战略空间：SA=(开发，不开发)。ABB开发不开发开发不开发不开发开发(-3,-3)(1，0)(0,1)(0,0)图2-8房地产开发博弈动态博弈的策略式表述27但B有两个信息集，每个信息集上有两个可选择的行动，因而B有四个纯战略，分别为A开发,我开发;A不开发，我开发；A开发，我开发，A不开发我不开发；A开发，我不开发，A不开发我开发；A开发，我不开发，A不开发我开发。ABB开发不开发开发不开发不开发开发(-3,-3)(1，0)(0,1)(0,0)图2-8房地产开发博弈动态博弈的策略式表述28若把B的信息集从左到右排列，上述四个纯策略可以简单记为{开发，开发}{开发，不开发}{不开发，开发}{不开发，不开发}上面四个纯策略含义：当A选择开发时，B选择大括号中前面的策略；当A选择不开发时，B选择大括号中后面的策略。ABB开发不开发开发不开发不开发开发(-3,-3)(1，0)(0,1)(0,0)图2-8房地产开发博弈动态博弈的策略式表述29B的纯策略为{开发，开发}{开发，不开发}{不开发，开发}{不开发，不开发}A的纯策略为SA=(开发，不开发)于是可以写成策略式表述形式，为ABB开发不开发开发不开发不开发开发(-3,-3)(1，0)(0,1)(0,0)图2-8房地产开发博弈动态博弈的策略式表述30ABB开发不开发开发不开发不开发开发(-3,-3)(1,0)(0,1)(0,0)图2-8房地产开发博弈开发，开发开发，不开发不开发，开发不开发，不开发开发-3，-3-3，-31，01，0不开发0，10，00，10，0表2-1房地产开发博弈：策略式表述动态博弈的策略式表述31该博弈有四个纯战略纳什均衡，分别为（开发，{开发，不开发}）（开发，{不开发，开发}）（开发，{不开发，不开发}）（不开发，{开发，开发}）ABB开发不开发开发不开发不开发开发(-3,-3)(1,0)(0,1)(0,0)图2-8房地产开发博弈开发，开发开发，不开发不开发，开发不开发，不开发开发-3，-31，01，01，0不开发0，10，00，10，0表2-1房地产开发博弈：策略式表述动态博弈的策略式表述32在扩展式表述博弈中，所有n个参与人的一个纯战略组合s=(s1,…,sn)决定了博弈树上的一个路径。比如（开发，{不开发，开发}）决定了博弈的路径为A

开发

B不开发(1,0)ABB开发不开发开发不开发不开发开发(-3,-3)(1,0)(0,1)(0,0)图2-8房地产开发博弈开发，开发开发，不开发不开发，开发不开发，不开发开发-3，-31，01，01，0不开发0，10，00，10，0表2-1房地产开发博弈：策略式表述动态博弈的策略式表述33（不开发，{开发，开发}）决定了博弈的路径为A

不开发

B开发(0,1)（开发，{不开发，开发}）决定了博弈的路径为A

开发

B不开发(1,0)ABB开发不开发开发不开发不开发开发(-3,-3)(1,0)(0,1)(0,0)图2-8房地产开发博弈开发，开发开发，不开发不开发，开发不开发，不开发开发-3，-3-3，-31，01，0不开发0，10，00，10，0表2-1房地产开发博弈：战略式表述动态博弈的策略式表述34动态博弈的策略式表述给出了扩展式表述的战略式表述转换，就可以像静态博弈那样，定义纯战略纳什均衡或混合战略纳什均衡。按照VonNeumann观点，将动态博弈模型转化成策略式表述形式后，按照静态博弈分析方法，即可处理动态博弈问题。近来研究表明，存在策略式表述相同，但却有本质差别的，不同扩展式表述的动态博弈。说明上述观点具有一定的局限性。因此，策略式表述并不能取代扩展式表述。35完全信息动态博弈纳什

均衡存在性定理如果有限博弈是完美信息博弈，他还有一个纯战略纳什均衡（Zermelo,1913）。通过一个简单实例（见图2-9）说明Zermelo定理。DURL(3,1)(0,0)图2-9逆推法求纳什均衡(2,2)AB36逆推归纳法逆推归纳法是求解完美信息动态博弈的经典方法。逆推法思路。假设博弈到了第二阶段，参与人B的信息集为{D}，选择L获利1单位，选择R获利0单位，因此B应该选择L;在博弈的第一阶段，参与人A选择U获利2单位，选择D获利状况取决于参与人B的选择；DURL(3,1)(0,0)图2-9逆推法求纳什均衡(2,2)AB37但A知道B是理性的，一旦到达第二阶段，B肯定会选择L行动，从而A获利为3单位，因此，A应选择D。因此，（D,L）是纯战略纳什均衡。DURL(3,1)(0,0)图2-9逆推法求纳什均衡(2,2)AB逆推归纳法38如果采用博弈的策略式表述（见表2-2）,可得到另一个纳什均衡(U,R)。如果A选择U,那么B的信息集不能达到，我们说B的信息集不在均衡路径上(out-of-equilibriumpath)。ABDURL(3,1)(0,0)图2-9逆推法求纳什均衡(2,2)LRU2,22,2D3,10,0表2-2策略式表述与策略式分析比较39此种情况下，B的选择对A没有什么影响。因此，纳什均衡对一个参与人在非均衡信息集上的选择没有限制。但是，一个参与人在非均衡信息集上的战略可以影响其他参与人在均衡信息集上的选择。ABDURL(3,1)(0,0)图2-9逆推法求纳什均衡(2,2)LRU2,22,2D3,10,0表2-2策略式表述与策略式分析比较40与策略式分析比较逆向归纳法实质上是重复剔除劣战略法在扩展式博弈中的应用。逆向归纳法不适用于无限博弈和不完美信息博弈。逆向归纳法剔除了“非理性”的均衡策略…41海盗分赃－逆向归纳案例5个海盗抢来了100枚金币，大家决定分赃的方式是：由海盗一提出一种分配方案，如果同意该方案的人达到半数，则该提议通过并实施；否则，提议人将被扔进大海喂鲨鱼。然后由接下来的海盗继续重复提议过程。假设每个海盗都绝顶聪明，也不相互合作，并且极度自私，那么第一个海盗该如何提议？42海盗分赃－逆向归纳案例使用逆向归纳法可以求解如下：首先，考虑只剩下最后的海盗五，显然他会分给自己100枚，并赞成自己；再回溯到只剩下海盗四和海盗五的决策，海盗四可以分给自己100枚并赞成自己；海盗五被分得0枚，即使反对也无用；43海盗分赃－逆向归纳案例回到海盗三，海盗三可以分给海盗五1枚得到海盗五的同意；分给自己99枚，自己也同意；分给海盗四0枚，海盗四反对但无用；回到海盗二，海盗二可以分给海盗四1枚得到海盗四同意；分给自己99枚，自己也同意；海盗三、五各分得0枚，他们会反对但反对没有用44海盗分赃－逆向归纳案例回到海盗一，他可以分给海盗三、五各1枚，获得海盗三、五的同意；分给自己98，自己也同意；分给海盗二、四各0枚，他们会反对但反对不起作用。45海盗分赃－逆向归纳案例因此，这个海盗分赃问题的答案是（98,0,1,0,1）：海盗一提出分给自己98枚，分给海盗二、四各0枚，分给三、五个1枚；该提议会被通过，因为海盗一、三、五会投赞成票。我们可以把这个逆向决策的过程用如下矩阵表达出来（下图，其中画下划线的数字表示海盗对该方案投了赞成票，未加下划线对应于反对票）46海盗分赃－逆向归纳案例海盗分赃逆向推理过程(全部海盗半数同意即可通过)分配者分配给各海盗的金币枚数海盗一海盗二海盗三海盗四海盗五海盗五100海盗四100

0海盗三99

01海盗二

99

0

1

0海盗一98

01

0147海盗分赃－逆向归纳案例思考：1，如果规则改为超过半数通过，怎么提议？2，如果规则改为除了提议人之外的海盗超过半数通过，怎么提议？48可信性问题可信性(credibility)的含义参与人事先宣布的行动方案是否在实际执行过程中也能保持一致？49一个实例BA分不借借不分图2-10开金矿博弈(1,0)(2,2)(0,4)A在开采价值4万元的金矿时缺1万元资金，B正好有1万元资金可以投资。设想A说服B将这1万元资金借给自己用于开矿，并许诺在采到金子后与B对半分成，B是否应该将钱借给A呢？B关心的是A开采到金子后是否会履行诺言？可信性问题50BA分不借借不分图2-10开金矿博弈(1,0)(2,2)(0,4)B的处境是“不借”则资金安全，但得不到利润；“借”则面临A的不守信风险。若根据“经济理性”原则，一旦B将钱借出，A将卷款逃走；因此，B的最优策略是“不借”这说明，在这样的博弈结构下，A的承诺是“不可信的”。可信性问题51BA分不借借不分图2-10开金矿博弈(1,0)(2,2)(0,4)因此，双方最优策略为第一阶段，B选择“不借”若博弈到达第二阶段，则A选择不分。如果引入法律机制…可信性问题52BA分不借借不分图2-11有法律保障的开金矿博弈(1,0)(2,2)(0,4)B(1,0)打不打可信性问题图2-11是有法律保障的开金矿博弈问题。由该图可以看出，最终博弈的理性结果为B借钱给A，开采结束后，A与B利润平分（用逆序归纳法，自己验证一下）。53可信性问题BA分不借借不分图2-12法律保障不足的开金矿博弈(1,0)(2,2)(0,4)B(-1,0)不打打若法律保障不足以使B坚持打官司，如图2-12所示，则与前面分析类似，B在第一阶段将选择“不借”，A在第二阶段将选择“不分”（一旦B借款给A的话）。一旦B由于“糊涂”将钱借给了A，则第三阶段将选择不打官司。54BA分不借借不分图2-12法律保障不足的开金矿博弈(1,0)(2,2)(0,4)B(-1,0)不打打上述分析说明，在一个有私心，重视自身利益的成员组成的社会里，完善公正的法律制度不但能保证社会的公平，而且还能提高社会经济活动的效率。可信性问题55逆向归纳法小结逆向归纳法求解策略：从动态博弈的最后一个阶段出发，对该参与人采用经济理性原则进行分析，逐步到推回前一个阶段相应参与人的行动选择，一直到第一阶段的分析方法。56逆向归纳法小结由于逆推法确定的各参与人在各阶段的行动选择，都是建立在后续阶段各个参与人理性选择基础上的，因此自然排除了包含不可信承诺的可能性。逆向归纳法中的共同知识。逆推归纳法是完美信息动态博弈分析中使用最普遍的方法。57反国家分裂法的承诺作用58子博弈完美均衡在动态博弈的战略式表述中，纳什均衡假定每一个参与人在选择最优战略时，是基于其他所有参与人战略选择给定前提下进行的，而没有考虑到自己的选择对其他参与人的影响，因此，纳什均衡具有一定的缺陷性。泽尔腾(Selten)的子博弈完美纳什均衡(subgameperfectNashEquilibrium)在一定程度上对此作出了贡献。59子博弈完美均衡子博弈概念一个扩展式博弈的子博弈G由一个决策结x和所有该决策结的后续结T(x)组成，它满足下列条件：x是一个单结信息集,即h(x)={x};对于所有的T(x)中的x’，如果x’’与x’同属于一个信息集，则x’’也在T(x)中。图2-13表示了子博弈与原博弈的关系。需要说明的是，G本身是自己的一个子博弈。60ABB开发不开发开发不开发开发图2-13博弈和子博弈B开发a)原博弈b)子博弈I不开发不开发B开发c)子博弈II不开发(-3,-3)(1,0)(0,1)(0,0)(-3,-3)(1,0)(0,1)(0,0)61子博弈完美均衡图2-14的两个博弈扩展型中，特殊颜色标示的部分都不是原博弈的子博弈。ABBLDURL图2-14构不成子博弈的图形表示(1)a)原博弈R62图2-15中红色部分构成的图形不是原博弈的子博弈，因为参与人C的信息集被切割。ABBLDURLRClCrlCrlCrlr图2-15构不成子博弈的图形表示(2)子博弈完美均衡63子博弈完美均衡子博弈完美纳什均衡扩展式博弈的一个战略组合s*=(s1*,…,si*,…,sn*)是一个子博弈完美纳什均衡，如果它是原博弈的纳什均衡。它在每一个子博弈上都是纳什均衡。64子博弈完美均衡纳什均衡与子博弈精炼纳什均衡的关系前面分析说明，一个特定的纳什均衡决定了原博弈树上唯一的一条路径，这条路径称为“均衡路径”(equilibriumpath)。相对该纳什均衡，其他路径称为非均衡路径(out-of-equilibriumpath)。如图2-16中的房地产博弈中65子博弈完美均衡博弈的路径A

不开发

B开发(0，1)是纳什均衡（不开发，{开发，开发}）的均衡路径，相对此纳什均衡，其他路径为非均衡路径。纳什均衡只要求在均衡路径的决策结上是最优的。不开发开发不开发开发(0,1)(0,0)图2-16房地产开发博弈ABB(-3,-3)(1,0)开发不开发66子博弈完美均衡在每一个子博弈上给出纳什均衡意味着，构成子博弈纳什均衡的战略不仅在均衡路径的决策结上是最优的，同时在非均衡路径的决策结上也是最优的。对于有限完美信息博弈，前面介绍的逆推归纳法得出的纳什均衡即是子博弈精炼纳什均衡。不开发开发不开发开发(0,1)(0,0)图2-16房地产开发博弈ABB(-3,-3)(1,0)开发不开发67一些说明逆推归纳法实质上是以“所有参与人是理性的”是所有参与人的共同知识。但对参与人数较多且博弈阶段数较多时，上述假设在实际中将会受到怀疑。请看图2-17的“蜈蚣博弈”

（1,…,1）（1/2,…,1/2）（1/i,…,1/i）（1/n,…,1/n）（2,…,2）……图2-17蜈蚣博弈DDDD1A2AAA68一些说明若使用逆推归纳法，可以预测所有参与人都将选择A。当n很大时，上述预测很值得怀疑。考虑参与人1...（1,…,1）（1/2,…,1/2）（1/i,…,1/i）（1/n,…,1/n）（2,…,2）……图2-17蜈蚣博弈DDDD1A2AAA69一些说明由此类问题及其他问