《运筹学教学资料》ch14 对策论

第十四章对策论引言对策行为的三要素对策的分类

二元对策模型二元对策的纯策略二元对策的混合策略

最优策略二元对策的基本定理二元对策的解法编辑ppt要想在现代社会做一个有文化的人，你必须对博弈论有一个大致了解.——诺贝尔经济学奖获得者

PaulSamuelson编辑ppt引言一、对策现象和对策论在人类社会活动中，经常会遇到各种具有竞争或对抗性质的行为。比如体育比赛、军事战争、政治斗争等，尤其是在经济生活中，企业之间的竞争，各种经济谈判.具有竞争或对抗性质的行为称为对策行为。在对策行为中，参与竞争的各方（局中人）各有不同的利益目标，各有自己的可能的行动方案（策略），在每一次竞争过程（局势）中，都力图选取对自己最为有利或最为合理的方案（最优策略）.编辑ppt对策论就是研究对策现象中各方是否存在最合理的行动方案，以及如何找到合理的行动方案的数学理论和方法，亦称博弈论或竞赛论.是运筹学的一个重要学科。对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般日常生活等有着密切联系，并且处理问题的方法又有明显特色，所以日益引起广泛的注意。编辑ppt齐王赛马战国时代，齐王有一天要和他的大将军田忌赛马。比赛三场，每场各自选上中下三个等级的马一匹进行比赛，并规定每个等级的马只能赛一场，三赛二胜者为赢。已知在同等级的马中，齐王的马都比田忌的马强；在不同等级中，齐王的马要比田忌的高一个等级的马弱。编辑ppt对局策略田忌为取得比赛的胜利，接受了孙膑的建议：每场比赛时先让齐王牵出要比赛的马(名为恭敬实有对策)，然后用自己的下马对齐王的上马，中马对齐王的下马，上马对齐王的中马。比赛结果，田忌获胜。在这个故事里，田忌并没有设法去得到更好的马，而只是在比赛中运用了较好的策略而获胜.编辑ppt囚徒困境问题甲和乙两个小偷联手作案，因私入民宅被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。将这些数据列出，如下：编辑ppt囚徒困境博弈编辑ppt博弈结果：尽管甲不知道乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年；但若两人都不招，结果是每人只被判1年，但在“人是理性的，即人人都会在约束条件下最大化自身的利益”的基本假设下，这种结果是不会出现的.编辑ppt甲和乙是参与博弈的人，称为“局中人”.表中每一个小方格内的数字被称为局中人的支付，其中左边的数字代表甲的支付，右边的是乙的支付.表中的双变量矩阵称为博弈支付矩阵.局中人所选择的战略构成的组合（招,招）被称为博弈均衡.这个组合中前后两个战略分别表示甲和乙所选择的战略.编辑ppt如果甲和乙在决策时抛掉谨慎，加入一定的“疯狂”，不约而同地采取“不招”的策略，其结果是每人只被判1年.显然，这对甲、乙二人来说，比他们采取理性策略的结果“好”.

编辑ppt商家价格战出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱.当一些商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来.编辑ppt博弈论有三个基本假设：参与人是理性的；他们有这些理性的共同知识；他们知道博弈规则.任何一个博弈问题都包含如下三个要素：局中人、策略和支付函数.编辑ppt二、对策行为的三要素（1）局中人（player)一个对策中，有权决定自己行动方案的对策参加者称为局中人，通常用I

表示局中人的集合。如果有

n

个局中人，则I＝{1，2，…，n}.一般要求一个对策中至少有两个局中人.如果局中人数为2，则称对策为二元对策。如在“齐王赛马”中，局中人是齐王和田忌。编辑ppt局中人的概念具有广义性。局中人除了可以理解为个人外，还可理解为一个集体.如球队、交战方、企业等。另外，在对策中利益完全一致的参加者只能看成是一个局中人．例如桥牌中的东、西方和南、北方各为一个局中人．虽有4人参赛，但只能算有两个局中人。对策论中对局中人的一个重要的假设是：每个局中人都是“理智的”，即对每一局中人来说，不能存在侥幸心理，不存在利用其它局中人决策的失误来扩大自身利益的行为.编辑ppt（2）策略集（strategyset）对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。所有策略构成局中人的策略集。每一局中人i的策略集记为Si，一般每一局中人的策略集中至少应包括两个策略。在“齐王赛马”中，三匹马依次参赛的次序就是一个完整的行动方案，即为一个策略。可见，齐王和田忌各自都有6个策略：(上,中,下)、(上,下,中)、(中,上,下)、(中,下,上)、(下,中,上)、(下,上,中).S1={α1，α2，α3，α4，α5，α6}S2={β1，β2，β3，β4，β5，β6}编辑ppt（3）赢得函数（支付矩阵,payoffmatrix）设si是第i

