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

1、第第 三三 章章 完全信息动态博弈完全信息动态博弈 3.1 动态博弈的表示法和特点动态博弈的表示法和特点1.定定 义义 与与 博博 弈树弈树 博弈的展开式所包含的信息和内容博弈的展开式所包含的信息和内容: 参与人的集合参与人的集合,记为记为i=1,2,n,用用N代表虚拟代表虚拟的参与人的参与人“自然自然”; 行动的次序行动的次序, 即谁在什么时候行动即谁在什么时候行动; 参与人的行动空间参与人的行动空间,即轮到某参与人行动时即轮到某参与人行动时,他从该时刻的纯策略空间中选取什么策略他从该时刻的纯策略空间中选取什么策略; 当参与人作出他们的行动决策时当参与人作出他们的行动决策时,他所他所观测到观

2、测到 或他所了解到的信息或他所了解到的信息,即他在此时即他在此时获得的信息获得的信息 集合集合; 参与人的得益参与人的得益(支付或效用支付或效用), 它们是已它们是已知行动的函数知行动的函数; 在任何外生事件的概率分布。在任何外生事件的概率分布。 例例 房地产开发博弈房地产开发博弈有两个房地产开发商有两个房地产开发商(分别为参与人分别为参与人1,记为记为A和参与人和参与人2,记为记为B) 在某地开发房地产在某地开发房地产, 但该但该地的房地产需求状况是不确定的地的房地产需求状况是不确定的, 假定该博弈假定该博弈的行动顺序如下的行动顺序如下:(1) 开发商开发商1先行动先行动, 选择开选择开发或

3、不开发发或不开发;(2)在在1决策后决策后,“ 自然自然”选择需求选择需求的大小的大小;(3)开发商开发商2在在 观测到观测到1的决策和市场的决策和市场的需求后的需求后, 再决定开发再决定开发 或不开发。或不开发。( 如如 下下 图图) 房房 地地 产产 开开 发发 博博 弈弈ANNBBBB 开开 发发 不不 开开 发发 需需 求求 大大 需需 求求 小小 需需 求求 大大 需需 求求 小小 开开 发发 不开发不开发 开发开发 不开发不开发 开发开发 不开发不开发 开发开发 不开发不开发 (4,4) (8,0) (-3,-3) (1,0) (0,8) (0,0) (0,1) (0,0) 单单

4、位位:百万元百万元hA(1)hN(1)hN(2)hB(1)hB(2)hB(3)hB(4)h表示信息集表示信息集 上述博弈树给出了有限博弈的几乎所有信息。上述博弈树给出了有限博弈的几乎所有信息。 博博 弈弈 树树 必必 须须 满满 足足 下下 列列 规规 则：则：(1)每一个结每一个结(node)至多有一个其他结直接位至多有一个其他结直接位于于 它的前面它的前面;(2)在博弈中没有一条路径可以使决策集与自身在博弈中没有一条路径可以使决策集与自身 相连相连;(3) 每一个结是唯一初始结的后续结每一个结是唯一初始结的后续结, 即博弈树即博弈树 必须有初始结必须有初始结;(4) 每个博弈树每个博弈树“

