引言纳什均衡NashEquilibrium反应函数法市公开课一等奖百校联赛特等奖课件.pptx

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 theory1第1页 博博弈弈论论（game theory）亦亦称称对对策策论论，是是研研究究含含有有反反抗抗或或竞竞争争性性质质现现象象数数学学理理论论和和方方法法，它它既既是是数数学学、也是运筹学一个主要分支。也是运筹学一个主要分支。博博弈弈行行为为是是博博弈弈论论中中一一个个主主要要概概念念。博博弈弈行行为为是是指指含含有有竞竞争争或或反反抗抗性性质质行行为为，在在这这类类行行为为中中，参参加加斗斗争争或或竞竞争争各各方方各各自自含含有有不不一一样样利利益益和和目目标标，各各方方需需考考虑虑对对手手各各种种可可能能行行动动方方案案，怎怎样样采采取取行行动动以以及及与与对对手手互互动对自己最为有利动对自己最为有利。12.1.1 博弈论概述博弈论概述12.1 引引 言言2第2页【例【例12-3】齐威王田忌赛马齐威王田忌赛马 齐王：上齐王：上 中中 下下 田忌：下田忌：下 上上 中中12.1.1 博弈论概述博弈论概述3第3页【补充例【补充例1】囚徒困境囚徒困境（-1，-1）（-10，-1/4）抵赖抵赖（-1/4，-10）（-5，-5）坦白坦白抵赖抵赖坦白坦白 囚徒囚徒2囚徒囚徒112.1.1 博弈论概述博弈论概述4第4页博弈：博弈：是是一一些些个个人人、团团体体或或其其它它组组织织，面面对对一一定定环环境境条条件件，在在一一定定规规则则下下，同同时时或或先先后后从从各各自自允允许许行行为为或或策策略略中中进行选择并加以实施，各自取得对应结果过程。进行选择并加以实施，各自取得对应结果过程。博弈行为含有共同特征：博弈行为含有共同特征：（1）有一定规则）有一定规则（2）有一个明确结果）有一个明确结果（3）有可供选择策略）有可供选择策略（4）策略与利益相互依存）策略与利益相互依存12.1.1 博弈论概述博弈论概述5第5页 在在现现实实社社会会、经经济济生生活活中中很很多多活活动动都都含含有有博博弈弈特特征征，比比如如：市市场场竞竞争争、经经营营决决议议、投投资资分分析析、价价格格制制订订、费费用用分分摊摊、财财政政转转移移支支付付、投投标标与与拍拍卖卖、反反抗抗与与追追踪踪、资源利用、谈判、竞选、战争等。资源利用、谈判、竞选、战争等。又又如如，三三国国时时代代曹曹不不兴兴溅溅墨墨画画蝇蝇、曹曹操操兵兵败败华华容容道道、北宋时期北宋时期丁渭挖河修皇宫丁渭挖河修皇宫等都是博弈论成功应用例子。等都是博弈论成功应用例子。12.1.1 博弈论概述博弈论概述6第6页博弈论研究问题博弈论研究问题:参加博弈各方是否存在最合理策略以及怎样参加博弈各方是否存在最合理策略以及怎样找到合理策略。找到合理策略。博博弈弈论论是是研研究究决决议议主主体体行行为为发发生生直直接接相相互互作作用用时时决决议议及及这这种种决决议议均均衡衡问问题题。即即它它是是研研究究聪聪明明而而又又理理智智决决议议者者在在冲冲突突或或合合作作中中策策略略选选择择理理论论。它它将将成成为为当当代代经经济管理学科前沿领城。济管理学科前沿领城。著著名名法法国国经经济济学学家家泰泰勒勒尔尔（Jean Jean Tirole Tirole）说说：“正正如如理理性性预预期期使使宏宏观观经经济济学学发发生生革革命命一一样样，博博弈弈论论广广泛泛而深远地改变了经济学家思维方式而深远地改变了经济学家思维方式”。12.1.1 博弈论概述博弈论概述7第7页 1944年年美美国国普普林林斯斯特特大大学学教教授授冯冯诺诺伊伊曼曼、摩摩根根斯斯坦坦著著作作博博弈弈论论和和经济行为出版，是博弈论诞生标志。经济行为出版，是博弈论诞生标志。普普林林斯斯特特大大学学对对博博弈弈论论作作出出重重大大贡献还有塔克、库恩、纳什等。贡献还有塔克、库恩、纳什等。12.1.1 博弈论概述博弈论概述 要想在当代社会做要想在当代社会做 一个有文化人，你必须对博弈一个有文化人，你必须对博弈论有一个大致了解。论有一个大致了解。萨缪尔森萨缪尔森8第8页12.1.1 博弈论概述博弈论概述约翰约翰纳什纳什(John F.Nash)1928年生于美国年生于美国,1994年取得诺贝尔经济学奖。年取得诺贝尔经济学奖。在非合作博弈均衡分析理论方面做出了开创性贡献，对博在非合作博弈均衡分析理论方面做出了开创性贡献，对博弈论和经济学产生了重大影响。弈论和经济学产生了重大影响。Nash对博弈论主要贡献有：（对博弈论主要贡献有：（1）合作博弈中讨价还价模）合作博弈中讨价还价模型，称为型，称为Nash讨价还价解；（讨价还价解；（2）非合作博弈均衡分析。）非合作博弈均衡分析。9第9页博弈论发展史上五次诺贝尔经济学奖博弈论发展史上五次诺贝尔经济学奖u1994年，纳什、海萨尼、塞尔顿，非合作博弈理论年，纳什、海萨尼、塞尔顿，非合作博弈理论12.1.1 博弈论概述博弈论概述10第10页博弈论发展史上五次诺贝尔经济学奖博弈论发展史上五次诺贝尔经济学奖u 1996年，莫里斯和年，莫里斯和维维克瑞，不克瑞，不对对称信息条件下称信息条件下激励机制激励机制问题问题12.1.1 博弈论概述博弈论概述11第11页博弈论发展史上五次诺贝尔经济学奖，罗伯特.奥曼，托马斯.谢林，合作博弈理论12.1.1 博弈论概述博弈论概述12第12页博弈论发展史上五次诺贝尔经济学奖 ，三名美国经济学家莱昂尼德.赫维奇，埃里克.马斯金，罗杰.迈尔森，“机制设计理论”12.1.1 博弈论概述博弈论概述13第13页博弈论发展史上五次诺贝尔经济学奖 ，美国经济学家阿尔文.罗思（Alvin E.Roth）和劳埃德.沙普利（Lloyd S.Shapley），“稳定匹配理论和市场设计实践”。12.1.1 博弈论概述博弈论概述14第14页博弈模型博弈模型3个基本要素：个基本要素：（1）局中人）局中人(players)：博弈参加者，能够是一个：博弈参加者，能够是一个人、一个团体、一个企业、交战一方等。人、一个团体、一个企业、交战一方等。假设每一个局假设每一个局中人都是中人都是“理智理智”。（2）策略集策略集(strategies)：策略是可供局中人选择：策略是可供局中人选择实际可行完整行动方案。实际可行完整行动方案。每个局中人策略集（每个局中人策略集（S）最少应）最少应包含两个策略。包含两个策略。（3）得益（赢得）函数得益（赢得）函数(payoffs)：当每个局中人：当每个局中人策略确定后，他们就会得到对应收益或损失称为局中人策略确定后，他们就会得到对应收益或损失称为局中人得益，不一样策略会造成不一样得益，所以，得益是策得益，不一样策略会造成不一样得益，所以，得益是策略函数。略函数。12.1.2 博弈三要素博弈三要素15第15页n人博弈人博弈全体局势集合全体局势集合S可用各局中人策略集迪卡尔集表示可用各局中人策略集迪卡尔集表示 12.1.2 博弈三要素博弈三要素局势局势：每一个局中人各选择一个策略形成对局每一个局中人各选择一个策略形成对局(策略组合策略组合)。两人博弈两人博弈二人博弈矩阵型表示二人博弈矩阵型表示:坦白坦白抵赖抵赖坦白坦白-5，-5-1/4，-10抵赖抵赖-10，-1/4-1，-1囚徒囚徒2囚囚徒徒116第16页分类依据分类依据类类 型型局中人数量局中人数量两人博弈，多人博弈，单人博弈两人博弈，多人博弈，单人博弈策略数量策略数量有限博弈，无限博弈有限博弈，无限博弈信息信息结结构构完全信息博弈，不对称信息博弈完全信息博弈，不对称信息博弈局中人局中人间间是否允是否允许许合作合作非合作博弈，合作博弈非合作博弈，合作博弈博弈博弈过过程程静态博弈，动态博弈，重复博弈静态博弈，动态博弈，重复博弈得益情况得益情况零和博弈，常和博弈，变和博弈零和博弈，常和博弈，变和博弈12.1.3 博弈结构和分类博弈结构和分类17第17页12.1.3 博弈结构和分类博弈结构和分类18第18页【例例12-2】1943年年2月月，日日本本统统帅帅山山本本五五十十六六大大将将计计划划由由南南太太平平洋洋新新不不列列颠颠群群岛岛拉拉包包尔尔出出发发，3天天穿穿过过俾俾斯斯麦麦海海，开开往往新新几几内内亚亚莱莱城城，支支援援困困守守日日军军。有有两两条条路路线：北线和南线。线：北线和南线。盟盟军军统统帅帅麦麦克克阿阿瑟瑟命命令令他他麾麾下下太太平平洋洋战战区区空空军军司司令令肯肯尼尼将将军军组组织织空空中中打打击击。侦侦察察机机重重点点搜搜索索有有两两个个方方案案：北线和南线。北线和南线。当当初初未未来来3天天中中：北北线线阴阴雨雨，能能见见度度差差；南南线线晴晴天天，能见度佳。日美双方各自应采取哪种方案。能见度佳。日美双方各自应采取哪种方案。12.1.3 博弈结构和分类博弈结构和分类19第19页北线北线南线南线20第20页【解】【解】局中人：盟军、日军局中人：盟军、日军 双方策略：北线、南线双方策略：北线、南线盟军赢得矩阵以下：盟军赢得矩阵以下：日军日军盟军盟军北线北线（）南线南线()北线（北线（）22南线（南线（）13最优局势最优局势是：是：即都选择北线。日军舰队受到重创，但未全歼。即都选择北线。日军舰队受到重创，但未全歼。双方选择策略思绪双方选择策略思绪：在最不利中选择最有在最不利中选择最有利策略。利策略。12.1.3 博弈结构和分类博弈结构和分类两人有限零和博弈两人有限零和博弈21第21页【补充例补充例2 2】双寡头削价竞争（两个厂商）双寡头削价竞争（两个厂商）类似地，广告投资、采取新技术等方面，厂商之间经常耗类似地，广告投资、采取新技术等方面，厂商之间经常耗资巨大，但不一定有利可图争夺战；对公共资源掠夺式使用资巨大，但不一定有利可图争夺战；对公共资源掠夺式使用等问题。等问题。我们目标是怎样利用这种困境到达有利于社会，合理利用我们目标是怎样利用这种困境到达有利于社会，合理利用和开发公共资源，保护环境。和开发公共资源，保护环境。12.1.3 博弈结构和分类博弈结构和分类 中南中南亚贸亚贸高价高价低价低价高价高价（100，100）（30，150）低价低价（150，30）（70，70）两人有限非零和博弈两人有限非零和博弈22第22页多寡头削价竞争（多寡头削价竞争（3个厂商：个厂商：亚贸，中南，中北亚贸，中南，中北）中北采取高价中北采取高价中北采取低价中北采取低价12.1.3 博弈结构和分类博弈结构和分类 中南中南亚贸亚贸高价高价低价低价高价高价(100,100,100)(20,150,20)低价低价(150,20,20)(130,130,20)中南中南亚贸亚贸高价高价低价低价高价高价(20,20,150)(20,130,130)低价低价(130,20,130)(70,70,70)23第23页【补充例【补充例3】动态博弈：甲向乙借一万元钱经营，甲许诺经营成功动态博弈：甲向乙借一万元钱经营，甲许诺经营成功后分给乙总利润（后分给乙总利润（4 4万）二分之一，乙是否借给甲？万）二分之一，乙是否借给甲？乙乙甲甲借借不借不借乙乙分分不分不分(2，2)(1，0)打打乙乙不打不打(0，4)(1，0)(1,0)有法律保障有法律保障法律保障不足法律保障不足12.1.3 博弈结构和分类博弈结构和分类完全信息动态博弈完全信息动态博弈24第24页12.2 纳纳 什什 均均 衡衡纳什均衡纳什均衡（Nash Equilibrium）:假假定定有有n个个博博弈弈方方参参加加博博弈弈，在在给给定定其其它它博博弈弈方方策策略略条条件件下下，每每个个人人选选择择自自己己最最优优策策略略（个个人人最最优优策策略略可可能能依依赖赖也也可可能能不不依依赖赖他他人人策策略略），从从而而使使自自己己利利益益最最大大化化，全全部部局局中中人人策策略略一一起起组组成成一一个个策策略略组组合合。而而Nash均均衡衡是是这这么么一一个个策策略略组组合合，由由全全部部参参加加人人最最优优策策略略组组成成，给给定定他他人人策策略略条条件件下下，没没有有任任何何单单个个参参加加人人有有主主动动性性选选择择其其它它策策略略，从从而而没没有有任任何何人人有有主主动动性性打打破破这这种种均均衡衡，Nash均均衡衡是是一一个个“僵局僵局”：给定他人不动情况下，没有些人有兴趣动。：给定他人不动情况下，没有些人有兴趣动。12.2.1 纳什均衡定义纳什均衡定义27第27页另一个解释：另一个解释：假假定定全全部部博博弈弈方方事事先先达达成成一一项项协协议议，要要求求每每个个人人行行为为规规则则，在在没没有有外外在在强强制制力力约约束束时时，当当事事人人会会自自觉觉恪恪守守这这个个协协议议，等等于于说说这这个个协协议议组组成成一一个个纳纳什什均均衡衡：假假定定他他人人恪恪守守协协议议情情况况下下，没没有有些些人人有有主主动动性性偏偏离离协协议议要要求求自自己己行行为为规规则则。换换句句话话说说，假假如如一一个个协协议议不不组组成成纳纳什什均均衡衡，它它就就不不可可能能自自动动实实施施，因因为为最最少少有有一一个个参参加加人人会会违违反反此此协议，不满足协议，不满足Nash均衡要求协议是没有意义。均衡要求协议是没有意义。12.2 纳纳 什什 均均 衡衡28第28页12.2 纳纳 什什 均均 衡衡 你你正正在在图图书书馆馆枯枯坐坐，一一位位陌陌生生美美女女主主动动过过来来和和你你搭搭讪讪，并并要要求求和和你你一一起起玩玩个个数数学学游游戏戏。美美女女提提议议：“让让我我们们各各自自亮亮出出硬硬币币一一面面，或或正正或或反反。假假如如我我们们都都是是正正面面，那那么么我我给给你你3元元，假假如如我我们们都都是是反反面面，我我给给你你1元元，剩剩下下情情况况你你给给我我2元元就就能能够够了了。”那那么么该该不不该该和和这这位位姑姑娘玩这个游戏呢？娘玩这个游戏呢？30第30页 用用G表表示示一一个个博博弈弈，若若一一个个博博弈弈中中有有n个个局局中中人人，则则每个局中人可选策略集合称为策略集，分别用每个局中人可选策略集合称为策略集，分别用 S1，S2，Sn表示表示 sij表表示示局局中中人人 i 第第 j 个个策策略略，其其中中 j 可可取取有有限限个个值值（有有限限策策略略博博弈弈），也也可可取取无无限限个个值值（无无限限策策略略博博弈弈）；博博弈弈方方 i 得得益益则则用用hi 表表示示；hi 是是各各博博弈弈方方策策略略多多元元函函数，数，n个局中人博弈个局中人博弈G常写成：常写成：G=S1，Sn；h1，hn12.2 纳纳 什什 均均 衡衡31第31页纯策略纳什均衡纯策略纳什均衡【定定义义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 纳纳 什什 均均 衡衡 各选取一个策略组成某个策略组合组成一个各选取一个策略组成某个策略组合组成一个局势局势，其最优，其最优局势称为纯策略意义下局势称为纯策略意义下最优局势最优局势（纳什均衡）（纳什均衡）。32第32页【例【例12-1】假设有三个厂商在同一市场上生产销售完全相同假设有三个厂商在同一市场上生产销售完全相同产品，它们各自产量分别用产品，它们各自产量分别用m1、m2和和m3表示，再假设表示，再假设m1、m2和和m3只能取只能取1、2、3等正整数值。市场出清价格一定是等正整数值。市场出清价格一定是市场总产量市场总产量Q=m1+m2+m3函数，假设该函数为：函数，假设该函数为：不妨先假设三个厂商开始时分别生产不妨先假设三个厂商开始时分别生产3单位，单位，9单位和单位和6单位产单位产量，这时三厂商是否满意各自产量，要从利润进行分析，因为量，这时三厂商是否满意各自产量，要从利润进行分析，因为产量不能超出产量不能超出20，则第，则第i个厂商利润函数为个厂商利润函数为 12.2 纳纳 什什 均均 衡衡33第33页 可算出在产量组合为（可算出在产量组合为（3，9，6）时，市场价格为）时，市场价格为2，三厂商，三厂商利润分别为利润分别为6，18和和12，再作其它产量组合时亦会有不一样结，再作其它产量组合时亦会有不一样结果。果。表表12-2 三厂商离散产量组合对应价格和利润三厂商离散产量组合对应价格和利润 m1m2m3p12339626181238639241855642020245555252525554630302433311333333633848242412.2 纳纳 什什 均均 衡衡最稳定产量组合，是一个纳什均衡最稳定产量组合，是一个纳什均衡34第34页【定定义义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 纳纳 什什 均均 衡衡35第35页【定定义义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 纳纳 什什 均均 衡衡36第36页 当得益是博弈多元当得益是博弈多元连续函数连续函数时，求出每个博弈时，求出每个博弈方反应函数，而方反应函数，而各个反应函数交点就是纳什均衡各个反应函数交点就是纳什均衡。12.3 反应函数法反应函数法38第38页【例例12-4】设设A，B两两厂厂家家生生产产一一样样产产品品，厂厂商商A产产量量为为q1，B产产量量为为q2，市市场场总总产产量量为为Q=q1+q2，市市场场出出清清价价格格是是市市场场总总产产量量函函数数P6Q。设设产产品品产产量量边边际际成成本本相相等等，C1=C2=2。求解两厂商纳什均衡（假设产量连续可分）。求解两厂商纳什均衡（假设产量连续可分）。分分析析：这这是是一一个个连连续续产产量量古古诺诺模模型型，不不难难看看出出，该该博博弈弈中中两厂商各自利润分别为各自销售收益减去各自成本，即：两厂商各自利润分别为各自销售收益减去各自成本，即：12.3 反应函数法反应函数法q1 q139第39页作反应函数作反应函数纳什均衡纳什均衡：(4/3,4/3)12.3 反应函数法反应函数法(0,4)（0,2)(2,0)(4,0)(4/3,4/3)R1R240第40页【例例12-6】设设有有3个个农农户户一一起起放放牧牧羊羊群群，现现有有一一可可供供大大家家自自由由放放牧牧草草地地，因因为为草草地地面面积积有有限限，只只能能供供有有限限只只羊羊群群吃吃饱饱，不不然就会影响到羊群产出，假设每只羊产出函数为然就会影响到羊群产出，假设每只羊产出函数为成本成本C=8，且每个农户在决定自己放牧羊群数时候并不知道其，且每个农户在决定自己放牧羊群数时候并不知道其它农户决议，试求出该决议问题纳什均衡。它农户决议，试求出该决议问题纳什均衡。【解】各农户得益函数分别为【解】各农户得益函数分别为 12.3 反应函数法反应函数法43第43页12.3 反应函数法反应函数法反应函数反应函数 所以该博弈纳什均衡为（所以该博弈纳什均衡为（1818，1818，1818）44第44页用反应函数法求纳什均衡步骤：用反应函数法求纳什均衡步骤：1.建立得益函数；建立得益函数；2.求反应函数：即对得益函数求偏导数；求反应函数：即对得益函数求偏导数；3.解反应函数方程组。解反应函数方程组。反应函数方程组解即为反应函数方程组解即为纳什均衡纳什均衡。12.3 反应函数法反应函数法45第45页12.4 二人有限零和博弈二人有限零和博弈 两两人人有有限限零零和和博博弈弈也也称称矩矩阵阵博博弈弈，在在众众多多博博弈弈模模型型中中占占有有主主要要地地位位，也也是是最最简简单单、理理论论和和算算法法都都比比较较完完善善一类。一类。齐威王田忌赛马，例齐威王田忌赛马，例12-2均为矩阵博弈。均为矩阵博弈。47第47页 12.4.1 数学模型数学模型 模型：模型：S1=1,2,，m局中人局中人纯策略集纯策略集 S2=1,2,，n局中人局中人纯策略集纯策略集 ai j局中人局中人在局势（在局势（i,j）下赢得值）下赢得值 局中人局中人得益矩阵得益矩阵 (局中人局中人得益矩阵为得益矩阵为-A)G=S1，S2；A:12.4 二人有限零和博弈二人有限零和博弈 48第48页 建立齐王田忌赛马数学模型建立齐王田忌赛马数学模型S1=(上中下）上中下）,（上下中）（上下中）,（中上下）（中上下）,（中下上）（中下上）,（下上中）（下上中）,（下中上（下中上)S2=(上中下）上中下）,（上下中）（上下中）,（中上下）（中上下）,（中下上）（中下上）,（下上中）（下上中）,（下中上（下中上)12.4.1 数学模型数学模型 田忌田忌齐王齐王上中下上中下上下中上下中中上下中上下中下上中下上下上中下上中下中上下中上上中下上中下3，31，11，11，11，11，1上下中上下中1，13，31，11，11，11，1中上下中上下1，11，13，31，11，11，1中下上中下上1，11，11，13，31，11，1下上中下上中1，11，11，11，13，31，1下中上下中上1，11，11，11，11，13，349第49页12.4.1 数学模型数学模型 齐王赢得矩阵齐王赢得矩阵50第50页【例【例12-7】求解矩阵博弈，其中求解矩阵博弈，其中博弈博弈G解（纳什均衡）为：解（纳什均衡）为：【解】【解】12.4.2 纯策略矩阵博弈纯策略矩阵博弈 局中人局中人最优策略是最优策略是2 ,局中人局中人最优策略是最优策略是2S1=1 1,2 2,3 3,4 4 S2=1 1,2 2,3 3 51第51页【定义【定义12.4】设设G=S1，S2；A为矩阵博弈，其中为矩阵博弈，其中 S1=1，2，m，S2=1，2，n，若等式若等式成立，成立，则称，则称VG为博弈为博弈G值值，对应策略组合，对应策略组合 称为该博弈纯策略称为该博弈纯策略纳什均衡纳什均衡。12.4.2 纯策略矩阵博弈纯策略矩阵博弈 52第52页【定定理理12.1】矩矩阵阵博博弈弈G=S1，S2；A在在纯纯策策略略意意义义下下有有纳纳什什均均衡衡充充要要条条件件是是：存存在在策策略略组组合合 使使得得对一切对一切i=1，m,j=1，n,都有：都有：意义：意义：当当局局中中人人选选定定纯纯策策略略i*后后，局局中中人人为为了了使使其其所所失失最最少少，只只能能选选择择纯纯策策略略j*，不不然然就就可可能能损损失失得得更更多多；反反之之，当当局局中中人人选选定定纯纯策策略略j*后后，局局中中人人为为了了得得到到最最大大赢赢得得也也只只能能选选择择纯纯策策略略i*，不不然然就就会会赢赢得得更更少少，双双方方竞竞争争在在局局势势（i*,j*）下到达了一个平衡状态。即纳什均衡。下到达了一个平衡状态。即纳什均衡。12.4.2 纯策略矩阵博弈纯策略矩阵博弈 53第53页【定义【定义12.5】设设 f(x，y)为一个定义在为一个定义在xA及及yB上实函上实函数数，假如存在假如存在x*A及及y*B,使得对一切使得对一切xA及及yB有有则称则称 为函数为函数 f 一个一个鞍点鞍点。矩阵博弈在纯策略意义下有解且矩阵博弈在纯策略意义下有解且 充要条件充要条件是：是：12.4.2 纯策略矩阵博弈纯策略矩阵博弈 是是A鞍点鞍点。（i*,j*）54第54页【例【例12-9】设有矩阵博弈设有矩阵博弈G=SG=S1 1，S S2 2；A A，赢得矩阵为，赢得矩阵为求纳什均衡求纳什均衡12.4.2 纯策略矩阵博弈纯策略矩阵博弈 S1=1 1,2 2,3 3,4 4 S2=1 1,2 2,3 3，4 4 55第55页纳什均衡为：纳什均衡为：(1,2)，(1,4)，(3,2)，(3,4)博弈值博弈值VG=5局中人局中人最优纯策略为最优纯策略为1，3局中人局中人最优纯策略为最优纯策略为2，412.4.2 纯策略矩阵博弈纯策略矩阵博弈 A=1234 1 2 3 4【解解】56第56页【性质【性质12.1】无差异性。若无差异性。若 和和 为为G两个解，两个解，则：则：【性质【性质12.2】可交换性。若可交换性。若 和和 为为G两个解，两个解，则则 和和 也是博弈解也是博弈解12.4.2 纯策略矩阵博弈纯策略矩阵博弈 57第57页 应用举例：应用举例：某某单单位位采采购购员员在在秋秋天天时时要要决决定定冬冬季季取取暖暖用用煤煤采采购购量量。已已知知在在正正常常气气温温条条件件下下需需要要煤煤15吨吨，在在较较暖暖和和较较冷冷气气温温条条件件下下分分别别需需要要煤煤10吨吨和和20吨吨。假假定定冬冬季季煤煤价价随随天天气气严严寒寒程程度度而而改改变变，在在较较暖暖、正正常常、较较冷冷气气温温条条件件下下每每吨吨煤煤价价格格分分别别为为100元元、150元元和和200元元。又又设设秋秋季季时时每每吨吨煤煤价价格格为为100元元，在在没没相相关关于于当当年年冬冬季季气气温温情情况况准准确确预预报报条条件件下下，秋秋季季时时应应采采购购多多少少吨吨煤煤能能使使总总支支出最少？试建立该问题矩阵对策模型，并求解。出最少？试建立该问题矩阵对策模型，并求解。12.4.2 纯策略矩阵博弈纯策略矩阵博弈 58第58页【解】【解】局中人局中人I（采购员）：（采购员）：S1=10吨，吨，15吨，吨，20吨吨局中人局中人II（大自然）：（大自然）：S2=较暖，正常，较冷较暖，正常，较冷 纳什均衡为（纳什均衡为（3，3），博弈值），博弈值VG=-既采购员在秋天购煤既采购员在秋天购煤20吨很好。吨很好。12.4.2 纯策略矩阵博弈纯策略矩阵博弈 59第59页12.4.3 混合策略矩阵博弈混合策略矩阵博弈矩阵博弈满足纯策略纳什均衡是指：矩阵博弈满足纯策略纳什均衡是指：满足局中人满足局中人有把握最少赢得是局中人有把握最少赢得是局中人有把握至有把握至多损失，即多损失，即 当当V1V2 时，时，这时不存在纯策略意义下纳什均衡这时不存在纯策略意义下纳什均衡。60第60页利用最小最大和最大最小标准，发觉不存在使得利用最小最大和最大最小标准，发觉不存在使得成立点，即不存在纯策略纳什均衡。成立点，即不存在纯策略纳什均衡。12.4.3 混合策略矩阵博弈混合策略矩阵博弈齐王田忌赛马齐王田忌赛马61第61页【定义【定义12.6】设矩阵博弈设矩阵博弈 ，其中，其中 记记12.4.3 混合策略矩阵博弈混合策略矩阵博弈则分别称则分别称 为局中人为局中人、混合策略集；混合策略集；、分别称为局中人分别称为局中人、混合策略混合策略，为一个为一个混合局势混合局势。称为称为G 混合扩充混合扩充。E是是局中人局中人赢得期望值赢得期望值62第62页纯策略与混合策略关系纯策略与混合策略关系 纯纯策策略略是是混混合合策策略略特特殊殊情情形形。一一个个混混合合策策略略X=(x1,x2,，xm)可可了了解解为为：假假如如进进行行多多局局博博弈弈话话，局局中中人人I分分别别选选取取纯纯策策略略1,2,，m频频率率；若若只只进进行一次博弈，则反应了局中人行一次博弈，则反应了局中人I对各纯策略偏爱程度。对各纯策略偏爱程度。12.4.3 混合策略矩阵博弈混合策略矩阵博弈63第63页【定理【定理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 混合策略矩阵博弈混合策略矩阵博弈 称为局中人称为局中人赢得函数赢得函数，VG 称为称为G*值。值。【定义【定义12.6】设设G*=S1*,S2*,E是矩阵博弈是矩阵博弈G=S1,S2,A混混 合扩充，当合扩充，当 时，称时，称 为局中人为局中人、在混合策略中在混合策略中纳什均衡纳什均衡。64第64页【例【例12-1112-11】考虑矩阵博弈考虑矩阵博弈G=S1，S2；A，其中，其中 试求纳什均衡试求纳什均衡【解解】纯策略纳什均衡不存在。设纯策略纳什均衡不存在。设x=（x1，x2）为局中人）为局中人混合策略，混合策略，y=(y1，y2)为局中人为局中人混合策略，则：混合策略，则：局中人局中人赢得期望值：赢得期望值：12.4.3 混合策略矩阵博弈混合策略矩阵博弈x1x2y1 y265第65页该博弈该博弈纳什均衡纳什均衡为：为：(x*,y*)其中其中局中人局中人和和最优策略最优策略分别为：分别为：x*,y*博弈值博弈值 12.4.3 混合策略矩阵博弈混合策略矩阵博弈取取 ，则则66第66页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 67第67页【定理【定理12.5】对任一矩阵博弈对任一矩阵博弈G=S1，S2；A，一定存在混一定存在混合策略意义下纳什均衡。合策略意义下纳什均衡。12.4.4 纳什均衡存在定理纳什均衡存在定理 定理定理12.4-12.6说明了说明了矩阵博弈总是有解矩阵博弈总是有解，并给出了解，并给出了解所应满足条件。所应满足条件。【定理【定理12.6】设（设（x*，y*）为矩阵博弈）为矩阵博弈G一个纳什均衡，一个纳什均衡，V=VG，则，则（1）若）若 xi*0，则，则（2）若）若 yj*0，则，则（3）若）若 ，则，则 （4）若）若 ，则，则68第68页例例12-1112.4.4 纳什均衡存在定理纳什均衡存在定理69第69页 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有相同解，且：有相同解，且：【补充例补充例】求解矩阵博弈求解矩阵博弈70第70页1.线性方程组法线性方程组法若最优策略中若最优策略中 和和 均不为零时，依据定理均不为零时，依据定理12.6，有，有 12.4.5 矩阵博弈求解方法矩阵博弈求解方法 注意注意：（：（1）应用此方法条件是全部策略概率大于零。应用此方法条件是全部策略概率大于零。（2）对于）对于22矩阵博弈当不存在纯策略鞍点时，矩阵博弈当不存在纯策略鞍点时，轻易证实，各局中人最优策略中轻易证实，各局中人最优策略中xi，yj均大于零，均大于零，可采取此法求解。可采取此法求解。71第71页【例【例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 矩阵博弈求解方法矩阵博弈求解方法 72第72页2.优超标准法优超标准法（严格下策重复消去法）（严格下策重复消去法）优超标准：优超标准：P311【定义【定义12.7】,【定理【定理12.8】【例【例12-12】设赢得矩阵设赢得矩阵A为为:求纳什均衡求纳什均衡 12.4.5 矩阵博弈求解方法矩阵博弈求解方法 73第73页【解】【解】12.4.5 矩阵博弈求解方法矩阵博弈求解方法 74第74页该矩阵博弈纳什均衡为该矩阵博弈纳什均衡为：(x*,y*)VG=4.8 12.4.5 矩阵博弈求解方法矩阵博弈求解方法 75第75页 3.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)为局中人为局中人极值点极值点l1l2CBAox1v176第76页 同理同理 V=35-30y1 V=10+10y1 解得解得 12.4.5 矩阵博弈求解方法矩阵博弈求解方法 该矩阵博弈纳什均衡为该矩阵博弈纳什均衡为：(x*,y*)VG=16.25 77第77页 【补补充充例例2】某某企企业业有有甲甲、乙乙两两个个工工厂厂，每每年年税税额额是是400万万元元和和1200万万元元。对对于于每每个个工工厂厂，企企业业可可如如实实申申报报税税款款，或或者者篡篡改改账账目目，声声称称税税额额为为零零，而而税税务务局局因因为为人人力力所所限限，每每年年只只能能检检验验一一个个工工厂厂账账目目，假假如如税税务务局局发发觉觉工工厂厂偷偷税税，则则不不但但要要工工厂厂如如数数缴缴纳纳税税款款，而而且且还还要要缴缴纳纳相相当当于于二二分分之之一一税税款款罚罚金金。（1）试试将将该该问问题题表表示示为为一一个个矩矩阵阵博博弈弈模模型型；（2）求求出出税税务务局局和和企企业业最优策略及税务局从企业征收税款（含罚金）。最优策略及税务局从企业征收税款（含罚金）。12.4.5 矩阵博弈求解方法矩阵博弈求解方法【解解】税务局：税务局：S1=查甲工厂，查乙工厂查甲工厂，查乙工厂 企业：企业：S2=甲乙都实报，甲乙都报零，甲实报乙报零，甲报零乙实报甲乙都实报，甲乙都报零，甲实报乙报零，甲报零乙实报 78第78页利用定理利用定理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)为局中人为局中人极值