博弈论第三章完全信息动态博弈

第三章完全信息动态博弈

3.1动态博弈的表示法和特点定义与博弈树

博弈的展开式所包含的信息和内容:⑴参与人的集合,记为i=1,2,…n,用N代表虚拟的参与人“自然”;⑵行动的次序,即谁在什么时候行动;⑶参与人的行动空间,即轮到某参与人行动时,他从该时刻的纯策略空间中选取什么策略;⑷当参与人作出他们的行动决策时,他所观测到或他所了解到的信息,即他在此时获得的信息集合;⑸参与人的得益(支付或效用),它们是已知行动的函数;⑹在任何外生事件的概率分布。例房地产开发博弈有两个房地产开发商(分别为参与人1,记为A和参与人2,记为B)在某地开发房地产,但该地的房地产需求状况是不确定的,假定该博弈的行动顺序如下:(1)开发商1先行动,选择开发或不开发;(2)在1决策后,“自然”选择需求的大小;(3)开发商2在观测到1的决策和市场的需求后,再决定开发或不开发。(如下图)

房地产开发博弈ANNBBBB开发不开发需求大需求小需求大需求小开发不开发开发不开发开发不开发开发不开发

(4,4)(8,0)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)

单位:百万元hA(1)hN(1)hN(2)hB(1)hB(2)hB(3)hB(4)h表示信息集

上述博弈树给出了有限博弈的几乎所有信息。博弈树必须满足下列规则：每一个结(node)至多有一个其他结直接位于它的前面;在博弈中没有一条路径可以使决策集与自身相连;

每一个结是唯一初始结的后续结,即博弈树必须有初始结;

