第五章 完全信息动态博弈

125第五章完全信息动态博弈本章将引入博弈顺序于博弈模型之中，并对不同博弈顺序对博弈均衡的影响作出评估。正如我们在第三章中所指出，在“动态”的博弈模型中，博弈中局中人的“出招”顺序对于均衡形成来说是十分重要的。所谓“动态”博弈模型，就是指在博弈中局中人的“出招”顺序对均衡的形成有实质性影响的博弈模型。本章将表明，影响动态博弈的均衡形成除了局中人的博弈顺序要素外，还有博弈的时间长短这一重要因素，即有限次和无限次（重复）博弈可能会有完全不同的均衡。在本章还暂不考虑信息不完全对博弈均衡的影响，因而所表达的博弈是完全信息动态博弈。本章将要指出的重要观点是，当我们在博弈中纳入决策的顺序结构时，纳什均衡作为模型的预测是不能令人满意的，并引入子博弈精炼纳什均衡这一概念来克服这一不足。这种新概念的引入实际上是将纳什均衡概念进一步精致化，消除了一些不可信的均衡，这也是一种有限度解决纳什均衡多重性的方案（尽管还不是终极性的）。5.1完全信息动态博弈：概念与定义我们在第三章已经对动态博弈概念作了一种粗略的介绍，这里，我们对完全信息动态博弈的精确定义及相关概念给出完整的说明。首先，我们通过图5.1给出的一个完全信息动态博弈的扩展式表示，来为即将给出的一些概念作出直观上的理解。1ab2cde11图5.1一个完全信息动态博弈模型让我们看看图5.1，在第三章中我们已给出了一些相关的概念，如决策结、枝、终点结、支付向量等等，我们称第一个行动选择对应的决策结为“初始结”。与那里给出2f11ghijklmn2PQRSTU(2,1)(3,1)(2,4)(5,1)(0,6)(7,1)(2,4)vw(1,2)(0,3)126的例子不同的一点是，图5.1中存在无限个“枝”，即该博弈是一个无限次的动态博弈。在每一个决策结处，对应一个局中人，他（她）在该决策结处进行决策。即在每一个决策结处相应存在一个对应的局中人和一个对应的行动空间。对于每一个终点结，我们都可以找到一条由相互连贯的许多“枝”构成的“路径”（Path），使得该终点结是该“路径”的一个“末端”。如终点结P是路径“adi”的一个末端，其中adi指由从枝a经枝d到达枝i的路径。我们发现，每一个终点结对应的这种“路径”是唯一的。所以，我们可以用这种“路径”来代表终点结。但是，沿由枝a、c、g、v、……和a、c、g、w、……构成的“路径”却没有终点结，但图中标明，若博弈沿路径“acgv……”进行下去，局中人1和2的支付分别为“1”和“2”，若博弈沿路径“acgw……”进行下去，局中人1和2可分别获得支付“0”和“3”。从图5.1中还可看出，局中人1在博弈中总是能记住他自己过去所进行的决策，局中人2也是如此，同时，局中人2不仅能在博弈进行中总能记住自己过去所做出的决策，而且还不会忘记自己过去所知道的事，我们称这种情况为局中人具有“完美回忆”。这就是在“完全信息”基础上所进一步作出的假设。当然，“完美信息”假定还要求局中人还知道在他自己进行决策之前由别的局中人所做出的决策。与图5.1的情形形成对比的是，图5.2给出的扩展式博弈就不具有“完美回忆”。(0,0)(1,0)(1,2)(2,1)(3,1)(4,2)(5,1)(6,1)(4,2)(2,5)(3,2)图5.2不具完美回忆的动态博弈下面给出“信息集”的定义。在图5.2中，局中人1在由决策结A和B构成的“信息集”处忘记了自己过去的决策，此时局中人1不知道自己到底位于A还是B处，我们称A和B构成一个“信息集”。在每一个决策结上，对应该决策结有一个唯一的局中人在此进行决策，决定其行动选择。假定每一个决策结处有一个唯一的行动空间，即由在该处进行决策的局中人进行行动选122111AB2C2222222(3,1)(2,0)(2,1)(0,2)(7,0)D127择时所可能选择的所有行动构成的集合。如果一个信息集中含有两个或两个以上的决策结，假定其中所有决策结上对应的行动空间都是相同的，否则局中人凭此就可以知道自己在哪一个决策结上，而这与该信息集的定义相矛盾。在由决策结C和D构成的另一信息集处，局中人2忘记了自己知道的事，即局中人1在博弈开始所进行的决策。如果每一个信息集都是单结的，则称博弈为“完美信息博弈”（gameofperfectinformation），即每一个信息集都含有唯一一个决策结。5.1.1完全信息动态博弈的定义在以上直观性说明的基础上，我们可以通过运用较为抽象的术语给出完全信息动态博弈的定义。其实，按照以下的方式，我们先给出动态（或扩展式）博弈的一般性定义（不局限于完全信息的动态博弈），然后在其基础上对信息完全性作出规定就获得完全信息动态博弈的相应定义。首先，我们借用图论中的概念对“博弈树”作出说明。设有可数性集合iVV，其中Ii，I为一可数指标集。构造另一集合IjiVvvvvvvAjijiji,,,,),(。一个未定向的“图”指由集合V与A的一个子集A~的一个构成[1]。称)(IiVvi为图的一个“顶点”（vertex）或“结点”（node），称),(~),(IjiAvvji为一段（联结“顶点”iv和jv的）弧（arc）或“枝”（branch）或“边”（edge）。一个连接结点1v与mv的（开的）“路径”（path）指一个结点序列1v，2v，…，mv满足：)(IiVvi且),(,),,(),,(13221mmvvvvvv都在集合A~中[2]。当1v=mv（且2m）时，我们就得到一个“圈”（cycle）或“闭路径”。图5.3中给出了两个“图”的例子。1v2v3v1v2v3v4v4v5v(a)(b)图5.3两个图的例子在(a)中，),,,(4321vvvvV，),(),,(),,(),,(~53433121vvvvvvvvA；在(b)中，V与(a)中相同，而),(),,(~3221vvvvA。当且仅当任意两结点由唯一的一条“路径”连接时，称一个图为一个“树”（tree）。图5.4中给出“树”和“非树”图的例子。1281v1v2v3v2v3v1v4v5v4v5v6v4v6v2v3v5v6v7v(b)(c)8v9v10v(a)图5.4(a)中的图是“树”、(b)和(c)中的图不是“树”显然，“树”中是没有圈的且任意两个结点间是“连通的”。现假设图T是一个“树”，并设r为T中的一个结点，定义r为图的一个“根”（root）。我们现在可以将树中所有的“枝”进行“定向”，使得它们都是从“根”向外“定向”的。对于A~中任意的),)(,(Ijivvji，我们知道从r到jv有唯一的一条路径。如果该路径通过结点iv，则枝),(jivv的方向为jivv或就记为),(jivv；否则，从r到iv的唯一路径[3]必经过jv，若不然，就不难找到两条从r到iv的路径了，这违反了“树”的定义。因此，在这种情形可将枝),(jivv方向定向为ijvv或记为),(ijvv。按照这种记法，我们知道r有如下性质：即r与另一不同结点iv所构成的枝的方向必为),(ivr，即从r只有“发出”（outgoing）的“枝”。相反，当从r只有发出的枝时，r必为“根”。当结点z与树中任意其它结点iv构成的枝的方向为),(zvi时，称z为“叶”（leaves）或终点结（terminalnodes），记)(TZZ为由树T的所有终点结所构成的集合。图5.5给出一个树的例子。r1v2v3v4v5v图5.5一个树的例子，其中r为根，543,,)(vvvTZ129注意，以上关于图及树的概念定义中不排除V（及A和A~）中有无限个元素的情形。我们在今后在不引起混乱的情况下可省略去表示枝的方向的箭头。有了上述概念准备，我们就可以正式给出n人动态博弈（扩展式表述的博弈）的定义。定义5.1一个动态博弈（扩展式表述的博弈）G被定义为同时满足下列条件的一个构成：(i)n,,2,1是局中人集合，n为自然数；(ii)T为一个树，称为博弈树，其中的根被称为初始结；(iii)T的非终点结集合T/Z(T)被分成n+1个不相交的子集nPPPP,,,,210。0P中的元素被称为“机会”（chance）或“自然”(nature)结；对于每个i，iP中的元素被称为局中人i的决策结；(iv)对于0P中的每个结点，从它向外发出的任一枝上被赋予了一个概率分布密度值；(v)对所有的i，iP又被分成)(iK个互不相交的集合，称为“信息集”（informationsets），记为iiKiiUUU)(21,,,，满足：对于每个)(,,2,1iKj，有：(a)从ijU中每个结点（)(,,2,1iKj）发出的枝的数目相同，且ijU中不同结点发出的枝的集合之间存在一个给定的1-1对应；(b)从根或初始结出发到终点结的每一个（定向的）路径至多通过每一个ijU一次；(vi)对每个终点结)(TZz，对应于一个n维支付向量))(,),(),(()(21zgzgzgzgn，其中)(zgi被称为局中人i的支付),,1(ni。(vii)上述从(i)到(vi)的完全描述是所有局中人之间的共同知识。定义5.1在描述上较为抽象，但其好处是概念较为一般和严密。我们可以这样来直观理解其含义：每一个信息集中的结点是一个局中人进行决策的位置，称为决策结；博弈从树T的根开始。按归纳法表述，假定博弈已进行到非终点结v处。若v是局中人i（即iPv）的决策结，则局中人i根据v所在的信息集选择从v发出的一个枝。由此，存在一条从初始结到某一终点结Z的唯一路径，博弈到Z处终止且每个局中人i获得支付)(zgi),,1(ni；或者博弈从初始结开始沿着唯一一条路径进行下去但并无终点结，但仍然规定局中人i获得支付ig),,1(ni；前者称为“有限”次进行的动态博弈，后者称为“无限次”进行的动态博弈。“自然”的选择通常表示局中人面临的不同的不确定性，是一种外生的条件。当不存在这种不确定性时，我们就得到完全信息博弈。定义5.2在定义5.1中，当0P为空集时，称G为完全信息动态博弈（Completeinformationdynamicgame）。定义5.3如果定义5.1中每个信息集))(,,1(iKjUij中只有一个元素（称为单结130信息集），则称G为完美信息博弈（Perfectinformationgame）。完全信息博弈中没有外生的不确定性，而完美信息博弈则不存在任何的不确定性（事前和事后的不确定性皆不存在）。5.1.2完全信息动态博弈中的战略概念局中人i的一个纯战略指对于局中人i在每一个信息集上所进行行动选择的一个规定。对局中人i来说，同一个信息集上的不同决策结应该在行动选择的范围上是不能有差别的，否则局中人就可以识别出他在同一信息集的哪一个决策结上，而这与信息集本来的含义相矛盾。对于局中人i，我们用)(ijiUA表示其信息集与行动空间的对应，即)(ijiUA是局中人i在信息集ijU上所有决策结所能进行选择的行动的集合，称为局中人i在信息集ijU上的行动空间。记)(,,1iKjUIiji，即iI为局中人i的信息集空间；定义映射)()(:ijiijiiUAUSS。则有定义5.3称iS为局中人i的一个纯战略。显然，局中人i的一个纯战略必是集合jijiiUAA)(中的一个元素，反之亦然。定义5.4称集合jijiiUAA)(为局中人i的纯战略空间。类似于战略式表述，我们可以有纯战略组合),,(1nsss及纯战略组合空间iiAS等概念。同样，在完全信息动态博弈中我们也有类似于完全信息静态博弈中的纯战略纳什均衡定义，这里不再给出。与静态博弈不同，在动态博弈情形，“战略”不等同于“行动”。在动态博弈中，在每一个信息集上有一个行动选择的问题，而一个局中人在由他进行行动选择的所有信息集所进行的行动选择构成他的一个战略，即战略是行动选择的一个谱系，一个战略规定了局中人在由他进行选择的所有信息集上所要选择的行动，即局中人在博弈开始之前所制定出的一个“相机行动计划”，它表明“如果……发生，我将选择