引言纳什均衡NashEquilibrium反应函数法.ppt

,12.1 引 言 12.2 纳什均衡 Nash Equilibrium 12.3 反应函数法 Method of reaction function 12.4 有限二人零和博弈 Two person finite zero-sum game 12.5 有限二人非零和博弈 Two person finite non-zero-sum game,第12章 博 弈 论game theory,Page 2,博弈论（game theory）亦称对策论，是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学、也是运筹学的一个重要分支。博弈行为是博弈论中一个重要的概念。博弈行为是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方案，如何采取行动以及与对手互动对自己最为有利。,12.1.1 博弈论概述,12.1 引 言,Page 3,【例12-3】齐威王田忌赛马 齐王：上 中 下 田忌：下 上 中,12.1.1 博弈论概述,Page 4,【补充例1】囚徒的困境,12.1.1 博弈论概述,Page 5,博弈：是一些个人、团队或其它组织，面对一定的环境条件，在一定的规则下，同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得相应结果的过程。博弈行为具有的共同特征：（1）有一定的规则（2）有一个明确的结果（3）有可供选择的策略（4）策略与利益相互依存,12.1.1 博弈论概述,Page 6,在现实社会、经济生活中很多活动都具有博弈的特征，例如：市场竞争、经营决策、投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、资源利用、谈判、竞选、战争等。又如，三国时代的曹不兴溅墨画蝇、曹操兵败华容道、北宋时期的丁渭挖河修皇宫等都是博弈论成功应用的例子。,12.1.1 博弈论概述,Page 7,博弈论研究的问题:参与博弈的各方是否存在最合理的策略以及如何找到合理的策略。博弈论是研究决策主体的行为发生直接相互作用时的决策及这种决策的均衡问题。即它是研究聪明而又理智的决策者在冲突或合作中的策略选择理论。它将成为当代经济管理学科的前沿领城。著名法国经济学家泰勒尔（Jean Tirole）说：“正如理性预期使宏观经济学发生革命一样，博弈论广泛而深远地改变了经济学家的思维方式”。,12.1.1 博弈论概述,Page 8,1944年美国普林斯特大学教授冯诺伊曼、摩根斯坦的著作博弈论和经济行为的出版，是博弈论诞生的标志。普林斯特大学对博弈论作出重大贡献的还有塔克、库恩、纳什等。,12.1.1 博弈论概述,要想在现代社会做 一个有文化的人，你必须对博弈论有一个大致的了解。萨缪尔森,Page 9,12.1.1 博弈论概述,约翰纳什(John F.Nash)1928年生于美国,1994年获得诺贝尔经济学奖。在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响。Nash对博弈论的主要贡献有：（1）合作博弈中的讨价还价模型，称为Nash讨价还价解；（2）非合作博弈的均衡分析。,Page 10,博弈论发展史上的五次诺贝尔经济学奖1994年，纳什、海萨尼、塞尔顿，非合作博弈理论,12.1.1 博弈论概述,Page 11,博弈论发展史上的五次诺贝尔经济学奖 1996年，莫里斯和维克瑞，不对称信息条件下激励机制问题,12.1.1 博弈论概述,Page 12,博弈论发展史上的五次诺贝尔经济学奖 2005年，罗伯特.奥曼，托马斯.谢林，合作博弈理论,12.1.1 博弈论概述,Page 13,博弈论发展史上的五次诺贝尔经济学奖 2007年，三名美国经济学家莱昂尼德.赫维奇，埃里克.马斯金，罗杰.迈尔森，“机制设计理论”,12.1.1 博弈论概述,Page 14,博弈论发展史上的五次诺贝尔经济学奖 2012年，美国经济学家阿尔文.罗思（Alvin E.Roth）和劳埃德.沙普利（Lloyd S.Shapley），“稳定匹配理论和市场设计实践”。,12.1.1 博弈论概述,Page 15,博弈模型的3个基本要素：（1）局中人(players)：博弈的参加者，可以是一个人、一个团队、一个企业、交战的一方等。假设每一个局中人都是“理智”的。（2）策略集(strategies)：策略是可供局中人选择的实际可行的完整的行动方案。每个局中人的策略集（S）至少应包括两个策略。（3）得益（赢得）函数(payoffs)：当每个局中人的策略确定后，他们就会得到相应的收益或损失称为局中人的得益，不同的策略会导致不同的得益，因此，得益是策略的函数。,12.1.2 博弈三要素,Page 16,n人博弈,全体局势的集合S可用各局中人的策略集的迪卡尔集表示,12.1.2 博弈三要素,局势：每一个局中人各选择一个策略形成的对局(策略组合)。两人博弈,二人博弈的矩阵型表示:,囚徒2,囚徒1,17,12.1.3 博弈的结构和分类,Page 18,12.1.3 博弈的结构和分类,Page 19,【例12-2】1943年2月，日本统帅山本五十六大将计划由南太平洋新不列颠群岛的拉包尔出发，3天穿过俾斯麦海，开往新几内亚的莱城，支援困守的日军。有两条路线：北线和南线。盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。侦察机重点搜索有两个方案：北线和南线。当时未来3天中：北线阴雨，能见度差；南线晴天，能见度佳。日美双方各自应采用哪种方案。,12.1.3 博弈的结构和分类,北线,南线,Page 21,【解】局中人：盟军、日军 双方策略：北线、南线盟军的赢得矩阵如下：,最优局势是：即都选择北线。日军舰队受到重创，但未全歼。,双方选择策略的思路：在最不利中选择最有利的策略。,12.1.3 博弈的结构和分类,两人有限零和博弈,Page 22,【补充例2】双寡头削价竞争（两个厂商）,类似地，广告投资、采用新技术等方面，厂商之间常常耗资巨大，但不一定有利可图的争夺战；对公共资源的掠夺式使用等问题。我们的目的是如何利用这种困境达到有利于社会，合理利用和开发公共资源，保护环境。,12.1.3 博弈的结构和分类,两人有限非零和博弈,Page 23,多寡头削价竞争（3个厂商：亚贸，中南，中北）,中北采用高价,中北采用低价,12.1.3 博弈的结构和分类,Page 24,【补充例3】动态博弈：甲向乙借一万元钱经营，甲许诺经营成功后分给乙总利润（4万）的一半，乙是否借给甲？,乙,甲,借,不借,乙,分,不分,(2，2),(1，0),打,乙,不打,(0，4),(1，0),(1,0),有法律保障,法律保障不足,12.1.3 博弈的结构和分类,完全信息动态博弈,Page 25,约束与激励、核吓阻、公共资源的悲剧路径依赖民航禁折令2002年国家邮政总局“64号文件”宇宙法则：78/22法则博傻理论胆小博弈胆大博弈,12.1.3 博弈的结构和分类,Page 26,下一节：纳什均衡,12.1 引言,Page 27,12.2 纳 什 均 衡,纳什均衡（Nash Equilibrium）:假定有n个博弈方参加博弈，在给定其他博弈方策略的条件下，每个人选择自己的最优策略（个人最优策略可能依赖也可能不依赖他人策略），从而使自己利益最大化，所有局中人的策略一起构成一个策略组合。而Nash均衡是这样一种策略组合，由所有参与人的最优策略组成，给定别人策略的条件下，没有任何单个参与人有积极性选择其他策略，从而没有任何人有积极性打破这种均衡，Nash均衡是一种“僵局”：给定别人不动的情况下，没有人有兴趣动。,12.2.1 纳什均衡定义,Page 28,另一种解释：假定所有博弈方事先达成一项协议，规定每个人的行为规则，在没有外在的强制力约束时，当事人会自觉遵守这个协议，等于说这个协议构成一个纳什均衡：假定别人遵守协议的情况下，没有人有积极性偏离协议规定的自己的行为规则。换句话说，如果一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个参与人会违背此协议，不满足Nash均衡要求的协议是没有意义的。,12.2 纳 什 均 衡,Page 29,12.2 纳 什 均 衡,“纳什均衡”改变了经济学的语言和表达方法。在进化博弈论方面相当有造诣的坎多利（Kandori，1997）对保罗萨缪尔森（Paul Samuelson）的名言“你甚至可以使一只鹦鹉变成一个训练有素的经济学家，因为它必须学习的只有两个词，那就是供给和需求”，曾做过一个幽默的引申，他说，“现在这只鹦鹉需要再学一个词，那就是纳什均衡”。,Page 30,12.2 纳 什 均 衡,你正在图书馆枯坐，一位陌生美女主动过来和你搭讪，并要求和你一起玩个数学游戏。美女提议：“让我们各自亮出硬币的一面，或正或反。如果我们都是正面，那么我给你3元，如果我们都是反面，我给你1元，剩下的情况你给我2元就可以了。”那么该不该和这位姑娘玩这个游戏呢？,Page 31,用G表示一个博弈，若一个博弈中有n个局中人，则每个局中人可选策略的集合称为策略集，分别用 S1，S2，Sn表示 sij表示局中人 i 的第 j 个策略，其中 j 可取有限个值（有限策略博弈），也可取无限个值（无限策略博弈）；博弈方 i 的得益则用hi 表示；hi 是各博弈方策略的多元函数，n个局中人的博弈G常写成：,G=S1，Sn；h1，hn,12.2 纳 什 均 衡,Page 32,纯策略纳什均衡【定义12.1】在博弈G=S1,S2,Sn；h1,h2hn中，如果由各个博弈方各选取一个策略组成的某个策略组合（s1*,s2*,sn*）中，任一博弈方 i 的策略si*，都是对其余局中人策略的组合（s1*,s*i-1,s*i+1,sn*）的最佳选择，即对任意sijSi都成立，则称（s1*,sn*）为G的一个纯策略“纳什均衡”（Nash Equilibrium）。,12.2 纳 什 均 衡,各选取一个策略组成的某个策略组合构成一个局势，其最优局势称为纯策略意义下的最优局势（纳什均衡）。,Page 33,【例12-1】假设有三个厂商在同一市场上生产销售完全相同的产品，它们各自的产量分别用m1、m2和m3表示，再假设m1、m2和m3只能取1、2、3等正整数值。市场出清价格一定是市场总产量Q=m1+m2+m3的函数，假设该函数为：,不妨先假设三个厂商开始时分别生产3单位，9单位和6单位产量，这时三厂商是否满意各自的产量，要从利润进行分析，由于产量不能超过20，则第i个厂商的利润函数为,12.2 纳 什 均 衡,Page 34,可算出在产量组合为（3，9，6）时，市场价格为2，三厂商的利润分别为6，18和12，再作其它产量组合时亦会有不同的结果。,表12-2 三厂商离散产量组合对应价格和利润,12.2 纳 什 均 衡,Page 35,【定义12.2】在博弈G=S1，Sn；h1，hn中，局中人i的策略集为Si=si1，sik，则他以概率分布pi=（pi1，pik）随机在其k个可选策略中选择的“策略”称为一个混合策略，其中0pij1对j1，k都成立，且pi1+pik=1。纯策略是混合策略的特殊情形，只是选择相应纯策略的概率服从（0-1）分布。一个混合策略可理解为：如果进行多局博弈G的话，局中人i分别选取纯策略的频率；若只进行一次博弈，则反映了局中人i对各纯策略的偏爱程度。,混合策略纳什均衡,12.2 纳 什 均 衡,Page 36,【定义12.3】如果一个博弈G=S1，Sn，h1，hn中，参予者i的策略集为Si=si1，sik，如果由各个博弈方的策略组成策略集合G*=s1*，s2*，sn*，其中都是对其余博弈方策略组合的最佳策略，即 hi(s1*,s2*,si-1*,si*,si+1*sn*)hi(s1*,s2*,si-1*,sij,si+1*,sn*)对任意sijSi都成立，则称(s1*,，sn*)为G的一个混合策略纳什均衡,12.2 纳 什 均 衡,Page 37,下一节：反应函数法,作业：教材P293 T10,12.2 纳什均衡Nash Equilibrium,Page 38,当得益是博弈的多元连续函数时，求出每个博弈方的反应函数，而各个反应函数的交点就是纳什均衡。,12.3 反应函数法,Page 39,【例12-4】设A，B两厂家生产同样产品，厂商A产量为q1，B产量为q2，市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数P6Q。设产品产量的边际成本相等，C1=C2=2。求解两厂商的纳什均衡（假设产量连续可分）。分析：这是一个连续产量的古诺模型，不难看出，该博弈中两厂商各自的利润分别为各自的销售收益减去各自成本，即：,12.3 反应函数法,q1 q1,Page 40,作反应函数,纳什均衡：(4/3,4/3),12.3 反应函数法,Page 41,【例12-5】考虑上述模型的另一种情况，即各厂商所选择的是价格而不是产量，假设产量与价格的函数关系为：,其它条件不变，边际成本为C1、C2，试求解其纳什均衡。【解】各自的策略空间为,两方的得益就是各自的利润,12.3 反应函数法,Page 42,为该博弈唯一的纳什均衡,12.3 反应函数法,Page 43,【例12-6】设有3个农户一起放牧羊群，现有一可供大家自由放牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则就会影响到羊群的产出，假设每只羊的产出函数为,成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道其它农户的决策，试求出该决策问题的纳什均衡。,【解】各农户的得益函数分别为,12.3 反应函数法,Page 44,12.3 反应函数法,反应函数,因此该博弈的纳什均衡为（18，18，18）,Page 45,用反应函数法求纳什均衡的步骤：1.建立得益函数；2.求反应函数：即对得益函数求偏导数；3.解反应函数方程组。反应函数方程组的解即为纳什均衡。,12.3 反应函数法,Page 46,下一节：有限二人零和博弈,作业：教材P293 T 9,12.3 反应函数法,Page 47,12.4 二人有限零和博弈,两人有限零和博弈也称矩阵博弈，在众多博弈模型中占有重要地位，也是最简单、理论和算法都比较完善的一类。齐威王田忌赛马，例12-2均为矩阵博弈。,Page 48,12.4.1 数学模型 模型：S1=1,2,，m局中人的纯策略集 S2=1,2,，n局中人的纯策略集 ai j局中人在局势（i,j）下的赢得值 局中人的得益矩阵(局中人的得益矩阵为-A),G=S1，S2；A,:,12.4 二人有限零和博弈,Page 49,建立齐王田忌赛马的数学模型S1=(上中下）,（上下中）,（中上下）,（中下上）,（下上中）,（下中上)S2=(上中下）,（上下中）,（中上下）,（中下上）,（下上中）,（下中上),12.4.1 数学模型,Page 50,12.4.1 数学模型,齐王的赢得矩阵,Page 51,【例12-7】求解矩阵博弈，其中,博弈G的解（纳什均衡）为：,【解】,12.4.2 纯策略矩阵博弈,局中人的最优策略是2,局中人的最优策略是2,S1=1,2,3,4 S2=1,2,3,Page 52,12.4.2 纯策略矩阵博弈,Page 53,【定理12.1】矩阵博弈G=S1，S2；A在纯策略意义下有纳什均衡的充要条件是：存在策略组合 使得对一切i=1，m,j=1，n,均有：意义：当局中人选定纯策略i*后，局中人为了使其所失最少，只能选择纯策略j*，否则就可能损失得更多；反之，当局中人选定纯策略j*后，局中人为了得到最大的赢得也只能选择纯策略i*，否则就会赢得更少，双方的竞争在局势（i*,j*）下达到了一个平衡状态。即纳什均衡。,12.4.2 纯策略矩阵博弈,Page 54,【定义12.5】设 f(x，y)为一个定义在xA及yB上的实函数，如果存在x*A及y*B,使得对一切xA及yB有,则称 为函数 f 的一个鞍点。,矩阵博弈在纯策略意义下有解且 的充要条件是：,12.4.2 纯策略矩阵博弈,Page 55,【例12-9】设有矩阵博弈G=S1，S2；A，赢得矩阵为,求纳什均衡,12.4.2 纯策略矩阵博弈,S1=1,2,3,4 S2=1,2,3，4,Page 56,纳什均衡为：(1,2)，(1,4)，(3,2)，(3,4)博弈值VG=5局中人的最优纯策略为1，3局中人的最优纯策略为2，4,12.4.2 纯策略矩阵博弈,A=,1234,1 2 3 4,【解】,Page 57,【性质12.1】无差别性。若 和 为G的两个解，则：【性质12.2】可交换性。若 和 为G的两个解，则 和 也是博弈的解,12.4.2 纯策略矩阵博弈,Page 58,应用举例：某单位采购员在秋天时要决定冬季取暖用煤的采购量。已知在正常气温条件下需要煤15吨，在较暖和较冷气温条件下分别需要煤10吨和20吨。假定冬季的煤价随天气寒冷程度而变化，在较暖、正常、较冷气温条件下每吨煤的价格分别为100元、150元和200元。又设秋季时每吨煤的价格为100元，在没有关于当年冬季气温情况准确预报的条件下，秋季时应采购多少吨煤能使总支出最少？试建立该问题的矩阵对策模型，并求解。,12.4.2 纯策略矩阵博弈,Page 59,【解】局中人I（采购员）：S1=10吨，15吨，20吨局中人II（大自然）：S2=较暖，正常，较冷 纳什均衡为（3，3），博弈值VG=-2000既采购员在秋天购煤20吨较好。,12.4.2 纯策略矩阵博弈,Page 60,12.4.3 混合策略矩阵博弈,矩阵博弈满足纯策略纳什均衡是指：满足局中人有把握的至少赢得是局中人有把握的至多损失，即,当V1V2 时，这时不存在纯策略意义下的纳什均衡。,Page 61,利用最小最大和最大最小原则，发现不存在使得成立的点，即不存在纯策略纳什均衡。,12.4.3 混合策略矩阵博弈,齐王田忌赛马,Page 62,【定义12.6】设矩阵博弈，其中 记,12.4.3 混合策略矩阵博弈,Page 63,纯策略与混合策略的关系 纯策略是混合策略的特殊情形。一个混合策略X=(x1,x2,，xm)可理解为：如果进行多局博弈的话，局中人I分别选取纯策略1,2,，m的频率；若只进行一次博弈，则反映了局中人I对各纯策略的偏爱程度。,12.4.3 混合策略矩阵博弈,Page 64,【定理12.2】矩阵博弈G=S1，S2；A在混合策略意义下有解的充要条件是：存在x*S1*，y*S2*，使（x*，y*）为函数E(x,y)的一个鞍点，即对一切xS1*，yS2*有,E（x，y*）E（x*，y*）E（x*，y）,12.4.3 混合策略矩阵博弈,Page 65,【例12-11】考虑矩阵博弈G=S1，S2；A，其中 试求纳什均衡,【解】纯策略纳什均衡不存在。设x=（x1，x2）为局中人的混合策略，y=(y1，y2)为局中人的混合策略，则：局中人的赢得期望值：,12.4.3 混合策略矩阵博弈,x1x2,y1 y2,Page 66,该博弈的纳什均衡为：(x*,y*)其中局中人和的最优策略分别为：x*,y*博弈值,12.4.3 混合策略矩阵博弈,取，则,Page 67,12.4.4 纳什均衡存在定理,【定理12.3】设x*S1*，y*S2*,则（x*，y*）为博弈G的纳什均衡的条件是：对任意i=1,，m，j=1,，n，有 E(i,y*)E(x*,y*)E(x*,j),【定理12.4】设x*S1*，y*S2*，则（x*，y*）是博弈G的纳什均衡的充要条件是：存在数V，使得x*，y*分别满足：,且V=VG,Page 68,【定理12.5】对任一矩阵博弈G=S1，S2；A，一定存在混合策略意义下的纳什均衡。,12.4.4 纳什均衡存在定理,定理说明了矩阵博弈总是有解的，并给出了解所应满足的条件。,【定理12.6】设（x*，y*）为矩阵博弈G的一个纳什均衡，V=VG，则,（1）若 xi*0，则（2）若 yj*0，则（3）若，则（4）若，则,Page 69,例12-11,12.4.4 纳什均衡存在定理,Page 70,12.4.4 纳什均衡存在定理,【定理12.7】设有两个矩阵博弈 G1=S1，S2；A,G2=S1，S2；kA 其中k0为一常数。则G1与G2有相同的解，且：,【补充定理】G1=S1，S2；A1=(aij)mn G2=S1，S2；A2=(aij+d)mn d为常数，则G1与G2有相同的解，且：,【补充例】求解矩阵博弈,Page 71,1.线性方程组法,若最优策略中 和 均不为零时，根据定理12.6，有,12.4.5 矩阵博弈求解方法,注意：（1）应用此方法的条件是所有策略的概率大于零。（2）对于22的矩阵博弈当不存在纯策略鞍点时，容易证明，各局中人的最优策略中xi，yj均大于零，可采用此法求解。,Page 72,【例12-14】求解矩阵博弈,【解】设x=(x1,x2,x3),y=(y1,y2,y3),xi0,yj0,i,j=1,2,3建立方程组,x*=(0.525，0.275，0.2)y*=(0.2，0.05，0.75)该矩阵博弈的纳什均衡为（x*,y*）,搏弈值VG=0.45,12.4.5 矩阵博弈求解方法,Page 73,2.优超原则法（严格下策反复消去法）优超原则：P311【定义12.7】,【定理12.8】,【例12-12】设赢得矩阵A为:,求纳什均衡,12.4.5 矩阵博弈求解方法,Page 74,【解】,12.4.5 矩阵博弈求解方法,Page 75,该矩阵博弈的纳什均衡为：(x*,y*),VG=4.8,12.4.5 矩阵博弈求解方法,Page 76,3.图解法【补充例1】用图解法求解【解】设x=(x1,1-x1)，y=(y1,1-y1)对于局中人：如果局中人选取 1，则有 V=20-15x1 如果局中人选取 2，则有 V=25x1+10,12.4.5 矩阵博弈求解方法,点B(1/4,65/4)为局中人的极值点,Page 77,同理 V=35-30y1 V=10+10y1 解得,12.4.5 矩阵博弈求解方法,该矩阵博弈的纳什均衡为：(x*,y*),VG=16.25,Page 78,【补充例2】某公司有甲、乙两个工厂，每年的税额是400万元和1200万元。对于每个工厂，公司可如实申报税款，或者篡改账目，声称税额为零，而税务局由于人力所限，每年只能检查一个工厂的账目，如果税务局发现工厂偷税，则不但要工厂如数缴纳税款，而且还要缴纳相当于一半税款的罚金。（1）试将该问题表示为一个矩阵博弈模型；（2）求出税务局和公司的最优策略及税务局从公司征收税款（含罚金）。,12.4.5 矩阵博弈求解方法,【解】税务局：S1=查甲工厂，查乙工厂 公司：S2=甲乙都实报，甲乙都报零，甲实报乙报零，甲报零乙实报,利用定理12.7及补充定理化简,设 x=(x1,1-x1)y=(y1,y2,y3,y4)V=6(1)V=-6x1+7(2)V=-9x1+9(3)V=3x1+4(4),点B(1/3,5)为局中人的极值点,=5,点B(1/3,5)不满足方程（1）、（3），由定理12.6 y1=y3=0解(5)(6)组成的方程组,该矩阵博弈的纳什均衡为：(x*,y*),税务局最优策略是以1/3的概率检查甲公司，2/3的概率检查乙公司，这样至少能征收到1400万元的税款,Page 81,【补充例2】用图解法求解,12.4.5 矩阵博弈求解方法,【解】设x=(x1,1-x1)y=(y1,y2,y3,y4)则V=4-2x1(1)V=2x1+1(2)V=-5x1+6(3)V=5x1(4),点B(5/7,17/7)为局中人的极值点,V=17/7,Page 82,12.4.5 矩阵博弈求解方法,同理可得 V=2y1+3y2+y3+5y4(5)V=4y1+y2+6y3(6)将 x1=5/7 代人方程（1）（4）由定理12.6知 y1=y4=0,y20,y30解方程组得,该博弈的纳什均衡为(x*,y*),博弈值为VG=17/7,Page 83,3.线性规划方法,任意矩阵博弈 的求解均等价于一对互为对偶的线性规划问题，而定理12.4表明，博弈G的解等价于下面两个不等式组的解,12.4.5 矩阵博弈求解方法,Page 84,则局中人、的最优策略等价于线性规划问题：,12.4.5 矩阵博弈求解方法,【定理12.9】设矩阵博弈的值为v，则：,Page 85,局中人：,12.4.5 矩阵博弈求解方法,Page 86,局中人：,12.4.5 矩阵博弈求解方法,Page 87,12.4.5 矩阵博弈求解方法,注意：（1）用线性规划法求解的必要条件是V0。如何判断 V0，可以证明，当aij0时，V 0。（2）若某个aij0，可对A的各元素加上适当的数d0，使 所有的aij0,Page 88,【例12-12】利用线性规划方法求解赢得矩阵为,的矩阵博弈的纳什均衡,【解】此问题可化为两个互为对偶的线性规划问题：,12.4.5 矩阵博弈求解方法,Page 89,最优解：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,12.4.5 矩阵博弈求解方法,Page 90,有无纯策略解,优超原则和定理12.7化简,1.A2n或Am2，图解法。2.A22，图解法，方程组法，代数法。3.LP法（aij0),12.4.5 矩阵博弈求解方法,解矩阵博弈的一般步骤,Page 91,下一节：有限二人非零和博弈,Page 92,12.5.1 数学定义假设：彼此了解对方的纯策略集和赢得函数，但不合作，并 且局中人在选择自己策略时不知道对方的选择。数学模型：=S1,S2;(A1,A2),其中 S1=1,2，m，S2=1,2,，n A1=(aij)mn,A2=(aij)mn,A1+A20 两人有限非零和博弈也称为双矩阵博弈。记局中人的混合策略为 x=(x1,x2,xm)，局中人的混合 策略为 y=(y1,y2,ym)，相应的策略集分别记为,12.5 二人有限非零和博弈,Page 93,12.5.1 数学定义,【补充例1】囚徒的困境,Page 94,12.5.1 数学定义,【例11.16】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩阵分别为,矩阵A1和A2合并为双矩阵,【例11.16】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩阵分别为,【例11.16】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩阵分别为,矩阵A1和A2合并为双矩阵,【例11.16】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩阵分别为,矩阵A1和A2合并为双矩阵,Page 95,【定义12.8】对于某个二人有限非零和博弈，其局中人的赢得（混合策略下）为,局中人的赢得为,12.5.1 数学定义,Page 96,12.5.2 二人有限非零和博弈纳什均衡,【定理12.10】（纳什定理）任何矩阵博弈及有限二人非零和博弈至少有一个纳什均衡。,Page 97,1.反应函数法,12.5.3 22二人有限非零和博弈的求解,【例12.17】解双矩阵博弈,【解】（1）局中人1的赢得(期望值)为,局中人2的赢得为,（2）对e1,e2分别求偏导数,x*=(1/2,1/2)Y*=(2/5,3/5)博弈值(u*,v*)=(2.4,2.5),Page 98,2.图解法,12.5.3 22二人有限非零和博弈的求解,【例11.17】图解下列非零和博弈,【解】（1）作出坐标系图123，原点为0，在各轴值为1的点分别引线段与坐标轴构成正方形，它便是(x，y)的定义域，（2）局中人1的赢得(期望值)为,图12-3,Page 99,当0y2/5，x=0 时 e1(x,y)最大；当y=2/5，0 x1时e1(x,y)最大；当2/5y1，x1时e1(x,y)最大；画出的曲线即图123中的曲线1，它是一条折线。,（3）局中人2的赢得为,12.5.3 22二人有限非零和博弈的求解,图12-3,图12-4,Page 100,图12,曲线l和曲线2在图12-4中有三个交点。这三个交点上的x*和y*所构成的局势,能够同时满足平衡条件,12.5.3 22二人有限非零和博弈的求解,（2）博弈值为(3,2),（3）博弈值为(2.4，2.5),（1）博弈值为(4，4),有效解为混合策略（3）,Page 101,纳什均衡(纯策略)为：局中人、的最优策略分别是2，3博弈值：方法：局中人对A1进行行比较，删去数据小的行；局中人对A2进行列比较，删去数据小的列。,3.优超原则法,【例12.18】用优超原则求解下列双矩阵博弈,12.5.3 22二人有限非零和博弈的求解,Page 102,4.划线法,（1）局中人从A1的每列选取最大值划线。（2）局中人从A2的每行选取最大值划线。（3）如果某一策略组合值下都划了横线，则此策略组合就是纳什均衡解，该组数字分别为两人的赢得值。否则，不存在纯策略意义下的纳什均衡。,12.5.3 22二人有限非零和博弈的求解,Page 103,【例12-19】用划线法求解双矩阵博弈,下都已划线，则纳什均衡为(2,3),12.5.3 22二人有限非零和博弈的求解,即：局中人、的最优策略分别是2，3博弈值：,【补充例】用划线法求解囚徒的困境,Page 104,【补充例】一对恋人商量周末的活动安排，是看足球赛还是听音乐会。已知不同策略组合下的收益值如表所示。,求解该博弈问题。（足球，足球），（音乐会，音乐会）是该问题的两个纳什均衡。,12.5.3 22二人有限非零和博弈的求解,Page 105,具有一个以上的纳什均衡时，根据博弈的背景、局中人的一些信息或理性，判断或预测出的最终结局，称为聚点。当存在多重纳什均衡时，一般很难判断最终结局，但在联系博弈背景及局中人习性后，一定条件下可以推断聚点的出现。,12.5.3 22二人有限非零和博弈的求解,Page 106,4.方程组方法,局中人2取策略1时的期望值为,局中人2取策略n时的期望值为,局中人2取策略2时的期望值为,局中人1选取概率x1，x2，xm的目的一定要使得局中人2取策略 j 的赢得期望值都相等并且概率求和等于1，即,12.5.3 22二人有限非零和博弈的求解,Page 107,方程组的解为纳什均衡的解。同理，对局中人1有,12.5.3 22二人有限非零和博弈的求解,Page 108,对于例12-17：,解方程组得到纳什均衡解：,博弈值为(2.4，2.5),12.5.3 22二人有限非零和博弈的求解,X*=(1/2,1/2),Y*=(2/5,3/5),Page 109,论 文,企业如何走出囚徒的困境,Page 110,The End of Chapter 12,作业：教材P292 T2、7,12.5 有限二人非零和博弈,Page 111,