35博弈论-第四章

第四草気全信息动态博弈更为现实的考虑是将静态博弈动态化，动态化后，纳什均衡这一概念是否仍然有效呢？答案是部分有效的。如果不存在动态不一致，那么纳什均衡在完全信息动态博弈中仍不失为一个有用的均衡概念，但纳什均衡概念本身并不能保证不出现动态不一致，为了克服这一点在纳什均衡的基础上生产了所谓子博弈完美均衡。而这一章，我们将围绕这子博弈完美均衡来展开。第一节完美信息与完全但不完美信息完全信息动态博弈可以分为两类，即完美信息与完全但不完美信息。所谓的完美信息博弈，是指博弈中的后行动者始终能够观察到前行动者的行动，因而动态博弈中不存在参与者同时行动这样的情况。而完全但不完美信息博弈，则指动态博弈中，至少存在两个参与者同时行动的情况，因而“后行动者”无法观察到“前行动者”的行动。我们不妨用两个例子来加以说明。例4.1动态囚徒困境囚徒1图4-1动态囚徒困境例4.2取消管制政府1和2进，进进，退退进退，退图4-2取消管制与图4-2完全等价的表示方法见图 4-3

政府图4-3取消管制定义4.1完美信息动态博弈就是不存在同时行动的完全信息动态博弈。显然，运用策略式来描述动态博弈会非常不便，特别是当信息不完全时更是如此，为了更简便地描述动态博弈，我们将引入一种新的博弈表达式扩展式。第二节动态博弈的扩展式我们把博弈中所有从开始到结束的行动序列称为全历史（Terminalhistory），而用参与者函数来表示在每一个全历史上，在博弈进行到某个阶段时谁来行动。因而要完整地描述一个动态博弈，必须具备四个要素：（1）参与者集合；（2）全历史集合；（3）参与者函数；（4）偏好。如果我们把全历史表示成一个行动序列（a1,a2,…,aK）（K为自然数，当K时，就表示无穷动态博弈），那么（a1,a2,…,am），其中mk,就称为全历史（a1,a2,…,aK）的子历史（Subhistory）。当m<K时，（a1,a2,…,am)就是全历史(a1,a2,…,aK)的真子历史(Propersubhistory)。显然，在博弈开始前的历史是一个空历史(Emptyhistory)，因而空历史是所有全历史的真子历史。今后我们将用来表示空历史，用h来表示子历史，而用H来表示全历史的集合，而P则表示参与者函数。定义4.2完全信息动态博弈的扩展式为{N,H,P,u}，其中N为参与者集合，H为博弈的全历史集合，即H={(a1,a2,…,aK)}，其中K为博弈从开始到结束依次发生的行动次数，行动序列中的每一个a都为向量。P为参与者函数，即P(h)={i:i€N},hH。u为收益函数，表示博弈参与者的偏好。与博弈的基本式相比，扩展式没有直接给出博弈参与者的行动集合，原因在于扩展式已经隐含地定义了各参与者在行动时有些什么样的行动可供选择，根据全历史和参与者函数，能很容易地得到各参与者的行动集合。在历史h之后，参与者P（h）所有可能的行动集合定义为Ap（h）（h）=｛ap（h）:（h,a）是一个子历史，ap（h）是行动向量a的第P（h）个元素｝例如，在取消管制博弈中，根据全历史集合H和参与者函数p（）=政府，P（取消）=｛1,2｝，可知A（）=｛维持，取消｝，即政府有两个行动一一维持和取消；Ai（取消）=｛进，退｝和A2（取消）=｛进，退｝，即两个企业各有两个行动——进和退。需要注意的是，在完美信息下，扩展式有三个地方与完全但不完美信息不同。首先，历史h由行动向量序列变为行动序列，例如，在取消管制中，历史（取消， ［进，进］）是一个向量序列，因为企业 1和企业2是同时行动的，如果改成企业2后行动，那么就变成（取消，进，进)，也就是由一个向量序列便成了单值序列，意思也完全不一样了。其次，参与者函数P(h)都是单点映射，对应着唯一一位参与者。最后，就是行动集合A可以省略下标，因为A(h)={a:(h,a)是一个子历史}。现在我们将例4.1和例4.2的扩展式表达如下：例4.1动态囚徒困境的扩展式为{N,H,P,u}，其中参与者集合：囚徒1和囚徒2，N={1,2}。全历史集合：招供为C，沉默为S，H={(C,C),(C,S),(S,C),(S,S)}。(3)参与者函数：P()=1，P(C)=P(S)=2。(4)偏好：对于囚徒1而言，最好的历史是(C,S)，其次为(C,C)，然后为(S,S)，最倒霉的历史为(S,C)。对囚徒2而言，最好的历史是(S,C)，其次为(C,C)，第三为(S,S),最差为(C,S)。例4.2取消管制的扩展式为 {N,H,P,u}，其中(1)参与者集合：政府，企业1和企业2，N={1,2,3}。全历史集合：维持为C,取消为D，进入为E,退出为Q,那么全历史集合H={(C),(D,[E,E]),(D,[E,Q]),(D,[Q,E]),(D,[Q,Q])。参与者函数：P()=1，P(D)={2,3}。(4)偏好：对于政府而言，根据五个历史对应的社会福利进行排序，对于企业1和企业2而言，则为五个历史对应的利润排序。例4.3进入博弈在一个垄断行业，已经存在一个垄断企业，我们将其称为在位者，现在有一个新的企业决定是否进入该行业，我们将其称为挑战者。挑战者首先行动，决定进入(E)或是退出(Q),如果挑战者进入，那么在位者将决定是与挑战者和平共处 (A)还是战斗(F)。其博弈的扩展式{N,H,P,u}如下：参与者集合：挑战者和在位者， N={1,2}。全历史集合：H={(Q),(E,A),(E,F)}。参与者函数：P()=1，P(E)=2。偏好：如果挑战者退出，那么挑战者得到 0的利润，而在位者得到3的利润；如果挑战者进入，那么如在位者选择战斗，有可能两败俱伤，挑战者的利润为-1，在位者的利润为0，如果在位者选择和平共处，那么挑战者得2的利润，而在位者得1的利润。因而，挑战者偏好历史(E,A)>(Q)>(E,F)，而在位者偏好历史(Q)>(E,A)>(E,F)。其扩展式也可用博弈树来加以描述，如图4-4所示。ALF ©3)(2,1)(-1,0)图4-4进入博弈例4.4蜈蚣博弈该博弈有两位参与者。当参与者1行动时，他将决定是结束博弈

