运筹学对策论ppt课件.ppt

11.1 引言引言Introduction对策论（对策论（game theory）亦称博弈论，是研究具有对抗或竞争）亦称博弈论，是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学的一个分支，也是性质现象的数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。对策论中有一个重要的概念即对策运筹学的一个重要学科。对策论中有一个重要的概念即对策行为，对策行为是指具有竞争或对抗性质的行为，在这类行行为，对策行为是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标，为中，参加斗争或竞争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方案各方需考虑对手的各种可能的行动方案,并力图选择对自己最并力图选择对自己最为有利或最为合理的方案为有利或最为合理的方案 许多游戏具有特征：许多游戏具有特征：（1）有一定的规则）有一定的规则（2）有一个结果）有一个结果（3）有可供选择的策略）有可供选择的策略（4）策略与利益相互依存）策略与利益相互依存12.1.1对策论概述对策论概述12.1 引言引言对策论，不同于日常游戏，它具有理论性，应用的范围也不局对策论，不同于日常游戏，它具有理论性，应用的范围也不局限于游戏。限于游戏。对策是一些个人、对组或其它组织，面对一定的环境条件，在对策是一些个人、对组或其它组织，面对一定的环境条件，在一定的规则下，同时或先后从各自允许的行为或策略中进行选一定的规则下，同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得相应结果的过程。择并加以实施，各自取得相应结果的过程。这些规则应用到经济、军事、政治等领域也有类似的特征。这些规则应用到经济、军事、政治等领域也有类似的特征。例如，市场竞争、经营决策、投资分析、价格制定、费用分摊、例如，市场竞争、经营决策、投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、资源利用、谈判、财政转移支付、投标与拍卖、对抗与追踪、资源利用、谈判、竞选、战争竞选、战争 例如，战国时代的田忌赛马、三国时代的曹不兴溅墨画蝇、例如，战国时代的田忌赛马、三国时代的曹不兴溅墨画蝇、曹操兵败华容道、北宋时期的丁渭挖河修皇宫等都是对策论曹操兵败华容道、北宋时期的丁渭挖河修皇宫等都是对策论成功应用的例子。成功应用的例子。12.1 引言引言 著名法国经济学家泰勒尔（著名法国经济学家泰勒尔（Jean Tirole Jean Tirole ）说：）说：“正如理正如理性预期使宏观经济学发生革命一样，对策论广泛而深远地改性预期使宏观经济学发生革命一样，对策论广泛而深远地改变了经济学家的思维方式变了经济学家的思维方式”。 是研究决策主体的行为发生直接相互作用时的决策及这种决是研究决策主体的行为发生直接相互作用时的决策及这种决策的均衡问题。即它是研究聪明而又理智的决策者在冲突或合策的均衡问题。即它是研究聪明而又理智的决策者在冲突或合作中的策略选择理论。它作中的策略选择理论。它将成为当代经济管理学科的前沿领城。将成为当代经济管理学科的前沿领城。 对策论就是研究对策行为中斗争各方是否存在着最合理的行对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理方案的数学理论和方法。动方案，以及如何找到这个合理方案的数学理论和方法。 12.1 引言引言一个对策需要一个对策需要3个基本要素：个基本要素： (1)局中人局中人(players) (2)策略集策略集(strategies) (3)得益函数（得益函数（payoffs） 12.1.2 对策三要素对策三要素),(21nssss是一个局势是一个局势 策略组策略组全体局势的集合全体局势的集合S可用各局中人的策略集的迪卡尔集表示可用各局中人的策略集的迪卡尔集表示 nSSSS2112.1 引言引言不完全信息动态对策完全信息动态对策动态对策不完全信息静态对策完全信息静态对策静态对策按对策状态多人对策二人非零和对策二人零和对策二人对策按对策人数合作对策有限理性完全理性非合作对策按对策方式对策分类12.1.3 对策的结构和分类对策的结构和分类12.1 引言引言【例【例12.1】1943年年2月，日本统帅山本五十六大将计划由南太平洋月，日本统帅山本五十六大将计划由南太平洋新不列颠群岛的拉包尔出发，新不列颠群岛的拉包尔出发，3天穿过俾斯麦海，开往新几内亚的天穿过俾斯麦海，开往新几内亚的莱城，支援困守的日军。有两条路线：北线和南线。莱城，支援困守的日军。有两条路线：北线和南线。盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。侦察机重点搜索有两个方案：北线和南线。织空中打击。侦察机重点搜索有两个方案：北线和南线。当时未来当时未来3天中：北线阴雨，能见度差；南线晴天，能见度佳。天中：北线阴雨，能见度差；南线晴天，能见度佳。日美双方各自应采用哪种方案日美双方各自应采用哪种方案 12.1 引言引言北线北线南线南线 日军日军盟军盟军北线北线（ ）南线南线 ( )北线（北线（ ）22南线（南线（ ）13【解】【解】局中人：盟军、日军；双方策略：北线、南线，记为局中人：盟军、日军；双方策略：北线、南线，记为:盟军的赢得矩阵如下：盟军的赢得矩阵如下：212211，；，SS12122min32max122maxmin3122*最优策略是：最优策略是： ,即都选择北线。日军舰队即都选择北线。日军舰队受到重创，但未全歼。受到重创，但未全歼。 *1*1,双方选择的策略是：在双方选择的策略是：在最不利中选择最有利的最不利中选择最有利的策略。策略。12.1 引言引言囚徒的困境（二人非零和对策）囚徒的困境（二人非零和对策）5，50，1010，01，1囚徒囚徒1囚徒囚徒2坦坦 白白 不坦白不坦白坦白坦白不坦白不坦白双方如何采取对策使结果对自己最有利？双方如何采取对策使结果对自己最有利？12.1 引言引言【例【例12.2】双寡头削价竞争（两个厂商）双寡头削价竞争（两个厂商）100，10020，150150，2070，70亚贸亚贸中南中南高高 价价 低低 价价高价高价低价低价类似地，广告投资、采用新技术等方面，厂商之间常常耗资类似地，广告投资、采用新技术等方面，厂商之间常常耗资巨大，但不一定有利可图的争夺战；对公共资源的掠夺式使巨大，但不一定有利可图的争夺战；对公共资源的掠夺式使用等问题。用等问题。我们的目的是如何利用这种困境达到有利于社会，合理利我们的目的是如何利用这种困境达到有利于社会，合理利用和开发公共资源，保护环境。用和开发公共资源，保护环境。12.1 引言引言多寡头削价竞争（多寡头削价竞争（3个厂商个厂商:亚贸亚贸,中南，中北中南，中北) ）100，100，10020，150，20150，20，20130，130，20亚亚 贸贸中南中南高高 价价 低低 价价高价高价低价低价20，20，15020，130，130130，20，13070，70，70亚亚 贸贸中南中南高高 价价 低低 价价高价高价低价低价中北采用高价中北采用高价中北采用低价中北采用低价12.1 引言引言【例【例12.3】动态对策：甲向乙借一万元钱经营，甲许诺经营成功动态对策：甲向乙借一万元钱经营，甲许诺经营成功后分给乙总利润（后分给乙总利润（4万）的一半，乙是否借给甲？万）的一半，乙是否借给甲？乙乙甲甲借借不借不借乙乙分分不分不分(2，2)(1，0)打打乙乙不打不打(0，4)(1，0)(1,0)有法律保障有法律保障法律保障不足法律保障不足12.1 引言引言下一节：纳什均衡下一节：纳什均衡12.1 引言引言12.2 纳什均衡纳什均衡Nash Equilibrium12.2 纳什均衡纳什均衡Nash对对策论的贡献有：（对对策论的贡献有：（1）合作对策中的讨价还价模型，称）合作对策中的讨价还价模型，称为为Nash讨价还价解；（讨价还价解；（2）非合作对策的均衡分析。）非合作对策的均衡分析。纳什均衡纳什均衡（Nash Equilibrium） 假定有假定有n个博弈方参加博弈，在给定其个博弈方参加博弈，在给定其他博弈方策略的条件下，每个人选择自己的最优策略（个人最优策略他博弈方策略的条件下，每个人选择自己的最优策略（个人最优策略可能依赖也可能不依赖他人策略），一起构成一个策略组合（可能依赖也可能不依赖他人策略），一起构成一个策略组合（Strategy Profile），而），而Nash均衡是这样一种策略组合，由所有参与人均衡是这样一种策略组合，由所有参与人的最优策略组成，给定别人策略的条件下，没有任何单个参与人有积的最优策略组成，给定别人策略的条件下，没有任何单个参与人有积极性选择其他策略，从而没有任何人有积极性打破这种均衡，极性选择其他策略，从而没有任何人有积极性打破这种均衡，Nash均均衡是一种衡是一种“ 僵局僵局”：给定别人不动的情况下，没有人有兴趣动。：给定别人不动的情况下，没有人有兴趣动。约翰约翰纳什纳什(John F. Nash )1928年生于美国年生于美国,1994年获得诺贝尔经济学奖年获得诺贝尔经济学奖在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响弈论和经济学产生了重大影响 12.2.1 纳什均衡定义纳什均衡定义另一种解释：另一种解释：假定所有博弈方事先达成一项协议，规定每个人的行假定所有博弈方事先达成一项协议，规定每个人的行为规则，在没有外在的强制力约束时，当事人会自觉遵守这个协议，为规则，在没有外在的强制力约束时，当事人会自觉遵守这个协议，等于说这个协议构成一个纳什均衡：假定别人遵守协议的情况下，等于说这个协议构成一个纳什均衡：假定别人遵守协议的情况下，没有人有积极性偏离协议规定的自己的行为规则。换句话说，如果没有人有积极性偏离协议规定的自己的行为规则。换句话说，如果一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个参与人会违背此协议，不满足参与人会违背此协议，不满足Nash均衡要求的协议是没有意义的。均衡要求的协议是没有意义的。12.2 纳什均衡纳什均衡用用G表示一个对策，若一个对策中有表示一个对策，若一个对策中有n个局中人，则每个局中人个局中人，则每个局中人可选策略的集合称为策略集，分别用可选策略的集合称为策略集，分别用 S1，S2，Sn表示；表示；Sij表示局中人表示局中人i的第的第j个策略，其中个策略，其中j可取有限个值（有限策可取有限个值（有限策略对策），也可取无限个值（无限策略对策）；对策方略对策），也可取无限个值（无限策略对策）；对策方i的得益的得益则用则用hi表示；表示；hi是各对策方策略的多元函数，是各对策方策略的多元函数，n个局中人的对策个局中人的对策G常写成：常写成：【定义【定义12.1】 在对策在对策G=S1，S2，Sn；h1，h2hn中，如果由中，如果由各个对策方的各选取一个策略组成的某个策略组合（各个对策方的各选取一个策略组成的某个策略组合（S1*，S2*，Sn*）中，任一对策方）中，任一对策方i的策略的策略Si*，都是对其余策略方策略的组合，都是对其余策略方策略的组合（S1*，S*i-1，S*i+1，Sn*）的最佳策略，即）的最佳策略，即h i（S1*，S*i-1，Si*，S*i+1Sn*）hi（S1*，S*i-1，Sij，S*i+1，Sn*）对）对任意任意SijSi都成立，则称（都成立，则称（S1*，Sn*）为）为G的一个纯策略的一个纯策略“纳什均衡纳什均衡”（Nash Equilibrium） G=S1，Sn；h1，hn12.2 纳什均衡纳什均衡各选取一个策略组成的某个策略组合构成一个各选取一个策略组成的某个策略组合构成一个局势局势，其最优局，其最优局势称为纯策略意义下的势称为纯策略意义下的最优局势最优局势【例【例12.4】 假设有三个厂商在同一市场上生产销售完全相同的假设有三个厂商在同一市场上生产销售完全相同的产品，它们各自的产量分别用产品，它们各自的产量分别用m1、m2和和m3表示，再假设表示，再假设m1、m2和和m3只能取只能取1、2、3等正整数值市场出清价格一定是市场等正整数值市场出清价格一定是市场总产量总产量Q=m1+m2+m3的函数，假设该函数为：的函数，假设该函数为： 12320 (),20( ) 200,20m mQP PQQQ 不妨先假设三个厂商开始时分别生产不妨先假设三个厂商开始时分别生产3单位，单位，9单位和单位和6单位产量，单位产量，这时三厂商是否满意各自的产量，要从利润进行分析这时三厂商是否满意各自的产量，要从利润进行分析由于产量不能超过由于产量不能超过20，则第，则第i个厂商的利润函数为个厂商的利润函数为 12.2 纳什均衡纳什均衡可算出在产量组合为（可算出在产量组合为（3，9，6）时，市场价格为）时，市场价格为2，三厂商的，三厂商的利润分利润分8，16和和12，再作其它产量组合时亦会有不同的结果，如，再作其它产量组合时亦会有不同的结果，如表表12.2 表表12.2 三厂商离散产量结合对应价格和利润三厂商离散产量结合对应价格和利润 m1m2m3p1233962618123863924185564202024555525252533311333333633848242412320()iiipmmmmm12.2 纳什均衡纳什均衡【定义【定义12.2】 在对策在对策G=S1，Sn；h1，hn中，局中人中，局中人i的策略集为的策略集为Si=Si1，Sik，则他以概率分布，则他以概率分布pi=（pi1，pik）随机在其随机在其k个可选策略中选择的个可选策略中选择的“策略策略”称为一个混合策略，其称为一个混合策略，其中中0pij1对对j1，k都成立，且都成立，且pi1+pik=1 12.2.2混合策略纳什均衡混合策略纳什均衡12.2 纳什均衡纳什均衡【定义【定义12.3】 如果一个策略如果一个策略G=S1，Sn，h1，hn中，参中，参予者予者i的策略集为的策略集为Si=Si1，Sik，如果由各个对策方的策略组，如果由各个对策方的策略组成策略集合成策略集合G*=S1*，S2*，Sn*，其中，其中1, 2 , 1, 0|1*iimiiiimiixmixExS都是对其余对策方策略组合的最佳策略，即都是对其余对策方策略组合的最佳策略，即i（S1*,S2*,，Si-1*，Si*，Sn*）i（S1*,S2*,，Si-1*，Si*，Sn*）对任意对任意SijSi都成立，则称（都成立，则称（S1*,，Sn*）为）为G的一个混合策略的一个混合策略纳什均衡纳什均衡12.2 纳什均衡纳什均衡下一节：反应函数法下一节：反应函数法作业：教材作业：教材P293 T1012.2 纳什均衡纳什均衡12.3 反应函数法反应函数法12.3 反应函数法反应函数法当得益是对策的多元连续函数时，求出每个对策方的反应函数，当得益是对策的多元连续函数时，求出每个对策方的反应函数，而各个反应函数的交点就是纳什均衡而各个反应函数的交点就是纳什均衡 【例【例12.5】设】设A，B两厂家生产同样产品，厂商两厂家生产同样产品，厂商A产量为产量为q1，B产量产量为为q2，市场总产量为，市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数，市场出清价格是市场总产量的函数P6Q。设产品产量的边际成本相等，。设产品产量的边际成本相等，C1=C2=2。求解两厂商的。求解两厂商的纳什均（假设产量连续可分）。纳什均（假设产量连续可分）。分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂商各自的利润分别为各自的销售收益减去各自成本，即：商各自的利润分别为各自的销售收益减去各自成本，即：212111211111142(6)(qqqqqqqqqCQpq222122212222242(6)(qqqqqqqqqCQpq212111)4(maxmax11qqqqqq)4(212*1qq)4(211*2qq12.3 反应函数法反应函数法)4(21)(221qqR)4(21)(112qqR作反应函数：作反应函数：(0,4)（0,2)(2,0)(4,0)(4/3,4/3)纳什均衡：纳什均衡：(4/3,4/3)12.3 反应函数法反应函数法【例【例12.6】 考虑上述模型的另一种情况即各厂商所选择的是价格考虑上述模型的另一种情况即各厂商所选择的是价格而不是产量，假设产量与价格的函数关系为：而不是产量，假设产量与价格的函数关系为：2111121)(pdpbapq1222212)(pdpbapq其它条件不变，边际成本为其它条件不变，边际成本为C1、C2，试求解其纳什均衡。，试求解其纳什均衡。各自的策略空间为各自的策略空间为 max22max11, 0, 0PSPS两方的得益就是各自的利润两方的得益就是各自的利润 1121 11 11111111112(,)()()()h p pp qc qpc qpcab pd p2122 22 22222222222( ,)()()()h p pp qc qpc qpcab pd p12.3 反应函数法反应函数法利用得益函数在偏导数为利用得益函数在偏导数为0时有最大值，各自的反应函数分别为：时有最大值，各自的反应函数分别为：)(21)(211111211pdcbabpRP)(21)(122222122pdcbabpRP)(21)(21*122222*2*211111*1pdcbabppdcbabp)(42)(41112121222221211*1cbaddbbbcbaddbbdP)(42)(42222121111121212*2cbaddbbbcbaddbbdP),(*2*1PP为该对策唯一的纳什均衡为该对策唯一的纳什均衡 12.3 反应函数法反应函数法【例【例12.7】设有】设有3个农户一起放牧羊群，现有一可供大家自由放个农户一起放牧羊群，现有一可供大家自由放牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则就会影响到羊群的产出，假设每只羊的产出函数为就会影响到羊群的产出，假设每只羊的产出函数为成本成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道，且每个农户在决定自己放牧羊群数的时候并不知道其它农户的决策，试求出该决策问题的纳什均衡。其它农户的决策，试求出该决策问题的纳什均衡。)(8080221qqqQV【解】各农户的得益函数分别为【解】各农户的得益函数分别为 1321118)(80qqqqqh22123280() 8hqqqqq33123380() 8hqqqqq12.3 反应函数法反应函数法反应函数 323211212136),(qqqqRq313112212136),(qqqqRq212113212136),(qqqqRq因此该对策的纳什均衡为（因此该对策的纳什均衡为（18，18，18） 下一节：有限二人零和对策下一节：有限二人零和对策 作业：教材作业：教材P293 T 912.4 有限二人零和对策有限二人零和对策 矩阵对策就是二人有限零和对策。矩阵对策就是二人有限零和对策。 通常矩阵用来表示局中人通常矩阵用来表示局中人1的赢得，局中人的赢得，局中人2的支付。的支付。12.4 有限二人零和对策有限二人零和对策 用用、表示两个局中人，并设局中人表示两个局中人，并设局中人有有m个纯策略，个纯策略，1，2，m，局中人，局中人有有n个纯策略个纯策略1，2，n，则按对策，则按对策论的相关要素定义，局中人论的相关要素定义，局中人、的策略集分别为：的策略集分别为：112212,nnSS可以算出，局中人可以算出，局中人、所构成的策略组合共有所构成的策略组合共有mn个，记局中个，记局中人人在策略（在策略（i,j）下的赢得）下的赢得aij，则，则在每个策略的赢得构成一个在每个策略的赢得构成一个矩阵矩阵mnmmnnaaaaaaaaaA212222111211当局中人当局中人、的策略集的策略集S1,S2及及I的赢得矩阵确定后，一个矩阵对策的赢得矩阵确定后，一个矩阵对策就给定了通常将矩阵对策记为：就给定了通常将矩阵对策记为： ,21ASSG12.4 有限二人零和对策有限二人零和对策 12.4.1数学定义数学定义12.4 有限二人零和对策有限二人零和对策 112212,mnSS mnmmnnaaaaaaaaaA212222111211称称A为局中人为局中人的赢得矩阵（或为的赢得矩阵（或为的支付矩阵），由于对策为零的支付矩阵），由于对策为零和的，故局中人和的，故局中人的赢得矩阵为的赢得矩阵为A。,21ASSG矩阵对策记为矩阵对策记为 成立，成立， ，则称，则称VG为对策为对策G的值，对应的策略组合的值，对应的策略组合 12.4.2 纯策略矩阵对策纯策略矩阵对策【定义【定义12.4】 设设G=S1，S2；A为矩阵对策，其中为矩阵对策，其中S1=1，2，n，S2=1，2，n，若等式若等式nmijaA)(*maxminminmaxjiijijijjiaaa*jiGaV *(,)ij称为该对策的纳什均衡称为该对策的纳什均衡12.4 有限二人零和对策有限二人零和对策 【例【例12.8】求解矩阵对策，其中求解矩阵对策，其中ASSG；，2115347106A59112*min519953437111112062max736ijjijiaAa则有则有22maxminminmax3ijijjjiiaaa对策对策G的解为：的解为：22GV（， ），对策值3【解】【解】12.4 有限二人零和对策有限二人零和对策 6021117435915A【定理【定理12.1】矩阵对策矩阵对策G=S1，S2；A在纯策略定义下有纳什均在纯策略定义下有纳什均衡的充要条件是：存在策略组合衡的充要条件是：存在策略组合 使得对一切使得对一切i=1，m, j =1，n,均有：均有： ),(*jiajijiijaaa*矩阵对策在纯策略意义下有解且矩阵对策在纯策略意义下有解且VG=ai*j*的充要条件是：的充要条件是：ai*j*是是A的鞍点，在对策论中，矩阵的鞍点，在对策论中，矩阵A的鞍点也称为对策的鞍点的鞍点也称为对策的鞍点 12.4 有限二人零和对策有限二人零和对策 【定义【定义5】设设f(x，y)为一个定义在为一个定义在xA及及yB上的实函数上的实函数，如如果存在果存在x*A及及y*B,使得对一切使得对一切xA及及yB有有yxfyxfyxf,*),(*yx*jiGaV *jia则称则称为函数为函数f 的有关鞍点。的有关鞍点。矩阵对策在纯策略意义下的解且矩阵对策在纯策略意义下的解且的充要条件是的充要条件是是是A的鞍点。的鞍点。12.4 有限二人零和对策有限二人零和对策 【解】【解】 直接在赢得表上计算，有直接在赢得表上计算，有 *maxminminmaxjiijijjijiaaa可知可知 =5，i*=1,3，j*=2,4故（故（1，2）（）（1，4）（）（2，2）（）（2，4）为对策的纳什均衡，）为对策的纳什均衡，VG=5* jia12.4 有限二人零和对策有限二人零和对策 8585232195650233A【例【例12.9】 设有矩阵对策设有矩阵对策G= S1，S2；A ，赢得矩阵为，赢得矩阵为1234*12*34*min8 5 85 52 3 2119 5 65 50 2 330max9 585 求纳什均衡求纳什均衡【性质【性质12.1】 无差别性若无差别性若 和和 为为G的两个解，的两个解，则：则：【性质【性质12.2】 可交换性若可交换性若 和和 为为G的两个解，的两个解，则则),11ji（),22ji（2211jijiaa),11ji（),22ji（以上方法也称以上方法也称“上策均衡法上策均衡法”(Dominant-stratege Eqyilibrium)12.4 有限二人零和对策有限二人零和对策 也是对策的解也是对策的解),21ji（),12ji（及及【例【例12.10】 甲、乙两个企业同时生产一种电子产品（假设市场甲、乙两个企业同时生产一种电子产品（假设市场上只有这两家，为一双寡头竞争局面），两个企业都想通过改革上只有这两家，为一双寡头竞争局面），两个企业都想通过改革管理获取更多的销售份额，甲企业的策略措施有：（管理获取更多的销售份额，甲企业的策略措施有：（1）降低产）降低产品价格；（品价格；（2）提高产品质量；（）提高产品质量；（3）推出新产品乙企业措施为：）推出新产品乙企业措施为：（1）增加广告费用；（）增加广告费用；（2）增设网点；（）增设网点；（3）改进产品性能，通）改进产品性能，通过预测，两个企业市场份额变动情况如表过预测，两个企业市场份额变动情况如表124所示，试确定最所示，试确定最优策略优策略 乙乙 企企 业业123min甲甲企企业业112131213103335855*max13105* 【解】【解】5maxminminmax33aaajiijjiji则对策最优解为则对策最优解为VG=5，纳什，纳什均衡为（均衡为（3，3）甲企业采）甲企业采用推出新产品策略，乙企业用推出新产品策略，乙企业采用改进产品性能策略，结采用改进产品性能策略，结果甲企业赢得果甲企业赢得5的市场份的市场份额额12.4 有限二人零和对策有限二人零和对策 12.4.3 混合策略矩阵对策混合策略矩阵对策 纯策略矩阵对策的满足纳什均衡是满足局中人纯策略矩阵对策的满足纳什均衡是满足局中人有把握的至少有把握的至少赢得是局中人赢得是局中人有把握的至多损失即：有把握的至多损失即： 21maxminminmaxVaaVjiijjiji当当V1V2 时，时，这时不存在纯策略意义下的纳什均衡这时不存在纯策略意义下的纳什均衡 。 田忌田忌齐王齐王上中下上中下上下中上下中中上下中上下中下上中下上下上中下上中下中上下中上上中下上中下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，312.4 有限二人零和对策有限二人零和对策 311111131111113111111311111131111113A利用最大最小和最小最大原则，发现不存在使得利用最大最小和最小最大原则，发现不存在使得成立的点成立的点jiijjijiaamaxminminmax12.4 有限二人零和对策有限二人零和对策 例：例：对局中人对局中人1来说，来说，v1=2，i*=2，对局中人，对局中人2来说，来说，v2=3，j*=1，v1v2。没有鞍点。没有鞍点。【定义【定义12.6】设矩阵对策】设矩阵对策 ，其中，其中 记记ASSG；，21nMSS，212211 nmijaA1, 2 , 1, 0|11miiimxmixExS1, 2 , 1, 0|12njjjnynjyEyS12.4 有限二人零和对策有限二人零和对策 323452124A 则分别称则分别称 为局中人为局中人、的混合策略集；的混合策略集； 、 分分别称为局中人别称为局中人1、2的混合策略，的混合策略， 为一个混合局势。为一个混合局势。21SS 和*1Sx*2Sy), yx（称为称为G 的混合扩充。的混合扩充。E是赢得期望值。是赢得期望值。ESSG,*2*1*【定义】当【定义】当 时，称时，称 为局中人为局中人、在混合策略中的纳什均衡。在混合策略中的纳什均衡。),(maxmin),(minmax*1*2*2*1yxEyxESxSySySx),(*yxYXAyxET),(称为局中人称为局中人在选取混合策略在选取混合策略S*1时的赢得函数时的赢得函数 【定理【定理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 有限二人零和对策有限二人零和对策 【例【例12.11】 考虑矩阵对策考虑矩阵对策G= S1，S2；A ，其中，其中12122653yyxAx局中人局中人1的赢得期望值：的赢得期望值：取取 ， 满足满足GV 4试求纳什均衡试求纳什均衡 【解】【解】 纯策略纳什均衡不存在设纯策略纳什均衡不存在设x=（x1，x2）为局中人）为局中人的混的混合策略，合策略，y=(y1，y2)为局中人为局中人的混合策略，则：的混合策略，则：*,4E xy)75,72(),73,74(*yx12.4 有限二人零和对策有限二人零和对策 111221221111111111,265326 (1)5(1)3(1)(1)116432E x yx yx yx yx yx yxyx yxyxy *1 21 1( , ),( , )3 32 2xy),(,),(*1*yxEyxEyxE分别为局中人分别为局中人和和的最优策略即该对策的纳什均衡。的最优策略即该对策的纳什均衡。 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)jjijyayiE),(其中：iiijxajxE),( jjiiiijijijjjiijyjxExyiExyayxayxE),(),()(),(12.4 有限二人零和对策有限二人零和对策 *1 21 1( , ),( , )3 32 2xy*,4E x yE xyE xy【定理【定理12.4】 设设x*S1*，y*S2*，则（，则（x*，y*）是对策）是对策G的纳什的纳什均衡的充要条件是：存在数均衡的充要条件是：存在数V，使得，使得x*，y*分别满足：分别满足：mixxnjVxaiiiiiij, 2 , 1, 01, 2 , 1,njyymiVyajjjjjij, 2 , 1, 01, 2 , 1,且且V=VG .【定理【定理12.5】 对任一矩阵对策对任一矩阵对策G=S1，S2；A，一定存在混合策，一定存在混合策略意义下的纳什均衡略意义下的纳什均衡12.4 有限二人零和对策有限二人零和对策 【定理【定理12.6】 设（设（x*，y*）为矩阵对策）为矩阵对策G的一个纳什均衡，的一个纳什均衡，V=VG，则，则 (1)若若xi*0，则，则 (2)若若yi* 0，则，则 (3)若若 ，则，则 (4)若若 ,则则ijjja yVVyajjijVxaiiji0*ix0*jyVxaiiji46832121xxAyy)75,72(),73,74(*yx12121212121238,64,136,84,1yyvyyv yyxxvxxv xx367v 12.4 有限二人零和对策有限二人零和对策 例例12.4 有限二人零和对策有限二人零和对策 【定理【定理12.7】 设有两个矩阵对策设有两个矩阵对策 G1=S1，S2；A,G2=S1，S2；A则则(1) VG2=VG1(2) T(G1)=T(G2)其中其中0为一常数，为一常数，T(G1)、T(G2)为两个对策的解集合为两个对策的解集合1. 优超原则法优超原则法【例【例12.12】 设赢得矩阵设赢得矩阵A为为: 求纳什均衡求纳什均衡 【解】【解】第第4行优于第行优于第1行，第行，第3行优于第行优于第2行，故可划去第行，故可划去第1行和第行和第2行，得到新的赢得矩阵行，得到新的赢得矩阵，x1=x2=012.4 有限二人零和对策有限二人零和对策 12.4.5矩阵对策求解方法矩阵对策求解方法 “严格下策反复消去法严格下策反复消去法”(Iterated Elimination of Strictly Dominated Strategies)2102030148649593687550793A1649593687550793A对于对于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 ，解方程组：，解方程组：该矩阵对策的纳什均衡为：该矩阵对策的纳什均衡为： 3 2(0,0,0)5 5x2 3( , ,0,0,0)5 5yVG=4.8 12.4 有限二人零和对策有限二人零和对策 2643650A36436A34343463461xxvxxvxx12121264361yyvyyvyy3432,55xx1223,55yy2.线性方程组法线性方程组法若最优策略中若最优策略中 和和 均不为零时，有均不为零时，有 mixxnjvxaiiiiiij, 2 , 1, 01, 1，njyymivyajjjjiij, 2 , 1, 0, 1, 1ixiy12.4 有限二人零和对策有限二人零和对策 121541221A ASSG;,21【例【例12.14】求解矩阵对策】求解矩阵对策【解】建立方程组【解】建立方程组123123123123522421xxxVxxxVxxxVxxx123123123123254221yyyVyyyVyyyVyyy求解得：求解得：x=(0.525，0.275，0.2),y=(0.2，0.05，0.75);VG=0.45 3. 线性规划方法线性规划方法任意矩阵对策任意矩阵对策 的求解均等价于一对互为对偶的的求解均等价于一对互为对偶的线性规划问题，而定理线性规划问题，而定理12.4表明，对策表明，对策G的解等价于下面两个不的解等价于下面两个不等式的解等式的解 ASSG,21mixxnjvxaiiiiiij, 101, 1njyymivyajjjjjij, 101, 1),(maxmin),(minmax*1*2*2*1yxEyxEvSxSySySx【定理【定理12.9】 设矩阵对策的值为设矩阵对策的值为v，则：，则： *2211maxmin( , )minmax( , )y Sy Sx Sx SvE x jE i y12.4 有限二人零和对策有限二人零和对策 mixxnjvxapvZiiiiiij, 2 , 1, 01, 2 , 1,)(maxnjyymivyaDvZjjjjjij, 2 , 1, 01, 2 , 1,)(min则则局中人局中人、的最优策略的最优策略等价于线性规划问题：等价于线性规划问题： 12.4 有限二人零和对策有限二人零和对策 令mivxxii, 1 有1max1,1,2,1( )0,1,2,iiijiiiiivxa xjnpxvxim mixnjxapxZiiiijii, 2 , 1, 0, 2 , 1, 1)(min局中人局中人：12.4 有限二人零和对策有限二人零和对策 同理同理,令令njvyyjj, 11min1,1,2,1()0,1,2,jjijjjjjjvya yimDyvyjn njymiyaDywjjjijjj, 2 , 1, 0, 2 , 1, 1)(max有有局中人局中人：12.4 有限二人零和对策有限二人零和对策 【例【例12.12】 利用线性规划方法求解赢得矩阵为利用线性规划方法求解赢得矩阵为 1075274836A的矩阵对策的纳什均衡的矩阵对策的纳什均衡 【解】【解】 此问题可化为两个互为对偶的线性规划问题：此问题可化为两个互为对偶的线性规划问题： 01102817731546min3, 2, 1321321321321xxxxxxxxxxxxxxxz0,1107512741836max3, 2132132132