运筹学对策论精.ppt

运筹学对策论第1页，本讲稿共74页11.1引言引言Introduction第2页，本讲稿共74页对策论（对策论（gametheory）亦称博弈论，是研究具有对抗或竞争性质现象的）亦称博弈论，是研究具有对抗或竞争性质现象的数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。数学理论和方法，它既是数学的一个分支，也是运筹学的一个重要学科。对策论中有一个重要的概念即对策行为，对策行为是指具有竞争或对抗性对策论中有一个重要的概念即对策行为，对策行为是指具有竞争或对抗性质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和质的行为，在这类行为中，参加斗争或竞争的各方各自具有不同的利益和目标，各方需考虑对手的各种可能的行动方案目标，各方需考虑对手的各种可能的行动方案,并力图选择对自己最为有并力图选择对自己最为有利或最为合理的方案利或最为合理的方案 许多游戏具有特征：许多游戏具有特征：（1）有一定的规则）有一定的规则（2）有一个结果）有一个结果（3）有可供选择的策略）有可供选择的策略（4）策略与利益相互依存）策略与利益相互依存12.1.1对策论概述对策论概述12.1引言引言第3页，本讲稿共74页对策论，不同于日常游戏，它具有理论性，应用的范围也不局限于对策论，不同于日常游戏，它具有理论性，应用的范围也不局限于游戏。游戏。对策是一些个人、对组或其它组织，面对一定的环境条件，在一定的规则下，对策是一些个人、对组或其它组织，面对一定的环境条件，在一定的规则下，同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得相应同时或先后从各自允许的行为或策略中进行选择并加以实施，各自取得相应结果的过程。结果的过程。这些规则应用到经济、军事、政治等领域也有类似的特征。这些规则应用到经济、军事、政治等领域也有类似的特征。例如，市场竞争、经营决策、投资分析、价格制定、费用分摊、财政转移例如，市场竞争、经营决策、投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、资源利用、谈判、竞选、战争支付、投标与拍卖、对抗与追踪、资源利用、谈判、竞选、战争例如，战国时代的田忌赛马、三国时代的曹不兴溅墨画蝇、曹例如，战国时代的田忌赛马、三国时代的曹不兴溅墨画蝇、曹操兵败华容道、北宋时期的丁渭挖河修皇宫等都是对策论成功应操兵败华容道、北宋时期的丁渭挖河修皇宫等都是对策论成功应用的例子。用的例子。12.1引言引言第4页，本讲稿共74页 著名法国经济学家泰勒尔（著名法国经济学家泰勒尔（Jean Tirole Jean Tirole）说：）说：“正如理性预期正如理性预期使宏观经济学发生革命一样，对策论广泛而深远地改变了经济学家使宏观经济学发生革命一样，对策论广泛而深远地改变了经济学家的思维方式的思维方式”。是研究决策主体的行为发生直接相互作用时的决策及这种决策的均衡是研究决策主体的行为发生直接相互作用时的决策及这种决策的均衡问题。即它是研究聪明而又理智的决策者在冲突或合作中的策略选择理问题。即它是研究聪明而又理智的决策者在冲突或合作中的策略选择理论。它论。它将成为当代经济管理学科的前沿领城。将成为当代经济管理学科的前沿领城。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理方案的数学理论和方法。案，以及如何找到这个合理方案的数学理论和方法。12.1引言引言第5页，本讲稿共74页一个对策需要一个对策需要3个基本要素：个基本要素：(1)局中人局中人(players)(2)策略集策略集(strategies)(3)得益函数（得益函数（payoffs）12.1.2对策三要素对策三要素是一个局势是一个局势策略组策略组全体局势的集合全体局势的集合S可用各局中人的策略集的迪卡尔集表示可用各局中人的策略集的迪卡尔集表示12.1引言引言第6页，本讲稿共74页12.1.3对策的结构和分类对策的结构和分类12.1引言引言第7页，本讲稿共74页【例【例12.1】1943年年2月，日本统帅山本五十六大将计划由南太平洋新月，日本统帅山本五十六大将计划由南太平洋新不列颠群岛的拉包尔出发，不列颠群岛的拉包尔出发，3天穿过俾斯麦海，开往新几内亚的莱城，天穿过俾斯麦海，开往新几内亚的莱城，支援困守的日军。有两条路线：北线和南线。支援困守的日军。有两条路线：北线和南线。盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组织空中打盟军统帅麦克阿瑟命令他麾下的太平洋战区空军司令肯尼将军组织空中打击。侦察机重点搜索有两个方案：北线和南线。击。侦察机重点搜索有两个方案：北线和南线。当时未来当时未来3天中：北线阴雨，能见度差；南线晴天，能见度佳。日美双方各天中：北线阴雨，能见度差；南线晴天，能见度佳。日美双方各自应采用哪种方案自应采用哪种方案12.1引言引言第8页，本讲稿共74页北线北线南线南线第9页，本讲稿共74页日军日军盟军盟军北线北线（）南线南线()北线（北线（）22南线（南线（）13【解】【解】局中人：盟军、日军；双方策略：北线、南线，记为局中人：盟军、日军；双方策略：北线、南线，记为:盟军的赢得矩阵如下：盟军的赢得矩阵如下：最优策略是：最优策略是：,即都选择北线。日军舰队即都选择北线。日军舰队受到重创，但未全歼。受到重创，但未全歼。双方选择的策略是：在双方选择的策略是：在最不利中选择最有利的最不利中选择最有利的策略。策略。12.1引言引言第10页，本讲稿共74页囚徒的困境（二人非零和对策）囚徒的困境（二人非零和对策）5，50，1010，01，1囚囚徒徒1囚徒囚徒2坦坦白白不坦白不坦白坦白坦白不坦白不坦白双方如何采取对策使结果对自己最有利？双方如何采取对策使结果对自己最有利？12.1引言引言第11页，本讲稿共74页【例【例12.2】双寡头削价竞争（两个厂商）双寡头削价竞争（两个厂商）100，10020，150150，2070，70亚亚贸贸中南中南高高价价低低价价高价高价低价低价类似地，广告投资、采用新技术等方面，厂商之间常常耗资巨大，但类似地，广告投资、采用新技术等方面，厂商之间常常耗资巨大，但不一定有利可图的争夺战；对公共资源的掠夺式使用等问题。不一定有利可图的争夺战；对公共资源的掠夺式使用等问题。我们的目的是如何利用这种困境达到有利于社会，合理利用和开发我们的目的是如何利用这种困境达到有利于社会，合理利用和开发公共资源，保护环境。公共资源，保护环境。12.1引言引言第12页，本讲稿共74页多寡头削价竞争（多寡头削价竞争（3个厂商个厂商:亚贸亚贸,中南，中北中南，中北)）100，100，10020，150，20150，20，20130，130，20亚亚贸贸中南中南高高价价低低价价高价高价低价低价20，20，15020，130，130130，20，13070，70，70亚亚贸贸中南中南高高价价低低价价高价高价低价低价中北采用高价中北采用高价中北采用低价中北采用低价12.1引言引言第13页，本讲稿共74页【例【例12.3】动态对策：甲向乙借一万元钱经营，甲许诺经营成功后分给乙总利动态对策：甲向乙借一万元钱经营，甲许诺经营成功后分给乙总利润（润（4万）的一半，乙是否借给甲？万）的一半，乙是否借给甲？乙乙甲甲借借不借不借乙乙分分不分不分(2，2)(1，0)打打乙乙不打不打(0，4)(1，0)(1,0)有法律保障有法律保障法律保障不足法律保障不足12.1引言引言第14页，本讲稿共74页下一节：纳什均衡下一节：纳什均衡12.1引言引言第15页，本讲稿共74页12.2纳什均衡纳什均衡NashEquilibrium第16页，本讲稿共74页12.2纳什均衡纳什均衡Nash对对策论的贡献有：（对对策论的贡献有：（1）合作对策中的讨价还价模型，称为）合作对策中的讨价还价模型，称为Nash讨价讨价还价解；（还价解；（2）非合作对策的均衡分析。）非合作对策的均衡分析。纳什均衡纳什均衡（NashEquilibrium）假定有假定有n个博弈方参加博弈，在给定其他博弈方策个博弈方参加博弈，在给定其他博弈方策略的条件下，每个人选择自己的最优策略（个人最优策略可能依赖也可能不依赖略的条件下，每个人选择自己的最优策略（个人最优策略可能依赖也可能不依赖他人策略），一起构成一个策略组合（他人策略），一起构成一个策略组合（Strategy Profile），而），而Nash均衡是这样均衡是这样一种策略组合，由所有参与人的最优策略组成，给定别人策略的条件下，没有任一种策略组合，由所有参与人的最优策略组成，给定别人策略的条件下，没有任何单个参与人有积极性选择其他策略，从而没有任何人有积极性打破这种均衡，何单个参与人有积极性选择其他策略，从而没有任何人有积极性打破这种均衡，Nash均衡是一种均衡是一种“僵局僵局”：给定别人不动的情况下，没有人有兴趣动。：给定别人不动的情况下，没有人有兴趣动。约翰约翰纳什纳什(JohnF.Nash)1928年生于美国年生于美国,1994年获得诺贝尔经济学奖年获得诺贝尔经济学奖在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论在非合作博弈的均衡分析理论方面做出了开创性的贡献，对博弈论和经济学产生了重大影响和经济学产生了重大影响12.2.1纳什均衡定义纳什均衡定义第17页，本讲稿共74页另一种解释：另一种解释：假定所有博弈方事先达成一项协议，规定每个人的行为规则，假定所有博弈方事先达成一项协议，规定每个人的行为规则，在没有外在的强制力约束时，当事人会自觉遵守这个协议，等于说这个协在没有外在的强制力约束时，当事人会自觉遵守这个协议，等于说这个协议构成一个纳什均衡：假定别人遵守协议的情况下，没有人有积极性偏离议构成一个纳什均衡：假定别人遵守协议的情况下，没有人有积极性偏离协议规定的自己的行为规则。换句话说，如果一个协议不构成纳什均衡，协议规定的自己的行为规则。换句话说，如果一个协议不构成纳什均衡，它就不可能自动实施，因为至少有一个参与人会违背此协议，不满足它就不可能自动实施，因为至少有一个参与人会违背此协议，不满足Nash均衡要求的协议是没有意义的。均衡要求的协议是没有意义的。12.2纳什均衡纳什均衡第18页，本讲稿共74页用用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*）的最佳策略，即）的最佳策略，即hi（S1*，S*i-1，Si*，S*i+1Sn*）hi（S1*，S*i-1，Sij，S*i+1，Sn*）对任意）对任意SijSi都成立，则称（都成立，则称（S1*，Sn*）为）为G的一个纯策略的一个纯策略“纳什均衡纳什均衡”（NashEquilibrium）G=S1，Sn；h1，hn12.2纳什均衡纳什均衡第19页，本讲稿共74页各选取一个策略组成的某个策略组合构成一个各选取一个策略组成的某个策略组合构成一个局势局势，其最优局势称为纯，其最优局势称为纯策略意义下的策略意义下的最优局势最优局势【例【例12.4】假设有三个厂商在同一市场上生产销售完全相同的产品，假设有三个厂商在同一市场上生产销售完全相同的产品，它们各自的产量分别用它们各自的产量分别用m1、m2和和m3表示，再假设表示，再假设m1、m2和和m3只能取只能取1、2、3等正整数值市场出清价格一定是市场总产量等正整数值市场出清价格一定是市场总产量Q=m1+m2+m3的的函数，假设该函数为：函数，假设该函数为：不妨先假设三个厂商开始时分别生产不妨先假设三个厂商开始时分别生产3单位，单位，9单位和单位和6单位产量，单位产量，这时三厂商是否满意各自的产量，要从利润进行分析这时三厂商是否满意各自的产量，要从利润进行分析由于产量不能超过由于产量不能超过20，则第，则第i个厂商的利润函数为个厂商的利润函数为12.2纳什均衡纳什均衡第20页，本讲稿共74页可算出在产量组合为（可算出在产量组合为（3，9，6）时，市场价格为）时，市场价格为2，三厂商的利润分，三厂商的利润分8，16和和12，再作其它产量组合时亦会有不同的结果，如表，再作其它产量组合时亦会有不同的结果，如表12.2表表12.2三厂商离散产量结合对应价格和利润三厂商离散产量结合对应价格和利润m1m2m3p1233962618123863924185564202024555525252533311333333633848242412.2纳什均衡纳什均衡第21页，本讲稿共74页【定义【定义12.2】在对策在对策G=S1，Sn；h1，hn中，局中人中，局中人i的策略集的策略集为为Si=Si1，Sik，则他以概率分布，则他以概率分布pi=（pi1，pik）随机在其）随机在其k个可个可选策略中选择的选策略中选择的“策略策略”称为一个混合策略，其中称为一个混合策略，其中0pij1对对j1，k都成立，且都成立，且pi1+pik=112.2.2混合策略纳什均衡混合策略纳什均衡12.2纳什均衡纳什均衡第22页，本讲稿共74页【定义【定义12.3】如果一个策略如果一个策略G=S1，Sn，h1，hn中，参予者中，参予者i的的策略集为策略集为Si=Si1，Sik，如果由各个对策方的策略组成策略集合，如果由各个对策方的策略组成策略集合G*=S1*，S2*，Sn*，其中，其中都是对其余对策方策略组合的最佳策略，即都是对其余对策方策略组合的最佳策略，即i（S1*,S2*,，Si-1*，Si*，Sn*）i（S1*,S2*,，Si-1*，Si*，Sn*）对任意对任意SijSi都成立，则称（都成立，则称（S1*,，Sn*）为）为G的一个混合策略纳什均的一个混合策略纳什均衡衡12.2纳什均衡纳什均衡第23页，本讲稿共74页下一节：反应函数法下一节：反应函数法作业：教材作业：教材P293T1012.2纳什均衡纳什均衡第24页，本讲稿共74页12.3反应函数法反应函数法第25页，本讲稿共74页12.3反应函数法反应函数法当得益是对策的多元连续函数时，求出每个对策方的反应函数，而各当得益是对策的多元连续函数时，求出每个对策方的反应函数，而各个反应函数的交点就是纳什均衡个反应函数的交点就是纳什均衡【例【例12.5】设】设A，B两厂家生产同样产品，厂商两厂家生产同样产品，厂商A产量为产量为q1，B产量为产量为q2，市场总产量为市场总产量为Q=q1+q2，市场出清价格是市场总产量的函数，市场出清价格是市场总产量的函数P6Q。设产。设产品产量的边际成本相等，品产量的边际成本相等，C1=C2=2。求解两厂商的纳什均（假设产量连续可分）。求解两厂商的纳什均（假设产量连续可分）。分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂商各自分析：这是一个连续产量的古诺模型，不难看出，该对策中两厂商各自的利润分别为各自的销售收益减去各自成本，即：的利润分别为各自的销售收益减去各自成本，即：第26页，本讲稿共74页12.3反应函数法反应函数法作反应函数：作反应函数：(0,4)（0,2)(2,0)(4,0)(4/3,4/3)纳什均衡：纳什均衡：(4/3,4/3)第27页，本讲稿共74页12.3反应函数法反应函数法【例【例12.6】考虑上述模型的另一种情况即各厂商所选择的是价格而不是产考虑上述模型的另一种情况即各厂商所选择的是价格而不是产量，假设产量与价格的函数关系为：量，假设产量与价格的函数关系为：其它条件不变，边际成本为其它条件不变，边际成本为C1、C2，试求解其纳什均衡。，试求解其纳什均衡。各自的策略空间为各自的策略空间为两方的得益就是各自的利润两方的得益就是各自的利润第28页，本讲稿共74页12.3反应函数法反应函数法利用得益函数在偏导数为利用得益函数在偏导数为0时有最大值，各自的反应函数分别为：时有最大值，各自的反应函数分别为：为该对策唯一的纳什均衡为该对策唯一的纳什均衡第29页，本讲稿共74页12.3反应函数法反应函数法【例【例12.7】设有】设有3个农户一起放牧羊群，现有一可供大家自由放牧的个农户一起放牧羊群，现有一可供大家自由放牧的草地，由于草地面积有限，只能供有限只羊群吃饱，否则就会影响草地，由于草地面积有限，只能供有限只羊群吃饱，否则就会影响到羊群的产出，假设每只羊的产出函数为到羊群的产出，假设每只羊的产出函数为成本成本C=8，且每个农户在决定自己放牧羊群数的时候并不知道其它农，且每个农户在决定自己放牧羊群数的时候并不知道其它农户的决策，试求出该决策问题的纳什均衡。户的决策，试求出该决策问题的纳什均衡。【解】各农户的得益函数分别为【解】各农户的得益函数分别为第30页，本讲稿共74页12.3反应函数法反应函数法反应函数 因此该对策的纳什均衡为（因此该对策的纳什均衡为（18，18，18）下一节：有限二人零和对策下一节：有限二人零和对策 作业：教材作业：教材P293T9第31页，本讲稿共74页12.4有限二人零和对策有限二人零和对策第32页，本讲稿共74页矩阵对策就是二人有限零和对策。矩阵对策就是二人有限零和对策。通常矩阵用来表示局中人通常矩阵用来表示局中人1的赢得，局中人的赢得，局中人2的支付。的支付。12.4有限二人零和对策有限二人零和对策 用用、表示两个局中人，并设局中人表示两个局中人，并设局中人有有m个纯策略，个纯策略，1，2，m，局中人，局中人有有n个纯策略个纯策略1，2，n，则按对策论的相关要素定，则按对策论的相关要素定义，局中人义，局中人、的策略集分别为：的策略集分别为：第33页，本讲稿共74页可以算出，局中人可以算出，局中人、所构成的策略组合共有所构成的策略组合共有mn个，记局中人个，记局中人在策略（在策略（i,j）下的赢得）下的赢得aij，则，则在每个策略的赢得构成一个矩阵在每个策略的赢得构成一个矩阵当局中人当局中人、的策略集的策略集S1,S2及及I的赢得矩阵确定后，一个矩阵对策就给的赢得矩阵确定后，一个矩阵对策就给定了通常将矩阵对策记为：定了通常将矩阵对策记为：12.4有限二人零和对策有限二人零和对策 第34页，本讲稿共74页12.4.1数学定义数学定义12.4有限二人零和对策有限二人零和对策 称称A为局中人为局中人的赢得矩阵（或为的赢得矩阵（或为的支付矩阵），由于对策为零和的，故的支付矩阵），由于对策为零和的，故局中人局中人的赢得矩阵为的赢得矩阵为A。矩阵对策记为矩阵对策记为第35页，本讲稿共74页成立，成立，则称，则称VG为对策为对策G的值，对应的策略组合的值，对应的策略组合12.4.2纯策略矩阵对策纯策略矩阵对策【定义【定义12.4】设设G=S1，S2；A为矩阵对策，其中为矩阵对策，其中S1=1，2，n，S2=1，2，n，若等式若等式称为该对策的纳什均衡称为该对策的纳什均衡12.4有限二人零和对策有限二人零和对策 第36页，本讲稿共74页【例【例12.8】求解矩阵对策，其中求解矩阵对策，其中则有则有对策对策G的解为：的解为：【解】【解】12.4有限二人零和对策有限二人零和对策 第37页，本讲稿共74页【定理【定理12.1】矩阵对策矩阵对策G=S1，S2；A在纯策略定义下有纳什均衡的充在纯策略定义下有纳什均衡的充要条件是：存在策略组合要条件是：存在策略组合使得对一切使得对一切i=1，m,j=1，n,均有：均有：矩阵对策在纯策略意义下有解且矩阵对策在纯策略意义下有解且VG=ai*j*的充要条件是：的充要条件是：ai*j*是是A的鞍点，的鞍点，在对策论中，矩阵在对策论中，矩阵A的鞍点也称为对策的鞍点的鞍点也称为对策的鞍点12.4有限二人零和对策有限二人零和对策 第38页，本讲稿共74页【定义【定义5】设设f(x，y)为一个定义在为一个定义在xA及及yB上的实函数上的实函数，如果存在如果存在x*A及及y*B,使得对一切使得对一切xA及及yB有有则称则称为函数为函数f的有关鞍点。的有关鞍点。矩阵对策在纯策略意义下的解且矩阵对策在纯策略意义下的解且的充要条件是的充要条件是是是A的鞍点。的鞍点。12.4有限二人零和对策有限二人零和对策 第39页，本讲稿共74页【解】【解】直接在赢得表上计算，有直接在赢得表上计算，有可知可知=5，i*=1,3，j*=2,4故（故（1，2）（）（1，4）（）（2，2）（2，4）为对策的纳什均衡，）为对策的纳什均衡，VG=512.4有限二人零和对策有限二人零和对策【例【例12.9】设有矩阵对策设有矩阵对策G=S1，S2；A，赢得矩阵为，赢得矩阵为求纳什均衡求纳什均衡第40页，本讲稿共74页【性质【性质12.1】无差别性若无差别性若和和为为G的两个解，则：的两个解，则：【性质【性质12.2】可交换性若可交换性若和和为为G的两个解，则的两个解，则以上方法也称以上方法也称“上策均衡法上策均衡法”(Dominant-strategeEqyilibrium)12.4有限二人零和对策有限二人零和对策 也是对策的解也是对策的解及及第41页，本讲稿共74页【例【例12.10】甲、乙两个企业同时生产一种电子产品（假设市场上只有这两甲、乙两个企业同时生产一种电子产品（假设市场上只有这两家，为一双寡头竞争局面），两个企业都想通过改革管理获取更多的销售份家，为一双寡头竞争局面），两个企业都想通过改革管理获取更多的销售份额，甲企业的策略措施有：（额，甲企业的策略措施有：（1）降低产品价格；（）降低产品价格；（2）提高产品质量；（）提高产品质量；（3）推出新产品乙企业措施为：（推出新产品乙企业措施为：（1）增加广告费用；（）增加广告费用；（2）增设网点；（）增设网点；（3）改）改进产品性能，通过预测，两个企业市场份额变动情况如表进产品性能，通过预测，两个企业市场份额变动情况如表124所示，试确定所示，试确定最优策略最优策略乙乙企企业业123min甲甲企企业业112131213103335855*max13105*【解】【解】则对策最优解为则对策最优解为VG=5，纳什均衡，纳什均衡为（为（3，3）甲企业采用推出）甲企业采用推出新产品策略，乙企业采用改进产新产品策略，乙企业采用改进产品性能策略，结果甲企业赢得品性能策略，结果甲企业赢得5的市场份额的市场份额12.4有限二人零和对策有限二人零和对策 第42页，本讲稿共74页12.4.3混合策略矩阵对策混合策略矩阵对策纯策略矩阵对策的满足纳什均衡是满足局中人纯策略矩阵对策的满足纳什均衡是满足局中人有把握的至少赢有把握的至少赢得是局中人得是局中人有把握的至多损失即：有把握的至多损失即：当当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有限二人零和对策有限二人零和对策 第43页，本讲稿共74页利用最大最小和最小最大原则，发现不存在使得利用最大最小和最小最大原则，发现不存在使得成立的点成立的点12.4有限二人零和对策有限二人零和对策 第44页，本讲稿共74页例：例：对局中人对局中人1来说，来说，v1=2，i*=2，对局中人，对局中人2来说，来说，v2=3，j*=1，v1v2。没有鞍点。没有鞍点。【定义【定义12.6】设矩阵对策】设矩阵对策，其中，其中记记12.4有限二人零和对策有限二人零和对策 第45页，本讲稿共74页则分别称则分别称为局中人为局中人、的混合策略集；的混合策略集；、分别称为分别称为局中人局中人1、2的混合策略，的混合策略，为一个混合局势。为一个混合局势。称为称为G 的混合扩充。的混合扩充。E是赢得期望值。是赢得期望值。【定义】当【定义】当时，称时，称为局中人为局中人、在混合策略中的纳什均衡。在混合策略中的纳什均衡。称为局中人称为局中人在选取混合策略在选取混合策略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有限二人零和对策有限二人零和对策 第46页，本讲稿共74页【例【例12.11】考虑矩阵对策考虑矩阵对策G=S1，S2；A，其中，其中局中人局中人1的赢得期望值：的赢得期望值：取取，满足满足试求纳什均衡试求纳什均衡【解】【解】纯策略纳什均衡不存在设纯策略纳什均衡不存在设x=（x1，x2）为局中人）为局中人的混合策略，的混合策略，y=(y1，y2)为局中人为局中人的混合策略，则：的混合策略，则：12.4有限二人零和对策有限二人零和对策 第47页，本讲稿共74页分别为局中人分别为局中人和和的最优策略即该对策的纳什均衡。的最优策略即该对策的纳什均衡。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有限二人零和对策有限二人零和对策 第48页，本讲稿共74页【定理【定理12.4】设设x*S1*，y*S2*，则（，则（x*，y*）是对策）是对策G的纳什均衡的的纳什均衡的充要条件是：存在数充要条件是：存在数V，使得，使得x*，y*分别满足：分别满足：且且V=VG.【定理【定理12.5】对任一矩阵对策对任一矩阵对策G=S1，S2；A，一定存在混合策略意义，一定存在混合策略意义下的纳什均衡下的纳什均衡12.4有限二人零和对策有限二人零和对策 第49页，本讲稿共74页【定理【定理12.6】设（设（x*，y*）为矩阵对策）为矩阵对策G的一个纳什均衡，的一个纳什均衡，V=VG，则，则(1)若若xi*0，则，则(2)若若yi*0，则，则(3)若若，则，则(4)若若,则则12.4有限二人零和对策有限二人零和对策 例例第50页，本讲稿共74页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)为两个对策的解集合为两个对策的解集合第51页，本讲稿共74页1.优超原则法优超原则法【例【例12.12】设赢得矩阵设赢得矩阵A为为:求纳什均衡求纳什均衡【解】【解】第第4行优于第行优于第1行，第行，第3行优于第行优于第2行，故可划去第行，故可划去第1行和第行和第2行，行，得到新的赢得矩阵，得到新的赢得矩阵，x1=x2=012.4有限二人零和对策有限二人零和对策 12.4.5矩阵对策求解方法矩阵对策求解方法“严格下策反复消去法严格下策反复消去法”(IteratedEliminationofStrictly DominatedStrategies)第52页，本讲稿共74页对于对于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 12.4有限二人零和对策有限二人零和对策 第53页，本讲稿共74页2.线性方程组法线性方程组法若最优策略中若最优策略中和和均不为零时，有均不为零时，有12.4有限二人零和对策有限二人零和对策【例【例12.14】求解矩阵对策】求解矩阵对策【解】建立方程组【解】建立方程组求解得：求解得：x=(0.525，0.275，0.2),y=(0.2，0.05，0.75);VG=0.45第54页，本讲稿共74页3.线性规划方法线性规划方法任意矩阵对策任意矩阵对策的求解均等价于一对互为对偶的的求解均等价于一对互为对偶的线性规划问题，而定理线性规划问题，而定理12.4表明，对策表明，对策G的解等价于下面两个不的解等价于下面两个不等式的解等式的解【定理【定理12.9】设矩阵对策的值为设矩阵对策的值为v，则：，则：12.4有限二人零和对策有限二人零和对策 第55页，本讲稿共74页则则局中人局中人、的最优策略的最优策略等价于线性规划问题：等价于线性规划问题：12.4有限二人零和对策有限二人零和对策 第56页，本讲稿共74页 令 有局中人局中人：12.4有限二人零和对策有限二人零和对策 第57页，本讲稿共74页同理同理,令令有有局中人局中人：12.4有限二人零和对策有限二人零和对策 第58页，本讲稿共74页【例【例12.12】利用线性规划方法求解赢得矩阵为利用线性规划方法求解赢得矩阵为的矩阵对策的纳什均衡的矩阵对策的纳什均衡【解】【解】此问题可化为两个互为对偶的线性规划问题：此问题可化为两个互为对偶的线性规划问题：12.4有限二人零和对策有限二人零和对策 第59页，本讲稿共74页最优解：最优解：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.3912.4有限二人零和对策有限二人零和对策 第60页，本讲稿共74页下一节：有限二人非零和对策下一节：有限二人非零和对策 12.4有限二人零和对策有限二人零和对策 作业：教材作业：教材P292T3、4、5、6、8第61页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策第62页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策12.5.1数学定义数学定义【例【例11.16】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩】市场上有两企业生产同样商品，甲企业与乙企业的赢得矩阵分别为阵分别为矩阵矩阵A1和和A2合并为双矩阵合并为双矩阵依然在混合扩充意义下考虑有限二人非零和对策，记局中人依然在混合扩充意义下考虑有限二人非零和对策，记局中人1的混合策的混合策略为略为x，局中人，局中人2的混合策略为的混合策略为y，相应的策略集记为，相应的策略集记为第63页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策【定义【定义12.8】对于某个有限二人非零和对策，其局中人对于某个有限二人非零和对策，其局中人1的赢得（混的赢得（混合策略下）为合策略下）为局中人局中人2的赢得为的赢得为第64页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策12.5.2有限二人非零和对策纳什均衡有限二人非零和对策纳什均衡分别是局中人分别是局中人1和和2的赢得，的赢得，和和如果有一对策略如果有一对策略为任意策略，为任意策略，满足满足则称则称为该对策的纳什均衡，称为该对策的纳什均衡，称为对策的纳什均衡解（或赢得）为对策的纳什均衡解（或赢得）【定理【定理12.10】（纳什定理）任何矩阵对策及有限二人非零和对策至少】（纳什定理）任何矩阵对策及有限二人非零和对策至少有一个纳什均衡有一个纳什均衡【定义【定义12.9】在有限二人非零和对策中，设】在有限二人非零和对策中，设第65页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策1.图解法图解法12.5.322有限二人非零和对策的求解有限二人非零和对策的求解【例【例11.17】图解下列非零和对策】图解下列非零和对策【解】（【解】（1）作出坐标系图）作出坐标系图123，原点为，原点为0，在各轴值为，在各轴值为1的点分的点分别引线段与坐标轴构成正方形，它便是别引线段与坐标轴构成正方形，它便是(x，y)的定义域，的定义域，（2）局中人）局中人1的赢得的赢得(期望值期望值)为为第66页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策当当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的赢得为的赢得为第67页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策（3）局中人）局中人2的赢得为的赢得为图图12曲线曲线l和曲线和曲线2在图在图124中有三个交点中有三个交点(用用“0”号标出号标出)这三个交点上的这三个交点上的x*和和y*所构所构成的局势成的局势能够同时满足平衡条件能够同时满足平衡条件第68页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策对策值为对策值为(3,2)对策值为对策值为(2.4，2.5)(1)(2)(3)对策值为对策值为(4，4)2.优超原则法优超原则法存在某个策略绝对劣于另一个策略时，称为下策，去掉下策。存在某个策略绝对劣于另一个策略时，称为下策，去掉下策。【例【例11.17】用优超原则求解下列非零和对策】用优超原则求解下列非零和对策纳什均衡纳什均衡(纯策略纯策略)解：解：对策值：对策值：有效解为混合策略（有效解为混合策略（3）第69页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策3.划线法划线法当局中人当局中人2采取策略采取策略j时，局中人时，局中人1在对自己最有利的策略值下划一横在对自己最有利的策略值下划一横线。线。同理，当局中人同理，当局中人1采取策略采取策略i时，局中人时，局中人2在对自己最有利的策略值下在对自己最有利的策略值下划一横线。划一横线。如果某一组合策略值下都划了横线，则此组合策略就是纳什均衡解。否则，如果某一组合策略值下都划了横线，则此组合策略就是纳什均衡解。否则，不存在纯策略意义下的纳什均衡。不存在纯策略意义下的纳什均衡。下都已划线，则纳什均衡解为下都已划线，则纳什均衡解为例例12.17：例例12.17得到两个解，无法确定。这种情形划线法失效！得到两个解，无法确定。这种情形划线法失效！第70页，本讲稿共74页4.方程组方法方程组方法12.5有限二人非零和对策有限二人非零和对策局中人局中人2取策略取策略1时的期望值为时的期望值为局中人局中人2取策略取策略n时的期望值为时的期望值为局中人局中人2取策略取策略2时的期望值为时的期望值为局中人局中人1选取概率选取概率x1，x2，xm的目的一定要使得局中人的目的一定要使得局中人2取策略取策略j 的赢得期望值都相等并且概率求和等于的赢得期望值都相等并且概率求和等于1，即，即第71页，本讲稿共74页12.5有限二人非零和对策有限二人非零和对策方程组的解为纳什均衡的解。同理，对局中人方程组的解为纳什均衡的解。同理，对局中