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

1、第 三 章 完全信息动态博弈 3.1 动态博弈的表示法和特点 1.定 义 与 博 弈树 博弈的展开式所包含的信息和内容: 参与人的集合,记为i=1,2, n,用N代表虚拟 的参与人“自然”; 行动的次序, 即谁在什么时候行动; 参与人的行动空间,即轮到某参与人行动时, 他从该时刻的纯策略空间中选取什么策略; 当参与人作出他们的行动决策时,他所他所 观测到 或他所了解到的信息,即他在此时 获得的信息 集合; 参与人的得益(支付或效用), 它们是已 知行动的函数; 在任何外生事件的概率分布。 例 房地产开发博弈 有两个房地产开发商(分别为参与人1,记为 A和参与人2,记为B) 在某地开发房地产,

2、但该 地的房地产需求状况是不确定的, 假定该博弈 的行动顺序如下:(1) 开发商1先行动, 选择开 发或不开发;(2) 在1决策后,“ 自然”选择需求 的大小;(3) 开发商2在 观测到1的决策和市场 的需求后, 再决定开发 或不开发。( 如 下 图) 房 地 产 开 发 博 弈 A N N B B B B 开 发 不 开 发 需 求 大 需 求 小 需 求 大 需 求 小 开 发 不开发 开发 不开发 开发 不开发 开发 不开发 (4,4) (8,0) (-3,-3) (1,0) (0,8) (0,0) (0,1) (0,0) 单 位:百万元 hA(1) hN(1) hN(2) hB(1)