每个博弈树“正好”只有一个初始结(多于一个可以用“自然”连接。

不允许出现的情况：

由以上规则，对于博弈树中的每一个终点结，我们，完全可以确定从初始结到终点结的路径，同时也展示了博弈的动态过程。

信息集:博弈树上的所有决策集分割成不同的信息集，我们用h∈H来表示这个信息。如果一个信息集包含结x,我们就可以将该信息集记为h(x),如果一个信息集只包含一个结,这是最简的情况。我们主要关心的是一个信息集包含不止一个结,假设x与x′∈h(x),则恰好拥有信息h(x)并正在选择自己行动的参与人其实对自己究竟是处于x还界x′是不确定的。

要求：如果x′∈h(x),则x与x′应该由同一个参与人采取行动，且可以选择的策略空间相同：A(x)=A(x′),由此可以将信息集h上的行动集记为A(h)。如果博弈树的所有信息集都是单结的,则称该博弈为完美(perfect)息博弈。(无虚线连接),而完全(complete)信息博弈是指得益函数和纯策略空间均为博弈各方的共同知识。完全信息可以是完美的也可以是不完美的。3.2展开型博弈的策略与均衡一、行为策略在策略型博弈中,参与人的策略是进行博弈的计划(或打算)的详细集合,而在展开型博弈中参与人的策略必须确定在该参与人的每一个决策集上所采取的行动,又结与信息集紧密相连,对于参与人i,基于信息hi的行动的的全体记汉A(hi),如果令Hi表示参与人i的信息集的集合,则Ai=∪A(hi)就是参与人i的所有行动的集合。参与人i的一个纯策略是从Hi到Ai的一个映射si:对每一个hi∈Ai,si(hi)∈Ai,所有这些si的全体记为Si,即的的纯策略空间Si,由此:

Si=×A(hi)hi∈Hihi∈Hi例参与人2有两个策略集,相应地也有两个信息集

A(h2(1))=A(h2(2))={左,右}1221111上下左右左右ABABCDCDh2(1)h2(2)h1(1)h1(2)h1(3)其中H2={h2(1),h2(2)};参与人2的纯策略空间为:S2=(A(h2(1)),Ah2(2))={(左,右)×(左,右)}={(左,左),(左,右),(右,左),(右,右)},其中纯策略(左,左)表明:当1取“上”时,2取“左”;当1取“下”时,2取“左”,……参与人1有三个信息集H1={hi(i),i=1,2,3},1的纯策略空间为:S1=A(h1(1))×A(h1(2))×A(h1(3))={(上,下)×(A,B)×(C,D)},共8种纯策略。一般地,参与人I的纯策略空间的纯策略数目为:

＃Si=Π＃(A(hi))hi∈Hi

展开型博弈中纯策略是由信息集与行动集定义的(与静态博弈不同,静态博弈中采取纯策略与采取某行动是一个意思)。

纯策略组合(剖面profile)是由参与人各自的纯策略空间中的任一纯策略构成的组合，在任一纯策略组合s下，总可以从初始结开始，沿着博弈树的某条路径(path),达到s相应的终点结。有一个事实非常重要：s中有些信息集在博弈树的这条路径上，我们称这些信息集是s的路径(path),当然也可能存在s中某些信息集不在此路径上。

定义了纯策略的得益函数后，我们就可以定义展开型博弈的Nash均衡；定义策略组合s*=(s1*,…si*,…sn*)是展开型博弈的一个Nash均衡，如果对每一个i,si*最大化ui(si,s-i*):即si*∈argmaxui(si*,s-i*),对任一i

策略型博弈的混合策略实际上是纯策略空间上的概率分布，因此展开型博弈中参与人i的混合策略也可以看作是其纯策略空间Si上的任一概率分布。

“参与人的每一个特定的纯策略si相当于一本指导说明书，书中每一页表示到了一个特定的信息集hi,在该页上告诉i如何行动。许多的si

相当于许多的说明书，Si表示这些说明书的全体。混合策略相当于i以一定的概率分布随机地抽取一本说明书”(Luce&Raiff)。

参与人i的行为策略bi

定义为：

bi∈×hi∈Hi△(A(hi))

其中△表示某集合是的概率分布。行为策略的Nash集合是这样一个策略组合，它使得没有一个参与人可以通过不同的使用策略而增加自己的得益。注意：行为策略是在A(hi)上随机化，而混合策略则是在Si(即A(hi)的乘积空间)上的随机化定理(Kuhn,1953)在完美回忆博弈中，混合策略与行为策略是等价的。完美回忆指没有参与人会忘记以前知道的信息。例下列展开型博弈不具备完美回忆：1221111ABLRLRCDCDCDCD现在重新考虑上述房地产开发博弈，以解释信息集的概念，其中开发商B是在知道A的选择和自然的选择之后决策的。如果B在决策时并不知道自然的选择，则有博弈树：ANNBBBB开发不开发大(1/2)小(1/2)大(1/2)小(1/2)

开发不开发开发不开发开发不开发开发不开发hBhBhA′另一种情况就则B知道自然的选择,但不知道A的选择,这时博弈树如下:ANNBBBB开发不开发大小大小开发不开发开发不开发开发不开发开发不开发(-5,-5)(0,-8)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)上述房地产开发博弈还有另一种表示：NABBABB大(1/2)小(1/2)开发不开发开发不开发开发不开发开发不开发开发不开发开发不开发有了信息集的概念,展开式表示也可以用来表示静态博弈,如“囚徒的困境”博弈可以表示为:122坦白不坦白

坦白不坦白坦白不坦白(-5,-5)(0,-8)(-8,0)(-1,-1)或者:211