5、正好正好”只有一个初始结只有一个初始结(多于多于一个一个 可以用可以用“ 自自 然然”连接。连接。 不允许出现的情况：不允许出现的情况： 由以上规则，对于博弈树中的每一个终点结，由以上规则，对于博弈树中的每一个终点结，我们，完全可以确定从初始结到终点我们，完全可以确定从初始结到终点 结的路结的路 径，同时也展示了博弈的动态过程。径，同时也展示了博弈的动态过程。 信息集信息集:博弈树上的所有决策集分割成不同的信博弈树上的所有决策集分割成不同的信息集，息集， 我们用我们用hH来表示这个信息。如果来表示这个信息。如果一个信息集包含一个信息集包含 结结x,我们就可以将该信息集我们就可以将该信息集记为记

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

7、完美(perfect)息 博弈。(无虚线连接),而完全(complete)信息博弈是指得益函数和纯策略空间均为博弈各方的共同知识。完全信息可以是完美的也可以是不完美的。3.2 展开型博弈的策略与均衡展开型博弈的策略与均衡一、一、 行行 为为 策策 略略 在策略型博弈中在策略型博弈中, 参与人的策略是进行博参与人的策略是进行博弈的计划弈的计划( 或打算或打算)的详细集合的详细集合, 而在展而在展开型博弈中开型博弈中 参与人的策略必须确定在该参与人的策略必须确定在该参与人的每一个决参与人的每一个决 策集上策集上 所所 采采 取取 的的 行行 动动,又又 结结 与与 信信 息息 集集 紧紧 密密 相

8、相 连连, 对对 于于 参参 与与 人人i,基于信息基于信息hi的行动的的行动的的全体记汉的全体记汉A(hi),如果令如果令Hi表示参与人表示参与人i的信息的信息集集的集合的集合,则则Ai= A(hi)就是参与人就是参与人i的所有行的所有行动动的集合。参与人的集合。参与人i的一个纯策略是从的一个纯策略是从Hi到到Ai的一的一个映射个映射si:对每一个对每一个hiAi,si(hi)Ai,所有这些所有这些si的全体记为的全体记为Si,即的的纯策略空间即的的纯策略空间Si,由此由此: Si= A(hi)hiHihiHi例参与人2有两个策略集,相应地也有两个信息集 A(h2(1)=A(h2(2)=左,

9、右1221111上上下下左左右右左左右右A B A B C D C Dh2(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(h

10、i)hiHi 展开型博弈中纯策略是由信息集与行动集展开型博弈中纯策略是由信息集与行动集定义定义 的的( 与静态博弈不同与静态博弈不同,静态博弈中采取纯静态博弈中采取纯策略与策略与 采取某行动是一个意思采取某行动是一个意思)。 纯策略组合纯策略组合(剖面剖面profile)是由参与人各自是由参与人各自的纯策的纯策 略空间中的任一纯策略构成的组略空间中的任一纯策略构成的组合，在任一纯合，在任一纯 策略组合策略组合s下，总可以从下，总可以从初始结开始，沿着博弈树的某条路径初始结开始，沿着博弈树的某条路径(path), 达到达到s相应的终点结。相应的终点结。 有一个事有一个事实非常重要：实非常重要：s

11、中有些信息集在博弈中有些信息集在博弈 树树的这条路径上，我们称这些信息集是的这条路径上，我们称这些信息集是s的的路路 径径(path), 当然也可能存在当然也可能存在s中某些信中某些信息集不在息集不在 此路径上。此路径上。 定义了纯策略的得益函数后，我们就可以定义 展开型博弈的Nash 均衡； 定义 策略组合s*=(s1*,si*,sn*)是展开型 博弈的一个Nash均衡，如果对每一个i,si*最大化ui(si,s-i*):即 si*arg max ui(si*,s-i*),对任一i 策略型博弈的混合策略实际上是纯策略空间上 的概率分布，因此展开型博弈中参与人i的混 合策略也可以看作是其纯策略

12、空间Si上的任一 概率分布。 “ 参与人的每一个特定的纯策略si相当于一本指导说明书，书中每一页表示到了一个特定的信息集hi,在 该页上告诉i 如何行动。许多的si 相当于许多的说 明书，Si表示这些说明书的全体。混合策略相当于i 以一定的概率分布随机地抽取一本说明书”(Luce & Raiff)。 参与人i的行为策略行为策略bi 定义为： bihiHi(A(hi) 其中 表示某集合是的概率分布。 行 为 策 略 的Nash 集 合 是 这 样 一 个 策 略 组 合， 它 使 得 没 有 一 个 参 与 人 可 以 通 过 不 同 的 使 用策 略 而 增 加 自 己 的 得 益。注

13、意：行为策略是在A(hi)上随机化，而混合策 略则是在Si( 即A(hi) 的乘积 空 间)上的随机化 定 理 (Kuhn,1953) 在完美回忆博弈中，混合 策略与行为策略是等价的。 完美回忆指没有参与人会忘记以前知道的信息。例 下列展开型博弈不具备完美回忆：1221111ABLRLRC D C D C D C D 现在重新考虑上述房地产开发博弈，以解释信 息集的概念，其中开发商B是在知道A的选择 和自然的选择之后决策的。 如果B在决策时并不知道自然的选择，则有博 弈树：ANNBBBB 开 发 不 开 发 大(1/2) 小(1/2) 大(1/2) 小(1/2) 开发 不开发 开发 不开发 开

14、发 不开发 开发 不开发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) 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发

15、发 不不 开开 发发 有了信息集的概念, 展开式表示也可以用来表 示静态博弈, 如“囚徒的困境 ”博弈可以表 示为:122 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白(-5,-5) (0,-8) (-8,0) (-1,-1)或者:211 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白(-5,-5) (0,-8) (-8,0) (-1,-1) 注注 意意: 得得 益益 向向 量量 的的 次次 序序 与与 参参 与与 人人 决决 策策 的的 顺顺 序序 一一 致。致。 同样地,展开型博弈也可以用策略式来表示,

16、如 展开型博弈:122TBL R L R(2,2) (4,0) (1,0) (3,1)可以表示为可以表示为:L RT 2,2 4,0 B 1,0 3,1 参参 与与 人人1 参参 与与 人人2 展 开 型 博 弈:122TBL R l r(2,2) (4,0) (1,0) (3,1)可以表示成可以表示成:Ll lr Rl RrT 2,2 2,2 4,0 4,0 B 1,0 3,1 1,0 3,1 参参 与与 人人2 参参 与与 人人1 同样地,展开型博弈也可以用策略式来表示: 例 摊牌博弈N1122 黑黑 红红 0.5 0.5加注加注r 摊牌摊牌f 摊牌摊牌F 加注加注R放弃放弃P 对抗对抗M

17、 放弃放弃P 对抗对抗M(-1,1) (1,-1)(1,-1) (-2,2) (1,-1) (2,-2) y2 x2 摊 牌 博 弈 的 策 略 空 间 分 别 为:S1=(R,F)(r,f)=Rr,Rf,Fr,Ff,S2=M,P可表示为策略型M PRr 0,0 1,-1Rf 0.5,-0.5 0,6Fr 0.5,0.5 1,-1 Ff 0,0 0,0 参参 与与 人人1 参参 与与 人人2注注:u1(Rf,M)=21/2+(-1)1/2=0,5u2(Rf,M)= -21/2+11/2=-0.5其中其中R(r)表示加注表示加注;F(f)表表示摊牌示摊牌;M表示对抗表示对抗;P表示表示放弃。放弃

18、。该博弈有唯一的Nash均衡(1,2)=(1/3(Rr)+2/2(Rf),2/3(M)+1/3(P),它与信念体系一起构成序贯均衡。 习 题1.写出下列博弈的策略型表示:(1) (2)122U DL R L R(2,1) (0,0) (-1,1) (3,2)122U DL R L R(2,1) (0,0) (-1,1) (3,2)(3)N11221/3 2/3Y1 z1 x1 w1(2,6) (5,6)a2 b2 a2 b2(9,0) (0,3) (9,5) (0,3)3.3 子子 博博 弈弈 与与 子子 博博 弈弈 完完 美美Nash 均衡在原则上适用所有的博弈均衡在原则上适用所有的博弈,但

19、对于预但对于预测测 参与人的行为来说参与人的行为来说,Nash均衡可能并不是均衡可能并不是一个一个 合理的预测合理的预测, 如房地产博弈如房地产博弈:ABB 开开 不不 开开 不不 开开 不不(-3,-3) (1,0) (0,1) (0,0)的的 策策 略略 式式 表表 示示 为为:( 开开, 开开) ( 开开, 不不) ( 不不, 开开) ( 不不, 不不) 开开 -3,-3 -3,-3 1,0 1,0 不不 0,1 0,0 0,1 0,0 参参 与与 人人B 参参 与与 人人A 由由 画画 线线 法法 可可 得得 三三 个个 纯纯 策策 略略Nash 均均 衡衡:( 不不 开开 发发,(

20、开开 发发, 开开 发发)( 开开 发发,( 不不 开开 发发, 不不 开开 发发)( 开开 发发,( 不不 开开 发发, 开开 发发) 但但中中B的策略是不合理的的策略是不合理的,这个威胁是不可置这个威胁是不可置 信的信的;中中B的策略的策略(不开发不开发,不开发不开发)也不合理也不合理, 因为若因为若A不开发不开发,B显然应该开发显然应该开发; 只有只有是一是一 个合理的均衡。个合理的均衡。2.3.1 子子 博博 弈弈 定定 义义 一一 个个 展展 开开 式式 博博 弈弈 的的 子子 博博 弈弈G 由由 一一 个个 决决 策策 结结x 和和 所所 有有 该该 决决 策策 结结 的的 后继结

21、后继结T(x)( 包包 括终点结括终点结0 组组 成成, 它它 满满 足足 下下 列列 条条 件件:x 是是 一一 个个 单单 点点 信信 息息 结即结即h(x)=x;对于所有的对于所有的xT(x),如果如果xh(x),则则xT(x)。例 房 地 产 博 弈ABB开开不不开开 不不 开开 不不有子博弈: 和子博弈:XXBBxX开开 不不开开 不不122U DL R L R无(真)子博弈1223333U DL R L RC D C D C D C D 参与人2 的信息集不能作为子博弈的初始结, 否则将导致3的信息被分割。3.3.2 子子 博博 弈弈 完完 美美 (精练精练)动动 态态 博博 弈弈

22、 定义定义 展开式博弈的略展开式博弈的略 组组s*=(s1*,si*,sn*) 是一个是一个 子博弈完美子博弈完美(精练精练)Nash均衡均衡, 如果满如果满足足:(1)它它 是原博弈的是原博弈的Nash均衡均衡;(2)它在每一它在每一个子博弈上个子博弈上 给出给出Nash均衡。均衡。 混合策略的子博弈完美混合策略的子博弈完美Nash均衡可类似定均衡可类似定义。义。 简单地说简单地说: 子博弈完美子博弈完美Nash均衡要均衡要求均衡策略求均衡策略 的行为规则在每一个信息集的行为规则在每一个信息集上都是最优的上都是最优的(包括均衡路径和非均衡路包括均衡路径和非均衡路径径)。 定定 义义 展开型博

23、弈的一个策略组合称为子展开型博弈的一个策略组合称为子博弈博弈 完美完美Nash均衡，如果对于该博弈均衡，如果对于该博弈的每一个子的每一个子 博弈，该策略组合都是博弈，该策略组合都是Nash均衡。均衡。例例 泽尔腾泽尔腾 (Selten)12(2,2)(3,1) (0,0)U DL RL RU 2,2 2,2D 3,1 0,0 该博弈有两个该博弈有两个Nash 均衡：均衡：（U，R）和（）和（D，L)但但Nash均衡均衡(U,R)从动态博弈的观点来看是不合从动态博弈的观点来看是不合理的理的,因为它依赖于参与人因为它依赖于参与人2取取R这一这一“空头威空头威胁胁”。 3.3.3 逆向归纳法逆向归纳

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

25、的最优策略一起收集起来就构成结上的最优策略一起收集起来就构成了最佳了最佳 策略。策略。例用逆向归纳法求下列博弈的子博弈完美例用逆向归纳法求下列博弈的子博弈完美Nash 均衡：均衡：1221L RA B C DE F(2,0) (1,1) (0,1/2)(3,1) (2,2)h1h1h2h2解为(R,E),(B,D) 定理定理 在一个具有完美信息的有限博弈中在一个具有完美信息的有限博弈中,使用逆使用逆向归纳法所选择的策略组合总是向归纳法所选择的策略组合总是Nash均衡。均衡。 承诺行动与子博弈完美均衡承诺行动与子博弈完美均衡 例例 法律的要胁诉讼法律的要胁诉讼(设原告为设原告为P,被告为被告为D

26、)PDP(0,0)不指控不指控 指控指控(提出要求提出要求)拒绝拒绝 接受接受起诉起诉 放弃放弃(sc,s)(x-c-p,-x-d) (-c,0) 其中指控成本为其中指控成本为c 如果决定指控如果决定指控,P 要求要求D支付支付s0以以“私了私了”,P 的的 起诉成本为起诉成本为d,如如果果P以概率以概率 赢赢 得得x, 则则xrD/2,若银行若银行同意到期后再收回同意到期后再收回,连本带利将得到连本带利将得到2R(RD)。122122Y NY N Y NY N Y N Y N(r,r) (D,2rD) (2rD,D)(R,R) (2RD,D) (D,2RD) (R,R)Y:提取提取; N:不

27、提不提日期日期1为投资到期之前为投资到期之前;日期日期2为之后为之后3.4.2 讨讨 价价 还还 价价 博博 弈弈(Rubinstein,1982) 假定两个人分一块蛋糕假定两个人分一块蛋糕,参与人参与人1先出价先出价,参与人参与人2 可以可以选择接受或拒绝选择接受或拒绝;如果如果1接受博弈结束接受博弈结束,蛋糕蛋糕 按按1的方案的方案分配分配;如果如果1拒绝拒绝,1再出价再出价;如此直下去直如此直下去直 到一个参与到一个参与人的出价被另一个人接收为止。人的出价被另一个人接收为止。 这是一个无限期完美信息博弈，参与人这是一个无限期完美信息博弈，参与人1在时期在时期1，3，5， 出价出价,参与人

28、参与人2在时期在时期2,4,6, 出价。出价。 用用x表示表示1的份额的份额,1x表示表示2的份额的份额,x1和和(1x1) 分别分别是是1出价时出价时1和和2的份额的份额,x2和和(1x2)分别表分别表 示示2出价出价时参与人时参与人1和参与人和参与人2的份额。的份额。 假定参与人假定参与人1和参与人和参与人2的贴现因子分别为的贴现因子分别为1和和2, 则如则如果在时期果在时期t博弈结束博弈结束,参与人参与人1和参与人和参与人2的支付贴现值分别是的支付贴现值分别是u1=1 xi 和和u2=2(1xi)t-1 t-1如果博弈是有限期的,可以使用逆向归纳法求解子博弈完美Nash均衡(T为期限)设

29、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,1212 x1A R,出出x2A R,出出x3(x1,1x1)(1x2,2(1x2)参与人1会接受,参与人2在t=2时的11单位相当于t=1时的2(11)单位,如果参与人1在t=1时出价1x1=2(11),参与人2会接受,因此,子博弈完美的唯一结果为: x=12(11)类似地:T=4

30、时的子博弈完美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), 在无限期讨价还价博弈在无限期讨价还价博弈 中中, 唯一的子博弈完美唯一的子博弈完美Nash均衡的结果是均衡的结果是: x*=(12)/(112)( 如果如果1=2=,x*=1/(1+)无限期讨价还价的子博弈完美Nash均衡的结果

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

32、分析的问题和扩展3.6.1 逆推归纳法的问题 例123nA A A AD 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,则0.9 0.314,较小的概率可能动摇1取A的决心。19例例12121A1 A2 A3 A4 A5D1 D2 D3 D4 D5 (1,0) (0,1) (3,0) (2,4) (6,3)(5,5)这是一个两人轮流行动的博弈,如果使用后退归纳法,则解宣布在每一个决策结上行动的参与人应采取行动Di,(i=15)。这个解是否令人信服?例 从子博弈完美是由后退归纳法引出的这一 事实，可知子博弈完美均衡其实后退归纳 解 的推广。由于子博弈完美的范围更宽广