个局中人的一个策略，则n个局中人的策略形成的策略组s

就是一个局势.对策中，每一局中人各自选取一个策略后，构成的策略组称为一个局势，或结局。s=(s1，s2，……，sn)全部局势的集合S可以表示为如(α1,β1)，(α1,β2)，(α3,β1)，……编辑ppt当局势出现后，对策行为的结果也就确定。当一个局势s

出现后，应该为每一局中人i

规定一个赢得值(或所失值)Hi(s).显然,Hi(s)是定义在S

上的函数，称为局中人i

的赢得函数（支付矩阵）

。“齐王赛马”中，αi

和βj构成一个局势sij.在局势s11下，齐王赢得H1(s11)=

3，田忌赢得H2(s11)=

-3.齐王应取得的支付值3,田忌得到的支付值是-3；或者说齐王赢得3，田忌输掉3。如此类推，可得到“齐王赛马”的支付矩阵.编辑ppt“齐王赛马”支付矩阵β1

β2

β3

β4

β5

β6α1α2α3α4α5α6一般，当局中人、策略集和赢得函数这3个要素确定后，一个对策模型也就给定了.编辑ppt例1

有三个位于某河流同侧的城市,从上游到下游依次为A,B,C，这三个城市的污水必须经处理后才能排入河中.A与B距离为20km,B与C距离38km，如图.设Q为污水流量(单位：),L为管道长度(km).建污水厂费用的经验公式为(单位：万元),而建管道费用的经验公式为(单位：万元).已知三城市的污水流量分别为，问应该怎样处理(单独设厂还是联合设厂)，才可使总开支最少？又每一城镇负担的费用应各为多少?三、对策问题举例对策论在经济管理的众多领域中应用十分广泛。编辑ppt例2(拍卖问题)最常见的一种拍卖形式是先由拍卖商把拍卖品描述一番，然后提出第一个报价。接下来由买者报价，每一次报价都要比前一次高，最后谁出的价最高招卖品即归谁所有。假设有

n

个买主给出的报价分别为p1,…,

pn,且不妨设pn>pn-1>…>p1,则买主n

