运筹学第3版教学课件作者熊伟ch13博弈论课件幻灯片.pptx

运筹学第3版教学课件作者熊伟ch13博弈论课件幻灯片.pptx

《运筹学第3版教学课件作者熊伟ch13博弈论课件幻灯片.pptx》由会员分享，可在线阅读，更多相关《运筹学第3版教学课件作者熊伟ch13博弈论课件幻灯片.pptx（78页珍藏版）》请在冰点文库上搜索。

,运筹学,OperationsResearch第13章博弈论gametheory引言纳什均衡反应函数法有限二人零和博弈有限二人非零和博弈,13.1引言,Introduction,红尘俗世，莫不博弈博弈是人类的天性竞争与合作猎人与猎狗：

竞争绩效学习型团队激励叛逃与招安裁员与创业股份公司的成立出书,13.1引言,13.1.1博弈论概述博弈论（gametheory）亦称对策论，是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。

博弈论中有一个重要的概念即博弈行为，博弈行为是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方案,如何采取行动以及与对手互动对自己最为有利,许多游戏具有特征：

有一定的规则有一个结果有可供选择的策略策略与利益相互依存,13.1引言,博弈论，不同于日常游戏，它具有理论性，应用的范围也不局限于游戏。

博弈是一些个人、对组或其它组织，面对一定的环境条件，在一定的规则下，同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得相应结果的过程。

这些规则应用到经济、军事、政治等领域也有类似的特征。

例如，市场竞争、经营决策、投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、资源利用、谈判、竞选、战争,例如，战国时代的田忌赛马、三国时代的曹不兴溅墨画蝇、曹操兵败华容道、北宋时期的丁渭挖河修皇宫等都是博弈论成功应用的例子。

13.1引言,13.1引言著名法国经济学家泰勒尔（JeanTirole）说：

“正如理性预期使宏观经济学发生革命一样，博弈论广泛而深远地改变了经济学家的思维方式”。

博弈论就是研究博弈行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理方案的数学理论和方法。

是研究决策主体的行为发生直接相互作用时的决策及这种决策的均衡问题。

即它是研究聪明而又理智的决策者在冲突或合作中的策略选择理论。

它将成为当代经济管理学科的前沿领城。

1944年由美国普林斯特大学教授冯诺伊曼、摩根斯坦的著作博弈论和经济行为的出版作为博弈论诞生的标志。

普林斯特大学对博弈论作出重大贡献的还有塔克、库恩、纳什等。

从1994年诺贝尔经济学奖授予3位博弈论专家开始，共有5届诺贝尔经济学奖与博弈论的研究有关，分别为：

1994年，普林斯顿大学约翰纳什、约翰海萨尼、莱因哈德泽尔腾等三位数学家；这三位数学家在非合作博弈的均衡分析理论方面做出了开创性的贡献，1996年，授予英国剑桥大学的詹姆斯莫里斯，威廉维克里在不对称信息条件下的经济激励理论、激励理论、博弈论等方面都做出了重大贡献2005罗伯特约翰奥曼,美国和以色列（双重国籍）经济学家托马斯克罗姆比谢林,美国经济学家通过博弈论分析促进了对冲突与合作的理解,13.1引言,2007美国经济学家莱昂尼德赫维奇、埃里克马斯金和罗杰迈尔森他们在创立和发展“机制设计理论”方面做出了贡献。

“机制设计理论”最早由赫维奇提出，马斯金和迈尔森则进一步发展了这一理论。

这一理论有助于经济学家、各国政府和企业识别在哪些情况下市场机制有效，哪些情况下市场机制无效。

2012年诺贝尔经济学奖得主为哈佛大学教授埃尔文罗斯及加州大学罗伊德沙普利两人因稳定配置和市场设计实践理论获奖。

这一领域源于博弈论思想，属于运筹学分支，强调优化策略问题（递延选择）。

13.1引言,博弈三要素一个博弈需要3个基本要素：

局中人（players）

