博弈论教程ppt课件.ppt

在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确博弈论教程一、博弈论概述一、博弈论概述1.1.1 1.1.1 博弈论的定义博弈论的定义博弈论研究的是人与人之间利益相互制约下策略选择时的理性行为及相应结局。博弈论研究的是人与人之间利益相互制约下策略选择时的理性行为及相应结局。豪尔绍尼（豪尔绍尼（John C.HarsanyiJohn C.Harsanyi）19941994年诺贝尔经济学奖获奖致词：博弈论是关于策略相互作用的理论。年诺贝尔经济学奖获奖致词：博弈论是关于策略相互作用的理论。博弈论研究人与人之间博弈论研究人与人之间“斗智斗智”的形式和后果，当人们利益存在冲突时，每个人所获得的利益不的形式和后果，当人们利益存在冲突时，每个人所获得的利益不仅取决于自己所获取的行动，还依赖于其他人采取的行动，每个人都需要针对对方的行为选择作出仅取决于自己所获取的行动，还依赖于其他人采取的行动，每个人都需要针对对方的行为选择作出对自己最有利的反应。对自己最有利的反应。2020/12/823 3、博弈论的分类、博弈论的分类 (1)(1)合作博弈合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。(2)(2)非合作博弈非合作博弈研究人们在利益相互影响的局势中如何选决策使自己的收益最大，即策略选择问题。(3)完全信息不完全信息博弈：参与者对所有参与者的策略空间及策略组合下的支付有充了解称为完全信息；反之，则称为不完全信息。(4)(4)静态博弈和动态博弈静态博弈和动态博弈静态博弈：指参与者同时采取行动，或者尽管有先后顺序，但后行动者不知道先行动者的策略。动态博弈：指双方的的行动有先后顺序并且后行动者可以知道先行动者的策略。2020/12/83博弈的分类及对应的均衡博弈的分类及对应的均衡静态动态完全信息完全信息静态博弈完全信息静态博弈纳什均衡；Nash(1950)完全信息动态博弈完全信息动态博弈子博弈精炼纳什均衡；泽尔腾（1965）不完全信息不完全信息静态博弈不完全信息静态博弈贝叶斯纳什均衡；海萨尼（1967-1968）不完全信息动态博弈不完全信息动态博弈精炼贝叶斯纳什均衡；泽尔腾（1975）Kreps,Wilson(1982),Fudenberg,Tirole(1991)2020/12/841.1.2一个非技本性的定义规定或定义一个博弈需要以下几个方面：1参与人参与人(Player)(Player)(局中人）局中人）指博弈中的决策主体，他的目的是通过选择行动（或策略）以最大化自己的支付（效用）水平，参与人可以是自然人、团体、自然（“上帝”作为虚拟的参与人）。2各个参与人各自可选择行动集行动集(action(action set)set),Ai=ai,是其可以采用的全部行动的集合。一个行动组合(action proile)是一个由博弈中的n个参与人每个选取一个行动所组成的有序集a=(a1,a2,an)。3.参与人i的策略策略(strategy)(strategy)是如下的一项规则:给定其信息集,该策略决定在博弈的每一时点他选 择何种行动。2020/12/85 参与人i的策略集(strategy set)Si=si是其可行策略的集合。策略组合(strategy pro(s1,s2,sn)是由博弈的n个参与人每人选择一个策略所组成的一个 有序集。4.参与人i的得益得益(支支)(payoff)(payoff)ui(s1,s2,sn)表示 这样的含义:在所有的参与人和自然都选择了各自的策略且博弈已经完成后,参与人i获得的效用。参与人i获得的期望效用，该期望效用是参与人i及其他参与人所选择的策略的函数。5.一个博弈的结果是指在博弈结束以后，建模者从行动、得益和其他变量的取值中所挑选出来的他所感兴趣的要素的集合。2020/12/861.2 几类经典的博弈模型1.2.1 囚徒的困境囚徒的困境(prisoners dilemma)囚徒囚徒A坦白不坦白囚徒囚徒B坦白不坦白5,50,1010,01,1这个例子本身就部分奠定了非合作博弈论的基础。2020/12/871.2.2 智猪博弈智猪博弈 猪圈里有两头猪:大猪和小猪,猪圈的一头有一个猪食槽,另头装有个按纽,控制着猪食的供应,按一下就会有10单位的猪食进槽,但谁按谁就要付出相当于2单位猪食的成本成本;当猪食进槽时,若大猪先到,大猪可吃到9单位;小猪先到,则小猪可吃到4单位,大猪吃6单位;若两者同时到,叫大猪可吃7单位,小猪吃3单位。小猪小猪 大猪大猪按等按等5,14,49,10,02020/12/881.2.3 性别战性别战1.2.4 斗鸡博弈斗鸡博弈女女足球芭蕾男男足球芭蕾2,10,00,01,3AB进退进退3,32,0 0,20,02020/12/891.2.5 市场进入阻挠1.2.6 猜硬币博弈 1.2.7 石头剪子布默许在位者进入者进入不进入斗争40,5010,00,3000,300猜硬币方正反正反盖硬币方1,11,11,11,1石头石头剪子剪子布布石头石头剪子剪子布布0,01,11,11,10,01,11,11,10,0AB2020/12/8101.3 博 弈 的 结 构 和 博 弈 的 分 类1.3.1 博 弈 中 的 博 弈 方 一、单人博弈 实际上是最优化问题，或 者是一个参与人与“自自 然然”的博弈。二、双人博弈最常见、研究得最多的博弈 双人博弈中的两个博弈方之间并不总是相 互对抗的。(互补性问题)掌握信息较多的一方并不能保证获益大。个人追自身的最大利益并不能保证所得最优。三、多人博弈可能存在“破坏者”与“联盟”。2020/12/8111.3.2 博 弈 中 的 策 略 博弈中独立决策、独立承担博弈结果的个人或 组织称为博弈方。博弈中各博弈方的决策内容称为“策略“，但应注意到并不是每个博弈方都有相同的可选略。如果在一个博弈中每个博弈方的策略数都是有 限的，则称该博弈为有限博弈；否则就称为 无限博弈。1.3.3 博弈中的得益(支付,payoff)得益指在一个特定的策略组合策略组合下参与人得到效用水平,即各个博弈方从博弈中所获得的利益.2020/12/812 一、零 和 博 弈 二、常 和 博 弈 三、变 和 博 弈国内常见的博弈论参考书:1.经济博弈论(第二版)谢识予 编著复旦大学出版社,20022.博弈论与信息经济学 张维迎 著,上海三联书店、上海人民出版社3.博弈论施锡铨 著,上海财经大学出版社,20024.Game Theory,1991,D.Fudenberg&J.Tirole中译本,中国人民大学出版社2020/12/813 第二章 完全信息静态博弈2.1 基 本 分 析 思 路 和 方 法 博弈可以有两种不同的表达方式：策略式策略式(Normal)表述和扩展式扩展式(extensive)表述，从 理论上来讲，这两种表述形式几乎是完全等 价的，但从分析的方便性来看，策略式更适 合表述静态博弈。在策略式表述中，所有参与人同时选择各自的 策略，所有参与人选择的策略一起决定每个参与人的支付。这里的“同时选择”的是策略，而不是行动。2020/12/814这里的“同时”是一个信息概念,而不是一个时间概念。可以设想,参与人是处于不同的房间里,要求在彼此没有联络的情况下,选择一个按纽。通常还假设,所有的参与人都知道博弈的结构,知道他们的对手知道这一结构,知道他们的对手了解他们知道如此直至无穷,也即博弈的结构是共同知识。更准确地,策略式表述给出:博弈的参与人集合:i,=1,2,n每个参与人的策略空间 Si,i=1,2,n策略组合(s1,s2,sn)(4)每个参与人的支付(收益)函数 ui=(s1,si,sn),i=1,2,n2020/12/815一般用 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 参参 与与 人人B2020/12/8162.1.1 上策均衡（严格占优战略均衡）如果在某个博弈中,无论其他博弈方选择什么策略,一个博弈方的某个策略给他带来的支付始 终不低于其他策略,则称该策略为这个博弈方 的一个上策(优势策略Dominant strategy)。如果一个博弈的某个策略组合中所有策略都是各个博弈方自己的上策，则称这样的策略组合为该博弈的一个“上策均衡”。例(囚徒的困境)囚徒囚徒A A坦白不坦白囚徒囚徒B B坦白不坦白5 5,5 50,0,101010,010,01,1,1 12020/12/8172.1.2 严格下策反复消去法（逐步剔除严格劣战略）例 LMRUMD8,35,16,22,18,43,09,62,83,6可以预测该博弈的合理结局为(U,L),即参与人A选择策略U,而参与人B选择策略L。2020/12/8182.2 Nash 均 衡2.2.1 Nash 均 衡 的 定 义 Nash 均衡是指这样的策略组合策略组合(或剖面):为了 极大化自己的收益(或效用),每一个参与人所 采取的策略一定应该是关于其他参与人所采 取的策略的最佳反应.因此没有一个参与人会 轻率地偏离这个策略组合而使自己蒙受损失。2020/12/819 定 义 在有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*Si2020/12/820Nash 均衡的哲学含义：设想n个参与人在博弈前规定每一个参与人选择一个特定的策略。s*=(si*,s-i*)代表这个协议，要问在没有外力 强制的情况下，是否有参与人有积极性 不遵守该协议？如没有，则说明该协议是可以 自动实施的。能够自动实施的协议就可以看作 一个Nash 均衡。例 求下列博弈的Nash 均衡：CRLUMN0，44，05，34，00，45，33，53，56，6得Nash均衡为:(D,R).用划线法划线法可求2020/12/821Nash均衡有强弱之分.上述定义中给出的是弱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均衡。均衡。2020/12/822本质上说,Nash 均 衡的概念对社会计划者和理 论家施加了一个约束，使他们不能建议或者 预测一种非均衡行为。博弈论可预测到，在均衡集较小的局势中，文 化规范的重要性也小。2.2.2 Nash 均衡的一致性预测性质Nash 均衡是参与人将如何博弈的“一致性”(consistent)预测:如果所有参与人预测 到一个特定的Nash 均衡将出现,那么,没有人 有兴趣作不同的选择。也只有Nash 均衡具有这样的特征：参与人预测到均衡，参与人预测到其他参与人预到均衡 等 等。2020/12/823 对比之下，预测一个非Nash 均衡的策略组合 意味着至少有一个参与人会犯错误，尽管这 样的错误确有可能出现。说Nash 是一致性预测并不意味着Nash 均衡一 定是一个好的预测，但只有Nash 均衡才有：“一 致 性”预测的性质。重要结论：一种制度安排要发生效力必须是一 种Nash均衡(Nash执行的,Nash Implementation),否则,这种制度便不能“稳定”。2020/12/8242.2.3Nash均衡与严格下策消去法命题2.1在博弈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均衡,那么严格下策消去法一定不会将它消去。检验纳什均衡（囚徒困境，智猪游戏）检验纳什均衡（囚徒困境，智猪游戏）2020/12/825性别战博弈性别战博弈克瑞丝克瑞丝歌剧拳击帕特帕特歌剧拳击2,10,00,01,22020/12/826思考题：思考题：为何几乎所有的卡特尔都会遭到失败？为何几乎所有的卡特尔都会遭到失败？2020/12/827几乎所有的卡特尔都会遭到失败，原因就在于卡特尔的协定（类似囚犯的攻守同盟）不是一几乎所有的卡特尔都会遭到失败，原因就在于卡特尔的协定（类似囚犯的攻守同盟）不是一个纳什均衡，没有成员有兴趣遵守。那么是不是不可能有卡特尔合作成功了？理论上，如果个纳什均衡，没有成员有兴趣遵守。那么是不是不可能有卡特尔合作成功了？理论上，如果是无限期的合作，双方考虑长远利益，他们的合作是会成功的。但只要是有限次的合作，合是无限期的合作，双方考虑长远利益，他们的合作是会成功的。但只要是有限次的合作，合作就不会成功。比如合作次，那么在第九次博弈参与人就会采取不合作态度。作就不会成功。比如合作次，那么在第九次博弈参与人就会采取不合作态度。2020/12/8282.3 2.3 无限策略博弈分析和反应函数无限策略博弈分析和反应函数2.3.1 Gournot（库诺特）双寡头竞争模型(Nash 均衡最早的 版本,1838 年)2020/12/829设有两个参与人,分别称为企业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)Cq22020/12/830(q1*,q2*)是Nash均衡产量意味着:q1*argmax u1(q1,q2*)=q1P(q1+q2*)C1(q1)q2*argmax u2(q1*,q2)=q2P(q1*+q2)C2(q2)找出Nash均衡的一个办法是对每个企业的利润 函数求一阶导数并令其为零:2020/12/831u1/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*)(如下图)2020/12/832Cournot模型q1q2R1(q2)R2(q1)NEOq1*q2*2020/12/8332.4 混 合 策 略 和 混 合 策 略Nash 均 衡2.4.1 严格竞争博弈和混合策略的引进 一、严格竞争博弈正面正面反面反面正面正面反面反面盖币方盖币方猜币方猜币方-1,11,-11,-1-1,1这个博弈实 际上是一个零和博弈，一方所得即另一方所失，该博弈没有纯策略的Nash均衡。例12020/12/834例2 社会福利博弈寻找工作寻找工作 游荡游荡救济救济不救济不救济3,23,2-1,3-1,3-1,1 0,0-1,1 0,0政府政府流浪汉流浪汉 这个博弈也不存在纯策略的Nash均衡，给定政府救济，流浪汉的最佳 策 略是游荡，给定流浪汉游荡，政府的最佳策略是不救济上述博弈的显著特征是：每一个参与人都想猜透对方的策略，而每个参与人又都不想让对方猜透自己的策略，所以此类博弈中都不存在(纯策略)Nash均衡。2020/12/835对猜硬币博弈来说，设出正面的概率友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个可选策略中选择的“策略”称为个混合策略。2020/12/836其中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取确定值。与混合策略相伴的是得益(支付)的不确定性。这时:2020/12/837ui()=ui(1,i,n)ui(i,i)表示参与人i的期望效用,它可定义为ui(i,-i)=(j(sj)ui(s)s Sj=1n其中j(sj)是混合策略j赋予纯策略sj的概率。以两人博弈为例:S1=s11,s12,s1p,S2=s21,s22,s2q如果参与人1相信参与人2的混合策略为:2=(21,22,2q)那么参与人选择纯策略s1p的期望效用为:2ju1(s1p,s2j)qj=12020/12/838参与人选择混合策略1=(11,12,1p)的期望效用(得益)为:u1(1,2)=1k 2ju1(s1k,s2j)pk=1qJ=1=1k2ju1(s1k,s2j)K=1J=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)(双矩阵博弈)2020/12/839下面重新定义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均衡。2020/12/840 22双矩阵博弈的Nash均衡的求法例1 求双矩阵博弈的混合策略Nash均衡,其中A=B=解:设1*=(x.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 42020/12/841要使上式取最大值,应取y=故两者的交点为(2/5,1/2)故混合策略的Nash均衡为:(2/5,3/5),(1/2,1/2),相应的得益为:U1=2.4,u2=2.50,0 x1/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均衡均衡:(鹿鹿,鹿鹿)和和(兔兔,兔兔),但但(兔兔,兔兔)是是 风风 险险 占占 优优 的。的。2020/12/854 三、聚点均衡聚点均衡(focal Points Equilibrum)四、相关均衡相关均衡 Nash均衡通常在参与人独立地选 择自己的策略范围下才有意义。实际上不少博弈中参与人之间选择的策略是相关的，如 与一个“信号装置”有关。如古代战将单打独斗不相上下时“鸣金收兵。例（Aumann,1974)相关均衡他证明如果参与人可以根据某个共同观测到的 信号选择行动，就可能出现“相关均衡”。2020/12/855 如 博 弈 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均衡。2020/12/856 更 重 要 的 是，Aumann 证明：如果每个人收 到不同但相关的信号，每个人都能得到更高的 期望效用。设想由第 三方掷骰子特定方法决 定两人的行动，如12点出现，则1选U，36点出现则1选D，对参与人2则：如果14点 出现，选L。56 点出现则选R，再假定第三 方只告诉参与人选择什么行动，而不透露什么 点数。这时：(U,R)不会出现 保证三个结果(U,L),(D,L),(D,R)各以1/3的概率出现。这时双方的期望得经均为10/3。(但“信号装置”是 有成本的)2020/12/857例 三人博弈的得益矩阵为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)。2020/12/8582.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)。2020/12/859 二、防防 共共 谋谋 均均 衡衡 防共谋均衡是两个以上博弈方的博弈中，博弈 方之间在Pareto 上策均衡中进行合作的思想 的扩展。定义；如果一个博弈的某个策略组合满足下列 条件：没有任何博弈方的串谋会改变博弈的 结果；给定选择偏离的博弈方有再次偏离的 自由时，没有任何两个博弈方的串谋会改变博 弈的结果；依次类推，直到所有博弈方都参 加的串谋也不会改变博弈的结果。则称该策略组合为一个防共谋均衡。2020/12/860 第第 三三 章章 完完 全全 信信 息息 动动 态态 博博 弈弈3.1 动 态 博 弈 的 表 示 法 和 特 点1.定 义 与 博 弈树2.2.博弈的展开式所包含的信息和内容:3.参与人的集合,记为i=1,2,n,用N代表虚拟的参匀人“自然”;4.行动的次序,即谁在什么时候行动;5.参与人的行的空间,即轮到某参与人行动时,他从该时刻的纯策略空间中选取什么策略;6.当参与人作出他们的行动决策时,他所观测到 或他所了解到的信息,即他在此时获得的信息 集合;7.参与人的得益(支付或效用),它们是已知行动的函数;8.在任何外生事件的概率分布。2020/12/861 例例 房地产开发博弈房地产开发博弈有两个房地产开发商有两个房地产开发商(分别为参与人分别为参与人1,1,记为记为A A和参与人和参与人2,2,记为记为B)B)在某地开发房地产在某地开发房地产,但该地的房地产需求状况但该地的房地产需求状况是不确定的是不确定的,假定该博弈的行动顺序如下假定该博弈的行动顺序如下:(1)(1)开发商开发商1 1先行动先行动,选择开发或不开发选择开发或不开发;(2);(2)在在1 1决策后决策后,“,“自自然然”选择需求的大小选择需求的大小;(3);(3)开发商开发商2 2在在 观测到观测到1 1的决策和市场的需求后的决策和市场的需求后,再决定开发再决定开发 或不开发。或不开发。(如如 下下 图图)2020/12/862 房房 地地 产产 开开 发发 博博 弈弈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表示信息集表示信息集2020/12/863 上述博弈树给出了有限博弈的几乎所有信息。上述博弈树给出了有限博弈的几乎所有信息。博博 弈弈 树树 必必 须须 满满 足足 下下 列列 规规 则：则：(1)(1)每一个结每一个结(node)(node)至多有一个其他结直接位于至多有一个其他结直接位于 它的前面它的前面;(2)(2)在博弈中没有一条路径可以使决策集与自身在博弈中没有一条路径可以使决策集与自身 相连相连;(3)(3)每一个结是唯一初始结的后续结每一个结是唯一初始结的后续结,即博弈树即博弈树 必须有初始结必须有初始结;(4)(4)每个博弈树每个博弈树“正好正好”只有一个初始结只有一个初始结(多于一个多于一个 可以用可以用“自自 然然”连接。连接。2020/12/864 不允许出现的情况：不允许出现的情况：由以上规则，对于博弈树中的每一个终点结，我们，完全可以确定从初始结到终点 结的路 径，同时也展示了博弈的动态过程。信息集:博弈树上的所有决策集分割成不同的信息集，我们用hH来表示这个信息。如果一个信息集包含 结x,我们就可以将该信息集记为h(x),如果一个信息 集只包含一个结,这是最简的情况。我们主要关心的 是一个信息集包含不止一个结,假设x与xh(x),则恰好拥有信息h(x)并正在选择自己行动的参与人其实对自己究竟是处于x还界x是不确定的。2020/12/865 要 求：如 果xh(x),则x与x 应 该由同 一个参与人采取行动，且可以选择的策略空 间相同：A(x)=A(x),由此可以将信息集h上 的行动集记 为A(h)。如果博弈树的所有信息集都是单结的,则称该 博弈为完美(perfect)息 博弈。(无虚线连接),而完全(complete)信息博弈是指得益函数和纯策略空间均为博弈各方的共同知识。完全信息可以是完美的也可以是不完美的。3.2 展开型博弈的策略与均衡 一、行 为 策 略 在策略型博弈中,参与人的策略是进行博弈的计划(或打算)的详细集合,而在展开型博弈中 参与人的策略必须确定在该参与人的每一个决 策集上 所 采 取 的 行 动,又 结 与 信 息 集 紧 密 相 连,对 于 参 与 人i,基于信息hi的行动的2020/12/866的全体记汉的全体记汉A(hi),A(hi),如果令如果令HiHi表示参与人表示参与人i i的信息集的信息集的集合的集合,则则Ai=A(hi)Ai=A(hi)就是参与人就是参与人i i的所有行动的所有行动的集合。参与人的集合。参与人i i的一个纯策略是从的一个纯策略是从HiHi到到AiAi的一个映射的一个映射si:si:对每一个对每一个hiAi,si(hi)Ai,hiAi,si(hi)Ai,所有这些所有这些sisi的全体记的全体记为为Si,Si,即的的纯策略空间即的的纯策略空间Si,Si,由此由此:Si=A(hi)Si=A(hi)hi Hihi Hi2020/12/867例参与人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)2020/12/868其中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 Hi2020/12/869 展开型博弈中纯策略是由信息集与行动集定义展开型博弈中纯策略是由信息集与行动集定义 的的(与静态博弈不同与静态博弈不同,静态博弈中采取纯策略与静态博弈中采取纯策略与 采取某行动是采取某行动是一个意思一个意思)。纯策略组合纯策略组合(剖面剖面profile)profile)是由参与人各自的纯策是由参与人各自的纯策 略空间中的任一纯策略构成的组合，在任一纯略空间中的任一纯策略构成的组合，在任一纯 策略组合策略组合s s下，总可以从初始结开始，沿着博弈树的某条路径下，总可以从初始结开始，沿着博弈树的某条路径(path),(path),达到达到s s相应的终点结。相应的终点结。有一个事实非常重要：有一个事实非常重要：s s中有些信息集在博弈中有些信息集在博弈 树的这条路径上，我们称这些信息集是树的这条路径上，我们称这些信息集是s s的路的路 径径(path),(path),当然也可能存在当然也可能存在s s中某些中某些信息集不在信息集不在 此路径上。此路径上。2020/12/870 定义了纯策略的得益函数后，我们就可以定义 展开型博弈的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)。2020/12/871 参与人i的行为策略行为策略bi 定义为：bihiHihiHi(A(hi)其中 表示某集合是的概率分布。行 为 策 略 的Nash 集 合 是 这 样 一 个 策 略 组 合，它 使 得 没 有 一 个 参 与 人 可 以 通 过 不 同 的 使 用策 略 而 增 加 自 己 的 得 益。注意：行为策略是在A(hi)上随机化，而混合策 略则是在Si(即A(hi)的乘积 空 间)上的随机化。2020/12/872 定 理(Kuhn,1953)在完美回忆博弈中，混合 策略与行为策略是等价的。完美回忆指没有参与人会忘记以前知道的信息。例 下列展开型博弈不具备完美回忆：1221111ABLRLRC D C D C D C D2020/12/873 现在重新考虑上述房地产开发博弈，以解释信 息集的概念，其中开发商B是在知道A的选择 和自然的选择之后决策的。如果B在决策时并不知道自然的选择，则有博 弈树：ANNBBBB 开 发 不 开 发 大(1/2)小(1/2)大(1/2)小(1/2)开发 不开发 开发 不开发 开发 不开发 开发 不开发hBhBhA2020/12/874另一种情况就则B知道自然的选择,但不知道A的选择,这时博弈树如下:ANNBBBB开发开发 不开发不开发大大 小小 大大 小小开发开发 不开发不开发 开发开发 不开发不开发 开发开发 不开发不开发 开发开发 不开发不开发(-5,-5)(0,-8)(-3,-3)(1,0)(0,8)(0,0)(0,1)(0,0)2020/12/875 上述房地产开发博弈还有另一种表示：NABBABB 大大(1/2)小小(1/2)开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发 开开 发发 不不 开开 发发2020/12/876 有了信息集的概念,展开式表示也可以用来表 示静态博弈,如“囚徒的困境”博弈可以表 示为:122 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白(-5,-5)(0,-8)(-8,0)(-1,-1)2020/12/877或者:211 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白 坦坦 白白 不不 坦坦 白白(-5,-5)(0,-8)(-8,0)(-1,-1)注注 意意:得得 益益 向向 量量 的的 次次 序序 与与 参参 与与 人人 决决 策策 的的 顺顺 序序 一一 致。致。2020/12/878 同样地,展开型博弈也可以用策略式来表示,如 展开型博弈:122TBL R L R(2,2)(4,0)(1,0)(3,1)可以表示为可以表示为:L RT 2,2 4,0 B 1,0 3,1 参参 与与 人人1 参参 与与 人人22020/12/879 展 开 型 博 弈: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 参参 与与 人人22020/12/880 同样地,展开型博弈也可以用策略式来表示:例 摊牌博弈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 x22020/12/881 摊 牌 博 弈 的 策 略 空 间 分 别 为: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,