还是继续，如果结束博弈，那么参与者 1得2,参与者2得0;如果继续博弈，那么轮到参与者2决定是结束博弈还是继续，如果结束博弈，那么参与者1得3,参与者2得1;如果继续博弈，那么轮到参与者1行动，如果他选择左(L)，那么参与者1得1，参与者2得2，如果他选择右(R)，那么两人都得0。该博弈的扩展式其博弈的扩展式 {N,H,P,u}如下：(1)参与者集合：N={1,2}。全历史集合：继续为C,结束为D,H={(D),(C,D),(C,C丄)，(C,C,R)}。参与者函数： P()=1，P(C)=2，P(C,C)=1。偏好：如果全历史为(D)，那么参与者1得2,而参与者2得0;如果全历史为(C,D)，那么参与者1得3,参与者2得1;如果全历史为(C,C,L)，那么参与者1得1，参与者2得2；如果全历史为(C,C,R)，那么两人都得0。参与者1最偏好历史(C,D)，而参与者2最偏好历史(C,C,L)。该扩展式如图4-5所示。C DC D(1,2)(3,1)(0,0)图4-5蜈蚣博弈(2,0)第三节策略和结果策略是“万全之策”，而不再是单纯的行动，如何理解这句话呢?1、动态囚徒困境中囚徒2的策略表4-1囚徒2的四个策略假如囚徒1选择招供假如囚徒1选择沉默策略1选择招供选择招供策略2选择招供选择沉默策略3选择沉默选择招供策略4选择沉默选择沉默2、蜈蚣博弈中参与者1的策略关键是理解DL，DR也是策略。所以说，策略是一个“万全之策”。定义4.3对于博弈{N,H,p,u}，参与者P(h)的一个策略Sp(h)(h)就是一个函数，它将每一个可能的历史h映射成行动空间Ap(h)(h)中的一个行动ap(h)。上述策略的定义实际上就是指当历史进行到某个阶段时，当轮到参与者i行动时，规定了他如何行动。例如，在蜈蚣博弈中，对于参与者1而言，一个策略就是当历史为空历史时，规定了参与者1如何行动，当历史为(C,C)时，规定了参与者1又如何行动，因而DL和DR就是参与者1的策略，至于历史(C,C)会不会发生那是另外一个问题，策略所要求的就是一旦出现了某个历史我应该如何做，而不能出现不知所措的情况。通过上面的说明我们看到，有什么样的策略组合就会有什么样的历史，但历史并不等于策略。为此，我们引入结果函数，即对于任意sS，存在某个hH，使得0(s)=h。参与者的收益函数u就是定义在结果上的函数。例如，在蜈蚣博弈中，可知参与者1有四个策略CL、CR、DL和DR，参与者2有两个策略C和D，因而策略组合有8个，其相应的结果函数为0(CL,C)=(CCL)u1(0(CL,C))=1和u2(0(CL,C))=2；0(CR,C)=(CCR)u1(0(CR,C))=0和u2(0(CR,C))=0；0(Cx,D)=(CD)u1(0(Cx,D))=3和u2(0(Cx,D))=1；0(Dx,x)=(D) u1(0(Dx,x))=2和u2(0(Dx,x))=0。其中x代表任意行动。上面的结果函数给了我们两点启示：一是，要得到全历史实际上只需行动计划就可以了，不一定需要去考察所谓

