矩阵博弈的求解

第一章绪论1.1引言 博弈论又称对称论或竞赛论，是一种以数学为基础，研究发生对抗与冲突时如何选择最优策略的一门学问。博弈论是当今经济学和整个社会科学中极为重要的理论学科。简单地说，其精髓是基于理性换位思考下做出明智选择。博弈理论已广泛应用于政治，经济学，军事活动，计算机科学乃至日常生活中。近百年来，数学家以经济学家们奉献了丰硕的研究成果，其中20世纪50年代约翰·福布斯·纳什（Nash）做出了决定性的贡献。他的研究成果：非合作博弈的“纳什均衡”理论，使博弈论发展的迎来了新开端。这一时期博弈论的突出特点是：博弈论的理论和方法被广泛应用于经济学的各个学科中，并成功地解释了不同利益主体在不完全信息条件下如何实现竞争均衡。许多学者对基础理论，数学描述和博弈论的应用关系进行了更深入的研究，使用非线性分析方法系统地研究纳什均衡的存在和性质[1]等等。博弈论研究的是如何找到最合理的行动计划。预测博弈结果是博弈分析的目的，而均衡是博弈的最优结果。纳什均衡是解决决策主体策略对其他决策主体策略的最优反应最佳反应[2]。总言之，纳什均衡解的解决方案无法通过简单的优化获得，仍是博弈论中的主要问题。当前，关于纳什均衡解算法的研究工作正在迅速发展，并且已经提出了诸多算法。如画线法求具体纯策略的纳什均衡，用线性规划方法求混合策略的纳什均衡等。近年来，人工智能中使用了模拟退火算法、禁忌搜索算法、进化算法等等。1.2博弈论的发展简史 从古至今，人类活动中一直并广泛存在着凭借策略决一胜负的竞争性现象，如“齐王田忌赛马”、《孙子兵法》、《三国演义》、塔木德破产分配法以及1500前巴比伦犹太教法典中“婚姻合同问题”等。这些现象都可以找出竞争的双方，抽象到数学上来，就是博弈论问题。竞争的各方各有长短处，在竞争的过程中，各方都想方设法发挥自己的长处，攻击对方的弱点，这样持有个人理性的参与者在博弈中自始至终去赢取自己最大的利益。表1博弈论发展阶段关于决策主体是个人理性的思想最早是由伯努里提出，但最终是被冯诺依曼和摩根斯特恩在1947年证明。冯诺依曼（VonNeumann）创建并证明了博弈论的基本原理，即最小最大定理，该定理用于处理一类二人博弈中最基本的问题。若任何一种博弈都考虑到每个可能的决定所可能造成的最大损失，并且如果您选择“损失”最小的方法作为“最佳”策略，则从统计角度来看，能够确保那是最好的解决方案[2]。与此同时，他与摩根斯恩提出了扩展博弈的定义。1944年，二人将二人博弈结构推广到n人博弈结构，并将博弈论的体系的应用于经济领域，进而奠定了这一学科的基础和该学科的理论体系并介绍了实际应用，这些都记录于二人的著作《博弈论与经济行为》，正是这本著作所涉及的经济理论的基本问题的讨论，导致了对经济行为和某些社会学问题的各种不同研究，如今，它已成为广泛使用且功能日益丰富的数学学科[2]。一些数学家热情称赞它为“20世纪上半叶最伟大的科学贡献之一”，也标志博弈论的第一个研究高潮的结束。美国数学家约翰·福布斯·纳什（JohnForbesNash）的贡献成为博弈论理论研究和发展史上第二个研究阶段最重要的标志。他是电影《美丽心灵》男主角原型，讲述研究生约翰福布斯纳什（JohnForbesNash）提出了著名的博弈论，但纳什的独特直觉受到了精神分裂症的困扰，这使他的辉煌经历变成了最高学历。他发表了三篇关于博弈论的论文，提出了非零和博弈的情况，并将矩阵博弈推广到许多参与者的情况；在合作博弈中，提出了讨价还价模型，也被称为纳什协商解；给出了多人非合作博弈的界定，后来在非合作博弈理论中被称为纳什均衡[3]。在此时期，塔克(Tucker)在1950年建立“囚徒困境”博弈，被作为社会困境的抽象概念。随后，夏普例(Sharply)和吉尼斯(Guinness)提出了“核”概念，这成为合作博弈论等的通用解决方案[3]。博弈论产生理论成果的阶段是20世纪50年代中期至70年代，也是博弈论理论研究和发展史上第三个研究阶段。在1954年至1955年出现的“微分博弈”，奥曼在1959年提出“强均衡”这一概念,在1950年，人们提出重复博弈并出现相关的“民间定理”；谢林介绍了“焦点”均衡的概念，其间最重要的是海萨尼在1967至1968年把非完全信息引入了博弈论的研究内容中，提出了“贝叶斯纳什均衡”概念以及他在1973年给出的非完全信息动态“完全贝叶斯纳什均衡”[3]。七十年代博弈理论发展中最重要的事件还包括“进化博弈论”的研究和重要发展，其中最重要的是梅纳德史密斯在1972年提出了生物学中博弈论的重要解概念，即“进化稳定策略”以及博弈论真正地融入经济学，因为这一时期的经济学家正在推动博弈论发展方面做出来重要的贡献[4]。随后，数学家们进一步促进了博弈论的发展，促使博弈论逐渐成熟。科尔伯格在1982年提出了“顺序归纳法”,克雷菩斯和威尔逊于1982年提出“序贯均衡”,伯恩海姆和皮尔斯在1984年提出了“可理性化性”概念,泽尔腾和海萨尼在1988年提出了非合作博弈与合作博弈的均衡选择的一般性理论和标准，以及弗得伯格和泰勒尔在1992年进一步提出“完美贝叶斯均衡”等概念都表示了博弈论理论研究的最高水平[5]。随后博弈论和经济信息学家莫里斯和维克瑞因在不对称信息条件下关于激励机制的基础性研究,二十一世纪初奥曼和谢林分别在博弈论的“贴切”概念方面、博弈论在经济学的深层研究的重大成果，和博弈论在哲学方面的重要贡献，都被授予了诺贝尔经济学奖，这说明了博弈论与经济学的密切联系，在数学等方面具有非常重要的地位和影响。古往今来，数学家们及经济学家们一直用数学知识研究人在现实生活中的行为，这也正是博弈论能产生的根本原因。博弈论作为一种理论，源于生活指导科学，其哲学思维方式推动人类思维模式向前发展。直至现在博弈论已经形成了一个相当庞大的知识理论体系，其威力将是它在多方面的运用和发展。1.3本文主要内容本文的主要内容是在博弈论的相关基础知识上浅谈纳什均衡，对矩阵博弈加深理解并探讨解法。论文主要工作如下：收集和总结非合作博弈论的参考材料中的内容；解释博弈论的研究过程，基本概念和发展历史；对纳什均衡的提出，相关基本概念进行阐述；对矩阵博弈进行学习并对纳什均衡加深理解；提出矩阵博弈的解法并应用于生活。第二章预备知识博弈论的复杂现象抽象逐步引入对其局势产生影响的其它因素再综合分析，确定计算方法特有的数学模型博弈论的复杂现象抽象逐步引入对其局势产生影响的其它因素再综合分析，确定计算方法特有的数学模型基本的元素预测结果分析构成图1博弈论研究过程诸多日常生活现象涉及到博弈论的知识，我们理应学会通过现象看本质。将博弈所需的基本元素从复杂的博弈现象中抽象出来，判断博弈类型，构建相应的数学模型，逐步引入对其局势产生影响的其它因素，再进行综合分析。综合分析的目的就是揭示事物的机理，发现其本质性地规律，从而找到解决问题的方法。在分析后，进行观察、归纳、确认，最终解决问题。2.2博弈论的基本概念基本假设：博弈论中不仅要求每个参与者都是理性的，并且彼此也都知道对方是理性的。理性指博弈参与者选择一种策略以获得最大化利润。假定参与者应该并且可以充分考虑人们的行为与其潜在影响之间的相互作用，并能够做出理性的选择。要素：简而言之，以下要素可构建一个完整的博弈论模型：表2博弈的七个要素决策主体策略赢得函数一个博弈中有权决定自己行动方案的博弈参加者为决策主体，通常用表示决策主体的集合。如果有个决策主体，则一般要求一个博弈中至少要有两个决策主体。博弈中，可供决策主体选择的一个实际可行的完整可行的完整的行动方案称为一个策略。参加博弈的每一决策主体，都有自己的决策集。一般，每一决策主体的策略集中至少应包括两个策略。一个博弈中，每一决策主体所出策略形成的策略组称为一个局势，即若是第个局中的一个决策，则个决策主体的策略形成的策略组就是一个局势。若记为全局行为：参与人在博弈的某个时点的决策变量，与行动相关的一个重要问题时行动的顺序，行动顺序往往决定博弈的结果。博弈的顺序，是指博弈参加者做出策略选择的先后。信息：参与人有关博弈的知识。即博弈者所掌握的对选择策略有帮助的情报资料。结果：博弈分析者所感兴趣的所有东西，如均衡战略组合、均衡行动组合、均衡支付组合等。均衡：所有参与人的最优战略组合。一般情况，博弈论模型由3个基本要素组成：一是决策主体、二是策略、三是赢得函数，而行动和信息是博弈的“积木”，参与人、行动和结果称为“博弈规则”，博弈胜负的评判结果主要是靠策略选择后的得失来衡量[6]。表述模型：表3博弈论三种表示模型标准式适合表示二人，三人博弈的列表形式扩展式可表示多人博弈（动态多人博弈）的博弈树形式特征函数式出现在合作博弈的一般表示中在非合作博弈中一般用标准式和扩展式，由博弈中决策主体的数量多少来决定；在合作博弈中一般用的是特征函数式。博弈论的分类：完全理性完全理性有限理性重复博弈博弈论合作博弈非合作博弈协议信息完全信息博弈完全信息静态博弈完全信息博弈不完全信息静态博弈不完全信息博弈不完全信息动态博弈静态博弈动态博弈顺序零和博弈非零和博弈结盟博弈不结盟博弈理性图2博弈论的分类由上图可以看出，这些分类并没有相连的的层次关系，但不同属性和特征的博弈论是由最初最基本的博弈论所展开的。在不同情景下会生成与之概念、性质相反的博弈论。譬如：合作博弈与非合作博弈、完全信息博弈与非完全信息博弈等等。不过，随着对博弈论问题的深入研究，理论和性质的不断发展，其所形成的表现形式也会有所不同，这样会更加方便的去解决一些问题，将复杂问题简单化。2.3纳什均衡的定义纳什均衡是一种特殊的平衡状态，表明了每个决策主体都不会主动采取行动偏离此状态，采取任何偏离此状态的行动都会带来损失。纳什均衡是完全信息静态博弈解的一般概念，换言之，博弈论就是建立在纳什均衡理论的基础之上。纳什均衡是所有决策主体的最优策略组成集合，即给定的情况下，决策主体所寻求的最优解是一种均衡解，整体达到均衡状态时，没有任何决策主体会选择其他策略，从而没有任何决策主体会打破这种均衡。在给出纳什均衡的定义前先给出下述博弈的标准表达式：在有个决策主体的博弈中，设各决策主体的策略空间分别为用表示每个决策主体选定某一策略时形成的局势，这里是相应于该局势的第个决策主体的赢得函数，可简写成，则称为博弈的标准式。设有和，如果对其他决策主体所有可能策略组成的局势均有，称是对的严格优策略。基于上述，纳什均衡的定义如下：在有个决策主体的标准式博弈中，如果局势满足对每一个决策主体，是至少不劣于它针对于其他各决策主体所选策略的最优反应策略，则称局势为该博弈的一个纳什均衡[6]。即有或是以下优化问题的解：纳什证明了在任何非合作的有限博弈（决策主体以及每个决策主体的策略空间均为有限）中，都存在至少一个纳什均衡[6]。第三章矩阵博弈矩阵博弈是博弈论的最基本内容，它是整个博弈论的基础，也是迄今研究比较成熟、成果比较卓著的博弈。近代博弈论的研究，其结果再深入，理论再抽象，都无法离开矩阵博弈者这个“第一道大门”。矩阵博弈也称为非合作二人有限零和博弈。“二人”指的是参与其中的决策主体数为二；“有限”是指每个决策主体的策略集均为有限集；“零和”是指任一局势下，两个决策主体的赢得之和总为零，即一个决策主体的所得值就等于另一决策主体所失值，双方的利益是完全对抗的[7]。3.1零和博弈的纯策略纳什均衡二人零和博弈的纯策略：纯策略：在完全信息博弈中，决策主体在任一局势下只能选取唯一确定的策略。矩阵博弈的定义：一般情况下，用和分别表示两个决策主体，设决策主体有个策略；决策主体有个策略。用表示决策主体的策略集，用表示决策主体的策略集，即。当决策主体选定纯策略，决策主体选定纯策略后，就形成了一个纯局势。显然，这样的纯局势一共有个，对于纯局势，即决策主体赢得为，即决策主体在每个纯局势的赢得构成了一个矩阵：称矩阵为决策主体的收益矩阵，（或决策主体的收益矩阵）。由于矩阵博弈为二人零和博弈，故决策主体的收益矩阵为。当决策主体、和策略集，以及决策主体的收益矩阵确定后，一个矩阵博弈就确定了;通常将矩阵博弈记为或简记为;这就是矩阵博弈的基本表示[7]。现在关心的是在二人零和博弈中的各决策主体应该如何选择自己的策略，使自己在博弈中获得最好的收益。下面用一个例子来分析各决策主体如何选择最有利于自己策略：例1设零和博弈，其中，决策主体的收益矩阵如下：由A可知，决策主体的最大收益是6，想要赢得此收益，就得选择纯策略。决策主体自会考虑到决策主体会出的心理，便将以对付，则决策主体不仅得不到6，还会有所损失。决策主体也会猜测决策主体的心理，故以纯策略对付，使得决策主体得不到7，反而失去1。双方都不愿冒险，彼此都希望对方有所损失或收益最小，则会从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据，称为“理性的行为”。例中，决策主体在各种纯策略下可能得到的最小收益为-7、1、-3，其中最好的结果是1.因此，无论决策主体选择怎样的纯策略，决策主体只要以参加博弈，可保证收益不少于1，而出其它纯策略，都可能使其收益少于1甚至输给对方。同理，决策主体在各种纯策略下可能得到的最不利的结果6,1，2，其中最好的结果也是1。因此，无论决策主体选择怎样的纯策略，决策主体只要选择，可保证损失不超过1，而出其它纯策略，都可能使其损失超过1甚至输给对方。上述分析表明：决策主体、的“理性行为”分别是选择纯策略和。这时，决策主体的收益值和决策主体的所失值的绝对值相等，决策主体得到其预期的最少收益2，而决策主体也不会给决策主体带来更多的收益，相互竞争的双方使博弈出现平衡局势,即纯策略纳什均衡，也称鞍点，并且此博弈的值为1。这个局势对双方都是一个最稳妥的结果。因此和分别是决策主体和决策主体的最优纯策略，也称为鞍点元素。对上述矩阵博弈讲述一个道理：做最坏的打算，争取最好的结果。我们将用数学语言来表达，如下：最小最大定理：零和博弈在纯策略意义下有纳什均衡的充分必要条件是：存在策略组合使得或应用最小最大定理解下列例题：例2俾斯麦海之战：1948年第二次世界大战中的日本处于明显的劣势，为扭转战局，日军海军受命运输一支部队由集结地拉包尔穿过俾斯麦海去莱城支援被困的日军。当盟军统帅接收到情报后，进行空军打击。自然条件对于双方来说是已知的，由拉包尔到莱城有南北线，且通过时间都为三天，北线阴雨能见度低，南线晴朗能见度佳。表4俾斯麦海之战盟军和日军的收益矩阵日军收益盟军北线南线北线2，-22，-2南线1，-13，-3表中正数为盟军轰炸日军的天数，负数的绝对值为日军被盟军轰炸的天数。盟军合理选择侦察机重点搜索方向，而日军合理选择日本舰队路线。观察表4盟军和日军都没有严格占优策略，由于在各种局势下双方收益为零，表4可简化为如下：表5俾斯麦海之战盟军的收益矩阵日军收益盟军北线南线北线22南线13盟军需选择获利最多的策略为最优策略，日军需考虑损失最少的策略为最优策略。因此盟军：日军：即两者相等，由最小最大定理知：此博弈的纯策略纳什均衡为（北线，北线）。例3以弱敌强博弈假设红军两个师的兵力攻一座城，由地理环境的因素只能通过南北两方向进攻，对此蓝军以三个师的兵力防守南北方向。设两军相遇时人数居多的一方获胜，当两方兵力相等时防守方获胜，且假设军队只能整师调动。策略如表6所示：表6红蓝军的进攻策略红军（攻方）蓝军（守方）A1：两个师集中沿北方向进攻B1：三师守北方向A2：一师沿北方向进攻；另一师沿南方向进攻B2：两师守北方向；一师守南方向B3：两师守南方向；一师守北方向A3：两个师集中沿南方向进攻B4：三师守南方向若用1和-1分别表示胜和败，则攻、守双方布阵的所有可能结果如表7所示：表7以弱敌强博弈的收益矩阵蓝军收益红军B1B2B3B4A1-1,1-1,11,-11,-1A21,-1-1,1-1,11,-1A31,11,-1-1,1-1,1由上述表7可知，这是一个二人零和博弈。那么，该模型可以简化成表8：表8以弱敌强博弈中红军的收益矩阵1蓝军收益红军B1B2B3B4A1-1-111A21-1-11A311-1-1红军争取收益最大，则蓝军争取损失最小，则我们发现，由最小最大定理知，此博弈不存在纯策略纳什均衡。但是由于蓝军争取损失最小，所以蓝军不会选择策略B1和策略B4,由于红军争取收益最大，所以红军不会选择策略A2。即表9可表示为：表9以弱敌强博弈中红军的收益矩阵2蓝军收益红军B2B3A1-11A31-1综上，红军可选择纯策略A1与A3，蓝军可选择纯策略B2与B3。两方的形式是相同的，即红军尽管开始在军力上弱于蓝军，但实际上其获得的可能与攻守方式相同，这就给军事谋略的运用留下了发挥的空间。3.2零和博弈的混合策略纳什均衡由上小节以弱敌强博弈中无纳什均衡，红蓝军如何在博弈中选择纯策略呢？我们可设X为红军选择纯策略A1的概率，则1-X为选择纯策略A3的概率。蓝军Y为选择纯策略B2的概率，则1-Y为选择纯策略B3的概率。由上表表5可计算出红军的期望为：从而蓝军的期望为。故红军以的概率选择纯策略A1，以的概率选择纯策略A3，其期望值为零。蓝军以的概率选择纯策略B1，以的概率选择纯策略B3，可以控制红军的收益不超过零。综上，不是决定用哪个纯策略，而是决定用多大的概率选择出最优纯策略，从而提出混合策略纳什均衡。混合策略：设零和博弈其中是决策主体的策略集，是决策主体的策略集，决策主体的收益矩阵假设分别是决策主体选取的概率，其中；分别是决策主体选取的概率，其中，从而记是决策主体的混合策略，是决策主体的混合策略，称为混合局势，决策主体的期望收益为决策主体的期望收益为混合扩充与最优混合策略：设零和博弈，决策主体的所有混合策略构成的集合,决策主体的所有混合策略构成的集合，以及与期望收益构成的组合称为博弈的混合扩充。决策主体以混合概率选取策略时，希望找到一个最大的数，对决策主体的每一种混合策略，都有，则称为决策主体的最优混合策略。同理决策主体满足：，则称是决策主体的最优混合策略。混合策略意义下的纳什均衡：在任何一个给定的二人零和博弈中，分别存在决策主体和决策主体的最优策略和，满足与，且，其中是决策主体在均衡下的期望收益，也就是博弈的值。混合局势是在混合策略意义下的一个纳什均衡。应用例4设零和博弈，其中，，决策主体的收益矩阵判断该博弈是否存在纯策略意义下的纳什均衡；如果不存在，求出该博弈在混合策略意义下的一个纳什均衡，并给出该博弈的值：解：显然，由最小最大定理，不存在鞍点，该博弈不存在纯策略意义下的纳什均衡。设决策主体选择纯策略A1的概率为X，则选择纯策略A2的概率为1-X。决策主体选择纯策略B1的概率为Y，则选择纯策略B2的概率为1-Y。故对于决策主体的期望为：当时，即分别以概率和选取纯策略A1和A2时，至少保证决策主体的收益为4.故对于决策主体的期望为：当时，即分别以概率和选取纯策略B1和B2时，其损失至多为-4。综上，决策主体的最优混合策略为；决策主体的最优混合策略为；混合策略意义下的纳什均衡为，该博弈的值.第四章矩阵博弈的求解下面介绍求解矩阵博弈的几种解法，比如常用的划线法，线性方程组方法，线性规划方法，避大不利法等.4.1划线法根据纳什均衡解的特性，可通过例子说明如何通过划线法求纳什均衡的解。例5囚徒困境[6]：希望因同一桩罪被捕的两名嫌疑犯坦白并提供对方的犯罪证据，规定两人均坦白各判3年；若一方坦白，另一方不坦白，坦白一方释放，不坦白一方判8年；若均不坦白，各判一年。其博弈的表达式如下： 表10囚徒困境博弈的表达式乙收益甲坦白不坦白坦白（-3，-3）（0，-8）不坦白（-8,0）（-1，-1）因纳什均衡是解决决策主体策略对其他决策主体策略的最优反应。当乙坦白时，甲的最优反应是坦白，其收益为-3并下画横线；相对乙不坦白，甲的最优反应仍是坦白，收益为0并下画横线。当甲坦白时，乙的最优反应是坦白，其收益为-3并下画横线；当甲不坦白时，乙的最优反应仍是坦白，收益为0并下画横线。由此得表11所示结果，表中双方坦白时的收益向量数字下均画了横线，则横线组合（-3，-3），即为所求纳什均衡解。从表11得两名囚徒的最好结局（-1，-1），即双方均不坦白。因为无论对甲或乙，坦白是相对于不坦白的优势策略。表11划线法下的囚徒困境博弈的表达式乙收益甲坦白不坦白坦白（-3，-3）（0，-8）不坦白（-8,0）（-1，-1）上述例子表明：纳什均衡解虽不一定是最有利的结局，但在其他各方策略不变时，任何一方单独改变策略智慧对自己带来不利，因而建立在纳什均衡基础上的规则协议，是博弈各方都能自觉遵守的。4.2线性方程组法定理1：记及分别为决策主体和决策主体取纯策略时赢得值。设,则为任一个矩阵博弈，的解的充要条件是：存在数，使得和分别是不等式组（1）和（2）的解，且.由上述定理，求矩阵博弈解的问题等价于求解不等式组（1）和（2）、若最优策略中的和均不为零，则可将上述求解问题转化为下面的两个方程组的求解问题：若方程组（3）和方程组（4）存在非负解和，便求得了一个博弈解。若这两个方程组不存在非负解，则可视具体情况，将方程组（3）和方程组（4）的某些等式改为不等式，继续试求解，直到求得博弈解。此方法由于先假定和均不为零，故当最优策略的某些分量实际为零时，方程组（3）和方程组（4）可能无解[7]。因此，此方法在实际应用中有一定的局限性，本质上是一种枚举法。田忌的马上、中、下三个等级齐王的马上、中、下三个等级从各自的的马各选一匹参赛，每匹马只能参赛一次；已知在同等级马中，田忌的马都不如齐王的马，而如果田忌的马要比齐王的马高一等级，则田忌的马取胜，可得一千两。齐王先出田忌的马上、中、下三个等级齐王的马上、中、下三个等级从各自的的马各选一匹参赛，每匹马只能参赛一次；已知在同等级马中，田忌的马都不如齐王的马，而如果田忌的马要比齐王的马高一等级，则田忌的马取胜，可得一千两。齐王先出最终田忌二胜负一，夺得千金。齐王上中下田忌下上中图3田忌赛马上述情景中，仅有田忌运用策略,而齐王没有运用策略与之抗衡。若齐王察觉田忌使用计谋,他将会做出相应举措,从而使两者的赛马变成一场决策较量。两名决策主体各有六个策略,在任一局势下,齐王的所得必为田忌的所失,反之亦然。表12齐王田忌赛马田忌收益齐王上中下上下中中上下中下上下上中下中上上中下3，-31，-11，-11，-1-1,11，-1上下中1，-13，-31，-11，-11，-1-1,1中上下1，-1-1,13，-31，-11，-11，-1中下上-1,11，-11，-13，-31，-11，-1下上中1，-11，-11，-1-1,13，-31，-1下中上1，-11，-1-1,11，-11，-13，-3解：由上述已知田忌赛马问题的收益矩阵：显然该博弈没有鞍点。因为中有很多1，所以把中的每个元素都减去1，然后再乘以，得到转而讨论以为收益矩阵的博弈的解。为此先解方程组由上面两个式子解得：得到博弈的解的一个解：因此原博弈的值:齐王的最优策略为田忌的最优策略为：齐王与田忌都以的均等概率选取每个纯策略，则结果是齐王胜出。图3指出：田忌胜出是因为田忌在得知齐王的出马次序(上，中，下)后才给出相应出马次序(下，上，中)。这表明，如果博弈中没有鞍点，则竞争双方必须在开始之前对自己的策略保密，否则无担保的一方将遭受损失。4.3线性规划法线性规划的数学理论已成熟，其解决方案统一而简单，即众所周知的单纯形法，其基本思想是从满足所有约束条件的一个基本可行解(即从可行域的一个顶点)出发，经基变换转换到另一个基本可行解，是目标函数值不断增大直至达到一个最大值点，从而得到问题的最优解[6]。数学模型的一般形式为:由此，齐王与田忌赛马表达成一个博弈问题如下:表13田忌赛马所表达的博弈问题（1）该博弈中有齐王和田忌两个决策主体；（2）因三匹马的排列次序共有3!=6种,则双方各有6种可选择的策略。（3）双方都不能先知道彼此的决策,因可看作是同时选择策略是没有先后次序；（4）把赢得一千两记成收益1,输1千两记成收益-1,则两方在各种策略的组合收益,如表3中数组的元素所示,每个数组表示两参与者在相应行和列中各自的收益,其中前者表齐王的收益,后者表田忌的收益。田忌赛马中的收益矩阵：求解方法为:先把收益矩阵A的每个元素都加1,得到每个元素都是正数的收益矩