只要报价略高于pn-1，就能买到拍卖品，即拍卖品实际上是在次高价格上卖出的。现在的问题是，各买主之间可能知道他人的估价，也可能不知道他人的估价，每人应如何报价对自己能以较低的价格得到拍卖品最为有利？最后的结果又会怎样?编辑ppt例3(市场购买力争夺问题)据预测，某乡镇下一年的饮食品购买力将有4000万元。乡镇企业和中心城市企业饮食品的生产情况是：乡镇企业有特色饮食品和低档饮食品两类，中心城市企业有高档饮食品和低档饮食品两类产品。它们争夺这一部分购买力的结局见表(表中数字的单位是万元)，问题是乡镇企业和中心城市企业应如何选择对自己最有利的产品策略。乡镇策略中心城市企业的策略出售高档饮食品出售低档饮食品出售特色饮食品20003000出售一般饮食品10003000乡镇企业所得.编辑ppt(1)根据局中人的个数，分为二人对策和多人对策；(2)根据各局中人的赢得函数的代数和是否为零，分为零和对策与非零和对策；(3)根据各局中人间是否允许合作，分为合作对策和非合作对策；(4)根据局中人的策略集中的策略个数．分为有限对策和无限对策等等。此外，还有许多其它的分类方式、例如根据策略的选择是否与时间有关，可分为静态对策和动态对策；根据对策模型的数学持征，可分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策等。（四）对策的分类编辑ppt在众多对策模型中，占有重要地位的是二人有限零和对策，简称二元对策，又称为矩阵对策。因为利用对策的支付矩阵能够完成对策的确定。矩阵对策是到目前为止在理论研究和求解方法方面都比较完善的一个对策分支。矩阵对策可以说是一类最简单的对策模型，其研究思想和方法十分具有代表性，体现了对策论的一般思想和方法，且矩阵对策的基本结果也是研究其它对策模型的基础。本章将着重介绍矩阵对策的基本内容。编辑ppt§14.1二元对策模型一、二元对策的纯策略二元对策即为二人有限零和对策。“二人”是指参加对策的局中人有两个；“有限”是指每个局中人的策略集均为有限集；“零和”是指在任一局势下，两个局中人的赢得之和总等于零，即一个局中人的所得值恰好等于另一局中人的所失值，双方的利益是完全对抗的。“齐王赛马”就是一个二元对策的例子，齐王和田忌各有6个策略，一局对策后，齐王的所得必为田忌的所失。编辑ppt设Ⅰ,Ⅱ表示二元对策中的两个局中人；局中人Ⅰ和局中人Ⅱ的策略集分别表示为，S1={α1,α2,…,αm}，S2={β1，β2，…,βn}。设αij表示局势(αi,βj)的结果，αij表明局中人Ⅰ选定策略αi、局中人Ⅱ选定策略βj后，局中人Ⅰ得到的赢得值。局中人Ⅰ的赢得矩阵（或局中人Ⅱ的支付矩阵）可记为：由于对策是零和的，局中人Ⅱ的赢得矩阵为：-A.编辑ppt当局中人I，Ⅱ的策略集S1,S2及局中人I的赢得矩阵A确定后，一个矩阵对策就给定了。通常，将矩阵对策记为G＝(I，Ⅱ，S1，S2，A)或G＝(S1，S2，A).“齐王赛马”的数学模型：G={S1，S2；A}，S1={α1，α2，α3，α4，α5，α6}S2={β1，β2，β3，β4，β5，β6}其中αi与βj表示策略为(上中下),(上下中),(中上下),(中下上),(下中上),(下上中)。A为齐王的赢得矩阵.编辑ppt在支付矩阵A中aij

既是局中人Ⅰ的赢得值，又是局中人Ⅱ的损失值。局中人Ⅰ希望赢得值aij越大越好，而局中人Ⅱ则希望损失值aij越小越好。因此，矩阵对策完全是对抗性的。当矩阵对策模型给定后，各局中人面临的问题是:如何选择对自己最有利的策略以取得最大的赢得(或最少所失?)通过例子来分析各局中人应如何选择最有利策略。编辑ppt例1矩阵对策G={S1，S2；A}编辑ppt由A可看出,局中人I的最大赢得是9，要想得到这个赢得,他就得选则策略3,同时满心希望局中人Ⅱ选择策略1,造成最有利于自己的局势(3,1).策略分析由于假定局中人Ⅱ也是理智的竞争者，他考虑到局中人I打算出3

的心理，便准备以3对付之，则将造成最不有利于局中人Ⅰ的局势（3,3

）,使局中人I不但得不到9，反而失掉l0。局中人I当然也会猜到局中人Ⅱ的这种心理．故转而出4

来对付，造成局势(4,3).使局中人

Ⅱ得不到10，反而失掉6；……编辑ppt所以，如果双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己所得最少这一点，策略分析则一个最有利的情形作为决策的依据，这就是所谓“理智行为”，也是对策双方实际上可以接受并采取的一种稳妥的方法。就应该从各自可能出现的最不利的情形中选-8，2，-10，-3．其中最好的结果是2.因此，无论局中人II选择什么样的策略,局中人I只要以2参加对策，就能保证他的收入不会少于2，而出其它任何策略，都有可能使局中人I的收入少于2，甚至输给对方。编辑ppt策略分析同理，对局中人II来说，各策略可能带来的最不利的结果是：9，2，6．其中最好的也是2.无论对方采取何策略,他的所失值都不会超过2.而选择任何其它的策略都有可能使自己的所失超过2.即局中人II只要选择策略2

，分析表明，局中人I和II的“理智行为”分别是选择策略2和2

．这时，局中人I的赢得值和局中人II的所失值的绝对值相等(都是2)。相互的竞争使对策出现了一个平衡局势(2，2)，这个局势就是双方均可接受的，且对双方来说都是一个最稳妥的结果。因此2和2分别是局中人I和II的最优策略.编辑ppt局中人Ⅰ希望aij越大越好，因此他可以选择使上式为最大的策略，从而他的赢得不少于极大极小原则：如果局中人Ⅰ采用他的策略αi,则至少赢得为局中人Ⅱ希望aij越小越好，他可以选择使上式最小的策略，即保证他的损失不大于极小极大原则：如果局中人Ⅱ选取策略βj，则他至多失去编辑ppt由于局中人Ⅰ所得不会超过局中人Ⅱ的所失,故则称