的“完全之策”，例如，0(D,x)=D=O(Dx,x)是一样的，这样做的好处是能够简化分析，但在观念上，我们必须牢记策略是“万全之策” 。二是，图4-5的蜈蚣博弈实际上与图4-6中的博弈完全等价，这就更为直观地指出了策略DL和DR的性质。实际上，汤普森(Thompson,1952)论证了对于任意两个等价的扩展式博弈，至少存在 4种转换方式，通过转换，可以把复杂的扩展式博弈变成最简单的形式去分析。(0,0)(2,0)图4-6与蜈蚣博弈等价的博弈(1,2)(0,0)(2,0)图4-6与蜈蚣博弈等价的博弈(1,2)(2,0)第四节纳什均衡与子博弈完美均衡一、纳什均衡纳什均衡概念的核心就在于，每一个参与者的策略都是给定其他参与者策略下的最优反应，并且对任意参与者成立。即便博弈是动态的，这一点也不会改变。那么，将静态博弈中的纳什均衡概念运用到动态博弈中应该是一个不错的思路，尽管这样做可能存在问题。定义4.4扩展式博弈{N,H,P,u}的纳什均衡是一个策略组合s*S，使得对任一参与者iN，siSi，不等式ui(O(si*,si*))ui(O(si,si*))成立。由于有什么样的策略就会有什么样的结果，因而收益函数又可直接看作是策略的函数，这样动态博弈{N,H,P,u}接看作是策略的函数，这样动态博弈{N,H,P,u}就有了与之等价的策略式博弈定义4.5G={N,S,u}称为完全信息动态博弈 {N,H,P,u}的策略式（或基本式），其中S就是动态博弈 {N,H,P,u}定义的策略空间，并且u(s)=u(0(s))图4-7完美动态博弈图4-7所示的完美动态博弈的策略式是什么呢?其策略式G={N,S,u}如下：