阵转而讨论以为收益矩阵的矩阵博弈,为此求解两个互为对偶的线性规划问题.上述线性规划可用MATLAB求解：>>f1=[111111]’;a1=[-4-2-20-2-2;-2-40-2-2-2;-2-2-4-20-2;-2-2-2-4-20;-20-2-2-4-2;-20-2-2-2-4];b1=[-1-1-1-1-1-1]’;b=[000000];[x,fval,exitflag]=linprog(f1,a1,b1,[],[],b)从而最优解为,最优值为。对于博弈的值且博弈的解为再考虑同理可用MATLAB求解,从而得到的最优解为,最优值为。对于原博弈的值且原博弈的解为因此，是原博弈的解并且值为1。田忌赛马中齐王和田忌选择各个策略的概率为，结果是齐王胜过田忌赢得一千两。4.4矩阵博弈的新解法--避大不利法上文例1及例2中都存在鞍点，可用最小最大法等方法求解矩阵博弈的纯策略解；例3与例4中的鞍点都不存在，则该矩阵博弈无纯策略解，但可求出混合策略解。而混合策略解表示：决策主体会根据不同纯策略的概率分布做出最优策略，若在决策主体都无法得知彼此选择某种纯策略的几率的情况下，则决策主体难以根据混合策略的解做出确切决定[9]，这说明混合策略解法在某种情况下存在局限性。为解决无鞍点的矩阵博弈的求解问题，弥补混合策略解法的缺陷，以及提高解法实际意义，我们提出避大不利法。该方法的原则：根据对自己的不利程度，决策主体逐一避开可能对自己带来不利的纯策略，直到仅剩下一个策略，则为决策主体最终所选取的纯策略[10]。若最大或最小的元素在若干行或若干列中同时出现(如下例有短线的数字)，则比较这些列或行中下一个最大或最小的元素，若还相等，则比较再次之的元素，若最大或最小的元素在若干行或若干列中同时出现(如下例有短线的数字)，则比较这些列或行中下一个最大或最小的元素，若还相等，则比较再次之的元素，直到能比较出大小即可，再重复步骤(2)(3)；在A中寻找最大元素，用max标出并且划去该列；接着在剩下的各列中寻最大元素用max标出并且划去该列，重复进行，直到剩下一列元素；写收益矩阵A；在A中寻找最小元素，用min标出并且划去该行；接着在剩下的各行中寻最小元素用min标出并且划去该行，依次进行，直到剩下唯一的元素；若对某些特殊的收益矩阵，通过上述步骤可能找不到解，就意味着对于决策主体来说，按此方法每个纯策略的不利程度是一致的，即取任意一行或列都是可行的，实际上这种情形的n阶矩阵博弈用混合策略解法求解，可求出混合策略解均为，也不具备很大的实际指导意义。最后必剩一元素，用星号标记数字，所在行右方也没有字母标记，则此元素的值为博弈的值，此元素对应的决策主体双方的纯策略就是博弈的解；图4避大不利法的具体步骤例7：设有矩阵博弈，其中则可以按照上述步骤求解过程如下：表14例7的具体步骤（1）在A中找到最大的元素8用max在下方标记并划去该列；（2）在A中剩下的元素中找到最大的元素7用max在下方标记并划去该列；（3）在A中剩下的元素中找到最大的元素5，但是发现5都出现在这剩下两列中用短线在下方标记，再找剩下元素中次大的元素4用max在下方标记并划去该列，这时只剩下最后一列；（4）继以上步骤，在A中找到最小的元素-1用min在下方标记并划去该行；（5）在A中剩下的元素中找到最小的元素0用min在下方标记并划去该行；（6）在A中剩下的元素中找到最小的元素5，但是发现5都出现在这剩下两行中用短线在下方标记，再找剩下元素中次小的元素6用min在下方标记并划去该行；（7）此时只剩下一个元素5，位于并用星号标记。因此，博弈，博弈的解为，是决策主体双方可以接受的选择。在上述矩阵博弈反映了策略主体的得失情况，同时按照步骤得到的纯策略是决策主体双方可以接受的选择，也是在该原则下最优策略。总结：实际上，避大不利法要求决策主体按照对自身的不利程度，尽可能地舍弃对自己不利的策略后逐步保留对自己较为有利的策略[11]；而最大最小法要求明确每种策略将带来的最大损失，紧接着在其中找出最小损失的策略。在各自这种情况下，若决策主体双方的得失的价值相等，则此值为博弈的解，对应的纯策略是决策主体双方的最优纯策略，若不相等则不存在纯策略解[12]。两种方法虽建立在悲观准则的基础之上，但显然的是当存在鞍点时，两种方法得到的答案是一致的；当不存在鞍点时，前者的解决方案不仅正确简单而且更具有实际指导意义。可知避大不利法是对原有解法的延伸和补充，它可解决鞍点不存在的矩阵博弈问题，并其解具有直接指导决策的满意纯策略解。结论众所周知博弈论经过半个多世纪的发展，已对我们研究生活中很多实际问题都有举足轻重的作用。本文介绍了博弈论的相关基础知识以及非合作博弈下的纳什均衡。博弈论是将日常生活中、经济学中等一系列的实际问题做出一个相对均衡合理的策略所引出的一个概念。简而言之，预测博弈结果是博弈分析的目的，而均衡是博弈的最优结果。纳什均衡是所有决策主体的最优策略组成集合，即给定的情况下，决策主体所寻求的最优解是一种均衡解，整体达到均衡状态时，没有任何决策主体会选择其他策略，从而没有任何决策主体会打破这种均衡。但是每位决策主体选择的策略本