（2）策略集（strategies）（3）得益函数（payoffs）,是一个局势,策略组,全体局势的集合S可用各局中人的策略集的迪卡尔集表示,13.1引言,13.1.3博弈的结构和分类,13.1引言,1943年2月，日本统帅山本五十六大将计划由南太平洋新不列颠群岛的拉包尔出发，3天穿过俾斯麦海，开往新几内亚的莱城，支援困守的日军。

有两条路线：

北线和南线。

盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。

侦察机重点搜索有两个方案：

北线和南线。

当时未来3天中：

北线阴雨，能见度差；南线晴天，能见度佳。

日美双方各自应采用哪种方案,13.1引言,南线,盟军,日军北线（）,南线,（）,2,北线（）2南线（）1,3,局中人：

盟军、日军；双方策略：

北线、南线，记为:

盟军的赢得矩阵如下：

最优策略是：

即都选择北线。

日军舰队受到重创，但未全歼。

双方选择的策略是：

在最不利中选择最有利的策略。

13.1引言,囚徒1,囚徒的困境（二人非零和博弈）囚徒2坦白,不坦白,坦白,不坦白,双方如何采取博弈使结果对自己最有利？

13.1引言,亚贸,【例13-1】双寡头削价竞争（两个厂商）中南高价低价高价,低价,类似地，广告投资、采用新技术等方面，厂商之间常常耗资巨大，但不一定有利可图的争夺战；对公共资源的掠夺式使用等问题。

我们的目的是如何利用这种困境达到有利于社会，合理利用和开发公共资源，保护环境。

13.1引言,高价,低价,多寡头削价竞争（3个厂商:

亚贸,中南，中北））中南高价低价高价亚贸低价中北采用高价中南,高价亚贸低价中北采用低价,13.1引言,约束与激励、核吓阻、公共资源的悲剧路径依赖民航禁折令2002年国家邮政总局“64号文件”宇宙法则：

78/22法则博傻理论胆小博弈胆大博弈,【例13-2】动态博弈：

甲向乙借一万元钱经营，甲许诺经营成功后分给乙总利润（4万）的一半，乙是否借给甲？

乙,甲,借,不借,乙,分,不分,（2，2）,（1，0）,打,乙,不打,（0，4）,（1，0）有法律保障,（1,0）法律保障不足,13.1引言,下一节：

纳什均衡,13.1引言,13.2纳什均衡NashEquilibrium,13.2纳什均衡,NashEquilibrium,Nash对博弈论的贡献有：

（1）合作博弈中的讨价还价模型，称为Nash讨价还价解；

（2）非合作博弈的均衡分析。

纳什均衡（NashEquilibrium）假定有n个博弈方参加博弈，在给定其他博弈方策略的条件下，每个人选择自己的最优策略（个人最优策略可能依赖也可能不依赖他人策略），一起构成一个策略组合（StrategyProfile），而Nash均衡是这样一种策略组合，由所有参与人的最优策略组成，给定别人策略的条件下，没有任何单个参与人有积极性选择其他策略，从而没有任何人有积极性打破这种均衡，Nash均衡是一种“僵局”：

给定别人不动的情况下，没有人有兴趣动。

13.2.1纳什均衡定义约翰纳什（JohnF.Nash）1928年生于美国,1994年获得诺贝尔经济学奖在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响,另一种解释：

假定所有博弈方事先达成一项协议，规定每个人的行为规则，在没有外在的强制力约束时，当事人会自觉遵守这个协议，等于说这个协议构成一个纳什均衡：

假定别人遵守协议的情况下，没有人有积极性偏离协议规定的自己的行为规则。

换句话说，如果一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个参与人会违背此协议，不满足Nash均衡要求的协议是没有意义的。

13.2纳什均衡NashEquilibrium,用G表示一个博弈，若一个博弈中有n个局中人，则每个局中人可选策略的集合称为策略集，分别用S1，S2，Sn表示；Sij表示局中人i的第j个策略，其中j可取有限个值（有限策略博弈），也可取无限个值（无限策略博弈）；博弈方i的得益则用hi表示；hi是各博弈方策略的多元函数，n个局中人的博弈G常写成：

