博弈论课件.ppt

按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,博弈论,2009,正大光明 公正無私 幫助別人 成就自己,*,博弈论,the Theory of Games,1,主要内容,一、博弈现象及基本概念,二、完全信息静态博弈,三、完全信息动态博弈,四、不完全信息静态博弈,五、不完全信息动态博弈,六、不完全信息专题,2,主要参考书,姚国庆：,博弈论,，高等教育出版社，,2007.,罗云峰：,博弈论教程,，清华大学出版社、北京交通大学出版社。,张维迎：,博弈论与信息经济学,，上海三联书店，上海人民出版社，,2004,。,施锡铨，,博弈论,，上海财经大学出版社，,2002,。,3,张守一，,现代经济对策论,，高等教育出版社，,1998,。,钱颂迪，,运筹学,，清华大学出版社，,1996,。,美,艾里克,.,拉斯缪森：,博弈与信息,，北京大学出版社，,2003,。,美,弗登博格：,博弈论,，中国人民大学出版社，,2002,。,4,第一讲,博弈现象与基本概念,1,博弈现象,2.,博弈概念,3.,博弈描述,4.,博弈练习,5.,关于博弈论,5,1,博弈现象,田忌赛马：,正确的策略可以反败为胜。,囚徒困境：,认罪,不认罪,认罪,（,-5,-5,）,（,0,-10,）,不认罪,（,-10,0,）,（,-1,-1,）,甲,乙,理性的人是自私自利的；,理性选择不是全局最优。,6,经济合作：,合作,欺骗,合作,（,2,2,）,（,-2,4,）,欺骗,（,4,-2,）,（,0,0,）,甲,乙,诚信的价值；,一报还一报策略；,人类生存环境启示。,7,长街上的超市（海滩占位模型）,0,1/2,3/4,1,1/4,A,O,资源浪费还是理性的必然？,其它相似情形：,旅行社的热门路线；黄金时间的电视节目；总统竞选。,8,狩猎与投资,狩猎：,两个猎人围住一头鹿，各卡住两个关口中的一个，齐心协力即可成功获得并平分猎物。此时有一群兔子跑过，任何一人去抓兔子必可成功，但鹿会跑掉。,他们会坚持猎鹿还是去抓兔子？,9,共同投资：,双方共同投资一个大项目，可期望有较大收益。此时如某方抽出资金去进行小项目投资，必可成功获小利，但会使共同项目陷入困境，使对方蒙受损失。,投资者会如何选择？,10,旅行者困境,两个旅行者花瓶被摔坏，向航空公司索赔。航空公司知道价格约为八九十元，但不知道确切价格。于是请两位旅客在,100,元以内自己写下花瓶的价格。,如两人写的一样，就认为他们讲真话，并按所写数额赔偿；如果两人写的不一样，就认定低者讲真话，并照此价格赔偿。同时，对讲真话的旅客奖励,2,元钱，对讲假话的旅客罚款,2,元。,理性原则下，他们会写多少价格呢？,11,什么是博弈：,个人或团体间在依存和对抗、合作和冲突中的决策问题。,博弈论研究博弈过程中的理性行为。,2.,博弈概念,12,如何理解理性行为：,自身利益最大；,持续地有意图的行动；,不对动机妄加猜测；,不考虑道德问题；,只研究合法问题；,盈利函数有多重标准。,13,博弈三要素,局中人,(,参与人）,players,：,决策主体,；,自然人、团体或“虚拟局中人”；,有可供选择的策略和明确定义的利益函数；,分为两人和多人,14,策略（战略）,strategies,：,采取行动的规则；,可以是一次行动也可以是一个行动序列；,可以是纯策略也可以是混合策略；,分为有限和无限。,支付（盈利函数）,payoff,：,对应于某策略组合的局中人利益或损失；,确定的或是期望的；,分为零和和非零和。,15,扩展术语：,信息：,信息集；,完全信息（,complete,）,；,完美信息（,perfect,）,。,共同知识：,双方可能获取的相同信息；,彼此都能算清楚。,博弈结果：,均衡策略组合；均衡行动组合。,均衡：,所有局中人最优策略的组合。,16,博弈的策略型（标准型、正则型）表述：,指定,n,个局中人，以及他们各自的纯策略空间,和这些局中人各自的支付（盈利）函数,我们将该博弈表示为：,3.,博弈描述,17,例：寡头竞争问题,策略型表述多适用于静态博弈。,另一种表述方式是扩展式表述，两种表述形式几乎是完全等价的，但是扩展式表述更适合于讨论动态博弈。,18,房地产开发实例,双方：,A,，,B,策略：,开发投资,1,亿元；不开发，投资,0,售价：,高需：,1.4,亿元,(,两栋,),，,1.8,亿元,(,一栋,),；,低需：,0.7,亿元,(,两栋,),，,1.1,亿元,(,一栋,),。,19,结果：,高需，,(,开，不开,),，,(0.8,，,0),高需，,(,不开，开,),，,(0,，,0.8),高需，,(,开，开,),，,(0.4,，,0.4),高需，,(,不开，不开,),，,(0,，,0),低需，,(,开，不开,),，,(0.1,，,0),低需，,(,不开，开,),，,(0,，,0.1),低需，,(,开，开,),，,(-0.3,，,-0.3),低需，,(,不开，不开,),，,(0,，,0),20,策略型表述：,（,两人有限博弈；矩阵形式）,开发,不开发,开发,（,0.4,0.4,）,（,0.8,0,）,不开发,（,0,0.8,）,（,0,0,）,A,B,高需求情况,低需求情况？,21,房地产博弈分析,假设：,同时决策；市场需求双方已知,若市场需求大，双方开发，各得,0.4,万元。,若市场需求小，依赖于对方行动。,若市场不确定，依赖对市场的判断及对方行动。,例：,P,0.5,最坏情况期望盈利,500,万元，开发。,P,0.3,对方开发概率,31/40,时，开发；否则，不开发。（？）,22,关键问题：,对自然状态的概率估计；,不同时间决策（决策顺序）；,对对方先验信息的估计（即估计对方对信息的掌握程度）。,现实困难：,对市场了解程度不同；,对对方了解程度不同；,如何向对方暗示自己的行动。,23,4.,博弈练习,游戏一：,心灵感应,两个人一组，独立写出,1,至,10,之间的任意,5,个数。如果不重复则得奖；否则受罚。,获胜的秘诀是什么？,24,游戏二：,海盗逃生,有,5,个海盗，即将被处死刑。法官愿意给他们一个机会。从,100,个黄豆中随意抓取，最多可以全抓，最少可以不抓，可以和别人抓的一样多。抓得最多的和最少的要被处死。,如果你第一个抓，你抓几个？,25,游戏三：,100,元怎么分？,你看见两个小孩在玩耍，出于好奇，你给他们,100,元，让他们猜拳。猜赢者决定怎么分这,100,元，而输者如果同意赢者的分配比例，那么他们将各有所得，如果不同意，那么这,100,元，你将收回。,请你替赢者考虑一下，怎样分配，赢者既得到最大利益，又能让输者也同意呢？,26,游戏四：,一元钱竞拍,给一元钱钞票开出你的价钱，使自己获益最大或损失最少；每次叫价以,5,分钱为单位；开价最高者得到这一元钱；出价最高和次高者一并按所开的价钱支付。,斜坡上的均衡；,“,骑虎难下,”,的博弈；,“,协和谬误,”,27,游戏五：,强盗分赃,有五个强盗抢得,100,枚金币，在如何分赃问题上争吵不休。于是他们决定：,（,1,）抽签决定自己的号码（,1,，,2,，,3,，,4,，,5,）；,（,2,）由,1,号提出分配方案，然后,5,人表决，如果方案超过半数同意就通过，否则他将被仍进大海喂鲨鱼；,28,（,3,）,1,号死后，由,2,号提方案，,4,人表决，当且仅当超过半数同意方案通过，否则,2,号同样被仍进大；,（,4,）依次类推，直到找到一个每个人都接受的方案（当然，如果只剩下,5,号，他当然接受一个人独吞的结果）。,如果你是第一个强盗，你该如何提出分配方案才能使自己的收益最大化呢？,29,5.,关于博弈论,博弈分类,:,合作、非合作：,是否存在一个具有约束力的协议（,binding agreement,）,前者强调团体理性（效率、公正、公平）,后者强调个人理性（最优决策，不保证效率）,30,完全信息与不完全信息：,每一个局中人对自己及其它局中人是否有完全的了解；,包括局中人特征、策略空间、盈利函数等知识。,动态与静态：,行动的先后顺序,;,是否同时（或不同时但对方不知）。,31,发展历史：,1944,Von Neumann&Morgenstern,“,The theory of games and economic behavior,”,1950,Nash&1953,Shapley,“,讨价还价,”,模型,1950,、,1951,Nash,非合作博弈,1950,Tucker Prisoners,dilemma,1953,Gillies&Shapley,合作博弈,1965,Selton,动态分析,；,“,精炼纳什均衡,”,1967,、,1968,Harsanyi,“,不完全信息,”,1994,Nash,、,Selton,、,Harsanyi,诺贝尔经济学奖,32,纳什的传奇人生,1928,年出生于一个电子工程师家庭。,17,岁进入今卡耐基梅隆大学，专攻数学。,20,岁时进入普林斯顿大学攻读博士学位。,1949,年，,21,岁的纳什写下论文,多人博弈的均衡点,。,1950,年以论文,非合作型博弈,获得数学博士学位。,33,34,毕业后先后在兰德研究所、普林斯顿大学、,MIT,工作。,1957,年他与,MIT,学生爱莉西娅结婚。,在而立之年患上了妄想型精神分裂症，九十年代逐渐恢复了正常。,1994,年纳什博士获诺贝尔经济学奖。,2002,年来北京参加,“,国际数学家大会,”,35,36,电影,“美丽心灵”,37,静态,动态,完全,信息,完全信息静态博弈,纳什均衡,纳什（,1950,，,1951,）,完全信息动态博弈,子博弈精炼纳什均衡,泽尔滕（,1965,）,不完全信息,不完全信息静态博弈,贝叶斯纳什均衡,海萨尼（,1967,1968,）,不完全信息动态博弈,精炼贝叶斯纳什均衡,泽尔滕（,1975,）,博弈论体系,38,第二讲,完全信息静态博弈,1.,矩阵博弈,2.,累次严优均衡,3.,纳什均衡,4.,混合策略纳什均衡,5.,纳什均衡的存在性与多重性,39,1.,矩阵博弈,什么是矩阵博弈：,两人零和有限策略博弈；,可用矩阵形式表述。,矩阵元素为局中人,A,的赢得，亦即,B,的损失。,例：,用矩阵形式表述田忌赛马博弈（？）,40,有鞍点情形,：,存在最优纯策略,例：,表中数据为,I,的赢得,II,I,1,2,3,min,1,6,1,8,8,2,3,2,4,2,3,9,1,10,10,4,3,0,6,3,max,9,2,6,2,博弈哲学,：,从最坏处考虑，争取最好结果,41,无鞍点情形：,最优混合策略,例：,II,I,1,2,min,1,11,5,5,2,7,9,7,max,11,9,?,设最优混合策,略：,42,对局中人,I,：,43,I,的最优混合策略为,同理，,II,的最优混合策略为,G,8,同理可求局中人,II,的最优混合策略（？）,44,2.,累次严优均衡,占优策略均衡,(,严格,),劣策略：,无论对方如何选择都更差,。,占优策略：,无论对方如何选择存在唯一最优。,占优策略均衡：,所有局中人占优策略的组合。,特点：,只要求每个人理性，并不要求知道其它人是不是理性。,45,例：裁军问题,以巴,武装,裁军,武装,（,3000,3000,）,（,10000,，,）,裁军,（,10000,）,（,0,0,）,例：,囚徒困境中的（认罪，认罪）,例：,房地产投资市场大情况下（开发，开发）,46,重复剔除的占优均衡,（,iterated elimination,）,也称为累次严优均衡。,通过重复剔除劣战略剩下唯一的战略组合。,如果存在则称为重复剔除占优可解的。,（,dominance solvable,）,特点：,不仅要求每个人理性，还要求知道其它人理性。理性是共同知识。,47,例：智猪博弈,按钮喂食：一次供应量为,8,，代价为,2,。,大猪先到,7,:,1,;,同时到,5,:,3,;,小猪先到,4,:,4,小猪,大猪,按,等,按,（,3,1,）,（,2,4,）,等,（,7,1,）,（,0,0,）,48,分析：,小猪有占优策略，大猪没有，所以不存在占优均衡；,在,“,理性,”,为共同知识的情况下，存在重复剔除的占优均衡，即（大猪按，小猪等）。,应用：,此为,“,多劳不多得，少劳不少得,”,的奇怪情形，是一种有趣的社会现象。经济学中称为,“,搭便车现象,”,49,II,I,L,M,R,U,（,4,3,）,（,5,1,）,（,6,2,）,M,（,2,1,）,（,8,4,）,（,3,6,）,D,（,3,0,）,（,9,6,）,（,2,8,）,无论局中人,I,怎样决策，局中人,II,与其选取策略,M,还不如选取策略,R,。,对于局中人,II,来说，,M,是个劣策略。,可以去掉,II,的,“,M,”,列。,例：,50,假定,II,不选,M,，,对于,I,来说,M,和,D,是劣策略。,II,I,L,R,U,（,4,3,）,（,6,2,）,M,（,2,1,）,（,3,6,）,D,（,3,0,）,（,2,8,）,51,故,I,选择,U,。,这时，,II,选择,L,而不选,R,。,可以预测博弈的合理结局可能是（,U,，,L,）,即（,4,，,3,）。,II,I,L,R,U,（,4,3,）,（,6,2,）,II,I,L,U,（,4,3,）,52,严优均衡的局限,有时无法开始累次严优的剔除；,例：房地产投资中市场小的情况,反常现象：,盈利函数取极端值时；,如果双方都存在严劣策略，从不同人开始的结果一致；,与混合策略的优劣比较。,53,II,I,L,R,U,（,7,9,）,（,1000,8.5,）,D,（,6,5,）,（,5,4.5,）,分析：,累次严优过程产生了唯一解（,U,，,L,）。,然而，不管局中人,I,如何行动，局中人,II,取,R,仅比取,L,在盈利上差,0.5,。,I,选策略,U,要冒极大的风险，策略,D,比,U,更加稳健。,所以，局中人,I,不会选,U,，,而是选择,D,。,稳健性。,例：,54,3.,纳什均衡,定义：,有,n,个局中人的策略式表述博弈,G=S,1,S,n,;u,1,u,n,，,策略组合,s*=(s,1,*,s,i,*,s,n,*),是一个纳什均衡，如果对于每一个,i,，,s,i,*,是给定其它局中人选择,s,-i,*=(s,1,*,s,i-1,*,s,i+1,*,s,n,*),的情况下第,i,个局中人的最优策略，即,u,i,(s,i,*,s,-i,*),u,i,(s,i,s,-i,*),s,i,S,i,i,55,或者用另一种表述方式：,s,i,*,是下述最大化问题的解：,s,i,*,argmax,u,i,(s,1,*,s,i-1,*,s,i,s,i+1,*,s,n,*),i=1,2,n,。,s,i,S,i,结论：,最优对任一参与者的任一策略成立；,是一种可以自动实施的协议,(,self-enforcing),56,两人有限博弈纳什均衡的确定,例：用表上作业法寻找,nash,均衡,B,A,L,C,R,U,（,0,4,）,（,4,0,）,（,5,3,）,M,（,4,0,）,（,0,4,）,（,5,3,）,D,（,3,5,）,（,3,5,）,（,6,6,）,57,对纳什均衡的理解,“,一致性,”,特征：,局中人预测到均衡；局中人也预测到其它人预测到均衡；,没有局中人有兴趣作不同的选择。,是局中人的一致性预测；但不一定最好。,58,与严优均衡的关系：,（,1,）每个占优均衡、重复剔除的占优均衡一定是纳什均衡，反之则不然。,（,2,）纳什均衡一定是在重复剔除严劣策略过程中没有剔除的策略组合，反之则不然。,（,3,）纳什均衡有强弱之分。强纳什均衡；弱纳什均衡。允许弱劣策略存在。,59,例：市场进入博弈,参与人：,在位者；进入者,策略：,在位者：默许、斗争；,进入者：进入、不进入。,假定：,进入之前的垄断利润为,300,，,进入之后寡头利润为,100,，,进入成本为,10,。,60,在位者,进入者,默许,斗争,进入,（,40,50,）,（,10,0,）,不进入,（,0,300,）,（,0,300,）,纳什均衡分析：,（进入，默许）是强纳什均衡，,（不进入，斗争）是弱纳什均衡。,61,重复剔除弱劣策略方法：,“,斗争,”,是在位者的弱劣战略被剔除，（进入，默许）是唯一重复剔除的占优均衡；,纳什均衡（不进入，斗争）将被剔除掉。,说明（弱）纳什均衡允许弱劣战略存在。,62,4.,纳什均衡应用举例,（,1,）,消耗战（鹰鸽博弈）,两只老虎为争夺猎物对峙。都坚持则猎物腐烂；一方放弃则归另一方；都放弃则都得不到猎物。猎物价值,f,，僵持成本为,c,。,（对称博弈与对称均衡）,63,（,2,）性别战（协调博弈）,一对情侣周末安排，女方喜欢音乐会，男方喜欢足球赛。情侣陪伴看喜欢的为最好，陪情侣看自己不喜欢的为次之，各自看自己喜欢的又次之，各自看不喜欢的最糟糕。,64,（,3,）协同作业,1,两人合作，报酬相同为,v,。两人同时用力，代价为,c,l,；只有一人用力，代价为,c,h,。,c,l,V 0,a,i,=0,（图？）,最优反应函数：,a,i,*,(a,j,)=(c+a,j,)/2,联立求,Nash,均衡得：,a,1,=a,2,=c,66,（,5,）,Cournot,寡头竞争模型,Cournot,，,1838,，,完全信息静态博弈。,参与人：,企业,1,和企业,2,；,企业策略：,选择产量；,支付：,利润，是两个企业产量的函数。,67,第,i,个企业的产量：,成本函数：,价格函数：,第,i,个企业的利润函数：,68,对每个企业的利润函数求导并令其等于零：,分别定义了两个反应函数：,结论：,每个企业的最优战略（产量）是另一个企业产量的函数。,69,两个反应函数的交叉点就是纳什均衡：,70,考虑上述模型的简单情况：,设，,价格函数取线性形式：,最优化的一阶条件分别为：,71,反应函数为：,解两个反应函数，得纳什均衡为：,每个企业的纳什均衡利润分别为：,72,与垄断情况作比较：,垄断企业的问题：,垄断企业的最优产量：,垄断利润：,73,结论：,（,1,）寡头竞争的总产量大于垄断产量的原因，在于每个企业在选择自己的最优产量时，只考虑对本企业利润的影响，而忽视对另一个企业的外部负效应。,（,2,）易证明，双方串谋成立卡特尔是不稳定的，双方都有欺骗的动机。（？）,74,（,6,）自学,伯川德模型,多党竞选；事故赔偿法；,公共地悲剧；争议仲裁；,合作性谈判；报案；专家诊断；,75,5.,混合策略纳什均衡,例：社会福利博弈（父母与懒惰儿子）,参与人：,政府；一个流浪汉,政府策略：,救济、不救济；,流浪汉策略：,找工作、流浪,76,支付矩阵：,流浪汉,政府,找工作,游荡,救济,（,3,，,2,）,（,1,，,3,）,不救济,（,1,，,1,）,（,0,，,0,）,77,假定：政府的混合策略,流浪汉的混合策略,则政府的期望效用函数为：,78,对上述效用函数求微分，得到政府最优化的一阶条件为：,即，流浪汉以,0.2,的概率选择寻找工作，,0.8,的概率选择流浪。,所以，如果，政府将选择不救济；如果，政府将选择救济；只有当,时，政府才会选择混合策略（）或任何纯策略。,79,同理，求解流浪汉的最优化问题，即可找出政府的均衡混合战略。,易知 （？）,纳什均衡要求，每个参与人的混合策略是给定对方的混合策略下的最优选择。因此，在社会福利博弈中，是唯一的纳什均衡。,80,例：监督博弈,参与人：,税收机关；纳税人,税收机关策略：,检查、不检查；,纳税人策略：,逃税、不逃税,81,支付矩阵：,a,是应纳税款，,C,是检查成本，,F,是罚款,;,C0,;,(2),如果决定控告，原告要求被告支付,s0,私了,;,(3),被告决定是否接受原告的要求,;,(4),如果被告拒绝，原告决定放弃或是向法庭起诉，原告的起诉成本为,p,，,被告的辩护成本为,d,;,(5),如果案子到了法庭，原告以,概率赢得,x,单位的支付,.,125,提出,s,126,分析：,原告指控条件,：,x-p0,，,即,xe,i,的,vV(i),，,存在一个贴现因子,*,1,，,使得对于所有,*,v=(v,1,v,2,.,v,n,),是一个特定的子博弈精炼纳什均衡结果。,159,说明：,a,*,为,v,的惩罚点，或纳什威胁点,Nash threat point,。,由于害怕触发阶段纳什均衡，局中人有积极性保持合作并乐于惩罚机会主义行为。,160,