3、hB(2) hB(3) hB(4) h表示信息集 上述博弈树给出了有限博弈的几乎所有信息。 博 弈 树 必 须 满 足 下 列 规 则： (1)每一个结(node) 至多有一个其他结直接位 于 它的前面; (2)在博弈中没有一条路径可以使决策集与自身 相连; (3) 每一个结是唯一初始结的后续结, 即博弈树 必须有初始结; (4) 每个博弈树“正好”只有一个初始结(多于 一个 可以用“ 自 然”连接。 不允许出现的情况：不允许出现的情况： 由以上规则，对于博弈树中的每一个终点结， 我们，完全可以确定从初始结到终点 结的路 径，同时也展示了博弈的动态过程。 信息集:博弈树上的所有决策集分割成不同

4、的信 息集， 我们用hH来表示这个信息。如果 一个信息集包含 结x,我们就可以将该信息集 记为h(x), 如果一个信息 集只包含一个结,这 是最简的情况。我们主要关心的 是一个信息 集包含不止一个结, 假设x与xh(x), 则恰 好拥有信息h(x) 并正在选择自己行动的参与 人其实对自己究竟是处于x还界x是不确定的。 要 求： 如 果xh(x), 则x与x 应 该由同 一 个参与人采取行动，且可以选择的策略空 间 相同：A(x)=A(x), 由此可以将信息集h上 的 行动集记 为A(h)。 如果博弈树的所有信息集都是单结的, 则称该 博弈为完美(perfect)息 博弈。(无虚线连接), 而完

5、全(complete)信息博弈是指得益函数和纯 策略空间均为博弈各方的共同知识。完全信息 可以是完美的也可以是不完美的。 3.2 展开型博弈的策略与均衡展开型博弈的策略与均衡 一、 行 为 策 略 在策略型博弈中, 参与人的策略是进行博 弈的计划( 或打算)的详细集合, 而在展 开型博弈中 参与人的策略必须确定在该 参与人的每一个决 策集上 所 采 取 的 行 动,又 结 与 信 息 集 紧 密 相 连, 对 于 参 与 人i,基于信息hi的行动的 的全体记汉A(hi),如果令Hi表示参与人i的信息 集 的集合,则Ai= A(hi)就是参与人i的所有行 动 的集合。参与人i的一个纯策略是从Hi

6、到Ai的一 个映射si:对每一个hiAi,si(h i)Ai,所有这些 si的全体记为Si,即的的纯策略空间Si,由此: Si= A(hi) hi H i hi H i 例 参与人2有两个策略集,相应地也有两个信息集 A(h2(1)=A(h2(2)=左,右 1 2 2 1 1 1 1 上 上 下 下 左 右 左 右 右 A B A B C D C D h2(1) h2(2) h1(1) h1(2) h1(3) 其中H2=h2(1),h2(2);参与人2的纯策略空间为: S2=(A(h2(1),Ah2(2)=(左,右)(左,右) =(左,左),(左,右),(右,左),(右,右),其中纯策略 (左

7、,左)表明:当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) hiHi 展开型博弈中纯策略是由信息集与行动集展开型博弈中纯策略是由信息集与行动集 定义 的的( 与静态博弈不同,静态博弈中采取纯 策略与 采取某行动是一个意思)。 纯策略组合纯策略组合(剖面剖面profile) 是由参与人各自是由参与人各自 的纯策 略空间中的任一纯策略构成的组 合，

8、在任一纯 策略组合s下，总可以从 初始结开始，沿着博弈树的某条路径 (path), 达到s相应的终点结。 有一个事 实非常重要：s中有些信息集在博弈 树 的这条路径上，我们称这些信息集是s的的 路 径(path), 当然也可能存在s中某些信 息集不在 此路径上。 定义了纯策略的得益函数后，我们就可以定义 展 开型博弈的Nash 均衡； 定义 策略组合s*=(s 1*,si*,sn*)是展开型 博弈的 一个Nash均衡，如果对每一个i,si*最大化ui(si,s-i*): 即 s i*arg max ui(si*,s-i*),对任一i 策略型博弈的混合策略实际上是纯策略空间上 的 概率分布，因此

9、展开型博弈中参与人 i的混 合策略也 可以看作是其纯策略空间 Si上的任一 概率分布。 “ 参与人的每一个特定的纯策略si相当于一 本指导说明书，书中每一页表示到了一 个特定的信息集hi,在 该页上告诉i 如何 行动。许多的si 相当于许多的说 明书， Si表示这些说明书的全体。混合策略相当 于i 以一定的概率分布随机地抽取一本说 明书” (Luce F(f) 表 示摊牌;M表示对抗;P表示 放弃。 该博弈有唯一的Nash均衡(1,2)=(1/3(Rr)+2/2(Rf), 2/3(M)+1/3(P),它与信念体系一起构成序贯均衡。 习 题 1.写出下列博弈的策略型表示: (1) (2) 1 2

10、 2 U D L R L R (2,1) (0,0) (-1,1) (3,2) 1 2 2 U D L R L R (2,1) (0,0) (-1,1) (3,2) (3) N 1 1 2 2 1/3 2/3 Y1 z1 x1 w1 (2,6) (5,6) a2 b2 a2 b2 (9,0) (0,3) (9,5) (0,3) 3.3 子 博 弈 与 子 博 弈 完 美 Nash 均衡在原则上适用所有的博弈,但对于预 测 参与人的行为来说,Nash均衡可能并不是 一个 合理的预测, 如房地产博弈: A B B 开 不 开 不 开 不 (-3,-3) (1,0) (0,1) (0,0) 的 策

11、略 式 表 示 为: ( 开, 开) ( 开, 不) ( 不, 开) ( 不, 不) 开 -3,-3 -3,-3 1,0 1,0 不 0,1 0,0 0,1 0,0 参 与 人B 参 与 人A 由 由 画画 线线 法法 可可 得得 三三 个个 纯纯 策策 略略Nash 均均 衡衡: ( 不 开 发,( 开 发, 开 发) ( 开开 发发,( 不不 开开 发发, 不不 开开 发发) ( 开 发,( 不 开 发, 开 发) 但中B的策略是不合理的,这个威胁是不可置 信的;中B的策略(不开发,不开发)也不合理, 因为若A不开发,B显然应该开发; 只有是一 个合理的均衡。个合理的均衡。 2.3.1 子

12、 博 弈 定 义 一 个 展 开 式 博 弈 的 子 博 弈G 由 一 个 决 策 结x 和 所 有 该 决 策 结 的 后继结T(x)( 包 括终点结0 组 成, 它 满 足 下 列 条 件:x 是 一 个 单 点 信 息 结即h(x)=x;对于所有的 xT(x), 如果xh(x), 则xT(x) 。 例 房 地 产 博 弈 A B B 开 开 不 不 开 不 开 不 有子博弈: 和子博弈: X X B B x X 开开 不 不 开开 不 不 1 2 2 U D L R L R 无(真)子博弈 1 2 2 3 3 3 3 U D L R L R C D C D C D C D 参与人2 的信

13、息集不能作为子博 弈的初始结, 否则将导致3的信 息被分割。 3.3.2 子 博 弈 完 美 (精练)动 态 博 弈 定义 展开式博弈的略 组s*=(s1*,si*,sn*) 是一个 子博弈完美(精练)Nash 均衡, 如果满 足:(1) 它 是原博弈的Nash 均衡;(2) 它在每一 个子博弈上 给出Nash 均衡。 混合策略的子博弈完美Nash 均衡可类似定 义。 简单地说: 子博弈完美Nash 均衡要 求均衡策略 的行为规则在每一个信息集 上都是最优的(包括均衡路径和非均衡路 径)。 定 义 展开型博弈的一个策略组合称为子 博弈 完美Nash 均衡，如果对于该博弈均衡，如果对于该博弈 的

14、每一个子 博弈，该策略组合都是 Nash 均衡。 例 泽尔腾 (Selten) 1 2 (2,2) (3,1) (0,0) U D L R L R U 2,2 2,2 D 3,1 0,0 该博弈有两个Nash 均衡： （U，R）和（D，L) 但Nash 均衡(U,R) 从动态博弈的观点来看是不合 理的,因为它依赖于参与人2取R这一“空头威 胁”。 3.3.3 逆向归纳法 逆向归纳法包括以几个步骤: 从博弈树的终点结出发, 追踪到紧接着它的前 面的结; 在步骤的中到达的每一个基本结上,通过对 该决策结出发到达的每一个终点结上参与人 得到的得益求最佳行动; 在步骤中检验过每一个基本决策结中 所引起

15、的所有非最优枝删去; ? 如达到树根,则中止,否则回到(1) ? 对每一个参与人,将该参与人在每一个决 策 结上的最优策略一起收集起来就构成 了最佳 策略。 例用逆向归纳法求下列博弈的子博弈完美 Nash 均衡： 1 2 2 1 L R A B C D E F (2,0) (1,1) (0,1/2) (3,1) (2,2) h1 h1 h2 h2 解为(R,E),(B,D) 定理 在一个具有完美信息的有限博弈中,使用逆 向归纳法所选择的策略组合总是Nash 均衡。 承诺行动与子博弈完美均衡承诺行动与子博弈完美均衡 例 法律的要胁诉讼(设原告为P, 被告为D) P D P (0,0) 不指控 指

16、控(提出要求) 拒绝 接受 起诉 放弃 (sc,s) (x -c-p,- x -d) (-c,0) 其中指控成本为c 如果决定指控,P 要求D支付s0 以“私了”,P 的 起诉成本为d,如 果P以概率 赢 得 x, 则xrD/2,若银行 同意到期后再收回 ,连本带利将得到2R(RD) 。 1 2 2 1 2 2 Y N Y N Y N Y N Y N Y N (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,

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

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

19、11单位相 当于t=1时的2(11)单位,如果参与人1在 t=1时出价1x1=2(11),参与人2会接受, 因此,子博弈完美的唯一结果为: x=12(11) 类似地: T=4时的子博弈完美Nash均衡的结果是: x=12(11(12) T=5时的子博弈完美的结果是: x=12(11(12(11) 当 1=2=0时,x=1,当2=0时仍为x=1, 但当1=0,20时结果为x=12,如果 1=2=1(即双方都有无限的耐心)那么 当T=1,3,5,时结果为x=1; 当T=2,4,6,时结果为x=0(后动优势) 定定 理理 (Rubinstein,1982), 在无限期讨价还价博弈在无限期讨价还价博弈

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

21、期的 2(11M),故1可在t2期出价x1=12(11M), 因为从t2期能得到的最大份额一定与从 t期开始的 博弈完全相同,故我们有: x1=M=12(11M) 解得 M=(12)/112),且结果是唯的. 3.6 动态博弈分析的问题和扩展 3.6.1 逆推归纳法的问题 例 1 2 3 n A A A A D D D D (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

22、,则0.9 0.314,较小的 概率可能动摇1取A的决心。 19 例 例 1 2 1 2 1 A1 A2 A3 A4 A5 D1 D2 D3 D4 D5 (1,0) (0,1) (3,0) (2,4) (6,3) (5,5) 这是一个两人轮流行动的博弈,如果使用后退归纳 法,则解宣布在每一个决策结上行动的参与人应采 取行动Di,(i=15)。这个解是否令人信服? 例 从子博弈完美是由后退归纳法引出的这一 事实，可知子博弈完美均衡其实后退归纳 解 的推广。由于子博弈完美的范围更宽广，因 此引起争议的内容更多一些。如下博弈： 1 2 3 1 1 L R L R F G F G F G （6,0,6) (8,6,8) (0,0,0) (7,10,7) (7,10,7) (0,0,0) 最后阶段1与是 否能够“协调”成 功 对2的策略有影响 逆推归纳法更大的问题是对参与人的理性要求 太高,不仅要求所有的博弈方都有高度的理性, 不允许犯如何错误,而且要求所有的博弈方相 互了解和相信其他参与人的理性,对理性有相 同的理解 。 例 犯错误的可能: 1 1 L R M N S T 2 (2,0) (0,3) 该博弈的子博弈完美 Nash均衡是(L,T); N. 但如果1“ 犯错误” 而选R,将会如何? 3.6.2 颤抖手均衡和顺推归纳法 一 颤 抖手均衡 例 下 列