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