参与者集合：N={1,2};策略集合：S={{L,R},{C1C2,Cid2,diC2,did2}};偏好:Ui(L,ciC2)=2,U2(L,ciC2)=1,其他依次类推。相对应的博弈矩阵如图4-8所示。参与者2L参与者1RL参与者1R2,12,14,24,25,23,35,23,3C1C2 Cid2 diC2 did2图4-8动态博弈的策略式根据纳什均衡的定义，易知该动态博弈存在两个纳什均衡：(R,Cid2)和(L,did2)0对于均衡(R,Cid2)，只要我们稍加考察，就会发现这个纳什均衡含有不合理的因素，在现实中根本不会出现，原因就在于参与者2在历史(L)“威胁”出ci是不可置信的，因为出di要比出ci优(2>1)。之所以出现这种情况，是由于当参与者1的策略为R时，历史进行到L的可能性为零，因此参与者2在历史L下无论采取什么行动都不会对他的最终收益造成影响。这意味着，纳什均衡这个概念对参与者 2在不可能发生的历史L下如何选择并未做出规定，参与者2就有可能乱选(像一个非理性的人一样)，而纳什均衡本身假设参与者是理性的，这就造成参与者2的策略是动态不一致的(Dynamicinconsistent)。一个动态不一致的策略肯定不会是一个最优的策略。我们也可以这样来理解参与者2的行动，参与者2之所以威胁当参与者1出L时，他要选择ci，目的在于通过威胁使参与者1选择有利于参与者2的R，因为在参与者1选择R下，参与者2通过选择d2,能得到3的报酬，明显好于当参与者1选L，参与者2选di时的收益2。但我们要问的是，如果参与者1不顾参与者2的威胁而选择了L，参与者2可能会出&吗？在参与者2为理性是公共信息的条件下，参与者2选择c1的报酬为1，而选择d1的报酬为2。由于d1要优于c1，因而参与者1没有理由相信参与者2会实施他的威胁，也就是说，参与者2的策略Cid2是一个不可置信的威胁。如果威胁成真，Cld2就是一个动态不一致的策略，因为参与者2事前是理性的，但在博弈进行到(L)时，他却成了一个非理性的人(选择了 Ci，而不是di)。出现上述问题的原因，在于一个纳什均衡只要求在博弈的总体上，参与者的策略须为均衡，而对博弈进行到某个部分时是否仍为均衡没有要求，这就可能导致总体和局部的冲突，产生不合理的结果。要消除动态博弈中的不可置信威胁，就需一个比纳什均衡更强的均衡概念。它不仅在整个博弈中是均衡的，而且在局部也是均衡的；不但在现在是均衡的，在将来也应是均衡的。只有满足这个要求，博弈的参与者才能实现策略的动态一致性，这就导致了子博弈完美均衡概念的产生。二、子博弈完美均衡最早由经济学家塞尔腾(Selten)在1965年提出。定义4.6完全信息动态博弈{N,H,P,u}的一个子博弈就是一个完整的动态博弈(h){Ns,Hs,Ps,us}，其具有如下特征：(1)参与者集合NsN；(2)给定真子历史h，对于任意行动序列 h*,(h,h*)H，而Hs={h*}；(3)Ps=P和us=u例，如图4-9图4-9存在着5个子博弈图4-9所示博弈存在5个子博弈：r(DE),r(DF),r(D),r(C)和原博弈r(N,H,P,u)o