是对策G的值；使上式成立的局势为G在纯策略意义下的解（或平衡局势）；与分别为局中人I和II的最优策略；称对策G是均衡对策。定义：给定二元对策G={S1，S2；A}；如果成立编辑ppt解：β1

β2β3α1α2α3α4-61-83249-1-10-306

依据矩阵A，α2与β2分别是局中人Ⅰ和Ⅱ的最优策略；对策G的值v=2。-82-10-3926注：（所在行最小，所在列最大）.编辑ppt该式的对策意义：当局中人Ⅰ坚守他的最优策略时，局中人Ⅱ若偏离他的最优策略，只能使局中人Ⅰ得到更多的支付值，至少不会减少；当局中人Ⅱ坚守他的最优策略时，局中人Ⅰ若偏离他的最优策略，只能他的赢得减少，至少不会增大。定理矩阵对策G={S1，S2；A}在纯策略意义下有解的充要条件是：存在纯局势

，使得对任意i

和j

，有编辑ppt称使式成立的元素为矩阵A的鞍点．在矩阵对策中，矩阵A的鞍点也称为对策的鞍点.鞍点性质：对策G是均衡对策当且仅当A有一个鞍点，即如果A有鞍点,则下式成立。支付矩阵A可能有不止一个鞍点.所有鞍点处的支付值都等于对策的值。编辑ppt可见都是A的鞍点，并且对策G的值是2。例2若对策G的支付矩阵是-1-322234编辑ppt二、二元对策的混合策略如果对策G={S1，S2；A}不是均衡对策，即A无鞍点，从而我们应该如何确定对策的最优解呢？编辑ppt例3两个小学生玩“锤子、剪刀、布”游戏。约束规则是：锤子胜剪刀，剪刀胜布，布胜锤子。双方各有三个策略αi与βj（i=1，2，3），分别表示锤子、剪刀和布，假定胜者得1分，负者得-1分，则支付矩阵编辑ppt分析容易验证这表明局中人Ⅰ至少可得赢得-1，局中人Ⅱ至多失去支付1。此时，局中人Ⅰ为了得到大于-1的赢得，局中人Ⅱ为了使支付小于1，都将尽最大努力不让对方猜出自己选择何种策略。局中人选取策略是随机的。对两个局中人来说，不存在一个双方都可以接受的平衡局势，即不存在纯策略意义下的解。编辑ppt在这种情况下，一个比较自然且合乎实际的想法是：既然局中人没有最优策略可出，是否可以给出一个选择不同策略的概率分布。如：局中人I可制订这样一种策略：分别以概率x1,x2,x3选取纯策略α1,

α2,α3，同样,局中人II也可以制定这样一种混合策略：分别以概率y1,y2,y3选取纯策略β1

,β2

,β3

.称这种策略为一个混合策略下面给出二元对策的混合策略及其在混合策略意义下解的定义。编辑ppt定义：设二元对策G={S1，S2；A}，xi

,yj表示局中人I,II选取策略αi,βj

的概率.称S1,S2为局中人I,

II的混合策略集(或策略集)对x∈S1，y∈S2,称x,y为混合策略.（x,y）为混合局势（或局势）.S1={α1，…,αm}S2={β1，…,βn}A=(aij)编辑ppt局中人Ⅰ选取策略αi，局中人Ⅱ选取策略βj时，支付aij的概率是xiyj

。局中人Ⅰ的赢得期望值（赢得函数）为：称对策是二元对策G的混合扩充。相对于混合策略，我们把前面所讨论的矩阵对策的策略称为纯策略。是混合策略的特殊情形。一个混合策略可理解为：如果进行多局对策G的话，局中人I分别选取纯策略α1，…,αm的频率；若只进行一次对策，则反映了局中人I对各纯策略的偏爱程度。编辑ppt因此，局中人I应选取x,使得同理，局中人Ⅱ可保证的所失的期望值至多是下面，讨论矩阵对策在混合策略意义下的解的概念.设两个局中人仍如前所述进行理智的对策。当局中人I选择混合策略x