12ni,一个策略组成的某个策略组合（S*，S*，S*）中，任一博弈方i的策略S*，都是对,1i-1,其余策略方策略的组合（S*，S*，S*,i+1,n,i1,，S*）的最佳策略，即h（S*，,S*,i-1ii+1ni1i-1iji+1niji,，S*，S*S*）h（S*，S*，S，S*，S*）对任意SS都成立，,1,n,则称（S*，S*）为G的一个纯策略“纳什均衡”（NashEquilibrium）,G=S1，Sn；h1，hn【定义13.1】在博弈G=S1，S2，Sn；h1，h2hn中，如果由各个博弈方的各选取,13.2纳什均衡NashEquilibrium,各选取一个策略组成的某个策略组合构成一个局势，其最优局势称为纯策略意义下的最优局势【例13-3】假设有三个厂商在同一市场上生产销售完全相同的产品，它们各自的产量分别用m1、m2和m3表示，再假设m1、m2和m3只能取1、2、3等正整数值市场出清价格一定是市场总产量Q=m1+m2+m3的函数，假设该函数为：

不妨先假设三个厂商开始时分别生产3单位，9单位和6单位产量，这时三厂商是否满意各自的产量，要从利润进行分析由于产量不能超过20，则第i个厂商的利润函数为,13.2纳什均衡,可算出在产量组合为（3，9，6）时，市场价格为2，三厂商的利润分8，16和12，再作其它产量组合时亦会有不同的结果，如表13-2表13-2三厂商离散产量结合对应价格和利润,13.2纳什均衡NashEquilibrium,13.2.2混合策略纳什均衡【定义13.2】在博弈G=S1，Sn；h1，hn中，局中人i的策略集为Si=Si1，Sik，则他以概率分布pi=（pi1，pik）随机在其k个可选策略中选择的“策略”称为一个混合策略，其中0pij1对j1，k都成立，且pi1+pik=1,13.2纳什均衡NashEquilibrium,【定义13.3】如果一个策略G=S1，Sn，h1，hn中，参予者i的策略集为,12n,Si=Si1，Sik，如果由各个博弈方的策略组成策略集合G*=S*，S*，S*，,其中,都是对其余博弈方策略组合的最佳策略，即i（S1,S2,，Si-1，Si，Sn）i（S1,S2,，Si-1，Si，Sn）*,对任意SijSi都成立，则称（S1,，Sn）为G的一个混合策略纳什均衡*,13.2纳什均衡NashEquilibrium,下一节：

反应函数法,13.2纳什均衡NashEquilibrium,13.3反应函数法Methodofreactionfunction,13.3反应函数法Methodofreactionfunction,当得益是博弈的多元连续函数时，求出每个博弈方的反应函数，而各个反应函数的交点就是纳什均衡【例13-4】设A，B两厂家生产同样产品，厂商A产量为q1，B产量为q2，市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数P6Q。

设产品产量的边际成本相等，C1=C2=2。

求解两厂商的纳什均（假设产量连续可分）。

分析：

这是一个连续产量的古诺模型，不难看出，该博弈中两厂商各自的利润分别为各自的销售收益减去各自成本，即：

作反应函数：

（0,4）,（0,2）,（2,0）,（4,0）,（4/3,4/3）,纳什均衡：

（4/3,4/3）,13.3反应函数法Methodofreactionfunction,【例13-5】考虑上述模型的另一种情况即各厂商所选择的是价格而不是产量，假设产量与价格的函数关系为：

其它条件不变，边际成本为C1、C2，试求解其纳什均衡。

解各自的策略空间为,两方的得益就是各自的利润,13.3反应函数法Methodofreactionfunction,13.3反应函数法Methodofreactionfunction利用得益函数在偏导数为0时有最大值，各自的反应函数分别为：