图4-10则给出了不是子博弈的情况。 在图4-10中，虚线围起来的部分不是子博弈因为它不构成一个完整的扩展式博弈定义4.7在扩展式博弈 {N,H,P,u}中，如果一个策略组合s*在所有该博弈的子博弈（h）{Ns，Hs，Ps，Us}中都是纳什均衡，那么我们就称策略组合S*为子博弈完美均衡，即对任意参与者iPs和任意Si，uui(Oh(s*))ui(Oh(si,si*))成立。其中h为任意真子历史，Oh(•)为子博弈(h)的结果函数。根据定义4.7，可知子博弈完美均衡一定是纳什均衡，但反之不成立。那么对于一个完全信息动态博弈我们如何去求解它的子博弈完美均衡呢？一个一般的方法就是所谓的逆推法(BackwardInduction)。定义4.8所谓逆推法是指如下程序：第一步，从扩展式博弈的终点开始，以找到该博弈的每一个最后子博弈(它不再包含任何其他更小的子博弈)，然后求出纳什均衡，并计算出相应的收益。第二步，将每一个最后子博弈的起点变成结束点，将计算出的每一个最后子博弈在纳什均衡下的收益写在其下方，我们就获得了一个新的扩展式博弈(或新的博弈树)，称为压缩的扩展式博弈。这样经过一次压缩，就剔除了最后子博弈。第三步，重复第一步和第二步，并重新得到一个压缩式博弈和相应的纳什均衡。这个过程一直进行到最后只剩下唯一一个子博弈为止，这时在逆推过程中找到的一系列子博弈的纳什均衡组合就是该扩展式博弈的一个完美均衡。第四步，如果在逆推过程中没有遇到多重均衡，那么这个策略组合就是唯一的完美均衡；如果遇到了多重均衡，就需要对子博弈中每一个可能的均衡重复以上步骤，从而得出所有的完美均衡。比如，一个扩展式博弈有两个子博弈分别存在2个和3个纳什均衡，其他子博弈只有1个纳什均衡，那么该博弈就有2X3=6个完美均衡。例，在图4-11所示的小蜈蚣博弈中，如果从正面求解子博弈完美均衡显然非常困难，而用逆推法却非常简单。逆推到最后一个阶段的结果如图4-12(1,0)图4-13小蜈蚣博弈的最后阶段定理4.1存在性定理只要扩展式博弈 {N,H,P,u}是有限的，即参与者有限，行动空间有限，博弈的阶段有限（不是无穷进行下去），那么扩展式博弈r至少存在一个子博弈完美均衡。定理4.2等价性定理{s*}为有限扩展式博弈{N,H,P,u}的所有子博弈完美均衡的集合，{s#}为该扩展式博弈运用逆推法找到的所有子博弈完美均衡的集合，那么{s*}={S#}，即子博弈完美均衡与逆推法是完全等价的。

例4.5—个简单博弈的子博弈完美均衡图4-14一个简单博弈运用逆推法，可得子博弈 (C)的纳什均衡为F和G，子博弈(D)的纳什均衡为H和J，子博弈(E)的纳什均衡为L，由此可得参与者2的4个均衡策略：(FHL)，(FJL)，(GHL)和(GJL)。现在，回到原博弈，寻找原博弈的纳什均衡。分四种情况：(1)给定参与者2的策略(FHL)，参与者1的最优策略为C，因而(C,FHL)为完美均衡。(2)给定参与者2的策略（FJL）,参与者1的最优策略为C,因而（C,FJL）为完美均衡。（3）给定参与者2的策略（GHL），参与者1的最优策略有三个：C,D和E。因而，完美均衡也有三个：（C，GHL），（D，GHL）和（E，GHL）。（4） 给定参与者2的策略（GJL），参与者1的最优策略为：D。因而，完美均衡为：（D，GJL）。综上所述，即该博弈存在6个完美均衡。从上面这个例子，我们可以得出这样一个判断，即如果每一个全历史的收益都不相等,那么扩展式博弈一定存在唯一的子博弈完美均衡。命题4.1在扩展式博弈{N,H,P,u}中,如果每一个全历史对应的参与者的收益都不相等,那么存在唯一的子博弈完美均衡。逆推法虽然在求解完美均衡上非常有效,但也