时，他的预期所得(最不利的情形)是显然，成立v1≤v2.编辑ppt对策论基本定理（或最小最大值定理）设二元对策的支付矩阵是A，则冯.诺依曼证明.编辑ppt定义：设是二元对策G={S1,S2;A},的混合扩充，如果记其值为VG，则称VG为对策G的值。称使上式成立的混合局势（x*,y*）为G在混合策略意义下的解（或平衡局势）.称

x*,y*分别为局中人I，II的最优混合策略.编辑ppt定义：设分别是与中的一个策略，如果对于一切和，成立或则称是的一个鞍点，或称是E的一个鞍点。以下约定，对矩阵对策G及其混合扩充G，一般不加区别，都用G={S1,S2;A}来表示。当G在纯策略意义下的解不存在时，自然认为讨论的是在混合策略意义下的解。编辑ppt

定理二元对策有鞍点的充要条件是成立最小最大值定理与鞍点存在是等价的。是局中人Ⅰ和Ⅱ的最优策略.是对策G的值。定理矩阵对策G在混合策略意义下有解的充要条件是存在鞍点。编辑ppt鞍点含义只要局中人Ⅰ坚守他的最优策略，那么不论局中人Ⅱ选择什么策略，局中人Ⅰ至少能够得到期望支付值只要局中人Ⅱ坚守他的最优策略，则不论局中人Ⅰ选择什么策略，都不能使期望支付超过编辑ppt例

考虑矩阵对策G={S1,S2;A}，其中故设x=(x1,x2)和y=(y1,y2)分别为局中人I和II的混合策略，则局中人I的赢得期望是显然G在纯策略意义下无解，编辑ppt取则即故为局中人I和II的最优策略,对策的值(局中人I的赢得期望值)为编辑ppt§14.2最优策略讨论二元对策解的存在性及其性质，给出算法.一、二元对策的基本定理二、二元对策的解法编辑ppt是二元对策，是G的混合对策.设Ai

是A

的第

i个行向量，Pj是A的第j个列向量,对于S1的任一策略X与S2

的任一策略Y,则局中人I取纯策略αi时的赢得值记为局中人II取纯策略βj时的赢得值记为一、二元对策的基本定理编辑ppt定理1

设v

是对策的值；X*,Y*分别是局中人Ⅰ、Ⅱ的最优策略,①如果对于某个i，有，则②如果对于某个j，有,则定理1说明了，如果已知矩阵对策的值v，并且是局中人Ⅱ的一个最优策略，那么当局中人Ⅰ采用纯策略时，所得的期望支付达不到v，则这个策略是不可取的。从而局中人Ⅰ的任何一个最优策略中一定不会包含这个纯策略。编辑ppt证明我们仅证①.因为Y*是局中人Ⅱ的最优策略,所以令则①如果对于某个i，有，则因此所以成立因为由于所以编辑ppt定理2

设v是对策的值；则①是局中人Ⅰ的最优策略，当且仅当②是局中人Ⅱ的最优策略当且仅当利用定理2,可以检验局中人的某个策略或是否为最优策略。下面讨论二元对策与线性规划的关系，并讨论二元对策最优策略的求法。编辑ppt证明只证①。必要性是显然的，仅证充分性.假设对

j=1，2，…，n成立令是对策的一个鞍点。即对一切和成立。①是局中人Ⅰ的最优策略，当且仅当编辑ppt要证是对策的一个鞍点。由假设知对于任意，则有特别的有又因为是鞍点，由定义可知从而得综合上述结论知所以也是一个鞍点，因此，X*是局中人Ⅰ的一个最优策略。编辑ppt定理3

设,则是对策的鞍点(即对策的解)当且仅当存在数v,使得分别是不等式组的解，并且对策的值等于v.(II)(I)编辑ppt证明由定理3，只需证明对任意支付矩阵A，不等式组（Ⅰ）与（Ⅱ）都有解即可。考虑如下线形规划问题(P)和(D)(D)(P)定理4

任意二元对策都存在鞍点。二元对策的基本定理（主要结果）.问题P与问题D互为对偶的线性规划问题.编辑ppt问题P与问题D互为对偶的线性规划问题，而且是问题P的一个可行解。是问题D的一个可行解。利用对偶理论可知，(P)和(D)都有最优解.设为和，并且即存在使得对一切i

和j，成立

并且可见，求解二元对策只需求解线性规划即可。编辑ppt定义设矩阵对策的支付矩阵是A，A

i是A的第i个行向量，Pj是A的第j个列向量。如果即则称局中人Ⅰ的策略优超于

如果，即则称局中人Ⅱ的策略优超于

若不等号严格成立，则称策略k严格优超于策略l.为简化矩阵对策的计算，引进策略优超的概念。例1

设矩阵对策的支付矩阵是二、二元对策求解编辑ppt例1

设矩阵对策的支付矩阵是可以看出，局中人Ⅰ决不会采取他的第1个策略，这是因为，不论局中人Ⅱ选取什么策略，局中人Ⅰ的第3个策略得到的支付总比第1个策略得到支付大（A3>A1）。因此，局中人Ⅰ的第1策略必定只能以零概率出现在它的最优策略里。这样，将A的第一行画去，得到一新的支付矩阵：编辑ppt从这个新的支付矩阵可以看出，局中人Ⅱ显然不愿采用他的策略1；因为不论局中人Ⅰ采用哪一个策略，局中人Ⅱ的第3个策略的支付都小于第1个策略的支付（P3<P1）。因此，可将上面矩阵的第1列画去，得另一新的支付矩阵：这个支付矩阵B对应的二元对策的最优策略是编辑ppt这个支付矩阵B对应的二元对策的最优策略是再回到相应于A的二元对策，它的最优策略应是相应于对策A与B的对策值都等于0。编辑ppt定理5

设是二元对策，是利用优超关系化简G所得的二元对策，则G的值等于的值；并且的最优策略适当加入0分量可得G的最优策略.

推论若αl

不是为纯策略α1,…,αl-1,αl+1

,…,αm中之一所优超，而是为α1,…,αl-1

,αl+1

,…,αm的某个凸线性组合所优超，定理结论仍然成立。编辑ppt例2

设矩阵对策的支付矩阵是：解由于第3行大于第1行，局中人Ⅰ的第3策略优超于第1策略，画去A的第1行，得：可见，此矩阵的第3列小于第1列,故局中人Ⅱ的第3策略优超于他的第1策略，将其第1列画去得：α1α2α3α4β1β2β3β4α2α3α4β1β2β3β4α2α3α4β2β3β4编辑ppt说明局中人Ⅱ的第2策略被其第3策略与第4策略的凸组合优超，由于因此，将这个3×3矩阵的第1列画去，得：又因此,将这3×2矩阵的第1行画去,得由此得一新的二元对策α2α3α4β2β3β4α2α3α4β3β4β3β4α3α4编辑pptβ3β4α3α4应用定理3，求解不等式组(I)(II)编辑ppt由定理1，首先求解方程组求得(I)(II)β3β4α3α4原二元对策的最优策略为对策的值为编辑ppt二元对策的解法：一、代数解法；

二、图解法；

三、线性规划法；编辑ppt1.代数解法例1求齐王与田忌各自的最优混合策略及博弈的值.解齐王的赢得矩阵

编辑ppt由于它没有鞍点，不存在纯策略解，由定理3可得到两组不等式：编辑ppt这里，每个均大于零，换言之，每个纯策略都可能被局中人选取。由定理1与定理4知，上面2式都应当取等号，将不等式组求解转化成线性方程组求解。将所有式子相加，便得：

由及其，故得。代入其他各式解得编辑ppt齐王的最优策略是；田忌的最优策略是。博弈值。即比赛的双方都很聪明，有理智，总的结果是齐王赢一千金。编辑ppt2.图解法

用平面直角坐标图解的方法来求出双方的最优策略。例2

用图解法求解如下博弈问题。其支付矩阵为解：先考虑局中人Ⅰ：如果局中人Ⅱ取纯策略，则局中人Ⅰ赢得的期望值为如果局中人Ⅱ取纯策略，则局中人Ⅰ赢得的期望值为编辑ppt现以策略和所取概率值和为横坐标，赢得为纵坐标，分别画出局中人Ⅱ取策略和时，局中人Ⅰ所能获得的赢得的变动直线l1和l2。如图编辑ppt这里注意到显然，只有以直线l1和l2的交点M处相应的概率值分别取策略和，才是局中人Ⅰ所选取的最优混合策略，这时，局中人Ⅰ的赢得总是，而不论局中人Ⅱ选择何种混合策略，由图知所以局中人Ⅰ的最优混合策略为编辑ppt当局中人Ⅰ取策略时，局中人Ⅱ损失的期望值为：用同样的方法作图，得局中人Ⅱ的最优混合策略，博弈值。同理，考虑局中人Ⅱ取最优策略的情况，当局中人Ⅰ取策略时，局中人Ⅱ损失的期望值为：编辑ppt3.线性规划解法从定理3的表示形式可以看出，求解矩阵博弈混合策略意义下的纳什均衡问题可以用线性规划方法求解。因为求相当于解

下面2式（1）（2）编辑ppt不妨设，引入新变量（1）化为线性规划（2）化为线性规划（3）（4）这两个线性规划的最优解都存在，而且最优值相等。编辑ppt例3设给定一个矩阵博弈，其中求其最优策略及博弈值。解

此博弈既无鞍点，又不能用优超法简化，可用线性规划求解。求解的线性不等式组为:编辑ppt及编辑ppt故局中人Ⅰ的最优混合策略为所以局中人Ⅱ的最优混合策略为解得

同理，解得

编辑ppt14.3纳什均衡在二人零和博弈中，双方局中人寻求的最优解是一种纳什均衡。当达到这种均衡时，无论是纯策略解还是混合策略解，只要其他局中人不改变自己的策略，则任何一方单独改变自己的策略，只能带来收益或效用的减少。纳什均衡是一种策略组合，它是每个局中人的策略对其他局中人策略的最优反应。下面先给出一个局中人博弈的标准式，然后给出相应的纳什均衡的定义。编辑ppt1.博弈的标准式在有n个局中人的博弈中，设第i个局中人的策略集为.用表示每个局中人选定某一个策略时形成的局势.这里是相应于该局势的第i个局中人的支付函数，则称为博弈的标准式.设有，如果对其他局中人所有可能策略组成的局势均有不等式成立，则称是对的严格劣战略.编辑ppt2.纳什均衡定义在有n个局中人的标准式博弈中，如果局势满足:对每一个局中人是至少不劣于他针对其他n-1个局中人所选策略的最优反应策略，则称局势是该博弈的一个纳什均衡。即对任意的，有或是最优化问题的解.纳什均衡是博弈论中最重要的概念。纳什证明了在任何非合作的有限博弈（指局中人个数有限、每个局中人的策略集中的策略个数有限）中，都存在至少一个纳什均衡。编辑ppt例1设有A,B二人博弈，各自的策略和支付值如表所示。表中的每个数对表示局中人A采用策略时，局中人B采用策略时，局中人A的支付为，局中人B的支付为。求其纳什均衡解。编辑ppt解先判别是否存在劣策略，若有将其删除。判别方法：比较A的第i个和第l个策略,如果有,而且其中至少有一个取“>”号，则称l为劣策略；比较B的第j个和第k个策略，如果有,其中至少有一个取“>”号，则称第k个策略为劣策略.在本例中，是劣策略，将其删除得到

编辑ppt由于纳什均衡是每个局中人策略对其他局中人策略的最优反应,对局中人A：当局中人B采用策略时，局中人A的最优反应是采取策略支付为5，在5下面划横线；当局中人B采用策略时，局中人A的最优反应是采取策略支付为6，在6下面划横线；当局中人B采用策略时，局中人A的最优反应是采取策略.支付为4，在4下面划横线。编辑ppt对局中人B：当局中人A采用策略时，局中人B的最优反应是采取策略，支付为6，在6下面划横线；当局中人A采用策略时，局中人B的最优反应是采取策略，支付为6，在6下面划横线.对支付值都划有横线的组合，即为所求的纳什均衡解.这种解法简称为划线法.由上表可知，本例的纳什均衡解为(4,6)，其对应的策略组合为.该局势是一种平衡局势.编辑ppt在战争史上，不乏以弱胜强的例子。例如在二战中的诺曼底登陆战的谋略策划中，盟军就面临以弱敌强的问题。盟军有两个可以选择的登陆目标地，一是多佛，二是诺曼底。德国守军在人数上超过了盟军，并且就军事进攻而言，在人数相同的情况下，攻方与守方相比会处于不利的情形。下面，将这种情形模型化。假设有一支军队准备进攻一座城市，它有军力两个师；守城军队有三个师。通往城市有甲、乙两条道路或方向。两军相遇时，人数居多的一方取胜，当两方人数相等时，守方获胜。并假定军队只能整师调动。