为该博弈唯一的纳什均衡,【例13-6】设有3个农户一起放牧羊群，现有一可供大家自由放牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则就会影响到羊群的产出，假设每只羊的产出函数为,成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道其它农户的决策，试求出该决策问题的纳什均衡。

【解】各农户的得益函数分别为,13.3反应函数法Methodofreactionfunction,反应函数,因此该博弈的纳什均衡为（18，18，18）,下一节：

有限二人零和博弈,作业：

教材T13.1,13.3反应函数法Methodofreactionfunction,13.4有限二人零和博弈Twopersonfinitezero-sumgame,矩阵博弈就是二人有限零和博弈。

通常矩阵用来表示局中人1的赢得，局中人2的支付。

用、表示两个局中人，并设局中人有m个纯策略，1，2，m，局中人有个纯策略1，2，n，则按博弈论的相关要素定义，局中人、的策略集分别为,13.4有限二人零和博弈,13.4有限二人零和博弈可以算出，局中人、所构成的策略组合共有mn个，记局中人在策略（i,j）下的赢得aij，则在每个策略的赢得构成一个矩阵,当局中人、的策略集S1,S2及I的赢得矩阵确定后，一个矩阵博弈就给定了通常将阵博弈记为：

13.4有限二人零和博弈13.4.1数学定义,称A为局中人的赢得矩阵（或为的支付矩阵），由于博弈为零和的，故局中人的得矩阵为（A）。

矩阵博弈记为,成立，,，则称VG为博弈G的值，对应的策略组合,13.4.2纯策略矩阵博弈【定义13.4】设G=S1，S2；A为矩阵博弈，其中S1=1，2，n，S2=1，2，n，若等式,称为该博弈的纳什均衡,13.4有限二人零和博弈,13.4有限二人零和博弈【例13-7】求解矩阵博弈，其中,则有,博弈G的解为：

【解】,13.4有限二人零和博弈【定理13.1】矩阵博弈G=S1，S2；A在纯策略定义下有纳什均衡的充要条件是：

存在策略组合使得对一切i=1，m,j=1，n,均有：

矩阵博弈在纯策略意义下有解且VG=ai*j*的充要条件是：

ai*j*是A的鞍点，在博弈论中，矩阵A的鞍点也称为博弈的鞍点,【定义13.5】设f（x，y）为一个定义在xA及yB上的实函数，如果存在x*A及y*B,使得对一切xA及yB有,则称为函数f的有关鞍点。

矩阵博弈在纯策略意义下的解且,的充要条件是,是A的鞍点。

13.4有限二人零和博弈,【解】直接在赢得表上计算，有,可知=5，i*=1,3，j*=2,4故（1，2）（1，4）（2，2）（2，4）为博弈的纳什均衡，VG=5,13.4有限二人零和博弈【例13-9】设有矩阵博弈G=S1，S2；A，赢得矩阵为,求纳什均衡,【性质13.1】无差别性若,和,为G的两个解，则：

【性质13.2】可交换性若,和,为G的两个解，则,及也是博弈的解以上方法也称“上策均衡法”（Dominant-strategeEqyilibrium）,13.4有限二人零和博弈,【例13-10】甲、乙两个企业同时生产一种电子产品（假设市场上只有这两家，为一双寡头竞争局面），两个企业都想通过改革管理获取更多的销售份额，甲企业的策略措施有：

（1）降低产品价格；

（2）提高产品质量；（3）推出新产品乙企业措施为：

（1）增加广告费用；

（2）增设网点；（3）改进产品性能，通过预测，两个企业市场份额变动情况如表134所示，试确定最优策略,max13,10,5*,【解】则博弈最优解为VG=5，纳什均衡为（3，3）甲企业采用推出新产品策略，乙企业采用改进产品性能策略，结果甲企业赢得5的市场份额,13.4有限二人零和博弈,13.4.3混合策略矩阵博弈纯策略矩阵博弈的满足纳什均衡是满足局中人有把握的至少赢得是局中人有把握的至多损失即：

当V1V2时，这时不存在纯策略意义下的纳什均衡。

田,忌,上中下,上下中,中上下,中下上,下上中,下中上,13.4有限二人零和博弈,利用最大最小和最小最大原则，发现不存在使得成立的点,13.4有限二人零和博弈,例：

对局中人1来说，v1=2，i*=2，对局中人2来说，v2=3，j*=1，v1v2。

没有鞍点。

【定义13.6】设矩阵博弈,，其中,记,13.4有限二人零和博弈,称为G的混合扩充。

E是赢得期望值。

【定义】当,时，称,为局中人、在混合策略中的纳什均衡。

称为局中人在选取混合策略S*时的赢得函数1【定理13.2】矩阵对象G=S1，S2；A在混合策略意义下有解的充要条件是：

存在x*,1,2,*,S，yS，使（,1,*，*,xy）为函数E（x，y）的一个鞍点，即对一切xS，,2,*,yS有,E（x，y*）E（x*，y*）E（x*，y）,13.4有限二人零和博弈,【例13-11】考虑矩阵博弈G=S1，S2；A，其中,试求纳什均衡【解】纯策略纳什均衡不存在设x=（x1，x2）为局中人的混合策略，y=（y1，y2）为局中人的混合策略，则：

局中人1的赢得期望值：

取,，,满足,13.4有限二人零和博弈,分别为局中人和的最优策略即该博弈的纳什均衡。

13.4.4纳什均衡存在定理,12,【定理13.3】设x*S*，y*S*,则（x*，y*）为博弈G的纳什均衡的条件是：

对任意,i=1,，m，j=1,，n，有E（i,y*）E（x*,y*）E（x*,j）,其中：

13.4有限二人零和博弈,【定理13.4】设x*S*，y*S*，则（x*，y*）是博弈G的纳什均衡的充要条件是：

存12在数V，使得x*，y*分别满足：

且V=VG.,【定理13.5】对任一矩阵博弈G=S1，S2；A，一定存在混合策略意义下的纳什均衡,13.4有限二人零和博弈,【定理13.6】设（x*，y*）为矩阵博弈G的一个纳什均衡，V=VG，则,*,

（1）若xi0，则,*,

（2）若yi0，则,（3）若,，则,（4）若,则,13.4有限二人零和博弈,例,13.4有限二人零和博弈【定理13.7】设有两个矩阵博弈G1=S1，S2；A,G2=S1，S2；A则

（1）VG2=VG1

（2）T（G1）=T（G2）其中0为一常数，T（G1）、T（G2）为两个博弈的解集合,1.优超原则法,【例13-12】设赢得矩阵A为:

求纳什均衡【解】第4行优于第1行，第3行优于第2行，故可划去第1行和第2行，得到新的赢得矩阵，x1=x2=0,13.4有限二人零和博弈,13.4.5矩阵博弈求解方法,“严格下策反复消去法”（IteratedEliminationofStrictlyDominatedStrategies）,13.4有限二人零和博弈对于A1第1列优于第3列，第2列优于第4列，（1/2）（第1列）+（1/2）（第2列）优超于第5列，因此去掉第3列，第4列和第5列，y3=y4=y5=0，得到A2：

又由于第1行优超于第3行，所以从A2中划去第3行，x5=0，得到A3，解方程组：

该矩阵博弈的纳什均衡为：

VG=4.8,2.线性方程组法若最优策略中和均不为零时，有,13.4有限二人零和博弈,【例13-14】求解矩阵博弈,【解】建立方程组,求解得：

x=（0.525，0.275，0.2）,y=（0.2，0.05，0.75）;VG=0.45,3.线性规划方法任意矩阵博弈的求解均等价于一对互为对偶的线性规划问题，而定理13.4表明，博弈G的解等价于下面两个不等式的解,【定理13.9】设矩阵博弈的值为v，则：

13.4有限二人零和博弈,13.4有限二人零和博弈则局中人、的最优策略等价于线性规划问题：

令,有,局中人：

13.4有限二人零和博弈,同理,令,有,局中人：

13.4有限二人零和博弈,13.4有限二人零和博弈【例13-12】利用线性规划方法求解赢得矩阵为,的矩阵博弈的纳什均衡【解】此问题可化为两个互为对偶的线性规划问题：

最优解：

X（0.1065，0.1448，0.0437）,Y（0.1093，0.1038，0.0819）；w0.29508利用变换,得到x*=（0.36，0.49，0.15），y*=（0.37，0.35，0.28）；v=3.39,13.4有限二人零和博弈,下一节：

有限二人非零和博弈,13.4有限二人零和博弈,作业：

教材,T13.2、3、4、5、6、7,13.5有限二人非零和博弈Twopersonfinitenon-zero-sumgame,13.5有限二人非零和博弈,13.5.1数学定义【例13.16】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩阵分别为,矩阵A1和A2合并为双矩阵,依然在混合扩充意义下考虑有限二人非零和博弈，记局中人1的混合策略为x，局中人2的混合策略为y，相应的策略集记为,13.5有限二人非零和博弈【定义13.8】对于某个有限二人非零和博弈，其局中人1的赢得（混合策略下）为,局中人2的赢得为,13.5有限二人非零和博弈,13.5.2有限二人非零和博弈纳什均衡,分别是局中人1和2的赢得，如果有一博弈略,，,和,为任意策略，,满足,则称,为该博弈的纳什均衡，称,为博弈的纳什均衡解（或赢得）【定理13.10】（纳什定理）任何矩阵博弈及有限二人非零和博弈至少有一个纳什均衡,【定义13.9】在有限二人非零和博弈中,设,13.5有限二人非零和博弈,13.5.322有限二人非零和博弈的求解1.图解法【例1317】图解下列非零和博弈,【解】

（1）作出坐标系图133，原点为0，在各轴值为1的点分别引线段与坐标轴构成正方形，它便是（x，y）的定义域，

（2）局中人1的赢得（期望值）为,13.5有限二人非零和博弈,当0y2/5，x=0时e1（x,y）最大；当y=2/5，0x1时e1（x,y）最大；当2/5y1，x1时e1（x,y）最大；画出的曲线即图133中的曲线1，它是一条折线。

（3）局中人2的赢得为,13.5有限二人非零和博弈,（3）局中人2的赢得为,图13,曲线l和曲线2在图134中有三个交点（用“0”号标出）这三个交点上的x*和y*所构成的局势,能够同时满足平衡条件,13.5有限二人非零和博弈,博弈值为（3,2）,博弈值为（2.4，2.5）,

（1）,

（2）,（3）有效解为混合策略（3）,博弈值为（4，4）,2.优超原则法存在某个策略绝对劣于另一个策略时，称为下策，去掉下策。

【例1318】用优超原则求解下列非零和博弈,纳什均衡（纯策略）解：

博弈值：

13.5有限二人非零和博弈,3.划线法当局中人2采取策略j时，局中人1在对自己最有利的策略值下划一横线。

同理，当局中人1采取策略i时，局中人2在对自己最有利的策略值下划一横线。

如果某一组合策略值下都划了横线，则此组合策略就是纳什均衡解。

否则，不存在纯策略意义下的纳什均衡。

例13-17：

下都已划线，则纳什均衡解为例13-17得到两个解，无法确定。

这种情形划线法失效！

4.方程组方法,13.5有限二人非零和博弈,局中人2取策略1时的期望值为局中人2取策略2时的期望值为局中人2取策略n时的期望值为局中人1选取概率x1，x2，xm的目的一定要使得局中人2取策略j的赢得期望值都相等并且概率求和等于1，即,13.5有限二人非零和博弈,方程组的解为纳什均衡的解。

同理，对局中人1有,13.5有限二人非零和博弈对于例13-17：

解方程组得到纳什均衡的解：

博弈值为（2.4，2.5）其中：

TheEndofChapter13,作业：

教材T13.813.9,13.5有限二人非零和博弈本章其它内容略。