坦白不坦白坦白不坦白坦白不坦白(-5,-5)(0,-8)(-8,0)(-1,-1)注意:得益向量的次序与参与人决策的顺序一致。同样地,展开型博弈也可以用策略式来表示,如展开型博弈:122TBLRLR(2,2)(4,0)((1,0)(3,1)可以表示为:LRT2,24,0B1,03,1参与人1参与人2展开型博弈:122TBLRlr(2,2)(4,0)(1,0)(3,1)可以表示成:LllrRlRrT2,22,24,04,0B1,03,11,03,1参与人2参与人1同样地,展开型博弈也可以用策略式来表示:

例摊牌博弈N1122黑红

[0.5][0.5]加注r摊牌f摊牌F加注R放弃P对抗M放弃P对抗M(-1,1)(1,-1)(1,-1)(-2,2)(1,-1)(2,-2)<1><1>

<1/4><3/4><1/3><2/3><0><1>y2x2摊牌博弈的策略空间分别为:S1={(R,F)×(r,f)}={Rr,Rf,Fr,Ff},S2={M,P}可表示为策略型MPRr0,01,-1Rf0.5,-0.50,6Fr–0.5,0.51,-1Ff0,0

0,0参与人1参与人2注:u1(Rf,M)=2×1/2+(-1)×1/2=0,5u2((Rf,M)=-2×1/2+1×1/2=-0.5其中R(r)表示加注;F(f)表示摊牌;M表示对抗;P表示放弃。该博弈有唯一的Nash均衡(σ1,σ2)=(1/3(Rr)+2/2(Rf),2/3(M)+1/3(P)),它与信念体系一起构成序贯均衡。

习题1.写出下列博弈的策略型表示:(1)(2)122UDLRLR(2,1)(0,0)(-1,1)(3,2)122UDLRLR(2,1)(0,0)(-1,1)(3,2)(3)N11221/32/3Y1z1x1w1(2,6)(5,6)a2b2a2b2(9,0)(0,3)(9,5)(0,3)3.3子博弈与子博弈完美Nash均衡在原则上适用所有的博弈,但对于预测参与人的行为来说,Nash均衡可能并不是一个合理的预测,如房地产博弈:ABB开不开不开不(-3,-3)(1,0)(0,1)(0,0)的策略式表示为:(开,开)(开,不)(不,开)(不,不)开-3,-3-3,-31,0

1,0

不0,10,00,10,0参与人B参与人A

由画线法可得三个纯策略Nash均衡:①(不开发,(开发,开发))②(开发,(不开发,不开发))③(开发,(不开发,开发))

但①中B的策略是不合理的,这个威胁是不可置信的;②中B的策略(不开发,不开发)也不合理,因为若A不开发,B显然应该开发;只有③是一个合理的均衡。2.3.1子博弈定义一个展开式博弈的子博弈G由一个决策结x和所有该决策结的后继结T(x)(包括终点结0组成,它满足下列条件:⑴x是一个单点信息结即h(x)={x};⑵对于所有的x′∈T(x),如果x″∈h(x′),则x″∈T(x)。例房地产博弈ABB开不开不开不有子博弈Ⅰ:和子博弈Ⅱ:XX′BBxX′开不开不122UDLRLR无(真)子博弈1223333UDLRLRCDCDCDCD参与人2的信息集不能作为子博弈的初始结,否则将导致3的信息被分割。3.3.2子博弈完美(精练)动态博弈定义展开式博弈的略组s*=(s1*,…si*,…sn*)是一个子博弈完美(精练)Nash均衡,如果满足:(1)它是原博弈的Nash均衡;(2)它在每一个子博弈上给出Nash均衡。

混合策略的子博弈完美Nash均衡可类似定义。简单地说:子博弈完美Nash均衡要求均衡策略的行为规则在每一个信息集上都是最优的(包括均衡路径和非均衡路径)。定义展开型博弈的一个策略组合称为子博弈完美Nash均衡，如果对于该博弈的每一个子博弈，该策略组合都是Nash均衡。例泽尔腾

(Selten)12(2,2)(3,1)(0,0)UDLRLRU2,22,2D3,10,0该博弈有两个Nash均衡：（U，R）和（D，L)但Nash均衡(U,R)从动态博弈的观点来看是不合理的,因为它依赖于参与人2取R这一“空头威胁”。

3.3.3逆向归纳法逆向归纳法包括以几个步骤:⑴从博弈树的终点结出发,追踪到紧接着它的前面的结;⑵在步骤⑴的中到达的每一个基本结上,通过对该决策结出发到达的每一个终点结上参与人得到的得益求最佳行动;⑶在步骤⑵中检验过每一个基本决策结中所引起的所有非最优枝删去;

如达到树根,则中止,否则回到(1)

对每一个参与人,将该参与人在每一个决策结上的最优策略一起收集起来就构成了最佳策略。例用逆向归纳法求下列博弈的子博弈完美Nash均衡：1221LRABCDEF(2,0)(1,1)(0,1/2)(3,1)(2,2)h1h1′h2h2′解为{(R,E),(B,D)}

定理在一个具有完美信息的有限博弈中,使用逆向归纳法所选择的策略组合总是Nash均衡。

承诺行动与子博弈完美均衡例法律的要胁诉讼(设原告为P,被告为D)PDP(0,0)不指控指控(提出要求)拒绝接受起诉放弃(s－c,－s)(γx-c-p,-γx-d)(-c,0)

其中指控成本为c

如果决定指控,P

要求D支付s>0以“私了”,P的起诉成本为d,如果P以概率γ赢得x,则γx<p。3.4几个经典的动态博弈模型3.4.1Stackelberg寡头竞争模型该模型可以看作是子博弈完美Nash均衡的最早版本。其中企业1(称为领头企业)先选择产量q1∈Q1=[0,∞),企业2(称为尾随企业)观测到q1后选择自己的产量q2∈Q2=[0,∞),这时企业2的策应该是从Q1到Q2一个数:S2:Q1→Q2,而企业1的策略就是简单地选择产量q1纯策略均衡结果是产出向量(q1,s(q1)),支付函数为:ui(q1,s2(q1)),由于产量是一个连续变量,故不能作出博弈树。

假定逆需求函数为P=a－q1－q2,两个企业有相同的不变单位成本c≥0,则支付(利润)函数为:ui(q1,q2)=qi(P－c),i=1,2我们可以用逆向归纳法求解这个博弈的子博弈完美Nash均衡。假定q1已经选定,企业2的问题是:

maxu2(q1,q2)=q2(a－q1－q2－c)

最优化一阶条件为:s2(q1)=(1/2)(a－q1－c)

因为企业1预测到企业2将根据s2(q1)选择q2,企业1在第一阶段的问题是:Maxu1(q1,s2(q1))=q1(a－q1－s2(q1)－c)

解一阶条件得:q1*=0.5(a－c)

将q1*代入s2(q1)得:q2*=s2(q1*)=0.25(a－c).(先动优势)委托-代理(Principle-Agents)理论1.无不确定性的情形122(0,0)委托不委托接受拒绝努力偷懒(0,0)(12,2)(7,1)2.有不确定性但可监督的情形12NN2委托不委托接受拒绝努力偷懒高产低产高产低产[0.9][0.1][0.1][0.9](0,0)(0,0)(16,2)(6,2)(18,1)(8,1)银行挤兑模型:设两个投资者各具某银行存款D,银行将这两笔存款用于一长期项目,如果在项目到期之前银行被迫抽回资金,仅可挽回2r,其中D>r>D/2,若银行同意到期后再收回,连本带利将得到2R(R>D)。122122YNYNYNYNYNYN(r,r)(D,2r－D)(2r－D,D)(R,R)(2R－D,D)(D,2R－D)(R,R)Y:提取;N:不提日期1为投资到期之前;日期2为之后3.4.2讨价还价博弈(Rubinstein,1982)

假定两个人分一块蛋糕,参与人1先出价,参与人2可以选择接受或拒绝;如果1接受博弈结束,蛋糕按1的方案分配;如果1拒绝,1再出价;如此直下去直到一个参与人的出价被另一个人接收为止。这是一个无限期完美信息博弈，参与人1在时期1，3，5，…出价,参与人2在时期2,4,6,…出价。用x表示1的份额,1－x表示2的份额,x1和(1－x1)分别是1出价时1和2的份额,x2和(1－x2)分别表示2出价时参与人1和参与人2的份额。假定参与人1和参与人2的贴现因子分别为δ1和δ2,则如果在时期t博弈结束,参与人1和参与人2的支付贴现值分别是u1=δ1xi

和u2=δ2(1－xi)t-1t-1如果博弈是有限期的,可以使用逆向归纳法求解子博弈完美Nash均衡(T为期限)设T=2,参与人2出价,如果他提出x2=0,1只有接受,因为他巳无出价机会,由于2在T=2时得到1单位相当于在t=1时得到δ2单位,所以1在t=1时出价1－x1≥δ2时2会接受,这时子博弈完美Nash均衡的结果是(1－δ2,δ2),设T=3,设1出价x=1,因为１在T=2时的1单位等于t=2时的δ1单位,如果2在t=2时出价x2=δ1,1212

x1AR,出x2AR,出x3(x1,1－x1)(δ1x2,δ2(1－x2))参与人1会接受,参与人2在t=2时的1－δ1单位相当于t=1时的δ2(1－δ1)单位,如果参与人1在t=1时出价1－x1=δ2(1－δ1),参与人2会接受,因此,子博弈完美的唯一结果为:

x=1－δ2(1－δ1)…………类似地:T=4时的子博弈完美Nash均衡的结果是:

x=1－δ2(1－δ1(1－δ2))T=5时的子博弈完美的结果是:

x=1－δ2(1－δ1(1－δ2(1－δ1)))当δ1=δ2=0时,x=1,当δ2=0时仍为x=1,

但当δ1=0,δ2>0时结果为x=1－δ2,如果δ1=δ2=1(即双方都有无限的耐心)那么当T=1,3,5,…时结果为x=1;当T=2,4,6,…时结果为x=0(后动优势)定理

(Rubinstein,1982),在无限期讨价还价博弈中,唯一的子博弈完美Nash均衡的结果是:

x*=(1－δ2)/(1－δ1δ2)(如果δ1=δ2=δ,x*=1/(1+δ)无限期讨价还价的子博弈完美Nash均衡的结果决定于参与人的贴现因子(耐心程度)证明:T=+∞,博弈无最后阶段,但参与人1出价的任何一个阶段开始的子博弈等价于从t=1开始的整个博弈,我们可以应用有限阶段逆向归纳法寻找子博弈完美均衡.假定t≥3,1出价,1能得到的最大份额是M1,对1而言t期的M1等价于t－1期的δ1M,故2知道在t-1期的任何x2≥δ1M的出价将被1所接受,因此2出价x2=δ1M,自得1－δ1M;又对2而言t－1期的1－δ1M等价于t－2期的δ2(1－δ1M),故1可在t－2期出价x1=1－δ2(1－δ1M),因为从t－2期能得到的最大份额一定与从t期开始的博弈完全相同,故我们有:

x1=M=1－δ2(1－δ1M)解得M=(1－δ2)/1－δ1δ2),且结果是唯－的.3.6动态博弈分析的问题和扩展3.6.1逆推归纳法的问题例123nAAAADDDD(1,1,…1)(1/2,1/2,…1/2)(1/3,1/3,…1/3)(1/n,1/n,…1/n)(2,2,…2)

如果参与人的数目n比较小,才能预测到最后“共同富裕”的结果(2,2,…2)；当n相当大时,情况就会发生变化:设每个参与人取A的概率为0.9,n=20,则0.9≈0.314,较小的概率可能动摇1取A的决心。19例12121A1A2A3A4A5D1D2D3D4D5

(1,0)(0,1)(3,0)(2,4)(6,3)(5,5)这是一个两人轮流行动的博弈,如果使用后退归纳法,则解宣布在每一个决策结上行动的参与人应采取行动Di,(i=1…5)。这个解是否令人信服?例从子博弈完美是由后退归纳法引出的这一事实，可知子博弈完美均衡其实后退归纳解的推广。由于子博弈完美的范围更宽广，因此引起争议的内容更多一些。如下博弈：12311LRLRFGFGFG（6,0,6)(8,6,8)(0,0,0)(7,10,7)(7,10,7)(0,0,0