博博 弈弈 论论 第一章 导论什么是博弈论(Game Theory)1.1.1 从游戏到博弈游戏都有一些共同的特点:1.都具有一定的规则;2.都有一个结果;一、博弈论概述一、博弈论概述1.1.1 1.1.1 博弈论的定义博弈论的定义博弈论研究的是人与人之间利益相互制约下策略选择时的博弈论研究的是人与人之间利益相互制约下策略选择时的理性行为及相应结局。理性行为及相应结局。豪尔绍尼（豪尔绍尼（John C.HarsanyiJohn C.Harsanyi）19941994年诺贝尔经济学奖获奖年诺贝尔经济学奖获奖致词：博弈论是关于策略相互作用的理论。致词：博弈论是关于策略相互作用的理论。 博弈论研究人与人之间博弈论研究人与人之间“斗智斗智”的形式和后果，当人的形式和后果，当人们利益存在冲突时，每个人所获得的利益不仅取决于自己们利益存在冲突时，每个人所获得的利益不仅取决于自己所获取的行动，还依赖于其他人采取的行动，每个人都需所获取的行动，还依赖于其他人采取的行动，每个人都需要针对对方的行为选择作出对自己最有利的反应。要针对对方的行为选择作出对自己最有利的反应。3 3、博弈论的分类、博弈论的分类 (1)(1)合作博弈合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。(2)(2)非合作博弈非合作博弈研究人们在利益相互影响的局势中如何选决策使自己的收益最大，即策略选择问题。(3)完全信息不完全信息博弈：参与者对所有参与者的策略空间及策略组合下的支付有充了解称为完全信息；反之，则称为不完全信息。(4)(4)静态博弈和动态博弈静态博弈和动态博弈静态博弈：指参与者同时采取行动，或者尽管有先后顺序，但后行动者不知道先行动者的策略。动态博弈：指双方的的行动有先后顺序并且后行动者可以知道先行动者的策略。博弈的分类及对应的均衡博弈的分类及对应的均衡静态动态完全信息完全信息静态博弈完全信息静态博弈纳什均衡；Nash(1950)完全信息动态博弈完全信息动态博弈子博弈精炼纳什均衡；泽尔腾（1965）不完全信息不完全信息静态博弈不完全信息静态博弈贝叶斯纳什均衡；海萨尼（1967-1968）不完全信息动态博弈不完全信息动态博弈精炼贝叶斯纳什均衡；泽尔腾（1975）Kreps,Wilson(1982),Fudenberg,Tirole(1991)一个非技本性的定义规定或定义一个博弈需要以下几个方面：1参与人参与人(Player)(Player)(局中人）局中人）指博弈中的决策主体，他的目的是通过选择行动（或策略）以最大化自己的支付（效用）水平，参与人可以是自然人、团体、自然（“上帝”作为虚拟的参与人）。2各个参与人各自可选择行动集行动集(action(action set)set),Ai=ai,是其可以采用的全部行动的集合。一个行动组合(action proile)是一个由博弈中的n个参与人每个选取一个行动所组成的有序集a=(a1,a2,an)。3. 参与人i的策略策略(strategy)(strategy)是如下的一项规则:给定其信息集,该策略决定在博弈的每一时点他选 择何种行动。 参与人i的策略集(strategy set)Si=si是其可行策略的集合。策略组合(strategy profile)s=(s1,s2,sn)是由博弈的n个参与人每人选择一个策略所组成的一个 有序集。4. 参与人i的得益得益( (支支)(payoff)(payoff)ui(s1,s2,sn)表示 这样的含义: 在所有的参与人和自然都选择了各自的策略且博弈已经完成后, 参与人i获得的效用。 参与人i获得的期望效用，该期望效用是参与人i及其他参与人所选择的策略的函数。5. 一个博弈的结果是指在博弈结束以后，建模者从行动、得益和其他变量的取值中所挑选出来的他所感兴趣的要素的集合。1.2 几类经典的博弈模型1.2.1 囚徒的困境囚徒的困境(prisoners dilemma)囚徒囚徒A坦白不坦白囚徒囚徒B坦白不坦白5,50,1010,01,1这个例子本身就部分奠定了非合作博弈论的基础。1.2.2 智猪博弈智猪博弈 猪圈里有两头猪:大猪和小猪,猪圈的一头有一个猪食槽,另头装有个按纽,控制着猪食的供应,按一下就会有10单位的猪食进槽,但谁按谁就要付出相当于2单位猪食的成本成本;当猪食进槽时,若大猪先到,大猪可吃到9单位;小猪先到,则小猪可吃到4单位,大猪吃6单位;若两者同时到,叫大猪可吃7单位,小猪吃3单位。小猪小猪 大猪大猪按等按等5 , 14,49,10,01.2.3 性别战性别战1.2.4 斗鸡博弈斗鸡博弈女女足球芭蕾男男足球芭蕾2 ,10,00,01, 3AB进退进退3,32 , 0 0 ,20 ,01.2.5 市场进入阻挠1.2.6 猜硬币博弈 石头剪子布默许在位者进入者进入不进入斗争40,5010,00,3000,300猜硬币方正反正反盖硬币方1,11,11,11,1石头石头剪子剪子布布石头石头剪子剪子布布0,01,11,11,10,01,11,11,10,0AB1.3 博 弈 的 结 构 和 博 弈 的 分 类1.3.1 博 弈 中 的 博 弈 方 一、单人博弈 实际上是最优化问题， 或 者是一个参与人与“自自 然然”的博弈。 二、 双人博弈最常见、研究得最多的博弈 双人博弈中的两个博弈方之间并不总是相 互对抗的。(互补性问题) 掌握信息较多的一方并不能保证获益大。 个人追自身的最大利益并不能保证所得最优。 三、多人博弈可能存在“破坏者” 与“联盟”。1.3.2 博 弈 中 的 策 略 博弈中独立决策、独立承担博弈结果的个人或 组织称为博弈方。 博弈中各博弈方的决策内容称为“策略“，但应注意到并不是每个博弈方都有相同的可选略。 如果在一个博弈中每个博弈方的策略数都是有 限的，则称该博弈为有限博弈；否则就称为 无限博弈。1.3.3 博弈中的得益(支付,payoff) 得益指在一个特定的策略组合策略组合下参与人得到效用水平, 即各个博弈方从博弈中所获得的利益. 一、 零 和 博 弈 二、 常 和 博 弈 三、 变 和 博 弈国内常见的博弈论参考书:1.经济博弈论(第二版) 谢识予 编著复旦大学出版社, 20022.博弈论与信息经济学 张维迎 著,上海三联书店、上海人民出版社3.博弈论施锡铨 著,上海财经大学出版社, 20024.Game Theory,1991,D.Fudenberg& 中译本,中国人民大学出版社 第二章 完全信息静态博弈2.1 基 本 分 析 思 路 和 方 法 博弈可以有两种不同的表达方式：策略式策略式(Normal)表述和扩展式扩展式(extensive)表述，从 理论上来讲，这两种表述形式几乎是完全等 价的，但从分析的方便性来看，策略式更适 合表述静态博弈。 在策略式表述中，所有参与人同时选择各自的 策略，所有参与人选择的策略一起决定每个参与人的支付。这里的“ 同时选择”的是策略，而不是行动。这里的“同时”是一个信息概念,而不是一个时间概念。可以设想,参与人是处于不同的房间里,要求在彼此没有联络的情况下,选择一个按纽。通常还假设,所有的参与人都知道博弈的结构,知道他们的对手知道这一结构,知道他们的对手了解他们知道如此直至无穷,也即博弈的结构是共同知识。更准确地,策略式表述给出:博弈的参与人集合: i,=1,2,n每个参与人的策略空间 Si, i=1,2,n策略组合(s1 ,s2 ,sn )(4)每个参与人的支付(收益)函数 ui=(s1,si,sn),i=1,2,n一般用 G=S1,S2,Sn;u1,u2,un表示策略式博弈。例 LMRUMD4,35,16,22,18,43,63,09,62,8S1=U,M,D , S2=L,M,R支付用矩阵表示,称为双矩阵博弈。 参参 与与 人人A 参参 与与 人人B2.1.1 上策均衡（严格占优战略均衡） 如果在某个博弈中,无论其他博弈方选择什么策略,一个博弈方的某个策略给他带来的支付始 终不低于其他策略,则称该策略为这个博弈方 的一个上策(优势策略Dominant strategy)。 如果一个博弈的某个策略组合中所有策略都是各个博弈方自己的上策，则称这样的策略组合为该博弈的一个“上策均衡”。例(囚徒的困境)囚徒囚徒A A坦白不坦白囚徒囚徒B B坦白不坦白5 5, ,5 50,0,101010,010,01,1,1 12.1.2 严格下策反复消去法（逐步剔除严格劣战略） 例 LMRUMD8,35,16,22,18,43,09,62,83,6可以预测该博弈的合理结局为(U,L),即参与人A选择策略U,而参与人B选择策略L。2.2 Nash 均 衡2.2.1 Nash 均 衡 的 定 义 Nash 均衡是指这样的策略组合策略组合(或剖面): 为了 极大化自己的收益(或效用), 每一个参与人所 采取的策略一定应该是关于其他参与人所采 取的策略的最佳反应. 因此没有一个参与人会 轻率地偏离这个策略组合而使自己蒙受损失。 定 义 在有n个参与人的博弈G=S1,S2Sn;u1,u2,un)中,策略组合s*=(s1 *,s2 *,sn *)是一个Nash均衡,如果对于每一个i, si*是给定其他参与人的选择:S-i*=(s1*,si-1*,si+1*,sn*)的情况下,第i个人的最优策略,即 ui(si*,s-i*)ui(si,s-i*) ,对所有的i或者用另一种表示方式,si*是下述最大化问题的解:si*arg ui(s1*,si-1*,si,si+1*,sn*),i=1,2,n因此,当且仅当没有一个参与人能从单方面背离某个策略组合的预见中增加自己的得益时,这个策略组合就是Nash均衡。Si*SiNash 均衡的哲学含义：设想n个参与人在博弈前规定每一个参与人选择一个特定的策略。 s*=(si*,s-i*) 代表这个协议，要问在没有外力 强制的情况下，是否有参与人有积极性 不遵守该协议？如没有，则说明该协议是可以 自动实施的。能够自动实施的协议就可以看作 一个Nash 均衡。例 求下列博弈的Nash 均衡：CRLUMN0，44，05，34，00，45，33，53，56，6得Nash均衡为:(D,R).用划线法划线法可求Nash均衡有强弱之分.上述定义中给出的是弱Nash均衡,一个Nash均衡是强的,如果给定其他参与人的策略,每一个参与人的选择是唯一的。即,s*是一个强Nash均衡,当且仅当对每一个i,sisi*总有:ui(si*,s-i*)ui(si,s-i*)。如果一个Nash均衡是强的,则没有任何参与人在均衡策 略和其他策略之间是无差异的。（弱Nash均 衡不是) 如在以下博弈中： C1C2C3R1R2R32,121,101,120,120,100,110,120,120,13(R1,C1)和和(R1,C3)都是都是Nash均衡均衡,但没有但没有一个强一个强Nash均衡。均衡。本质上说,Nash 均 衡的概念对社会计划者和理 论家施加了一个约束， 使他们不能建议或者 预测一种非均衡行为。 博弈论可预测到，在均衡集较小的局势中，文 化规范的重要性也小。2.2.2 Nash 均衡的一致性预测性质Nash 均衡是参与人将如何博弈的“一致性”(consistent) 预测: 如果所有参与人预测 到一个特定的Nash 均衡将出现, 那么, 没有人 有兴趣作不同的选择。也只有Nash 均衡具有这样的特征：参与人预测到均衡， 参与人预测到其他参与人预到均衡 等 等。 对比之下，预测一个非Nash 均衡的策略组合 意味着至少有一个参与人会犯错误，尽管这 样的错误确有可能出现。说Nash 是一致性预测并不意味着Nash 均衡一 定是一个好的预测，但只有Nash 均衡才有： “一 致 性”预测的性质。 重要结论：一种制度安排要发生效力必须是一 种Nash均衡(Nash执行的,Nash Implementation), 否则, 这种制度便不能“ 稳定”。均衡与严格下策消去法命题在博弈G=S1,S2,Sn;u1,u2,un中,如果严格下策反复消去法排除了除( s1*,s2*sn*)之外的所有策略组合,那么(s1*,s2*,sn*) 一定是该博弈唯一的Nash均衡。命题2.2 在博弈G=S1,S2,Sn;u1,u2,un中,如果(s1*,s2*,sn*)是G的一个Nash均衡,那么严格下策消去法一定不会将它消去。检验纳什均衡（囚徒困境，智猪游戏）检验纳什均衡（囚徒困境，智猪游戏）性别战博弈性别战博弈克瑞丝克瑞丝歌剧拳击帕特帕特歌剧拳击2,10,00,01,2思考题：思考题：为何几乎所有的卡特尔都会遭到失败？为何几乎所有的卡特尔都会遭到失败？几乎所有的几乎所有的卡特尔都会遭到失败卡特尔都会遭到失败，原因就在于，原因就在于卡特尔的协定（类似囚犯的攻守同盟）不是一卡特尔的协定（类似囚犯的攻守同盟）不是一个纳什均衡，没有成员有兴趣遵守。那么是不个纳什均衡，没有成员有兴趣遵守。那么是不是不可能有卡特尔合作成功了？理论上，如果是不可能有卡特尔合作成功了？理论上，如果是无限期的合作，双方考虑长远利益，他们的是无限期的合作，双方考虑长远利益，他们的合作是会成功的。但只要是有限次的合作，合合作是会成功的。但只要是有限次的合作，合作就不会成功。比如合作次，那么在第九作就不会成功。比如合作次，那么在第九次博弈参与人就会采取不合作态度。次博弈参与人就会采取不合作态度。2.3 2.3 无限策略博弈分析和反应函数无限策略博弈分析和反应函数2.3.1 Gournot （库诺特）双寡头竞争模型(Nash 均衡最早的 版本,1838 年)设有两个参与人,分别称为企业1和企业2,每个企业的策略是选择产量,得益是利润,它是两个企业产量的函数。我们用qi0,)表示第i个企业的产量,总供给量为Q= q1+q2 ，Ci(qi)cqi表示成本函数,P=P(q1+q2)=a-(q1+q2)表示逆需求函数（售价）。第i个企业的利润函数为: ui(q1+q2)=qiP(q1+q2)Ci(qi),i=1,2即u1(q1+q2)=q1P(q1+q2)Cq1 u2(q1+q2)=q2P(q1+q2)Cq2(q1*,q2*)是Nash均衡产量意味着:q1*argmax u1(q1,q2*)=q1P(q1+q2*)C1(q1)q2*argmax u2(q1*,q2)=q2P(q1*+q2)C2(q2)找出Nash均衡的一个办法是对每个企业的利润 函数求一阶导数并令其为零:u1/q1=P(q1+q2)+q1P(q1+q2)C1(q1)=0u2/q2=P(q1+q2)+q2P(q1+q2)C2(q2)=0上述两个一阶条件分别定义了两个反应函数:q1*=R1(q2) q2*=R2(q1)反应函数意味着每个企业的最优策略(产量)是另一个企业产量的函数,两个函数的交点就是Nash均衡 q*=(q1*,q2*) (如下图)Cournot模型q1q2R1(q2)R2(q1)NEOq1*q2*2.4 混 合 策 略 和 混 合 策 略Nash 均 衡2.4.1 严格竞争博弈和混合策略的引进 一、 严格竞争博弈正面正面反面反面正面正面反面反面盖币方盖币方猜币方猜币方-1,11,-11,-1-1,1这个博弈实 际上是一个零和博弈，一方所得即另一方所失，该博弈没有纯策略的Nash均衡。例1例2 社会福利博弈寻找工作寻找工作 游荡游荡救济救济不救济不救济3,23,2-1,3-1,3-1,1 0,0-1,1 0,0政府政府流浪汉流浪汉 这个博弈也不存在纯策略的Nash均衡，给定政府救济，流浪汉的最佳 策 略是游荡，给定流浪汉游荡，政府的最佳策略是不救济上述博弈的显著特征是：每一个参与人都想猜透对方的策略，而每个参与人又都不想让对方猜透自己的策略，所以此类博弈中都不存在(纯策略)Nash均衡。对猜硬币博弈来说，设出正面的概率友p,则出反面的概率为1p,如果p1/2,且猜币方全猜正面,他的期望得益为: p1+(1p)(1)=2p10即从平均来讲,这时猜币方一定是赢多输少;而如果 p1/2,猜币方也可通过全猜反面而占优。只有p=1/2, 对方无法占便宜，从而双方各选1/2作为正反面的概率也就成了一种 “均 衡”。 二、 混合策略和混合策略Nash均衡 定 义 在博弈GS1,S2,Sn;u1,u2,un中参与 人的策略空间为Si=si1,si2,sik,则参与人i以概率分布i=(i1,ik)随机地在其k个可选策略中选择的“策略”称为个混合策略。其中0ij1,且ij=1纯策略可以理解为混合策略的特例，如纯策略si1可以看作是混合策略i=(1,0,0)。我们用i表示参与人i的混合策略空间:ii用=(1,2,n)表示n个博弈方的混合策略 组合。用i表示混合策略组合空间:在纯策略情形下,ui=ui(s)=ui(u1,ui,un)对任何一个给定的纯策略组合:s=(s1,s2,sn),ui取确定值。与混合策略相伴的是得益(支付)的不确定性。这时:ui()=ui(1,i,n)ui(i,i)表示参与人i的期望效用,它可定义为ui(i,-i)=(j(sj)ui(s)sSj=1n其中j(sj)是混合策略j赋予纯策略sj的概率。以两人博弈为例:S1=s11,s12,s1p,S2=s21,s22,s2q如果参与人1相信参与人2的混合策略为:2=(21,22,2q)那么参与人选择纯策略s1p的期望效用为: 2ju1(s1p,s2j)qj=1参与人选择混合策略1=(11,12,1p)的期望效用(得益)为: u1(1,2)=1k 2ju1(s1k,s2j)pk=1qJ=1= 1k2ju1(s1k,s2j)K=1 J=1pq类似地有 u2(1,2)= 1k2ju2(s1k,s2j)k=1 j=1p q例如对博弈L M RU 4,3 5,1 6,2M 2,1 8,4 3,6D 3,0 9,6 2,8参与人参与人2(B)参与人参与人1(A)(双矩阵博弈)下面重新定义Nash均衡定义 在博弈G=S1,S2,Sn;u1,u2,un中,混合策略组合*=(1*,i*,n*)是一个Nash均衡,如果对任一i,有: ui(i*,-i*)ui(i,-i*),对任ii这个定义也可以写为:定义 对在博弈G=S1,Sn;u1,un中的混合策略组合*=(1*,i*,n*),如果对所有的参与人i,有ui(i*,-i*)ui(sik,-i*),对每一sikSi成立,则称*为博弈G的Nash均衡。 22双矩阵博弈的Nash均衡的求法例1 求双矩阵博弈的混合策略Nash均衡,其中A=B=解:设1x),2*=(y,1y)为Nash均衡点,u1(1*,2*)=xAy=3xy+2x(1-y)+4(1-x)(1-y)=x(5y-2)+4-4y,如果y2/5,则在x=1时达到最大值。类似地u2(1*,2*)=xBy=y(2x-1)+4-3x3 2 0 42 13 4要使上式取最大值,应取y=故两者的交点为(2/5,1/2)故混合策略的Nash均衡为:(2/5,3/5),(1/2,1/2),相应的得益为:U1=2.4,u20, 0x1/20,1, x=1/21, 1/2x1,两个人所得为 零,这时,任何满足x1+x2=1 的 点(x1,x2) 都是Nash均衡点。(但x1+x21/8时,99y8y, 如果参与人1认为参与 人2取R的可能性大于1/8, 他宁愿取D, 因此, 从风险占优的角度看,(D,R)优于 (U,L )。例 猎猎 鹿鹿 博博 弈弈猎猎 鹿鹿 猎猎 兔兔猎猎 鹿鹿 3,3 0,1猎猎 兔兔 1,0 1,1猎手猎手1猎手猎手2是介是介 于于“囚徒的困境囚徒的困境”与与“协调博弈协调博弈之间的博弈之间的博弈,它有两个它有两个Nash均衡均衡:( 鹿鹿, 鹿鹿) 和和( 兔兔, 兔兔), 但但( 兔兔, 兔兔) 是是 风风 险险 占占 优优 的。的。 三、聚点均衡聚点均衡(focal Points Equilibrum) 四、相关均衡相关均衡 Nash均衡通常在参与人独立地选 择自己的策略范围下才有意义。实际上不少博弈中参与人之间选择的策略是相关的，如 与一个“ 信号装置”有关。 如古代战将单打独斗不相上下时“鸣金收兵。 例（Aumann,1974)相关均衡他证明如果参与人可以根据某个共同观测到的 信号选择行动，就可能出现“相关均衡”。 如 博 弈 L RU 5，1 0，0D 4，4 1，5 参参 与与 人人1 参参 与与 人人2该博弈有三个Nash均衡(U,L),(D,R)和混合策略：(1*,2*)=(1/2,1/2),(1/2,1/2), 相应的得益为(5,1),(1,5),(2.5,2.5)。但假若双方约定抛一枚硬币，正面朝上则1选U，2选L；反面朝上别1选R，2选D，此时每人的期望效用为3，大于混合Nash均衡的期望值。这时，按上述规则行动是一个Nash均衡。 更 重 要 的 是，Aumann 证明：如果每个人收 到不同但相关的信号，每个人都能得到更高的 期望效用。设想由第 三方掷骰子特定方法决 定两人的行动，如12点出现，则1选U，36点出现则1选D，对参与人2则：如果14点 出现，选L。56 点出现则选R，再假定第三 方只告诉参与人选择什么行动，而不透露什么 点数。这时：(U,R)不会出现 保证三个结果(U,L),(D,L),(D,R)各以1/3的概率出现。这时双方的期望得经均为10/3。(但“信号装置”是 有成本的)例 三人博弈的得益矩阵为L R L R L R乙乙 乙乙 乙乙U 2,1,3 0,0,0 U 2,2,2 0,0,0 U 0,1,0 0,0,0D 1,1,1 1,0,0 D 2,2,0 2,2,2 D 1,1,0 1,0,3甲甲甲甲甲甲A B C丙丙 该博弈有唯一的该博弈有唯一的Nash均衡均衡(D,L,A),相应的得益（相应的得益（1，1，1，),但可但可以建立以建立 一个抛均匀硬币的信号装置，甲、乙可以看到结果：一个抛均匀硬币的信号装置，甲、乙可以看到结果： 甲：看到正面取甲：看到正面取U，反面取，反面取D； 乙：看到正面取乙：看到正面取L，反面取，反面取D； 丙：丙： 总是总是 取取B。（丙不能看到硬币正反。（丙不能看到硬币正反) 这这 时时 最最 终终 得得 益益 为为(2，2，2)。2.6.2 共共 谋谋 和和 防防 共共 谋谋 博博 弈弈 一、 多 人 博 弈 中 的 共 谋 问 题 例L R L RU 0，0，10 5，5，0 U 2，2，0 5，5，0D 5，5，0 1，1，5 D 5，5，0 1，1，5A B丙丙甲甲甲甲乙乙乙乙易用划线法知(U,L,A)与(D,R,B)是纯策略Nash均衡，前者在Pareto意义下优于后者，而后者在风险上优于前者，如不考虑串通结果应为(U,L,A), 但如果考虑甲、乙串通取(D,R), 则结果应为(D,R,B)。 二、 防防 共共 谋谋 均均 衡衡 防共谋均衡是两个以上博弈方的博弈中，博弈 方之间在Pareto 上策均衡中进行合作的思想 的扩展。 定义；如果一个博弈的某个策略组合满足下列 条件：没有任何博弈方的串谋会改变博弈的 结果；给定选择偏离的博弈方有再次偏离的 自由时，没有任何两个博弈方的串谋会改变博 弈的结果；依次类推，直到所有博弈方都参 加的串谋也不会改变博弈的结果。则称该策略组合为一个防共谋均衡。 第第 三三 章章 完完 全全 信信 息息 动动 态态 博博 弈弈3.1 动 态 博 弈 的 表 示 法 和 特 点1.定 义 与 博 弈树2.2. 博弈的展开式所包含的信息和内容:3. 参与人的集合,记为i=1,2,n,用N代表虚拟的参匀人“自然”;4. 行动的次序, 即谁在什么时候行动;5. 参与人的行的空间,即轮到某参与人行动时,他从该时刻的纯策略空间中选取什么策略;6. 当参与人作出他们的行动决策时,他所观测到 或他所了解到的信息,即他在此时获得的信息 集合;7. 参与人的得益(支付或效用), 它们是已知行动的函数;8. 在任何外生事件的概率分布。 例例 房地产开发博弈房地产开发博弈有两个房地产开发商有两个房地产开发商( (分别为参与人分别为参与人1,1,记为记为A A和参与人和参与人2,2,记为记为B) B) 在某地开发房地产在某地开发房地产, , 但该地的房地产需求状况是不确定的但该地的房地产需求状况是不确定的, , 假定该博弈的行动顺序如下假定该博弈的行动顺序如下: :(1) (1) 开发商开发商1 1先行动先行动, , 选择开发或不开发选择开发或不开发;(2);(2)在在1 1决决策后策后,“ ,“ 自然自然”选择需求的大小选择需求的大小;(3);(3)开开发商发商2 2在在 观测到观测到1 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表示信息集表示信息集 上述博弈树给出了有限博弈的几乎所有信息。上述博弈树给出了有限博弈的几乎所有信息。 博博 弈弈 树树 必必 须须 满满 足足 下下 列列 规规 则：则：(1)(1)每一个结每一个结(node)(node)至多有一个其他结直接位于至多有一个其他结直接位于 它的前面它的前面; ;(2)(2)在博弈中没有一条路径可以使决策集与自身在博弈中没有一条路径可以使决策集与自身 相连相连; ;(3)(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)息 博弈。(无虚线连接),而完全(complete)信息博弈是指得益函数和纯策略空间均为博弈各方的共同知识。完全信息可以是完美的也可以是不完美的。3.2 展开型博弈的策略与均衡 一、 行 为 策 略 在策略型博弈中, 参与人的策略是进行博弈的计划( 或打算)的详细集合, 而在展开型博弈中 参与人的策略必须确定在该参与人的每一个决 策集上 所 采 取 的 行 动,又 结 与 信 息 集 紧 密 相 连, 对 于 参 与 人i,基于信息hi的行动的的全体记汉的全体记汉A(hA(hi i),),如果令如果令H Hi i表示参与人表示参与人i i的信息的信息集集的集合的集合, ,则则Ai= A(hAi= A(hi i) )就是参与人就是参与人i i的所有的所有行动行动的集合。参与人的集合。参与人i i的一个纯策略是从的一个纯策略是从H Hi i到到A Ai i的一的一个映射个映射s si i: :对每一个对每一个h hi iAAi i,s,si i(h(hi i)A)Ai i, ,所有这所有这些些s si i的全体记为的全体记为S Si i, ,即的的纯策略空间即的的纯策略空间S Si i, ,由此由此: : S Si i= A(h= A(hi i) )hiHihiHi例参与人2有两个策略集,相应地也有两个信息集 A(h2(1)=A(h2(2)=左,右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(hi)hiHi 展开型博弈中纯策略是由信息集与行动集定义展开型博弈中纯策略是由信息集与行动集定义 的的( ( 与静态博弈不同与静态博弈不同, ,静态博弈中采取纯策略静态博弈中采取纯策略与与 采取某行动是一个意思采取某行动是一个意思) )。 纯策略组合纯策略组合( (剖面剖面profile)profile)是由参与人各自的是由参与人各自的纯策纯策 略空间中的任一纯策略构成的组合，在略空间中的任一纯策略构成的组合，在任一纯任一纯 策略组合策略组合s s下，总可以从初始结开始，下，总可以从初始结开始，沿着博弈树的某条路径沿着博弈树的某条路径(path), (path), 达到达到s s相应的相应的终点结。终点结。 有一个事实非常重要：有一个事实非常重要：s s中有些信息中有些信息集在博弈集在博弈 树的这条路径上，我们称这些信息树的这条路径上，我们称这些信息集是集是s s的路的路 径径(path), (path), 当然也可能存在当然也可能存在s s中某中某些信息集不在些信息集不在 此路径上。此路径上。 定义了纯策略的得益函数后，我们就可以定义 展开型博弈的Nash 均衡； 定义 策略组合s*=(s1*,si*,sn*)是展开型 博弈的一个Nash均衡，如果对每一个i,si*最大化ui(si,s-i*):即 si*arg max ui(si*,s-i*),对任一i 策略型博弈的混合策略实际上是纯策略空间上 的概率分布，因此展开型博弈中参与人i的混 合策略也可以看作是其纯策略空间Si上的任一 概率分布。“ 参与人的每一个特定的纯策略si相当于一本指导说明书，书中每一页表示到了一个特定的信息集hi,在 该页上告诉i 如何行动。许多的si 相当于许多的说 明书，Si表示这些说明书的全体。混合策略相当于i 以一定的概率分布随机地抽取一本说明书”(Luce & Raiff)。 参与人i的行为策略行为策略bi 定义为： bihiHihiHi(A(hi) 其中 表示某集合是的概率分布。 行 为 策 略 的Nash 集 合 是 这 样 一 个 策 略 组 合， 它 使 得 没 有 一 个 参 与 人 可 以 通 过 不 同 的 使 用策 略 而 增 加 自 己 的 得 益。注意：行为策略是在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) 开发 不开发 开发 不开发 开发 不开发 开发 不开发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) 注注 意意: 得得 益益 向向 量量 的的 次次 序序 与与 参参 与与 人人 决决 策策 的的 顺顺 序序 一一 致。致。 同样地,展开型博弈也可以用策略式来表示, 如 展开型博弈: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 参参 与与 人人1 参参 与与 人人2 同样地,展开型博弈也可以用策略式来表示: 例 摊牌博弈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) 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)=其中其中R(r)表示加注表示加注;F(f)表表示摊牌示摊牌;M表示对抗表示对抗;P表示表示放弃。放弃。该博弈有唯一的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 3.3 子子 博博 弈弈 与与 子子 博博 弈弈 完完 美美Nash Nash 均衡在原则上适用所有的博弈均衡在原则上适用所有的博弈, ,但对于预但对于预测测 参与人的行为来说参与人的行为来说,Nash,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 Nash 均均 衡衡: :( ( 不不 开开 发发,( ,( 开开 发发, , 开开 发发)( ( 开开 发发,( ,( 不不 开开 发发, , 不不 开开 发发)( ( 开开 发发,( ,( 不不 开开 发发, , 开开 发发) 但但中中B B的策略是不合理的的策略是不合理的, ,这个威胁是不可置这个威胁是不可置 信的信的;中中B B的策略的策略( (不开发不开发, ,不开发不开发) )也不合理也不合理, , 因为若因为若A A不开发不开发,B,B显然应该开发显然应该开发; ; 只有只有是一是一 个合理的均衡。个合理的均衡。2.3.1 2.3.1 子子 博博 弈弈 定定 义义 一一 个个 展展 开开 式式 博博 弈弈 的的 子子 博博 弈弈G G 由由 一一 个个 决决 策策 结结x x 和和 所所 有有 该该 决决 策策 结结 的的 后继结后继结T(x)T(x)( ( 包包 括终点结括终点结0 0 组组 成成, , 它它 满满 足足 下下 列列 条条 件件:x :x 是是 一一 个个 单单 点点 信信 息息 结即结即h(x)=x;h(x)=x;对于对于所有的所有的xT(x),xT(x),如果如果xh(x),xh(x),则则xT(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 3.3.2 子子 博博 弈弈 完完 美美 动动 态态 博博 弈弈 定义定义 展开式博弈的略展开式博弈的略 组组s*=(ss*=(s1 1*,s*,si i*,s*,sn n*) *) 是一个是一个 子博弈完美子博弈完美NashNash均衡均衡, , 如果满足如果满足:(:(1)1)它它 是原博弈的是原博弈的NashNash均衡均衡;(2);(2)它在每一个子博弈上它在每一个子博弈上 给出给出NashNash均衡。均衡。 混合策略的子博弈完美混合策略的子博弈完美NashNash均衡可类似定义。均衡可类似定义。 简单地说简单地说: : 子博弈完美子博弈完美NashNash均衡要求均衡策略均衡要求均衡策略 的行为规则在每一个信息集上都是最优的的行为规则在每一个信息集上都是最优的( (包包括均衡路径和非均衡路径括均衡路径和非均衡路径) )。 定定 义义 展开型博弈的一个策略组合称为子博展开型博弈的一个策略组合称为子博弈弈 完美完美NashNash均衡，如果对于该博弈的每一个均衡，如果对于该博弈的每一个子子 博弈，该策略组合都是博弈，该策略组合都是NashNash均衡。均衡。例例 (Selten) (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 3.3.3 逆向归纳法逆向归纳法逆向归纳法包括以几个步骤逆向归纳法包括以几个步骤: :从博弈树的终点结出发从博弈树的终点结出发, , 追踪到紧接着它的追踪到紧接着它的前面的结前面的结; ;在步骤在步骤的中到达的每一个基本结上的中到达的每一个基本结上, ,通过对通过对该决策结出发到达的每一个终点结上参与人该决策结出发到达的每一个终点结上参与人 得到的得益求最佳行动得到的得益求最佳行动; ;在步骤在步骤中检验过每一个基本决策结中所引中检验过每一个基本决策结中所引起的所有非最优枝删去起的所有非最优枝删去; ; 如达到树根如达到树根, ,则中止则中止, ,否则回到否则回到(1)(1) 对每一个参与人对每一个参与人, ,将该参与人在每一个决策将该参与人在每一个决策 结上的最优策略一起收集起来就构成了最佳结上的最优策略一起收集起来就构成了最佳 策略。策略。例用逆向归纳法求下列博弈的子博弈完美例用逆向归纳法求下列博弈的子博弈完美Nash Nash 均衡：均衡：1221L RA B C DE F(2,0) (1,1) (0,1/2)(3,1) (2,2)h1h1h2h2解为(R,E),(B,D) 定理定理 在一个具有完美信息的有限博弈中在一个具有完美信息的有限博弈中,使用逆使用逆向归纳法所选择的策略组合总是向归纳法所选择的策略组合总是Nash均衡。均衡。例例 开金矿博弈开金矿博弈( (相机选择问题相机选择问题Contingent Contingent Play)Play)乙乙甲甲借借 不借不借(钱钱)分分 不分不分(利益利益)(1,0)(2,2) (0,4)乙乙(1,0) (0,4)(-1,0) (0,4) 考虑法律保障考虑法律保障保障不足保障不足打打 不打不打(官司官司)3.4 .4 几几 个个 经经 典典 的的 动动 态态 博博 弈弈 模模 型型3.4.1 Stackelberg 3.4.1 Stackelberg 寡寡 头头 竞竞 争争 模模 型型 该模型可以看作该模型可以看作 是子博弈完美是子博弈完美NashNash均衡的最均衡的最早版本。其中企业早版本。其中企业1(1(称为领头企业称为领头企业) )先选择产先选择产 量量q q1 1QQ1 1=0,), =0,), 企业企业2(2(称为尾随企业称为尾随企业) )观测观测 到到q q1 1后选择自己的产量后选择自己的产量q q2 2QQ2 2=0,), =0,), 这时这时企企 业业2 2的策应该是从的策应该是从Q Q1 1到到Q Q2 2一个反应函数一个反应函数:S:S2 2:Q:Q1 1QQ2 2, , 而企业而企业1 1的策略就是简单地选择的策略就是简单地选择产量产量q q1 1纯策略纯策略 均衡结果是产出向量均衡结果是产出向量(q(q1 1,s(q,s(q1 1),),支付函数为支付函数为:u:ui i(q(q1 1,s,s2 2(q(q1 1),),由于由于产量是一个连续变量产量是一个连续变量, ,故不能作出博弈树。故不能作出博弈树。 假定逆需求函数为假定逆需求函数为P=aP=aq q1 1q q2 2, ,两个企业有相两个企业有相 同的不变单位成本同的不变单位成本c0,c0,则支付则支付( (利润利润) )函数为函数为:u:ui i(q(q1 1,q,q2 2)=q)=qi i(P(Pc),i=1,2 c),i=1,2 我们可以用逆向我们可以用逆向 归归纳法求解这个博弈的子博弈完美纳法求解这个博弈的子博弈完美NashNash均衡。均衡。 假假定定q q1 1已经选定已经选定, , 企业企业2 2的问题是的问题是: : max u max u2 2(q(q1 1,q,q2 2)=q)=q2 2(a(aq q1 1q q2 2c)c) 最优化一阶条件为最优化一阶条件为:s:s2 2(q(q1 1)=(1/2)(a)=(1/2)(aq q1 1c)c) 因为企业因为企业1 1预测到企业预测到企业2 2将根据将根据s s2 2(q1)(q1)选择选择q q2 2, ,企企 业业1 1在第一阶段的问题是在第一阶段的问题是: :Max uMax u1 1(q(q1 1,s,s2 2(q(q1 1)=q)=q1 1(a(aq q1 1s s2 2(q(q1 1) )c)c) 解一阶条件得解一阶条件得: q: q1 1*=0.5(a*=0.5(ac)c) 将将q q1 1* *代入代入s s2 2(q(q1 1) )得得:q:q2 2*=s*=s2 2(q(q1 1*)=0.25(a*)=0.25(ac).c).( ( 先先 动动 优优 势势) )委托委托- -代理代理(Principle-Agents)(Principle-Agents)理论理论1.1.无不确定性的情形无不确定性的情形122(0,0)委托委托 不委托不委托接受接受 拒绝拒绝努力努力 偷懒偷懒(0,0)(12,2) (7,1)12NN2委托委托 不委托不委托接受接受 拒绝拒绝努力努力 偷懒偷懒高产高产 低产低产 高产高产 低产低产0.9 0.1 0.1 0.9(0,0)(0,0)(16,2) (6,2) (18,1) (8,1)银行挤兑模型银行挤兑模型: :设两个投资者各具某银行存款设两个投资者各具某银行存款D,D,银行将银行将这两笔存款用于一长期项目这两笔存款用于一长期项目, ,如果在项目到期之前银如果在项目到期之前银行被迫抽回资金行被迫抽回资金, ,仅可挽回仅可挽回2r,2r,其中其中DrD/2,DrD/2,若银行若银行同意到期后再收回同意到期后再收回, ,连本带利将得到连本带利将得到2R(RD)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:不提不提日期日期1为投资到期之前为投资到期之前;日期日期2为之后为之后3.4.2 3.4.2 讨讨 价价 还还 价价 博博 弈弈(Rubinstein,1982)(Rubinstein,1982) 假定两个人分一块蛋糕假定两个人分一块蛋糕, ,参与人参与人1 1先出价先出价, ,参与人参与人2 2 可以可以选择接受或拒绝选择接受或拒绝; ;如果如果1 1接受博弈结束接受博弈结束, ,蛋糕蛋糕 按按1 1的方案的方案分配分配; ;如果如果1 1拒绝拒绝,1,1再出价再出价; ;如此直下去直如此直下去直 到一个参与到一个参与人的出价被另一个人接收为止。人的出价被另一个人接收为止。 这是一个无限期完美信息博弈，参与人这是一个无限期完美信息博弈，参与人1 1在时期在时期1 1，3 3，5 5， 出价出价, ,参与人参与人2 2在时期在时期2,4,6, 2,4,6, 出价。出价。 用用x x表示表示1 1的份额的份额,1,1x x表示表示2 2的份额的份额,x,x1 1和和(1(1x x1 1) ) 分别分别是是1 1出价时出价时1 1和和2 2的份额的份额,x,x2 2和和(1(1x x2 2) )分别表分别表 示示2 2出价时出价时参与人参与人1 1和参与人和参与人2 2的份额。的份额。 假定参与人假定参与人1 1和参与人和参与人2 2的贴现因子分别为的贴现因子分别为1 1和和2 2, , 则则如果在时期如果在时期t t博弈结束博弈结束, ,参与人参与人1 1和参与人和参与人2的支付贴现值分别是的支付贴现值分别是u1=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,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时的子博弈完美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均衡的结果决定于参与人的贴现因子(耐心程度)证明: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),且结果是唯的. 承诺行动与子博弈完美均衡承诺行动与子博弈完美均衡 例例 法律是的要胁诉讼法律是的要胁诉讼( (设原告为设原告为P,P,被告为被告为D)D)PDP(0,0)不指控不指控 指控指控(提出要求提出要求)拒绝拒绝 接受接受起诉起诉 放弃放弃(sc,s)(x-c-p,-x-d) (-c,0) 其中指控成本为其中指控成本为c 如果决定指控如果决定指控,P 要求要求D支付支付s0以以“私了私了”,P 的的 起诉成本为起诉成本为d,如如果果P以概率以概率 赢赢 得得x, 则则xp。3.6 动态博弈分析的问题和扩展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)。这个解是否令人信服?例 从子博弈完美是由后退归纳法引出的这一 事实，可知子博弈完美均衡其实后退归纳 解 的推广。由于子博弈完美的范围更宽广，因 此引起争议的内容更多一些。如下博弈：12311L RL R F GF G F G（6,0,6)(8,6,8)(0,0,0) (7,10,7) (7,10,7) (0,0,0)最后阶段1与是否能够“协调”成功对2的策略有影响 逆推归纳法更大的问题是对参与人的理性要求 太高,不仅要求所有的博弈方都有高度的理性, 不允许犯如何错误,而且要求所有的博弈方相 互了解和相信其他参与人的理性,对理性有相 同的理解 。 例 犯错误的可能:11L RM NS T2(2,0)(0,3)(0,1) (1,3)该博弈的子博弈完美Nash均衡是(L,T); N. 但如果1“犯错误”而选R,将会如何?3.6.2 颤抖手均衡和顺推归纳法 一 颤 抖手均衡例 下 列 博 弈 L RU 10,0 5,2D 10,1 2,0中,(D,L)和(U,R)都是Nash均衡, 但(U,R)是一个颤抖手均衡。定义 在博弈G=S1,S2,Sn;u1,u2,un中,Nash均衡(1,2,n)是一个颤抖手均衡,如果对每一个参与人i,存在一个严格混合策略序列i满足下列条件:(1) lim i =i; (2)i是对-i=(1,i-1,i+1,n)的最佳反应。 m m m m mmmm例 动态博弈1212L RM NS TU V(2,1)(1,2)(1,1)(0,0) (2,3)3 这个博弈有两条均衡 路 径,一条是1在第,一 阶 段 选 择L,博弈结束; 另一条是R-N-T-V, 但第 二条不是颤抖手均衡路 径,因为只要1认为2在第 二 阶段有如何一点偏离 的可能性,第一阶段就不 可能坚持R策略。 但如果将最后的策略V的得益改一下( 如 图), 则R-N-T-V就是颤抖手均衡。 例（例（van Damme) van Damme) 顺推归纳法顺推归纳法1R（2，2)s ws 0,0 3,1w 1,3 0,02策略式表述策略式表述S wR 2,2 2,2Ds 0,0 2,1Dw 1,3 0,0 参与人参与人2参与人参与人1可以验证(Rw,s)和(Ds,w)都是该博弈的子博弈完美Nash 均衡, 并且也都是颤抖手均衡, 但对(Rw,s)这个博弈均衡 是有疑问的。较 可 能 出 现 的 结 果 是(Ds,W)。 第第 四四 章章 重重 复复 博博 弈弈4.1 重 复 博 弈 引 论4.1.1 为 什 么 要 研 究 重 复 博 弈 人们之间的长期关系与短期关系之间有重要 的性质差别,人们在对待与其有长期关系的 人与对待那些以后不再交往的人可能会有非 常不同的行为。短期难以形成某种默契或合作关系，而长期可以通过报复、制裁的威胁来相互约束各方的行动。4.1.2 基 本 概 念 一般地,重复博弈就是指在每个周期中,参与人 面对的是同样的博弈,经典的重复博弈是指每 个周期有相同的参与人集合、相同的策略空 间以及相同的得益函数的重复博弈。4.2 有 限 重 复 博 弈 有限重复博弈简单地说就是阶段博弈实施有限次(T次)。如我们考虑T2。考虑下列博弈：L RU 1，1 5，0D 0，5 4，412 它有一个Nash 均衡(U,L),假设博弈进行两次, 两阶段重复博弈中每个参与人的得益相当于 各个阶段得益之和(或者平均数),考虑到贴现 因子,再一次借助于后退归纳法, 第二阶段 唯一的Nash均衡为(U,L),得益向量为(1,1),所 得的贴现值为(,),由此在第一阶段相当于 博弈:L R U 1+,1+ 5+,D ,5+ 4+,4+12 该博弈有唯一的Nash均衡(U,L),因此我们得到唯一的子博弈完美Nash均衡:(U,L),(U,L) 定 义 令G=S1,S2,Sn;u1,u2,un,G重复T次, 称G为T阶段博弈,G(T)表示实施了T次的重复 博弈。 在某次阶段博弈之前，所有已采取过的前面 阶 段的行动都可以观测到，参与人在G(T) 中的 得益简单地来自T个阶段博弈得益的贴现值之 和。另外G(T)的得 益也可以定义为T个阶段博 弈的贴现值的平均,它与贴现值之和仅相差常数因子1/(1+ + ), 并不影响子博 弈完美的结局。 定 理 如果阶段博弈G有唯一的Nash均衡，那么对任意有限次重复博弈G(T)有唯一的子博弈完美结局:在 每一阶段取G的Nash均衡策略。 2 T 例例 连锁店悖论连锁店悖论(Selten)(Selten)设有如下市场进入博弈设有如下市场进入博弈进入者进入者在位者在位者不进入不进入 进入进入默许默许 斗争斗争(0,300)(40,50) (-10,0)策略式默许默许 斗争斗争进入进入 40,50 -10,0不进入不进入 0,300 0,300在位者在位者进入者进入者Nash均衡为(进入,默许)和(不进入,斗争)但后者不是子博弈完美。 假定同样的市场有20个(可以理解为在位者有20个联锁店), 进入者每次进人一个市场,博弈就成了20次的重复博弈。人们也许会猜想，尽管从一个市场看，在位者的最优选择是默许，但因为有20个市场要保护，为了防止进入者进入其他19个市场，应该选择斗争，但子博弈完美的结果为进入者在每一市场选择进入，而在位者总是选择默许。 例 三 价 博 弈 的 重 复 博 弈H M LH 5，5 0，6 0，2M 6，0 3，3 0，2L 2，0 2，0 1，1厂商厂商1厂商厂商2其中H表示高价，M表示中价L表示低价。该博弈有两个Nash均衡： (M,M) 和(L,L)。 策略组合 ： ( H，H) 对双方最有利, 但不是Nash 均衡。两次重复博弈情况会有变化吗？12225,5) (0,6) (0,2) (6,6) (3,3) (0,3) (2,0) (2,0) (1,1)H M L H M L H M L两次重复博弈共有99=81种纯策略组合(路径),这时,子 博弈完美有多个,但重要的是:存在在第一阶段取(H,H)的子博弈完美 双方的策略是这样的:博弈方1:第一次选H,如果第一次结果为(H,H),则第二次选择M;如果第一次结果为其它任何组合,则第二次选L。(触发策略)博弈方2的策略与博弈方1相同。在双方的上述策略组合下,两次重复博弈的路径一定为第一阶段(H,H),第二阶段(M,M)。如果上述博弈是进行n次,仍可采用“触发策略”实现比较好的结果。触发策略在重复博弈的分析中有非常重要的作用,但上例中的触发策略也存在可信性的问题,因为参与人在报复对方的偏离时,自己也会受到损失,故也可能是未偏离的一方不计前嫌,在第二阶段与对方共同采用M,这对他自己也是有利的。 实际上,触发策略中的报复机制的可信性是一个很复杂的问题,会受到相互预期等很多复杂因素的影响。 H M LL 8 ,8 3, 9 3, 5M 9, 3 6, 6 1, 3L 5, 3 5, 3 4, 4 重复两阶段三价博弈的等价博弈重复两阶段三价博弈的等价博弈:不可不可信报复信报复,最佳选择为最佳选择为(M,M)两市场博弈的重复博弈在某些场合其他策略可能比触发策略更有效,如两个厂商同时面临市场机会A和B,得益如下表:表中得益意味着市场A较大但开发程度很低,市场B较小但开发程度高,这个博弈的两个纯策略Nash均衡和一个混合策略的Nash均衡的结果都不很理想。如果该博弈重复两次双方会采用什么策略?这时有多种子博弈完美的均衡路径,但双方均采用“轮流策略”是比较好的。A 2 BA 3 , 3 1, 41B 4, 1 0, 0厂商厂商2厂商厂商1(1,4)(3,3)(2,2)(4,1)(1.5,3)(3,1.5)(2.5,2.5)两市场博弈及其重复博弈各均衡的两市场博弈及其重复博弈各均衡的平均得益平均得益有限次重复博弈的无名氏(Folk)定理用wi i记博奕方i在一次性博弈中最差的均衡得益,w=(w1 1,w2 2,wn n),不管其他方的行为如何,一个博弈方在某个博弈中只要采取某种特定的策略,最低限度保证能获得的得益称为“个体理性得益”或“保留得益”(wi=min(max u(i i,- -i i);博弈中所有纯策略组合的的加权平均(凸组合)数组称为“可实现得益”有限次重复博弈的无名氏定理:设原博弈的一次性博弈得益组合优于w,那么在该博弈的多次重复中,所有不小于个体理性得益的可实现得益,都至少有一个子博弈完美的Nash均衡的极限的平均得益来实现他们。-i iW=(1,1)W=(1,1)(4,1)(3,3)(1,4)厂商厂商1两市场博弈有限次重复的无名氏定理两市场博弈有限次重复的无名氏定理厂商厂商24.3 无 限 次 重 复 博 弈 如果囚徒的困境实施一次或有限次,则两个囚徒“总是坦白”构成了子博弈完美均衡，但如果 该博弈不断重复地实施，而每存在博弈前可以 看到以前各次所采取的行动 ,就可以认为是无 限重复博弈(这里的“无 限”可以理解为不固 定次数)。 前面已经看到: 在有限次重复博弈中,如果G有多重Nash均衡可能存在这样子 博弈完美: 对 任意的tei 对 任 意 的i 都成立, 而充分接近1,那么 无限次重复博弈G(,)中一定存在一个子博 弈完美Nash均衡,使得各方的平均得益就是(x1,x2,xn)。 第 五 章 有 限 理 性 和 进 化 博 弈5.1 有 限 理 性 的 分 析 框 架5.1.1 有 限 理 性 及 其 对 博 弈 的 影 响 传统的博弈均衡,特别是Nash均衡及其完美是以博弈规则、参与人的理性以及参与人的得益 都是共同知识(common knowledge)为前提的， 这并不完全符合现实。 进化博弈的基本思路是：有限理性的经济主体不可能正确地知道自己所处的利害状态，它只是通过它认为最有利的策略逐渐模仿下去， 最终到达 一 种 均 衡状 态。在这样 变化的系统中，采用得益高的策略的参与人的比率逐渐上升。 博弈论分析研究的是参与人在特定的问题中的 行为和策略，因此重要的不是人们始终一贯 的理性，而是在具体问题上的理性，因此在具体问题中完全理性的假定仍有可能成立，但理性的局限的情况也很普遍。在分析复杂问题时就可能具有很大的理性局限性。 如果具体的博弈中博弈方不满足完全理性的假 设，称为有限理性博弈方(boundedly rational player)，相应地有有限理性博弈。 完全理性包括理性知识、分析推理能力、识别判断能 力和准确行为能力等多方面 完美性要求，其中任何 一方不完美就不是完全理性。但有限理性有多种情况和层次：较高的层次和较低的层次。 有限理性意味着博弈方往往不会一开始就找到 最优策略而是会“在战争中学习战争”，必须通过“试错”来寻找较好的策略。5.1.2 有 限 理 性 博 弈 的 分 析 框 架 在有限理性博弈中具有真正稳定性和 较强预测 能力的均衡，必须是能够通过博弈方的模仿、 学习的调整过程达到的，具有能经受错误偏离的干扰 的均衡，是在受到少量干扰后仍然能够“恢复”的均衡。这时博弈分析的核心不是博弈方的最优策略的 选择，而是有限理性的博弈方组成的群体成员的策略调整过程、趋势和稳定性，这里的稳定性是指采用特定 策略的成员的比例不变，而非某个博弈方的策略不 变 有限理性博弈分析的关键是确定博弈方学习和 调整的模式(机 制)，进化博弈主要采用的是 生物进化的“模仿者动态”机制模拟博弈方 的学习和动态调整，但由于博弈方的学习能 力的差异，需要多种机制来模拟。 具有快速学习能力的是“最优反应动态”; 学习速度很慢的是“ 模仿者动态” (replicator dynamics )。5.2 最 优 反 应 动 态 前提:少数有快速学习能力的有限理性的博弈方 之间的反复博弈和策略进化这种分析框架对博 弈方的理性假设为相当快的学习能力,虽然在 复杂局面下准确判断分析和运用预见性的能力 较差,但它们能对不同策略的结果作出比较正 确的事后评估并相应地调整策略。5.2.1 协调博弈的有限理性博弈方快速学习模型 例 一个群体有5个人,进行下述“协调博弈”:A BA 50,50 49,0B 0,49 60,60该静态博弈有两个Nash均衡:(A,A)和(B,B),但(A,A)是风险上策均衡,由于Nash均衡的多重性,即使博弈方则高度理性的也很难作出保险的预测。模仿者动态和进化稳定性两人对称博弈设某一群体进行对称阶段博弈,在重复动态博弈 中,假定所有的参与人均采用纯策略,每一个参 与人只代表某一特定的群体。令t(s)表示所有在t阶段采用策略s的参与人集合,则t(s)=t(s)/t(s)为在t阶段采用纯策略s的参与人在群体中所占的比例,故在t阶段采用策略s的参与人的期望效用为:ut(s)= t(s)u(s,s)群体的平均期望效用为ut= t(s)ut(s) sSsS- 假定每个参与人通常采取某种纯策略，并将长期 坚持下去,每类参与人的净增长率与他们在阶段博弈中的所得成正比： (t(s)/t(s)=ut(s)这时dt(s)/dt=t(s)ut(s)ut 这表明一个群体采用的策略的效用为负即意味着 增长率为负，采用这种策略的人数在群体中会逐 渐减少。 如果一种策略组合不是Nash均衡。它就不可能是 稳定的。5.3.1 同类群体模仿者动态的稳定性 问题 模仿者动态稳定性会使Nash均衡完美吗? 即通过稳定性的讨论,能否缩小Nash均衡的范 围? 模仿者动态一定收敛于稳态吗? 或者说,是否稳定的模仿者动态是唯一长期可能的结果? 结论是: 稳定性的讨论使Nash均衡完美是可能 的,模仿者动态不一定收敛于稳态。例A BA 0，0 1，1 B 1，1 0，0 例 “石头-剪子-布”博弈 R S PR 0,0 1, 1 1,1S 1, 1 0,0 1,1P 1, 1 1, 1 0, 0其中其中R:石头石头;S:剪子剪子; P:布布5.3.3 协调博弈的模仿者动态和均衡稳定性 50， 50 49， 0 0， 49 60，60 模仿者动态方程为；dx/dt=x(1x)(61x11)x*=0,x*=1是ESS,x=11/61不是。 进化博弈的结果常常取决于初始状态，但x*=1实现的可能性要大得多(概率为50/61), 如果初次 进行这个博弈是群体成员的x落在0,1区间上任一点的概率相同。111/61O5.3.4 鹰 鸽博弈的模仿者动态和进化稳定性Hauk DoveHauk (v-c)/2,(v-c)/2 v,0Dove 0, v v/2,v/2 v代表双方争夺的利益c是争夺失败一方的损失 模仿者动态方程为：dx/dt=x(1x)x(vc)/2(1x)v/2设v=2,c=12则方程为dx/dt=x(1x)(16x)因为F(0)0,F(1)0,F(1/6)u(,(1-)+)即ESS要求在群体混合策略(1-)+中能够得到比突变体更高的效用水平。由效用函数的线性性质,我们有:(1-)u(,)+u(,)(1-)u(,)+u(,)这一不等式只要求在接近于0时成立,它等同于要求对于所有的以下两式必有一式成立:u(,)u(,)或u(,)=u(,)且u(,)u(,)上述不等号如换为号则称为弱ESS。定义定义 如果策略满足:u(,)u(,),对任意,若u(,)=u(,)则u(,)u(,)则称为ESS策略。 在两个或多个有差别的博弈方群体成员相互间 随机配对, 这时就成了非对称博弈,可用双矩阵 来表示:(A,B),设X=(x1,x2,xn)和Y=(y1,y2,yn)分别为双方的混合策略,则有动态方程:dxi i/dt=xi i(AY)i iXAY,i=1,2,ndyj j/dt=yj j(BX)j jYBX,j=1,2,n例 市场进入博弈的模仿者动态和ESS进入进入 不进不进打击打击 不打不打(1,5)(0,0) (2,2)打击打击 不打不打进入进入 0,0 2,2不进不进 1,5 1,5这时由稳定性理论分析结果知进化稳定策略只有(x*,y*)=(1,0)这一点,其他所有的点都不是模仿者动态中收敛和具有抗扰动的稳定状态。这意味着有限理性的博弈方通过长期博弈学习,潜在的进入者会进入,在位者会容忍。非对称鹰鸽博弈的进化稳定分析现在我们设v1=10,v2=2,c=12,得下列博弈:进化稳定策略为(x*,y*)=(1,0),(0,1)鹰 鸽鹰 (v1-c)/2,(v2-c)/2 v1,0鸽 0, v1 v1/2,v2/212在非对称的情形中,一个目标对双方有不同的价值,如v1v20,再设其他方面与对称博弈一样。鹰 鸽鹰鹰 -1,-5 10,0鸽鸽 0,2 5,121Y15/6O 1/6 1 xADCB 第 六 章 完 全 但 不 完 美 信 息 博 弈6.1 不 完 美 信 息 动 态 博 弈6.2 完美Bayes均衡 在完全但不完美信息博弈中,因为存在多节点信息集,一些重要的选择及其后续阶段不构成子博弈,所以仅满足子博弈完美性无法排除不可置信的威胁或承诺,无法保证均衡策略中所有选择的可信性,为此必须发展新的均衡概念。6.2.1 完 美Bayes 均 衡 的 概 念借助于子博弈完美的思想,新的均衡概念必须满足 一些基本要求。 为了说明这些基本要求，首先分析下面的例子：例122L M R (1,3)(2,1) (0,0) (0,2) (0,1)A B A BA BL 2,1 0,0M 0,2 0,1R 1,3 1,321该博弈的策略型如右图:它有两个Nash 均 衡:(L,A)和(R,B),由于该博弈没有真子博弈,子博弈完美的要求将自动满足,Nash均衡就是子博弈完美均衡;但直觉上,2选B是不合理的(劣策略),故2取B是一个“空头威胁”。p 1-p 上面的例子反映了一个重要的事实：在完全但 不完美信息博弈中，尽管(R,B)是子博弈完美 的,但仍然依赖于一个不可置信的空头威胁。之所以会发生上述现象,是因为2在他将要采取的信息集上不知道哪一个结会将会达到,因此他关于这个问题需要一个“信念”,由此提出下列条件:R1: 在每一个信息集,在该集具有行动的参与人关于博弈到达信息集中的哪一个结必须有一 个信念。 对于非单点信息集，信念是集中各个结上的概 率分布；对于单点集，信念则置概率1于单决 策集上。R2: 在给定的信念下,参与人的策略必须是序贯理性 的(sequentially rational),即在每一个信息集,具行动的参与人所采取的行动(以及参与人以后的 行动)在给定该参与人在该信息集上的信念与其 他参与人以后的策略下必须是最优的。如上例,我们在参与人2的信息集上赋与一个概率分布p,1-p作为信念,可以给出2的期望得益:若2取A为 1p+2(1p)=2p若2取B则为 0p+1(1p)=1p由于0p1,所以2p1p,根据R2的要求, 参 与人2不应取B。R3:参与人在均衡路径上信息集的信念，是通过Bayes 法则与参与人的均衡策略来确定的。 对完美Bayes均衡来说R1R3抓住了它的主要精神， 信念被提高到如同均衡定义中策略那 样重要的地位，但是，在较广泛的经济应用 中，将需要更多的要求以删除难以置信的均 衡，不同的作者使用不同的完美Bayes均衡的 定义，但有一 个共同点是都包含了R1R3， 大多数定义还包括了对非均衡路径上信念的 要求。我们添加如下的：R4： 在非均衡路径上信息集的信念通过Bayes 法则和参与人的可能的均衡策略来确定。 定定 义义 一个完美的Bayes 均衡由满足R1R4的 策略和信念信念组成。Bayes法则:在日常生活中,当面临不确定时,在任何一个时点上,我们对某件事情发生的可能性有一个判断(先验概率),然后,会根据新的信息来修正这个判断(后验概率),Bayes法则就是这样的方法。设参与人的类型是独立分布的,参与人i有K个可能的类型;有H个可能的行动,k和ak分别表示特定的类型和行动,则P(k)0,P(k)=1,i选择ak的概率为:PaK=P(a11)P(1)+P(aKK)P(K)=Bayes公式:Bayes法则要求P(aK)0,否则后验概率无意义。如果P(aK)=0,我们允许P(KaK)在区间0,1区间取任何值,只要所取的值与均衡策略相容。在动态博弈中,P(aK)=0对应的则为非均衡路径上的信息集。Bayes法则举例:如果我们把所有的人划分为好人(GP)和坏人(BP)两类;所有的事分为好事(GT)和坏事(BT)两类,如果我观测到某人干了件好事,则有PGT=PGTGPPGP+PGTBPPBPPGPGT=PGTGPPGP/PGT为具体起见,我们认为某人为好人的概率为1/2,那么在观察到告干了件好事后如何修正他是好人的概率?设:设PGTGP=1,PGTGP=0, 则PGPGT=1设PGPGT=1,PGTBP=1,则PGPGT=1/2,即无改变。设PGTGP=1,PGTBP=1/2,则PGPGT=2/3,即他是好人的可能性增大了。如果我们观察到这个人干了一件坏事,我们会怎样改变看法?设PBTGP=0,PBTBP=p0,则PGPBT=0,PBPBT=1,即他一定是一个坏人;如果我们原来认为他肯定是一个坏人,突然发现他干了一件好事,设PGTBP=p0,PGTGP=q0则PBPGT=1例(可能的均衡策略)该博弈的真子博弈有唯一Nash均衡(L,R),因此整个博弈有唯一的子博弈完美Nash均衡(D,L,R),这个策略组合是否是完美Bayes均衡?在参与人3看来,若1采用D,R是2的劣策略,因而p=1,在给定如此信念下,3的最优选择为R,1233AL R L R L R（2，0，0)(1，2，1 (3,3,3) (0,1,2) (0,1,1) p 1-pL RL 2,1 3,3R 1,2 1,132可见(D,L,R)与信念p=1满足要求R1-R3,由于该博弈树不存在任何一个信息集不在该均衡路径上,即R4 “平凡地”得到满足。于是它也是完美Bayes均衡。现在考虑另一个策略组合(A,L,L)以及信念p=0,这是一个Nash均衡,也满足R1-R3,但它肯定不是子博弈完美的(仅有的真子博弈有唯一的Nash均衡(L,R),这表明仅有R1-R3并不能保证参与人的策略是子博弈完美Nash均衡,问题在于参与人3的信念p=0与2的策略L并不相合(p=0意味着2取R而不是L),如果按(A,L,L)进行的话,3的信息集不能达到,即3的信息集不在Nash均衡(A,L,L)的路径上。故要求R4。 第 七 章 不 完 全 信 息 博 弈 完全信息博弈的主要特点是“参与人的得益是 “共同知识”(理想模式)。 如果至少有一个参与人不知道(或不确定)其他 参与人的得益函数,信息便成为不完全的。这 类博弈又称为Bayes博弈。具体的例子有“密 封投标拍卖”。7.1 静 态Bayes 博 弈 和Bayes Nash 均 衡7.1.1 静态Bayes博弈的例子 例 假定某行业有一个在位者(参与人1)和个潜在的进入者(参与人2),1决定是否要建一个新工厂,2决定是否进入该行业。假定2不知道1建厂的成本是3还是1,但1自己知道。进入进入 不进不进 进入进入 不进不进建厂建厂 0, 1 2, 0 建厂建厂 3, 1 5, 0不建不建 2, 1 3, 0 不建不建 2, 1 3, 02 21 11高成本时的得益矩阵高成本时的得益矩阵 1低成本时的得益矩阵低成本时的得益矩阵2的得益取决于1是否建厂, 而不是取决于1的成本, 但1有 一个优势策略:低成本则建厂; 高成本则不建厂。设p1为2认为1为高成本的先验概率(主观概率): 因为当且仅当1为低成本时才会建厂,因此,只要 p11/2,2就会进入;而当p11/2时,2会选择不进入,因为选择进入的期望利润是: 1p1+(1)(1p1)=2p110而不进入的期望值为0。Harsanyi 首先给出了一种模拟和处理这一类不 完全信息博弈的方法,他引入了一个虚拟的参 与人“自 然”,“自然”先选择参与人1的类 型(这里是他的成本),形成如下博弈:N112222 高成本高成本 低成本低成本p 1p 建厂建厂 不不 建建 建建 厂厂 不不 建建 进进 入入 不不 进进 进入进入 不不 进进 进进 入入 不不 进进 进进 入入 不不 进进(0,-1) (2,0) (2,1) (3,0) (3,-1) (5,0) (2,1) (3,0)不完全信息意味着至少有一个参与人有多个类型(否则就成为完全信息博弈),在上例中,在位者有两个类型,进入者有一个类型。在n人静态Bayes博弈GA1,An;T1,tn;p1,pn;u1,un中,参与人i的得益函数不仅依赖于行动组合(a1,a2,an),而且依赖于所有的类型(t1,t2,tn),故可记ui(a1,an;t1,tn),为求期望得益,需要计算信念pi(t-iti),设自然按照先验分布p(t)抽取类型向量t=(t1,tn),这是一个共同知识,当自然向参与人i展示其类型ti时,参与人 i可以通过Bayes法则计算信念p(t-iti):常假设参与人的类型是随机独立的,于是信念:pi(t-iti)=p(t-i),这时计算公式为:参与人i的策略是类型ti的函数si(ti),即对类型空间Ti中的每一个类型ti,si(ti)在自然抽取类型ti时I从可行集Ai所选择的行动。当所有参与人采取了策略组合s=(s1(t1),sn(tn)时,类型ti的参与人i的条件期望得益为:定义n人静态Bayes博弈的策略式表述包括参与人的行动空间A1,A2,An和相应类型空间T1,T2,Tn,以及它们的信念p1,p2,pn及各参与人的得益函数u1,u2,un。其中参与人的类型ti为的私人信息,它确定了的ui(a1,a2,an;ti):,tiTi,(i=1,2,n), 的信念 p(t-iti)为在给定自己的类型ti的条件下关于其他n1个参与人可能类型t-i 的条件概率,我们记这类博弈为:G=A1,A2,An;T1,T2,Tn;p1,p2,pn;u1,u2,un)Harsanyi 转换: 将不完全信息弈 通过引进虚拟的 参与人“自然”而转换为完全但不完美信息博弈 的方法称为Harsanyi转换。n人静态博弈GA1,An;T1,Tn;p1,pn;u1,un中,参与人i的得益函数不仅依赖于行动组合(a1,.a2),而且依赖于参与人的类型(t1,tn),为求期望得益,需要计算信念pi(t-iti),设自然按照先验分布pt抽取向量(t1,tn)是一个共同知识,当自然向参与人i展示其类型ti时,i可以由Bayes法则计算信念: pi(t-iti)=p(t-i,ti)/p(ti)=p(t-i,ti)/ p(t-i,ti)当参与人的类型是随机独立时: pi(t-iti)=pi(t-i)=pi(t1,ti-1,ti+1,tn)=p(t1,t i-1,ti+1,yn)参与人i的策略是类型ti的函数si(ti),当所有的参与人采取了策略组合Ss1(t1),sn(tn)时,类型ti的参与人的期望效用为:Eui(si(ti)=ui(s-i(t-i),si(ti),ti,t-i)pi(t-iti)t-iT-i定义 在静态Bayes博弈G(A1,An,T1,Tn,p1,pn)中,策略s*=(s1*,sn*)是一个(纯策略)Bayes均衡,当且仅当对每一个参与人i和Ti中的每一个类型ti,以及 的每一个其他策略s i (ti),总有:Eui(s*,ti)Eui(s1*(ti),si-1*(ti-1),si(ti),si+1*(ti+1),sn*(tn),ti) 就是说，无论参与人是属于何种类型，参与人的 策略一定是关于其他参与人策略的最佳反应。例在上例中设p=1/3则有策略式: ( 建建, 建建) ( 不不 , 建建) ( 建建, 不不) ( 不不, 不不) 进进 入入 1,(-1, 2) -1/3, (1, 2) 1/3, (-1,-1) 1, (1, 1) 不进不进 0, (0, 4) 0, (3, 4) 0 ,(0, 3) 0,(3, 3)在位者在位者进入者进入者该博弈有唯一的该博弈有唯一的Nash均衡均衡不进入不进入,(不建不建,新建新建)7.1.2Bayes 均 衡 的若干例子 例 不完全信息下提供公共产品 公共产品的供给产生了著名的搭便车(free-rider) 问题。 这里仅考虑一个简单的例子：有两个参 与人i=1,2,他们同时决定是否向公共部门捐款， 捐款可用01决策来表示，要么捐款要么不捐 款，设参与人i捐款外ci，则有得益矩阵： 捐 款 不 捐 款 捐款捐款 1c1,1-c2 1-c1,1 不捐款不捐款 1，1c2 0, 0 只要有人捐款则各人获益为，这是共同知识，至于 捐款多少：c1与c2分别为参与人1和2的私人信息。但是双方都相信“ci独立地来自c,c c上一个连续且严格增加累积分布P(.)”是共同知识,其中c1bj(vi-bi)/2 如果bi=bj0, 如果bibj(vj),理性地,i的标价bi应满足ajbiaj+cj这时期望得益为:利用一阶条件,易知I的最佳反应为bi=(vi+ai)/2,由于bi必须大于aj,因此若vipb,双方在p=(ps+pb)/2上成交;如果pspb没有交易发生,双方的得益均为0,如果在不完全信息的情况:这时c和v都分别是双方的私人信息(因而是双方的类型),假定c和v在0,1上均匀分布,P.为共同知识。7.2 机制设计与显示原理迄今为止,我们只是对给定的博弈问题,设法寻找它的均衡解。实际生活中,存在着有意义的实际问题:给定n个参与人,在一系列可能的结果中给定他们的得益,以及他们有关这些得益所拥有的私人信息,是否能构造出一个静态Bayes博弈,使得该博弈的Bayes Nash均衡满足一定的特殊的性质?我们首先考虑如下一个具体的例子:一个卖者有一个单位的不可分割的商品要出卖,有两个潜在的买者i=1,2,每个买者的需求是1或0,该商品对买者1和买者2的价值分别为1和2,假定1和2是独立的,具有相同的分布函数,特别地,假定i只有两个可能的值: 和,其中sj j,xi i(s1 1,s2 2)=1,xj j(s1 1,s2 2)=0,Ti i(s1 1,s2 2)=si i ( (sj j) ), Tj j(s1 1,s2 2)=0, ij为了简单起见,只考虑纯策略均衡。假定 s1*(.),s2*(.)是这个博弈的纯策略Bayes均衡, 因为买者有不买的自由,买者1的参与约束参与约束是:(IR) 这里IR表示个人理性,由Bayes均衡的定义,买者的 激励相容约束是:(IC)卖者2的参与约束和激励相容约来可以类似地给出,假定卖者的供给成本为0,则卖者的期望效用为:卖者的问题是在满足两个卖者的参与约束和激励相容约束的条件下,选择信号空间Si,分配函数xi(s1,s2)和价格,以最大化上述期望效用函数。如果我们不得不考虑所有可能的信号空间,找出最优拍卖机制几乎是不可能的,但根据下面要讨论的显示原理,我们可以把注意力集中于“直接显示博弈”(direct revelation game):将信号空间Si选择为类型空间i=,两个买者同时宣布自己的类型(1,2)(他们可能说谎)- 为了说明这点,定义:在这样定义的分配函数和价格函数下,参与约束保证买者愿意参加这个直接显示博弈,Bayes均衡是买者宣布自己的真实类型:即,如果在原博弈中si i=si i*(i i)是i的最优选择,那么在直接博弈中,将选择i i=i i。机制设计与显示原理机制设计与显示原理假设有n+1个参与人,其中i=0是委托人,i=1,2,n是代理人,委托人没有私人信息,代理人的类型i是私人信息,假定类型空间=i ii i的概率分布P(.)是共同知识,委托人的机制设计的任务是决定一个配置函数: y=(x(.),t(.),其中x是决策向量,t=(t1,t2,tn)是从委托人到代理人的转移支付向量。假定每个参与人i(i=0,1,2,n)有一个von Neumann Morgenstern效用函数ui(y,),u0是ti i的递减函数,ui i(i=1,2,n)是ti i的严格递增函数,ui i都是二阶连续可微的。一个机制m给每个代理人i规定一个信号空间Mi i,如果代理人在第二阶段接受机制,他就在第三阶段选择i iMi i,所有代理人的选择信号=(1,2,n)共同决定配置结果y=(x,t),我们用ym:MY=XR 代表配置函数。因为代理人的类型是私人信息,配置函数y=(x,t)只能通过代理人发出的信号依赖于代理人的类型。但是,不论委托人设计什么机制,配置函数最终依赖于代理人的类型:=(1,2,n)。给定类型依存配置y()具有类型i i的代理人的期望效用函数是:n委托人的期望效用函数是: U0 0=Eu0 0(y(),)委托人可以选择任何一个满足代理人参与约束和激励相容约束的机制。但所有可选择的机制可以划分为两类:直接机制和间接机制,在直接机制中,信号空间等同于类型空间,即Mi i=i i,i=1,2,n,其他为间接机制。Myerson显示原理表明:任何一个机制所能达到的配置结果都可以通过一个(说真话的)直接机制来实现。因此,委托人只需考虑直接机制的设计。总结起来,有:定理(显示原理,Myerson),假定以Mi i为信号空间和以ym m(.)为配置函数的机制的Bayes均衡是:那么,存在一个以Mi i=i i为信号空间的直接显示机制: ,该机制的Bayes均衡是:所有代理人在第二阶段接受机制,在第三阶段同时报告自己的真实类型:=(1 1,2 2,.n n)。直接机制的均衡配置结果与原机制的配置结果相同。不完全信息与资源配置效率不完全信息与资源配置效率机制设计理论研究的一个重要着眼点是讨论不完全信息与个人理性约束一起如何影响资源的有效配置(对比Coase定理)Myerson-Satterthwaite无效率定理:假定卖者的成本和买者的价值分别在区间c, ,和区间v,v上有严格正的可微密度函数,存在正的概率交易是有效率的(cv),那么,不存在一个满足参与约来、激励相容约束和预算平衡约束的机制,使得所有有效率的交易机会都被利用。这里的预算平衡约束是指卖者的所得等于买者支付的价格。-7.3 混 合 策 略 的 再 解 释 例 抓 钱(grab the dolla) 博 弈: 每个参与人有两个可能的行动:投资(“抓”)或不 投资,在完全相信博弈中两人的得益如下: 抓抓 不不 抓抓 抓抓 -1, -1 1,0 不抓不抓 0,1 0,0该博弈有唯一的混合策略Nash均衡1=2=(1/2,1/2)。现在我们稍微扰动一下得益矩阵,即对部分得益赋予一个小的“ 随机干扰”: 投投 资资 不不 投投 资资 投资投资 -1 ,-1 1+1, 0 不投资不投资 0, 1+2 0,0 其中i在-,上均匀地分布。12这是一个不完全信息的Bayes博弈,如果把“抓钱”看作投资,不论公司属于什么类型,它们依然各有两个策略:投资或不投资,信念密度为:如果当1超过某临界值x时,公司1投资,否则就不投资;同样,如果2超过某临界值y时,公司2投资,否则就不投资,x.y-,。公司1投资时的期望利润为:时公司1投资;类似地,只有当时公司2投资,将上面两式联立,解得:x=y=0。于是我们得到对称的纯策略Bayes均衡解为:公司i当i i0时投资,当i i0),当b0时双方偏好趋于一致。(Crawford & Sobel模型)8.3 信号博弈信号传递博弈是一种比较简单但有广泛应用意义的不完全信息动态博弈。在这个博弈中,有两个参与人i=1,2:参与人1称为信号发送者,参与人2称为信号接收者,参与人1的类型是私人信息,参与人2的类型为公共信息(即只有一个类型)。博弈的顺序如下:(1)自然首先选择参与人1的类型tiT=t1,t2,tK参与人1知道ti,但参与人2不知道,只知道1的类型的先验概率p(ti),p(ti)=1。(2)参与人1在知道自己的类型后选择发出信号mM=m1,m2,mJ。(3)参与人2观测到参与人1发出的信号(但不是类型)使用Bayes法则从先验概率p=p(ti)得到后验概率p=p(tim),然后选择行动aA=a1,a2,aH;(4)双方的得益函数为u1(m,a,ti)和u2(m,a,t )。下图是一个简单的信号传递博弈的展开式表述,这里K=J=H=2,p=p(t1m1),q=p(tim2)(省略了得益):N112222ti t2 p 1-pm1 m2 m1 m2P q 1-p 1-qa1 a2 a1 a2 a1 a2 a1 a2令m(t)是参与人1的类型依存信号策略,a(m)是参与人2的行为策略(允许混合策略),则有定义定义: 信号传递博弈的完美Bayes均衡是策略组合(m*(t),a*(m)和后验概率p(tim)的结合,它满足: 信号博弈的所有可能的完美Bayes均衡可以划分为以下三类:分离均衡分离均衡(separating equilibrium):不同类型的发送者(参与人1)以概率1选择发送不同的信步,这时信号准确地揭示出类型,在K=J=2时:u1(m1,a*(m),t1)u1(m2,a*(m),t1);u1(m2,a*(m),t2)u1(m1,a*(m),t2);因此,后验概率是:p(t1m1)=1,p(t1m2)=0;p(t1m1)=0,p(t2m2)=1。混同均衡混同均衡(pooling equilibrium):不同类型的发送者(参与人1)选择相同的信号,或没有任何类型选择与其他类型不同的信号,因此接收者(参与人2)不修正先验概率(参与人的选择没有信息量)。设mj是均衡策略,那么: u1(mj,a*(m),1)u1(m,a*(m),1) u1(mj.a*(m),2)u1(mj.a*(m),2) p(k|mj)p(k)准分离均衡准分离均衡(semi-separating equilibrium):一些类型的发送者随机地发送信号,另一些类型的发送者选择特定的信号。假定类型1的发送者随机地选择m1或m2,类型2的发送者以概率1选择m2,如果这个策略组合是均衡策略组合,那么: u1(m1,a*(m),1)=u1(m2,a*(m),1) u1(m1,a*(m),2)u1(m2,a*(m),2) p (1|m1)=P (1|m2)=P (2|m2)=在所有上述三个定义中,都应该适当加上参与人2的最优化条件和非均衡路径上的后验概率,在只有两个类型和两个信号的情况下,只有混同均衡有非均衡路径,分离均衡和准分离均衡的所有信息集都在均衡路径上。但一般说来,如果信号的种类多于类型的种类,每种均衡下均有非均衡路径。8.4 展开型博弈的序贯均衡(Kreps & Wilson)我们用 表示展开型博弈,参与人集是1,2,n对任一参与人i,用Hi表示i的所有可能的信息状态所组成的集合,当ij时,HiHj=,记H=Hi。对于任一参与人i和Hi中的任一信息状态hi,A(hi)表示i在信息状态hi处的所有可利用的行动组成的集,在展开型博弈中,一个参与人的纯策略是在博弈中每一个可能的信息状态都规定一个行动的一个函数。为纯策略空间,混合策略被定义为纯策略空间的任一概率分布,i的行为策略 即一个混合策略为参与人在进行博弈时的整个策略集上确定的一个概率分布;而一个行为策略则为他在每个可能的信息状态下确追其可能行动集上的一个概率分布。定理 对于任一具有完美回忆的展开型博弈,总存在一个行为策略的Nash均衡。如果当信息状态hi实际发生时参与人i将确定会按照某个策略为他在hi处确定的行动去做,则称参与人i的这个策略对他来说是在Hi中的信息状态hi处序贯理性的。包含结点x的信息集记为h(x);在x处行动的参与人i记作i(x),i(x)在结x处的混合或行为策略记作i(|x)或i(|h(x),表示所有策略组合=(1,2,n)的集合的全体,当策略组合给定时以 分别表示结x和信息结到达的概率,这些概率明显依赖于先验概率p,信念体系确定了在每个信息集h上的信念:(x)表示参与人i(x)基于信息集h(x)已到过所赋予结x的条件概率。(一般用.表示先验概率,用表示后验概率)例1223330.5 x1 0.5x2 y20.2 0.8 0.8 0.2x3 y3 w3 z7z1 z2 z3 z4 z5 z61 0 1 0 1 0 计算如下:现在回顾一下完美Bayes均衡的四点要求:(R1)在每一个信息集,在该集具有行动的参与人关于博弈到达信息集中的哪个结必须有一个信念信念。(R2)在给定的信念下,参与人的策略必须是序贯序贯理性理性的。即在每一个信息集,具行动的参与人所采取的行动(以及往后的行动)在给定该参与人在该信息集上的信念以及其他参与人以后的策略下必须是最优的。(R3)参与人在均衡路径上的信念,是通过Bayes法则和参与人的均衡策略来确定的。(R4)在非均衡路径上信息集的信念通过Bayes法则和可能的均衡策略可能的均衡策略来确定。令ui(h)(|h,(h)表示参与人i(h)(即信息集h上有行动的参与人i)在信息集到达,参与人的信念为下的期望得益。我们称(,)为一个状态,它确定了个策略组合和一个信念体系,所有可能的状态的集合记为。前面提到的序贯理性,用本节引进的记号与说法就是说,给定了信念体系,没有一个参与人可以通过任意信息集上的偏离而获益:(S) 状态(,)如果满足下列条件:则称(,)是序贯理性序贯理性的。令 表示所有完全混合(行为)策略的集合,即策略组合中所有满足:令 表示所有满足下述条件的状态(,)的集合: ,(唯一地)通过Bayes法则由所确定。 (c)状态(,)称为一致性的,如果存在 中的某状态序列 ,使得:定义 (KrepsWilson) 满足条件(S)与(c)的状态(,)称为序贯均衡序贯均衡。例 回到前面的“摊牌博弈”一致性要求(c)是序贯均衡概念最重要的创造,也可理解为均衡(,)的“颤抖”;颤抖使得Bayes法则适用于博弈的所有路径。1122x1 x21/3 2/3U D U D 1 0 0 1如图若参与人如图若参与人1的最优策略为的最优策略为U,则参则参与人与人2的信息集为非均衡路径的信息集为非均衡路径,如如1偏偏离均衡选择了离均衡选择了D,2的后验概率应如何的后验概率应如何呢呢? y1 y21不能区分x1和x2,因此1在两个结上偏离的可能性应当一样,故2应认为(y1)=1/3,(y2)=2/3。但D为0概率事件,任何(y)都与Bayes法则相容,这时,一致性条件(c)可以给出正确的结论。考虑收敛于零的序列:这样,颤抖保证了参与人2的后验概率尊重了原来的信息结构。有关序贯均衡的结论:(1)存在性定理 任何有限展开型博弈至少存在一个序贯。(2)序贯均衡与完美Bayes均衡的关系。定理(Fudenberg & Tirole,1991)考虑具有独立类型的不完全信息多阶段博弈,如果参与人至多有两个类型,或者博弈有两个周期,完美Bayes均衡和序贯均衡的集合是一致的。例 在如图所示的博弈中,可能的序贯均衡为A与(R1,R2)。我们仅考虑参与人取A的结局,将验证状态:(1(A)=1,2(L2)=1,(w1)=1)是序贯均衡。也就是要验证它满足条件(S)和(c)。条件(S)的满足是显然的,因为在2(L2)=1的情况下,参与人1不可能偏离行动A,关键在于验证一致性条件(c),是否满足。122(2,2)L1 R1A(0,1) (0,0) (1,0) (4,1)L2 R2 L2 R2w y考虑如下的颤抖:显然这个策略组合是完全混合策略。由Bayes法则:Selton颤抖的手均衡如图(D,L)是一个Nash均衡,(U,R)是一个颤抖的手均衡定义 在n人策略式博弈中,Nash均衡(1,2,n)是一个颤抖的手均衡,如果对每一个参与人i,存在一个严格混合策略序列使得:U 10,0 5,2D 10,1 2, 0L R非合作博弈均衡概念的简要总结(不同均衡之间的关系):颤抖手均衡序贯均衡完美Bayes均衡子博弈完美均衡NashNash均衡均衡 习 题1.求出下列博弈的策略式表示:N11221/3 2/3z1 y1 w1 x1 b2 a2 b2 a2(2,6) (5,6)(0,3) (9,0) (0,3) (9,5)并求出它的所有序贯均衡,并对每个序贯均衡给出所有的行动概率和信念概率。第九章 合作博弈简介一、双人博弈的讨价还价与合作9.1 合作博弈理论的非合作基础合作意味着“为共同的目的而一起行动”。由此,个人不得不置其各自的效用函数于不顾,而创造某个全新的、用于决定他们集体行为的集体效用函数。但这又与博弈论的基本假定相冲突,因此,我们需要那种不放弃个人决策论基础的合作行为模型。Nash(1951)提出,研究参与人之间的合作,可以利用Nash均衡这一基本概念。他认为合作行动是参与人之间某种讨价还价讨价还价(bargaining也译为谈判)过程的结果,并且在这个讨价还价的过程中,可以预期每个参与人都应该按照某个讨价还价策略来行动、以满足个人效用最大化准则,就象在其他博弈中一样。不妨观察两个谈判者在进行谈判时的一般过程并找出规律:可以设想存在一系列可供双方选择的谈判方案,它们都是由参与人双方提出自己的要求以及相应的策略形成的。这些方案应该在实际中是可行的。所有这些可行方案的全体构成的集合称为可行集(feasible set),记为F由于在每一个方案中参与人1和2可以分别获得的得益分别为v1和v2,因此可以用v=(v1,v2)来表示一个方案,(v1,v2)F即表示方案(v1,v2)是可行的。双方都会有一个谈判的基点(底线),即双方认为都不能再让步的得益,设它们分别是v1和v2,双方分别以v1、v2为基础进行谈判,在双矩阵博弈G=(A,B)中:即以双方分别采取保守策略时的得益为基点。我们把讨价还价问题记为(F,v)，如果经过双方讨价还价,或者由一位仲裁人的裁定,最后得到一个能为双方共同接受的方案由 的过程看作一种映射,记此映射为:怎样求出讨价还价解?观察双方的行为可以得出一些共同遵守的规律,称之为公理。下述公理由Nash首先提出:公理公理1 1(个体理性)公理公理2 2(可行性)公理公理3 3(Pareto最优性)如果公理公理4 4(无关方案的独立性)若公理公理5 5(线性变换的无关性),设G是由F经由如下的线性变换:u1=a1v1+b1,u2=a2v2+b2得到的,如果其中a1,a2为正常数,b1,b2为常数。公理公理6 6(对称性)若F使(u1,u2)F(u2,u1)F并设 ,以及(F,v1,v2)=定理9.1 对于所有讨价还价问题(F,v1,v2),存在满足公理1-6的唯一函数。这个解函数满足:(v1,v2)F若集F有光滑的边界,则解(x1,x2)在F的边界上。在(x1,x2)作F的切线(F上的Pareto最优点集范围内的点都有可能成为Nash讨价还价解),此曲线的斜率表示参与人之间的得益转换比率,Nash讨价还价解实际上是在所增加的得益方面按得益转换的适当比例在参与人之间进行分配。 假定得益可以按线性方式转换,并设k为双方联合在一起时所能取得的最大得益:u1+u2=k,此时对应的Nash讨价还价解是:9.2 “威胁”(Threat)问题在讨价还价过程中,有时一方会利用自己的有利态势或地位来“要挟”对方,这便导致“威胁”问题。Nash提出了如下的讨价还价模式:(1)参与人1宣告要采取一种“威胁”策略x;(2)假设此时参与人2也宣布将要采取一种威胁策略y;(3)既然如此,双方分别宣布采取策略x和y,那么问题就变成双方各以x和y为谈判基点进行讨价还价,如果威胁不成,双方只好执行x和y,从而取得相应的得益。由Nash公理,此时应考虑:定理9.2 任何双矩阵博弈至少有一个关于威胁策略的解。例 考虑双矩阵博弈:解 在不考虑得益转移的情况下,双方的谈判基点为(0,0),相应的混合策略为x=(3/4,1/4),y=(1/2,1/2),Nash仲裁解为(x1,x2)=(5/2,5/2),但2若坚持采用b1策略,1确实没有多少反抗能力。b1 b2a1 1,4 -4/3,4a2 -3,-1 4,112(0,0)(1,4)(4,1)(-4/3,-4)(-3,-1) 习 题1对于下列两个双矩阵博弈(1) (2,1) (4,3) (2) (4,-30) (10,6)(2) (6,2) (3,1) (12,8) (5,4)(3)求出它们的的所有Nash均衡;并进一步求出协商(4)集、最大最小讨价还价解和威胁讨价还价解。(5) (6) 9.3 合作博弈中的联盟 由于可能出现联盟联盟,当参与人的个数n2时,不能把2人的讨价还价问题简单地推广到n人合作博弈中来。现在我们记参与人的集合为N=1,2,n,一个联盟就是指N的某个非空子集S,为了方便起见,有时称空集也是一个联盟,意即没有人参加的联盟。所有联盟的全体记为p p(N)(N)。关于n人合作对策,需要研究的两个基本而且重要的问题是:可能形成什么样的联盟?当联盟形成后所获得的(联盟的)得益如何分配给它的各个参与者?定义9.1 n人对策的特征函数是指定义在p(N)上的一个实值函数v,其中v(S)表示联盟经过协商其成员的策略所能保证得到的最大得益。规定v()=0若S是一个联盟,余下的参与人NS形成另外一个联盟,其策略集分别为XS和YNS则这个n人对策就好象是两个参与人S与NS在进行非合作对策,故它们的特征函数可以表示为:若S和T是两个不相交的联盟,即ST=,则有 v(ST)v(S)+v(T) (超可加性)上式等号成立称v具有可加性,特征函数具有可加性(即等号成立)的的博弈称为非本质博弈。这时:例1(石油市场博弈) 国家1有石油,若是自用,所获利润为a元/桶,国家2与国家3需要石油,若国家1把石油卖给国家2,则获利润忖b元/桶;卖给国家3,则利润为c元/桶,这里: abc,求这个市场博弈的特征函数。解 v()=0,v(1)=av(2)=v(3)=v(2,3)=0v(1,2)=b,v(1,3)=v(1,2,3)=c例2 (委员会博弈) 假设有某个委员会,有两个常设成员1与2,他们拥有否决权,另外还有3个普通成员,每通过一项决议,其得益是1。如果决议没有通过,得益为0,但要通过必须有3票赞成,且无人使用否决权,求这5人对策的特征函数。解: v(1,2,3)=v(1,2,4)=v(1,2,5)=v(1,2,3,4)=v(1,2,3,5)=v(1,2,4,5)=v(1,2,3,4,5)=1,其余为0。9.4 分配问题前面讨论的是n人博弈中可能形成什么样的联盟(使得益最大)以及度量联盟力量的一种方法(特征函数)下面来讨论第二个重要问题:联盟获得的得益如何合理地分摊给它的各个成员?这个问题十分重要,因为分摊不合理会影响联盟的形成,即使形成了也有破裂的危险,所以,n人博弈的重要部分是进行预先的协商,以确定联盟的形式以及关于关于博弈所获取的得益的分配方法。 注意,二人合作博弈与n人合作博弈的区别:前者只在策略上进行合作,而后者是联盟在博弈后的得益,要按事先讲好的分配方案进行分配。9.4.1 分配向量定义9.2 在特征函数为v的n人对策中,用xi表示第i个参与人所分得的份额,如果满足:则称向量X=(x1,x2,xn)为分配向量。条件(1)称为个体合理性条件;条件(2)称为群体合理性条件。分配向量全体所形成的集合记为F(v),在非本质博弈中在本质博弈中却有很多个分配向量,因为此时有:而把a分为n个非负实数a1,a2,.an有无穷多种分法。如前面石油市场博弈中有:在委员会博弈中有:定义9.3 设X和Y是两个分配向量,S是一个联盟,如果定义9.4 设X与Y是两个分配向量,如果存在某个联盟S使得 应当指出的是:对只有单个参与人的联盟或者包含所有参与人的大联盟来说,一个分配向量X绝不会优超另一个分配向量Y。9.4.2 核心 下面要考虑如何在分配集中选择一个或一些分配向量,使这些向量能够为联盟S中各个参与人所接受定义定义9.5 9.5 n人合作博弈(N,v)的核心核心C(v),是指在分配集F(v)中对任何联盟S均不能被优超的分配向量的集合。根据这个定义,若XC(v),则X是这个联盟的最佳分配向量,或者说,即使这个联盟更喜欢另一个分配向量Y,它也会由于 而无法将X改变为Y注意,在核心中可能有不止一个分配向量。定理 X在核心C(v)中的充分必要条件是: 定理中的条件(2)称为联盟的合理性条件。核心是一个凸集。但把核心作为解的一个缺陷是:核心有时是空集或比较大。例 石油市场博弈的核心是:C(v)=(x,0,1x)|bxc委员会博弈的核心是:C(v)=(x1,x2,x3,x4,x5)=(x,1x,0,0,0)|0x19.4.3 稳定集定义(von Neumann & Mongenstern) n人合作博弈(N,v)的稳定集S(v)是满足下列条件的分配集的子集:(1)如果X,YS(v),则X与Y之间没有优超关系;(2)如具Z不在S(v)中,则存在XS(v),使X优超Z。上述两个条件中,条件(1)被称为内部稳定性;条件(2)被称为外部稳定性。关系:9.3.4 核仁 这是合作对策的另一种解的概念,核仁又称为核子把核仁作为解,主要基于它有两个十分有用的性质:(1)每一个博弈有一个且只有一个核仁;(2)如果核心存在,则核仁是核心的一部分。 核仁依据的基本思想是:当分配向量属于核仁时,最不理想的联盟也要优于其他分配向量的最不理想联盟。 对任何分配向量X和任何联盟S,记则每个联盟都会考虑v(S)X(S)的大小,这个数表示联盟自己能得到的与实际上所得到的报酬的差额,差额越大,采取这个分配X的联盟对X越不满意,现将所有联盟 的超出值从大到小排列起来,得到一个向量,记为(X):它反映了对分配向量X,各联盟的满意程度。 现在给定分配向量X和Y,我们要按照下述办法来比较X与Y的优劣,设采用分配向量X时最不理想的联盟为S,而采用Y时最不理想的联盟为S,对这两个联盟,分别计算v(S)X(S)和v(S)Y(S),其差值较小的表示“较好的”一种分配,如果两者相等,再考虑第二对不理想的联盟,再比较这两种分配,如此继续下去,可以使X和Y排好了顺序,这种顺被称为的字典顺序,即当时,若存在下标则称(X)的字典顺序小于(Y),记为定义定义(Schmeidler,1969) n人合作博弈(N,v)的核仁N(v),是在使(X)按字典顺序下达到最小的那种分配向量的全体,即:按照这个定义,在核仁中,优先考虑最不满意(怨言最多)的联盟,选择分配要使这种联盟的怨言达到最小;在此基础上再考虑次不满意的联盟,所选分配也是使其不满意程度尽可能地小,如此继续下去,就可以得到结果。例 石油市场博弈的核仁 委员会博弈中X=(1/2,1/2,0,0,0)9.3.5 Shapley值公理1 (对称性) 与参与人的编号顺序无关,假设是1,2,n的一个排列,(i)是参与人i的任意一个排列, 是博弈在这个排列下的特征函数。则公理2(有效性)期望得益的总和应等于博弈所能得到的最大值,即公理3(可加性) 假定u,v是两个博弈的特征数,u+v表示同时独立实施两种博弈时的特征函数,则有:公理3表明:参与人在“和博弈”中分配得到的份额,是在两个单独对策中分配得到的份额之和。 定理 存在唯一的一个函数 满足公理13,且由下式给出:式中求和是遍及所有包含参与人i的联盟S,而是联盟内的参与人个数;这个值称为Shapley值。 定理 任何合作博弈的核仁非空,且只有一点构成。9.3.5 Shapley值 前述n人合作博弈的解均是博弈的平衡结果,这些解的概念考虑了在预先进行的协商中想坚持的一种分配或一组分配,如果这种分配是未被优超的,它们就是核心;如果它们优超于集外的其他分配,则它是稳定集;如果这些分配把联盟最大的不满意最小化,那它就是核仁。 Shapley在1953年注意到,每个参与人在开始博弈前,总希望得到合理的得益,这种得益作为参与人拥有的“势力” 的表征,他认为在特征函数为v的博弈中第i个参与人的期望得益 应该满足三条公理: