博弈论教程.ppt
- 文档编号:18734964
- 上传时间:2023-10-23
- 格式:PPT
- 页数:243
- 大小:941KB
博弈论教程.ppt
《博弈论教程.ppt》由会员分享,可在线阅读,更多相关《博弈论教程.ppt(243页珍藏版)》请在冰点文库上搜索。
博弈论,第一章导论,1.1什么是博弈论(GameTheory),1.1.1从游戏到博弈,游戏都有一些共同的特点:
1.都具有一定的规则;,2.都有一个结果;,3.策略至关重要;,4.策略和利益有相互依存性,一、博弈论概述,1.1.1博弈论的定义博弈论研究的是人与人之间利益相互制约下策略选择时的理性行为及相应结局。
豪尔绍尼(JohnC.Harsanyi)1994年诺贝尔经济学奖获奖致词:
博弈论是关于策略相互作用的理论。
博弈论研究人与人之间“斗智”的形式和后果,当人们利益存在冲突时,每个人所获得的利益不仅取决于自己所获取的行动,还依赖于其他人采取的行动,每个人都需要针对对方的行为选择作出对自己最有利的反应。
3、博弈论的分类
(1)合作博弈研究人们达成合作时如何分配合作得到的收益,即收益分配问题。
(2)非合作博弈研究人们在利益相互影响的局势中如何选决策使自己的收益最大,即策略选择问题。
(3)完全信息不完全信息博弈:
参与者对所有参与者的策略空间及策略组合下的支付有充了解称为完全信息;反之,则称为不完全信息。
(4)静态博弈和动态博弈静态博弈:
指参与者同时采取行动,或者尽管有先后顺序,但后行动者不知道先行动者的策略。
动态博弈:
指双方的的行动有先后顺序并且后行动者可以知道先行动者的策略。
博弈的分类及对应的均衡,1.1.2一个非技本性的定义规定或定义一个博弈需要以下几个方面:
1参与人(Player)(局中人)指博弈中的决策主体,他的目的是通过选择行动(或策略)以最大化自己的支付(效用)水平,参与人可以是自然人、团体、自然(“上帝”作为虚拟的参与人)。
2各个参与人各自可选择行动集(actionset),Ai=ai,是其可以采用的全部行动的集合。
一个行动组合(actionproile)是一个由博弈中的n个参与人每个选取一个行动所组成的有序集a=(a1,a2,an)。
3.参与人i的策略(strategy)是如下的一项规则:
给定其信息集,该策略决定在博弈的每一时点他选择何种行动。
参与人i的策略集(strategyset)Si=si是其可行策略的集合。
策略组合(strategyprofile)s=(s1,s2,sn)是由博弈的n个参与人每人选择一个策略所组成的一个有序集。
4.参与人i的得益(支)(payoff)ui(s1,s2,sn)表示这样的含义:
在所有的参与人和自然都选择了各自的策略且博弈已经完成后,参与人i获得的效用。
参与人i获得的期望效用,该期望效用是参与人i及其他参与人所选择的策略的函数。
5.一个博弈的结果是指在博弈结束以后,建模者从行动、得益和其他变量的取值中所挑选出来的他所感兴趣的要素的集合。
1.2几类经典的博弈模型1.2.1囚徒的困境(prisonersdilemma),这个例子本身就部分奠定了非合作博弈论的基础。
1.2.2智猪博弈猪圈里有两头猪:
大猪和小猪,猪圈的一头有一个猪食槽,另头装有个按纽,控制着猪食的供应,按一下就会有10单位的猪食进槽,但谁按谁就要付出相当于2单位猪食的成本;当猪食进槽时,若大猪先到,大猪可吃到9单位;小猪先到,则小猪可吃到4单位,大猪吃6单位;若两者同时到,叫大猪可吃7单位,小猪吃3单位。
小猪,大猪,按,等,按,等,5,1,4,4,9,1,0,0,1.2.3性别战1.2.4斗鸡博弈,女,足球,芭蕾,男,足球,芭蕾,2,1,0,0,0,0,1,3,A,B,进,退,进,退,3,3,2,0,0,2,0,0,1.2.5市场进入阻挠1.2.6猜硬币博弈1.2.7石头剪子布,默许,在位者,进入者,进入,不进入,斗争,40,50,10,0,0,300,0,300,猜硬币方,正,反,正,反,盖硬币方,1,1,1,1,1,1,1,1,石头,剪子,布,石头,剪子,布,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,0,A,B,1.3博弈的结构和博弈的分类1.3.1博弈中的博弈方一、单人博弈实际上是最优化问题,或者是一个参与人与“自然”的博弈。
二、双人博弈最常见、研究得最多的博弈双人博弈中的两个博弈方之间并不总是相互对抗的。
(互补性问题)掌握信息较多的一方并不能保证获益大。
个人追自身的最大利益并不能保证所得最优。
三、多人博弈可能存在“破坏者”与“联盟”。
1.3.2博弈中的策略博弈中独立决策、独立承担博弈结果的个人或组织称为博弈方。
博弈中各博弈方的决策内容称为“策略“,但应注意到并不是每个博弈方都有相同的可选略。
如果在一个博弈中每个博弈方的策略数都是有限的,则称该博弈为有限博弈;否则就称为无限博弈。
1.3.3博弈中的得益(支付,payoff)得益指在一个特定的策略组合下参与人得到效用水平,即各个博弈方从博弈中所获得的利益.,一、零和博弈二、常和博弈三、变和博弈国内常见的博弈论参考书:
1.经济博弈论(第二版)谢识予编著复旦大学出版社,20022.博弈论与信息经济学张维迎著,上海三联书店、上海人民出版社3.博弈论施锡铨著,上海财经大学出版社,20024.GameTheory,1991,D.Fudenberg&J.Tirole中译本,中国人民大学出版社,第二章完全信息静态博弈,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表示策略式博弈。
例,L,M,R,U,M,D,4,3,5,1,6,2,2,1,8,4,3,6,3,0,9,6,2,8,S1=U,M,D,S2=L,M,R,支付用矩阵表示,称为双矩阵博弈。
参与人A,参与人B,2.1.1上策均衡(严格占优战略均衡)如果在某个博弈中,无论其他博弈方选择什么策略,一个博弈方的某个策略给他带来的支付始终不低于其他策略,则称该策略为这个博弈方的一个上策(优势策略Dominantstrategy)。
如果一个博弈的某个策略组合中所有策略都是各个博弈方自己的上策,则称这样的策略组合为该博弈的一个“上策均衡”。
例(囚徒的困境),2.1.2严格下策反复消去法(逐步剔除严格劣战略)例,L,M,R,U,M,D,8,3,5,1,6,2,2,1,8,4,3,0,9,6,2,8,3,6,可以预测该博弈的合理结局为(U,L),即参与人A,选择策略U,而参与人B选择策略L。
2.2Nash均衡2.2.1Nash均衡的定义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*argui(s1*,si-1*,si,si+1*,sn*),i=1,2,n因此,当且仅当没有一个参与人能从单方面背离某个策略组合的预见中增加自己的得益时,这个策略组合就是Nash均衡。
Si*Si,Nash均衡的哲学含义:
设想n个参与人在博弈前规定每一个参与人选择一个特定的策略。
s*=(si*,s-i*)代表这个协议,要问在没有外力强制的情况下,是否有参与人有积极性不遵守该协议?
如没有,则说明该协议是可以自动实施的。
能够自动实施的协议就可以看作一个Nash均衡。
例求下列博弈的Nash均衡:
C,R,得Nash均衡为:
(D,R).,用划线法可求,Nash均衡有强弱之分.上述定义中给出的是弱Nash均衡,一个Nash均衡是强的,如果给定其他参与人的策略,每一个参与人的选择是唯一的。
即,s*是一个强Nash均衡,当且仅当对每一个i,sisi*总有:
ui(si*,s-i*)ui(si,s-i*)。
如果一个Nash均衡是强的,则没有任何参与人在均衡策略和其他策略之间是无差异的。
(弱Nash均衡不是)如在以下博弈中:
C1,C2,C3,R1,R2,R3,2,12,1,10,1,12,0,12,0,10,0,11,0,12,0,12,0,13,(R1,C1)和(R1,C3),都是Nash均衡,但没有,一个强Nash均衡。
本质上说,Nash均衡的概念对社会计划者和理论家施加了一个约束,使他们不能建议或者预测一种非均衡行为。
博弈论可预测到,在均衡集较小的局势中,文化规范的重要性也小。
2.2.2Nash均衡的一致性预测性质Nash均衡是参与人将如何博弈的“一致性”(consistent)预测:
如果所有参与人预测到一个特定的Nash均衡将出现,那么,没有人有兴趣作不同的选择。
也只有Nash均衡具有这样的特征:
参与人预测到均衡,参与人预测到其他参与人预到均衡等等。
对比之下,预测一个非Nash均衡的策略组合意味着至少有一个参与人会犯错误,尽管这样的错误确有可能出现。
说Nash是一致性预测并不意味着Nash均衡一定是一个好的预测,但只有Nash均衡才有:
“一致性”预测的性质。
重要结论:
一种制度安排要发生效力必须是一种Nash均衡(Nash执行的,NashImplementation),否则,这种制度便不能“稳定”。
2.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均衡,那么严格下策消去法一定不会将它消去。
检验纳什均衡(囚徒困境,智猪游戏),性别战博弈,思考题:
为何几乎所有的卡特尔都会遭到失败?
几乎所有的卡特尔都会遭到失败,原因就在于卡特尔的协定(类似囚犯的攻守同盟)不是一个纳什均衡,没有成员有兴趣遵守。
那么是不是不可能有卡特尔合作成功了?
理论上,如果是无限期的合作,双方考虑长远利益,他们的合作是会成功的。
但只要是有限次的合作,合作就不会成功。
比如合作次,那么在第九次博弈参与人就会采取不合作态度。
2.3无限策略博弈分析和反应函数2.3.1Gournot(库诺特)双寡头竞争模型(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)Cq1u2(q1+q2)=q2P(q1+q2)Cq2,(q1*,q2*)是Nash均衡产量意味着:
q1*argmaxu1(q1,q2*)=q1P(q1+q2*)C1(q1)q2*argmaxu2(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模型,q1,q2,R1(q2),R2(q1),NE,O,q1*,q2*,2.4混合策略和混合策略Nash均衡2.4.1严格竞争博弈和混合策略的引进一、严格竞争博弈,正面,反面,正面,反面,盖币方,猜币方,-1,1,1,-1,1,-1,-1,1,这个博弈实际上是一个零和博弈,一方所得即,另一方所失,该博弈没有纯策略的Nash均衡。
例1,例2社会福利博弈,寻找工作游荡,救济,不救济,3,2,-1,3,-1,10,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),sS,j=1,n,其中j(sj)是混合策略j赋予纯策略sj的概率。
以两人博弈为例:
S1=s11,s12,s1p,S2=s21,s22,s2q,如果参与人1相信参与人2的混合策略为:
2=(21,22,2q),那么参与人选择纯策略s1p的期望效用为:
2ju1(s1p,s2j),q,j=1,参与人选择混合策略1=(11,12,1p)的期望效用(得益)为:
u1(1,2)=1k2ju1(s1k,s2j),p,k=1,q,J=1,=1k2ju1(s1k,s2j),K=1,J=1,p,q,类似地有u2(1,2)=1k2ju2(s1k,s2j),k=1j=1,pq,例如对博弈,LMR,U4,35,16,2,M2,18,43,6,D3,09,62,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=解:
设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-3x,32,04,21,34,要使上式取最大值,应取y=故两者的交点为(2/5,1/2)故混合策略的Nash均衡为:
(2/5,3/5),(1/2,1/2),相应的得益为:
U1=2.4,u2=2.5,0,0x1/2,0,1,x=1/2,1,1/2x1,x,y,2/5,1/2,例2社会福利博弈,寻找工作流浪,救济,不救济,3,21,3,1,10,0,流浪汉,政府,这个博弈不存在纯策略Nash均衡,设政府的混合策略为:
G=(x,1x),流浪汉的混合策略为L=(y,1y),则政府的,期望效用为uG(G,L)=x(5y1)y,而流浪汉的期望效用,为:
uL(G,L)=y(2x1)+3x,用类似上例的方法(如图):
可得x*=1/2,y*=1/5。
1,1/2,1,0.2,y,x,例3审计博弈(猜迷博弈的变种):
逃税不逃税,检查aC+F,a-FaC,a,不检查0,0a,a,纳税人,税收机关,这里a是应纳税款,C是检查成本,F是罚款。
设x表示检查的概率;y表示逃税的概率,给定y,选择检查和,不检查的期望得益分别为:
uG(1,y)=yF+aC和uG(0,y)=,a(1y),令uG(1,y)=uG(0,y)得y*=C/(a+F);类似地,给定x,纳,税人选择逃税和不逃税的得益:
up(x,1)=(a+F)x和up(x,1),=a,解up(x,1)=up(x,)0得x*=a/(a+F),由此*=(x*,y*)。
2.4.2多重均衡博弈和混合策略以上引进的混合策略Nash均衡及其分析方法,是以没有纯策略Nash均衡的严格竞争博弈为基础的,下面讨论有多个纯策略Nash均衡的博弈。
例1性别战,芭蕾足球,芭蕾2,10,0,足球0,01,3,女,男,这个博弈有两个纯策略Nash均衡(芭蕾,芭蕾)和(足球,足球),还可以求出一个混合策略均衡(3/4,1/4),(1/3,2/3)。
例2(分级)协调博弈,大小,大2,21,1,小,1,11,1,A厂,B厂,该博弈也有两个纯策略Nash均衡(大,大)和(小,小),和一个混合策略Nash均衡(2/5,3/5),(2/5,3/5)。
2.4.3混合策略和严格下策消去法在混合策略下,下列结论仍然成立:
如何博弈方都不会采取任何严格下策严格下策消去法不会消去任何Nash均衡如果经反复消去后留下的策略组合是唯一的,那它一定是Nash均衡例,LR,U2,01,0,M0,00,0,D1,02,0,参与人1,参与人2,参与人1的策略M不是在纯策略下,的严格下策,但如果参与人1采用混,合策略(1/2,0,1/2),不管对方如何,行动,总能保证期望得盖1/2,从而M,在混合策略意义下是严格下策。
2.5Nash均衡的存在性2.5.1Nash定理(Nash,1950)每一个有限博弈至少存在一个Nash均衡(混合策略意义下)。
2.5.2Nash定理的意义及其扩展,上策均衡,重复剔除上策均衡,纯策略Nash均衡,混合策略Nash均衡,其它存在性定理定理(Debreu,1952Glicksberg,1952Fan,1952)考虑一个策略型博弈,其中各参与人的策略空间Si为欧氏空间中的非空紧凸子集,得益函数ui关于策略组合s为连续的且关于参与人i的纯策略si为拟凹的,那么博弈存在一个纯策略的Nash均衡.定理(Glicksberg,1952)考虑策略型博弈,其参与人的策略空洵Si是度量空间中的非空紧子集,如果得益函数ui为连续函数,那么博弈至少存在一个混合策略的Nash均衡.,2.6Nash均衡的选择和分析方法的扩展2.6.1多重Nash均衡的博弈分析一个博弈可能有多个(甚至是无穷多个)Nash均衡,如考虑两个人分一块蛋糕,每人独立地提出自己要求的份额,设x1为参与人1要求的额,x2为参与人2要求的份额,如果x1+x21,每个人得到自己的份额;如果x1+x21,两个人所得为零,这时,任何满足x1+x2=1的点(x1,x2)都是Nash均衡点。
(但x1+x21的点不是),x1,x2,X1+x2=1,O,1,1,在有多个Nash均衡时,要求所有的参与人预测同一Nash均衡是非常困难的(均衡集较大意味着文化影响较大),如在分蛋糕的博中,(0.5,0.5)的均衡经常出现,这是一个“焦点“均衡。
保证一个Nash均衡出现的另一个方法是参与人在博弈开始前进行不化成本的“廉价磋商”(cheaptalk),尽管我们无法保证磋商会达成一个协议,即使达成了协议也不一定被遵守。
例如协调博弈(coordinationgame):
LR,U9,90,0,D0,01,1,参与人1,参与人2,如果两人在博弈前相遇,参与人1之将选择U;而参与人2告之将选择L,则(U,L)这“Pareto上策均衡”将有很大可能出现。
在“性别战”博弈中,如果事先打个电话预约,则可先定某一均衡。
一、Pareto上策均衡例战争与和平博弈,战争和平,战争5,58,10,和平10,810,10,国家1,国家2,该博弈有两个纯策略Nash,均衡(战,战)与(和,和),而,(和,和)是Pareto上策均衡。
二、风险上策均衡例该博弈有两个纯策略Nash均衡(U,L)和(D,R),(U,L)为Pareto上策均衡,但(D,R)为“风险占优均衡”。
人们通常比较倾向接受预测风险较小的结局。
LR,U9,90,8,D8,07,7,参与人1,参与人2,在本例中,策略D比策略U更“安全”一些,设参与人1取U,而参与人取R的概率为y,则u1=9(1y)+0y=99y参与人1取D时,u1=8(1y)+7y=8y当y1/8时,99y8y,如果参与人1认为参与人2取R的可能性大于1/8,他宁愿取D,因此,从风险占优的角度看,(D,R)优于(U,L)。
例猎鹿博弈,猎鹿猎兔,猎鹿3,30,1,猎兔1,01,1,猎手1,猎手2,是介于“囚徒的困境”与“协调博弈,之间的博弈,它有两个Nash均衡:
(鹿,鹿)和(兔,兔),但(兔,兔)是,风险占优的。
三、聚点均衡(focalPointsEquilibrum)四、相关均衡Nash均衡通常在参与人独立地选择自己的策略范围下才有意义。
实际上不少博弈中参与人之间选择的策略是相关的,如与一个“信号装置”有关。
如古代战将单打独斗不相上下时“鸣金收兵。
例(Aumann,1974)相关均衡他证明如果参与人可以根据某个共同观测到的信号选择行动,就可能出现“相关均衡”。
如博弈,LR,U5,10,0,D4,41,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)。
但假若双方约定抛
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 博弈论 教程