第2章完全信息动态博弈

博弈论与信息经济学中央财经大学周德清2.完全信息动态博弈2.1博弈扩展式表述2.2扩展式表述博弈的纳什均衡2.3子博弈精炼纳什均衡2.3.1引言2.3.2子博弈精炼纳什均衡2.3.3用逆向归纳法求解子博弈精炼的纳什均衡2.3.4承诺行动与子博弈精炼纳什均衡2.3.5逆向归纳法与子博弈精炼均衡存在的问题2.4子博弈精炼纳什均衡应用举例2.4.1斯坦克尔伯格(Stackelberg)寡头竞争模型2.4.2宏观经济政策的动态一致性2.4.3中国过去的财政包干制度：中央与地方的关系2.4.4工会与雇主之间的博弈2.4.5轮流出价的讨价还价模型2.5重复博弈和无名氏定理2.5.1有限次重复博弈：连锁店悖论2.5.2无限次重复博弈和无名氏定理2.5.3参与人不固定时的重复博弈2.5.4不确定环境下的重复博弈博弈论与信息经济学回主目录博弈论与信息经济学中央财经大学周德清2.1博弈扩展式表述n人有限战略博弈的扩展式表述可以用博弈树来表示参与人集合：i=1,…,n,此外，我们将用N代表虚拟参与人“自然”；参与人的行动顺序（theorderofmoves）：谁在什么时候行动；参与人的行动空间（actionset）：在每次行动时，参与人有些什么选择；参与人的信息集（informationset）：每次行动时，参与人知道些什么；参与人的支付函数：在行动结束之后，每个参与人得到些什么（支付是所有行动的函数）；外生事件（即自然的选择）的概率分布。博弈的扩展式表述包括以下要素：博弈论与信息经济学中央财经大学周德清博弈树的基本结构包括：枝(branches)和信息集(informationsets)A开发不开发NNBBBB开发开发开发开发开发不开发不开发不开发大大小小（1/2）（1/2）（1/2）(0，0)(0，1)(0，0)(4，4)(8，0)(-3，-3)(1，0)(0，8)图2.1房地产开发博弈1.结(nodes):包括决策结和终点结两类。一般用X表示所有结的集合，x∈X表示某个特定的结。用“”表示定义在X上的顺序关系（precedencerelation）：xx’’意味着“x在x”之前”。假定“”满足传递性（transitive）和反对称性(asymmetric)。x'x''x图2.2博弈树不允许的情况(a)(b)博弈论与信息经济学中央财经大学周德清2.枝(branches):枝是一个决策结到它的直接后续结的连线(有时用箭头表述)，每一个枝代表参与人的一个行动选择。3.信息集(informationsets):博弈树上的所有决策结分割成不同的信息集。每一个信息集是决策结集合的一个子集，该子集包括所有满足下列的决策结：(1)每一个决策结都是同一参与人的决策结(2)：该参与人知道博弈进入该集合的某个决策结，但不知道自己究竟处在哪一个决策结。A开发不开发NNBBBB开发开发开发开发开发不开发不开发不开发大大小小（1/2）（1/2）（1/2）(0，0)(0，1)(0，0)(4，4)(8，0)(-3，-3)(1，0)(0，8)图2.3房地产开发博弈Ⅱ图2.1和2.3的区别在于B的信息集不同博弈论与信息经济学中央财经大学周德清房地产开发博弈的另一种可能情况是，B知道自然选择，但不知道A的选择只包括一个决策信息集称为单结信息集博弈树所有的信息都是单结的，该博弈称为完美信息博弈A开发不开发NNBBBB开发开发开发开发开发不开发不开发不开发大大小小（1/2）（1/2）（1/2）(0，0)(0，1)(0，0)(4，4)(8，0)(-3，-3)(1，0)(0，8)图2.4房地产开发博弈ⅢN大不开发AABBBB开发开发开发开发开发不开发不开发不开发开发开发不开发（1/2）不开发（1/2）(0，0)(0，1)(0，0)(4，4)(8，0)(-3，-3)(1，0)(0，8)图2.5房地产开发博弈Ⅰ：另一种表述不完美信息集博弈论与信息经济学中央财经大学周德清N大不开发AABBBB开发开发开发开发开发不开发不开发不开发开发开发不开发小（1/2）不开发(0，0)(0，1)(0，0)(4，4)(8，0)(-3，-3)(1，0)(0，8)图2.6房地产开发博弈Ⅲ：第二种表述N大不开发BBAAAA开发开发开发开发开发不开发不开发不开发开发开发不开发不开发(0，0)(0，1)(0，0)(4，4)(8，0)(-3，-3)(1，0)(0，8)图2.7房地产开发博弈Ⅲ：第三种表述博弈论与信息经济学中央财经大学周德清有了信息集的概念，扩展式表述也可以用于表述表示静态博弈一般假定博弈满足“完美回忆”(perfectrecall)的要求。完美回忆是与信息集有关的一个概念，指的是没有参与人会忘记自己以前知道的事情，所有参与人都知道自己以前的选择。(-8，-8)(0，-10)(-10，0)(-1，-1)坦白抵赖坦白抵赖坦白抵赖AB(-8，-8)(0，-10)(-10，0)(-1，-1)坦白抵赖坦白抵赖坦白抵赖BA图2.8囚徒困境扩展式表述博弈论与信息经济学中央财经大学周德清图2.3参与人不具完美记忆的两个例子12UUUDDLLLLRRR1112(a)(b)N参与人1不能区别三个行动序列(U，R)，(D，L)和(D，R)参与人1不具有完美回忆参与人1也不能满足有完美回忆的要求1博弈论与信息经济学中央财经大学周德清如果(1)(和属于同一信息集)，(2)x∈P(x1)(x是x1的前列集)(3)i(x)=i(x1)(x和x1都是i的决策结)，那么，存在一个(可能是X本身)，满足：(1)，(2)(3)在x点为到达x1的行动与在点为到达x2的行动是一样的。1UDDUx1x''x2x1图2.10完美记忆的要求)(12xhx2x1x''x)(''xhx)(2''xpx''x2.2扩展式表述博弈的纳什均衡为了说明如何从扩展式表述构造战略式表述，考虑房地产开发博弈的例子。为了排除上述两种情况以确保博弈具有完美回忆的特征，要求：博弈论与信息经济学中央财经大学周德清假定在博弈开始前自然就选择了“低需求”，并且已成为参与人的共同信息；开发商A先决策，开商B在观测到A的选择后决策。那么，博弈扩展式表述如图。这是一个完美信息博弈(每个人的信息集都是单结的。)-3，-3-3，-31，01，00，10，00，10，0ABB开发开发开发不开发不开发不开发(0，1)(0，0)(-3，-3)(1，0)图2.11房地产开发博弈Ⅳ表2.1是这个博弈的战略式表述开发商B{开发，开发}{开发，不开发}{不开发，开发}{不开发，不开发}开发开发商A不开发令Hi为第i个参与人的信息集的集合，为其行动集合，其中A(hi)是在信息集hi的行动集合。参与人i的一个纯战略是从信息集集合Hi到行动集合Ai的一个映射。一个参与人可选择的纯战略的总数#Si等于：)(iHhihAAii)(iHhihASiiiHihihA))((#博弈论与信息经济学中央财经大学周德清在扩展式表述博弈，所有n个参与人的一个纯战略组合决定了博弈树上的一个路径。每一个战略组合决定了一个支付向量。战略组合是扩展式博弈的一个纳什均衡，如果对于所有的i,最大化，即*s*is),(*iiissuissusiiSsiiii),,(maxarg**在扩展式表述博弈中，混合战略被称为“行为战略”。行为战略是指参与人在每一个信息集上随机地选择行动。尽管扩展式博弈和战略式博弈有完全相同的纯战略空间，战略式博弈的混合战略集合不同于扩展式博弈的行为战略集合。我们也可以从行为战略构造出混合战略博弈论与信息经济学中央财经大学周德清行为战略令混合战略为特别地，122LLURRDh''h),,,(242322212图2.12，参与人2有四个纯战略：{L，L}，{L，R}，{R，L}和{R,R}.)41,41,41,41(2)21,0,0,21(2对应于行为战略。一个行为战略可能对应多个混合战略，反之不成立如果一个扩展式博弈有有限个信息集，每个信息集上参与人有有限个行动选择，我们说这个博弈是有限博弈。21111{(,),(,)}2222b博弈论与信息经济学中央财经大学周德清定理(Zermelo,1913;Kuhn,1983):一个有限完美信息博弈有一个纯战略纳什均衡。可以使用动态规划的逆向归纳法(backwardinduction)证明上述定理。上述归纳法过程不适用于无限博弈和不完美信息博弈。逆向归纳法的逻辑仍可用来找出不完美信息博弈的均衡解2，22，23，10，021LURD(0，0)(2，2)(3，1)参与人2LRU参与人1D图2.13图2.13的战略式表述我们可以用图2.13所示的扩展式博弈(表2.2是这个博弈的长表述)说明这个定理博弈论与信息经济学中央财经大学周德清2.3子博弈精炼纳什均衡泽尔腾(Selten)的“子博弈精炼纳什均衡”是纳什均衡概念的第一个最重要的改进子博弈精炼纳什均衡是完全信息动态博弈解的基本概念2.3.1引言用上一节房地产开发博弈的例子来说明上述论点ABB开发开发开发不开发不开发不开发(0，1)(0，0)(-3，-3)(1，0)图2.14房地产开发博弈容易看出，只有(开发，{不开发，开发})是一个合理的均衡，因为构成这个均衡的每个参与人的均衡战略都是合理的。事实上，(开发，{不开发，开发})是这个博弈的唯一的子博弈精炼纳什均衡。博弈论与信息经济学中央财经大学周德清2.3.2子博弈精炼纳什均衡定义：一个扩展式博弈的子博弈G由一个决策结x和所有该决策后续结T(x)(包括终点结)组成，它满足下列条件(1)x是一个单结信息集，即h(x)={x};(2)对于所有的x1∈T(x),如果x’’∈h(x1),那么x’’∈T(x)。解释：条件(1)说的是一个子博弈必须从一个单结信息集开始。ABB开发开发开发不开发不开发不开发(0，1)(0，0)(-3，-3)(1，0)图2.15房地产开发博弈x'x(-3，-3)(1，0)开发不开发开发不开发x'x(0，1)(0，0)(b)子博弈Ⅰ(b)子博弈Ⅱ(a)原博弈博弈论与信息经济学中央财经大学周德清解释：条件(2)说的是，子博弈的信息集和支付向量都直接继承自原博弈。122LLURRDx'xZ4Z1Z2Z3122LLURRD3lrlllrrr3图2.16囚徒困境的扩展式表述图2.17下面给出“子博弈精炼纳什均衡”的正式定义博弈论与信息经济学中央财经大学周德清定义：扩展式博弈的战略组合是一个子博弈精炼纳什均衡，如果：(1)它是原博弈的纳什均衡；(2)它在每一个子博弈上给出的纳什均衡。2.3.3用逆向归纳法求解子博弈精炼的纳什均衡假定博弈有两个阶段，第一阶段参与人1行动，第二阶段参与人2行动，并且2在行动前观测到1的选择。当博弈进入第二阶段，给定参与人1在第一阶段的选择a1∈A1，参与人2面临的问题是：),,,,(***1*nissss),(21222aaMaxuAa参与人1在第一阶段面临的问题是：))(,(121111aRaMaxuAa令上述问题的最优解为。那么，这个博弈的子博弈精炼纳什均衡为，均衡结果为*1a))(,(*12*1aRa))(,(12*1aRa博弈论与信息经济学中央财经大学周德清图2.18是一个三阶段完美信息博弈均衡结果是参与人1在第一阶段选择U结束博弈，参与1得到2个单位的支付，参与人2得到0个单位的支付。有些非完美信息博弈也可以运用逆向归纳法求解。21U’LUD’RD(2,0)(1,1)(3,0)(0,2)图2.18用逆向归纳法求解子博弈精炼纳什均衡的过程，实质是重复剔除劣战略过程在扩展式博弈上的扩展：21U’LUD’RD(2,2)(3,1)图2.19不完全信息博弈(2,-2)(-2,2)(-2,2)(2,-2)R’L’R’L’12博弈论与信息经济学中央财经大学周德清2.3.4承诺行动与子博弈精炼纳什均衡“承诺行动”(commitment)----为改变博弈结果而采取的措施将承诺行动纳入模型的一个