例2以弱敌强博弈编辑ppt攻方战略：

a.两个师集中沿甲方向进攻；

b.兵分两路，一个师沿甲方向进攻，另一个师沿乙方向进攻；

c.两个师集中沿乙方向进攻。守方战略：

A.三个师集中守甲方向；

B.两个师守甲方向，一个师守乙方向；

C.一个师守甲方向，两个师守乙方向；

D.三个师集中守乙方向。用“+”、“－”分别表示胜和败，攻、守双方布阵结果见下表编辑ppt分析：进攻方无劣战略，但守方有劣战略，A劣于B，D劣于C，故守方不会采用战略A和D，剔除后的博弈变为：编辑ppt攻方知道守方不会选A和D，他由此知道博弈变成如图所示。此时，攻方就有一个劣战略b，他剔除b后得到新的博弈：

此时，两方的形势是相同的，即攻方尽管开始在军力上劣于守方，但实际上它只要运用计谋，其获胜的可能与守方是相同的。编辑ppt攻方战略：

a.两个师集中沿甲方向进攻；

c.两个师集中沿乙方向进攻。守方战略：

B.两个师守甲方向，一个师守乙方向；

C.一个师守甲方向，两个师守乙方向；编辑ppt14.4动态博弈与承诺行动如果局中人在进行行动选择时有先后顺序之分，这种博弈就被称为动态博弈.【例5.14】有两个房地产开发商A和B分别决定在同一地段上开发一栋写字楼。由于市场需求有限，如果他们都开发，则在同一地段会有两栋写字楼，超过了市场对写字楼的需求，难以完全出售，空置房太多导致各自亏损100万.当只有一家开发商在这个地段开发一栋写字楼时，它可以全部售出，赚得利润100万.假定A先决策，B在看见A的决策后再决策是否开发写字楼.在下图中，用“博弈树”表示博弈过程：编辑ppt在上图中每一条“路径”的末端用向量给出A和B的支付，称为支付向量.图1房地产开发博弈编辑ppt下面用“逆向归纳法”可以求解这个博弈.在B进行决策的两个“决策结”上，B在左边的决策结上选择“不开发”；而在右边的决策结上选择“开发”.即给定A开发，B就不开发；给定A不开发，B就开发.B应避免同时与A都选择开发而蒙受损失.在这种情况下，A在自己的决策结上当然选择“开发”，因为他预计当自己选择“开发”后，B会选择“不开发”，自己就净赚一百万.当B威胁A说：“不管你是否开发，我都会在这里开发写字楼.”倘若A将B的话当了真，A就不敢开发，让B单独开发写字楼占便宜.编辑ppt但是，B的威胁是“不可置信”的.当A不理会B的威胁而果断地开发出一栋写字楼时，B其实不会将事前的威胁付诸实施.因为“识时务者为俊杰”，在A已开发的情况下，B的最优决策是“不开发”而不是“开发”.但是，如果B在向A发出威胁的同时又当着A的面与第三者C打赌一定要在该地段上开发出一栋写字楼，否则输给C二百万元.B与C为此签定合同并加以公证有效.这时，博弈变成下图所示的动态博弈.编辑ppt称B的这种行动为“承诺行动”，它使原来不可置信的威胁变为可以置信.图2承诺行动后房地产开发博弈编辑ppt这时，A就不得不相信B一定要开发写字楼的威胁了，于是放弃开发写字楼的计划，让B如愿以偿单独开发写字楼。B不仅未向C支付2百万元，反而净赚1百万.我们可以运用“承诺行动”的原理来分析许多经济及军事现象.编辑ppt例3欧共体为了打破美国波音公司对全球民航业的垄断，曾放弃欧洲传统的自由竞争精神而对与波音公司进行竞争的空中客车公司进行补贴.当双方都未获得政府的补贴时，两个公司都开发新型飞机会因市场饱和而亏损，但若一家公司开发而另一家公司不开发时，则开发的那家公司会获巨额利润.未补贴时的博弈矩阵为下表.此时有两个纳什均衡，即一家开