学习资料：博弈论导论.pdf

目 录IB目 录*序言.IChi绪言.11.1 博弈的定义.11.2 博弈论发展简史.7Ch2 von Neumann 经典理论.,.102.1 矩阵博弈.1022 Minimax 定理.172.3 矩阵博弈求解.322.4 无限博弈.40Ch3 Nash 均衡.483.1 Nash均衡的定义.48 3.2两人一般和有限博弈的Nash均衡.513.3 Cournot 模型.593.4 Nash均衡的存在性.633.5 均衡的近似计算.77Ch4合作博弈.974.1 Nash的讨论还价模型.974.2 联盟博弈与核心.1084.3 Shapley 值.129Ch5 Nash均衡的引伸与其它.1445.1 完全信息动态博弈与子博弈完美Nash均衡.1445.2 不完全信息静态博弈与BayesnNash均衡.1575.3 不完全信息动态博弈与完美BaygNash均衡.1685.4 对均衡与博弈论发展的议论.185参考文献.193重要词汇英汉时照.194Chi绪言UI绪言WWW住 ww*Game Theory,是研究竞争条件下决策分析的科学。它研究的典型问题是若干个利 益冲突者在同一环境中进行决策以求自己的利益得到满足。例如,不同企业在同一市场 上为销售相同的产品而形成的竞争;不同国家在同一问题上不同政治立场所引起的外交 纷争乃至军事冲突;游戏中各方为获胜而采取的行为组成的格局都是Game Theory 要研究的。下面我们介绍Game Theory的最基本概念博弈的定义以及博弈论发展的 简史。1.1 博弈的定义Game的译名是博弈，博弈即下棋。但在博弈论中所言的博弈远不止是下棋。举凡 有竞争行为的局面都是博弈.博弈问题有五个要素:局中人,局中人的可行方案集，局中人决策的先后顺序,局中人 的收益函数,信息。所谓局中人，是指在问题中为自己的利益进行决策的各方。它可以是人、法人或机 构。可行方案集是局中人可以采取的行为方案的全体在博弈问题中，局中人在其可行 方案上的选择，便是决策分析。许多学者把Game Theory称为对策论,就是由于在对抗冲 突的条件下进行决策分析。决策先后顺序是实际问题动态性质的反映，任何一种博弈的规则都要明确各个局中 人进行决策分析的时间先后。如果各个局中人是同时进行决策,问题便是静态博弈。还 有一种情形也是静态博弈，那就是不同局中人决策时间有先后顺序，但后决策的局中人并 不知道前于其决策的局中人究竟选择了什么行为方案。除开上述两种情形，问题都是动 态博弈。收益函数是博弈最后结果中各个局中人利益的表示收益的内涵因博弈问题而异,在市场竞争博弈中，它可以是各企业的销售量、销售额、市场占有率、利润额等。在军事战 争中它可以是有生力量被消灭的数量。在游戏中它可以是局中人所得分数。在许多问题 2博弈论导怆中,效用函数起着收益的作用。在博弈决策分析中，局中人把收益当作目标函数,通常力 求使其极大化但在有的问题中则是使收益极小化，例如上面提到的军事战争中各方力 求有生力量损失尽可能少。在问题中出现不确定性的，收益通常是估值，比方说行为结果 的数学期望。信息,指的是局中人在决策时对其条件的知识。信息包括两类，一类是有哪些局中 人，他们的可行方案集是什么，所有局中人的收益函数是怎样的这些知识;另一类是局中 人决策之前已作过的决策的结果。在博弈中，如果所有局中人对前一类信息有确切的了 解，就称之为完全信息的博弈，否则称之为不完全信息的博弈6而在博弈中如果所有局中 人对后一类信息有确切的了解，就称之为完美信息的博弈，否则称之为不完美信息的博 弈。为了给出博弈的形式化定义，还需对偏好关系、理性选择加以界定C设C为某类事件所有可能结果的集合。如果存在C上的二元关系R,满足以下三个 条件：1.完备性c即对任何工，7 C,关系xRy或jyRz至少有一个成立；2.自反性c即对任何工ec.关系足选总成立；3.可传递性。即对任何8,3,zWC,如果的 与加N都成立，则及必成立。则称R为C上的弱序（weak order）。如果对所有z q E C,关系工Ky意味着认为“结果x 不比结果3差二则称弱序R为C上的偏好关系，并记作如果对于偏好关系，恰巧有局中人对C中结果的看好程度的比较结果与之相合，即对 所有ayC有C该局中人认为工不差于y,则称此为该局中人的偏好序O在决策论中证明了,在一定条件下存在效用函数“（）,满足/工）裳以（了），中工3yse称二元组C,为一个偏好结构，其中C是结果集,是C上的偏好序。称四元组r-ACg,A）为一个理性选择结构，其中A是可行方案集，C是可能结果集，g：Af C是可行方案集到可能结果集的映射，是。上的偏好关系，Chi绪言3如果决策者有理性选择结构，并且在决策分析中通过最优化来审慎地选择自己的行为方 案，则称此决策者是理性的。在博弈分析中，我们假定所有局中人都是理性的决策者,即要求他们都通过最优化来 进行决策。定义1称三元组G=N,（Xf）,（Pj）为策略博弈（strategic game），或正规博弈（normal game）,其中N台 1,2,，力为局中人集，共九个局中人，（出）。1/2./3及是局中人；的可行方案集,，=12“，（丹）（P-P2,P3p是局中人，的收益函数，比较具体地马（叫，孙，.）是在行为组合（可，央，公）之下局中人i的收益值，为6苟,j=1,。而局中人在博弈中理性化的表现是使H,极大化。又称行为组合（定i,i2,，马）为对策局势,且记局中人集N的人数为INI,即令|N|二 n 例1甲，乙两球队对赛，甲队有加个不同的出场名单，乙队有笈个不同的出场名 单,球赛结果以（Q）来表示，q 相应为甲队、乙队所得分。这是一个策略博弈G,其组 件分别为N与甲，乙1（K）=（x甲，x乙），x甲=为甲队不同出场名单，乂乙%,X为乙队不同出场名单。（PJ=（尸甲，尸乙），尸甲=Q（q,期），乙=（石，才），（不，为）是对策局势。例2其他情况同上，只是甲、乙的收益用甲队所得分与乙队所得分之差表示，比较 确切地说，甲队收益此差，乙队收益此差的负值。这是与例1同一个策略博弈，只是 组件不同而已。此时两个局中人的收益和恒等于0。例3企业在市场上销售某种产品，市场情况有不确定性，可能前景有畅销，一般，滞销三种,而企业有两个不同的销售方案A,BO估计销售所获利益依次为4博弈论导论以：述2，G3，试问企业应如何决策？这是一个风险决策问题，也是一个策略博弈问题,其组件n|企业),|N|=1(Xj)=X=A SB(PJ=P,P的定义是Zi，畅销P(A)=v a2l 一般E3，滞销畅销P(B)=*2，一般U3,滞销一般地说,单人不确定决策问题皆可视为局中人只有1个的策略博弈。竞争决策分析问题的情况很是多样，用策略博弈这种形式来模型化往往不一定方便,于是又引出了扩展博弈(extensive即me)的定义定义2称六元组为扩展博弈，其中N是局中人集，H是时间过程中各局中人的决策结果形成的记录序列的集合。比较细致地说,H具有以下三个性质：L规定空序列2.对于任一正整数优或m=+8,如果决策记录序列I e h,则对一切正整数2僧，必有这表明，历史的截段也是历史，3.如果对于无限长的决策记录1114=1,2.-而言，任一长为m的截段(J!k=e H,chi绪言5则必有I/1 艮=12 Ho称H的每一元素即决策记录为历史，而称H为历史集，又称如此的历史I/4=I,t为终极历史，其中初=+8,或切有这样的特点即不存在使得I I 4=1,筋+1 e Ho历史的特点是其作为序列，每一项都是局中人的决策结果。P为局中人函数,尸（五）在历史h之后进行决策的局中人。F是概率分布族。FQ 6）2在历史人之后可行方案以被取作行为方案的概 率当博弈中出现不确定性时，用F来描述（L）=（h,，L）,匕是对于集合的剖分，满足:若阳”2是此剖分的同一子集的元素，则4&。=4（幻）4（万）是局 中人i在五之后决策的结果，即i在人之后取定的可行方案。称的每个子集为局 中人：的一个信息集.据上面所言,局中人f在决策时对同一信息集的不同历史是 不加区别的，即对同一信息集历史的决策点是不加区别的。=1,，非。（U。=（1，4）,见是局中人在H上的效用函数,1=1,，a与定义1对照，定义2显得冗长，但是用它来描述动态博弈、不完全信息博弈却比较 方便，这是因为在定义2的组件中，局中人函数P反映了博弈的决策顺序,L则与信息有 密切的关系。对于扩展博弈，如果把局中人的决策处当作结点，把可行方案当作连接结点的有向 弧，便得到树，称此树为博弈树，它是博弈特别是扩展博弈的几何表示，但当可能有无限长 历史以及局中人的可行方案集可能含无限多个元素时,博弈树大多不能完全描出。然而 对于有限规模问题，即历史长度有限且可行方案集有限的博弈,博弈树作为几何表示，以 其直观性有助于进行博弈问题的分析。例4两人挪银币,局中人1先掷,局中人2后掷，但是2在掷时并不知道1的结果。假设两个局中人掷出正面在上的概率都是寺，并且两人掷出的结果相互独立q规定，如果 结果是两人掷出的面相同，则局中人1支付给局中人2以1元,反之则局中人2支付给局 中人1以1元。这是一个动态的问题，但由于局中人2不知道局中人1掷出在上的是哪一面，而成为 6博弈论导论不完美信息的博弈，客观上还是静态博弈。博弈树如图1所示。图L1在博弈树中，所有非终极结点用圈表示,圈中的数字是在此结点决策的局中人,非终极结 点又称为状态，有向弧表示矢初状态处决策所选取的一个可行方案。此例的终极结点一 共4个，用括弧表示，其中两个数字依次表示局中人1,2的终极所获。在这个博弈中，六个组件依次是：H=|正正，正反，反正，反反|产是L h=iP（h）=2,力=|正2%二|反|F是F（正M）=F（负|内）=/，F（正|正）=F（负|正FCEI 负）=F（负|负）=*,是h=612=1正，负，它不再被剖分，因此局中人2只有一个信息集，由树中标明2 的两个状态组成，亦即局中人2在决策时对此两结点是不加区别的0（5）是收益值，如图L1树中所示。例5房地产商1与2先后来到某地考察，决定是否开发。1先决定并付诸行动，遇 Chi绪言7到的需求可能较大，也可能较小c 2决策时并未了解需求情况就作出了选择。两个地产 商在此地开发各种情况下的最终收益估计值列于图L2树中终极结点处的括弧内。图L2在图L2博弈树中列出了上述问题的多方面信息。这是一个动态博弈:局中人集=10,1,21,0是市场需求，为虚拟的局中人，而1,2是房地产商.为真实的局中人。由于房 地产商2不了解市场需求情况就决策，所以它是一个不完美信息的博弈。2在树中有4 个决策结点（即状态），但是它们组成两个信息集，分别用虚线把它们圈了出来。也就是 说,心是这样的剖分，把满足P（力）=2的4个结点分成两个子集，上面两个结点是一个 信息集，下面两个结点是另一个信息集0 2在决策时知道1是开发还是不开发,也就是2 知道自己在此树的上下两枝中哪一枝进行决策但是2在决策时不知道市场需求是大还 是小，因此不能区别究竟在一枝的那一个结点进行决策。这就是会是上述剖分的理由。1.2博弈论发展简史Game Thsry 是 1944 年由于 von Neumann 和 Morgenstern 合著的“Theory of Games and Economic 出版而逐渐形成的名词据Webstar辞典记载，此词最早出现在1949年，然而Game Theory的内容有的出现得早得多。有的作者把田忌向齐威王献计赛马的故事说成中国古代早就有了博弈论思想的例 8博弈论导论证。不过毕竟只有朴素的观念,离现代的模型差得太远,而且那以后两千多年在中国对博 弈的数量分析并没有得到发展。人类历史上用数学模型分析竞争的最早事例公认是 1838年Cournot的研究。1913年Zermelo用逆推归纳研究过国际象棋博弈。Borel在 1921年到1927年期间研究了 minimax解。1928年von Neumann提出了博弈的扩展形 式，对两人零和博弈证明了有名的minimax定理。1944年他与Morgenstern合著的书出 版，表明Game Theory正式成为了一门学科。然而由于高深的数学内容，当时很少有经济 学家能理解Q从20世纪40年代到50年代初，研究博弈论的几乎全是数学家，并且大部分与 Princeton大学有关系。von Neumann从1931年开始有许多时间在这所大学工作，1948 年他专门在该大学高等研究院从事研究，他与Morgenstern合著的书无疑对年轻学者研 究博弈论起着重要的启迪作用.当时有人称这本书为“那部圣经前后有Tucker,Shapley,Nash等人在这段时期对Game Theory的发展作出了重要的创新c Tucker研究 囚徒问题,使对不合作博弈解的认识深化。Shapley研究联盟博弈的核心、值等，也加深了 对合作博弈的认识。Nash则以其对不合作博弈均衡解与谈判问题解的研究，最终导致获 得1994年的Nobel经济学奖。Nash与von Neumann是博弈论发展史上所起作用最大的两位学者，他们都是富于创 新的人物，Nash是von Neumann的学生，当前者向后者介绍自己对均衡存在性证明的思 路时,后者作为纯粹数学与应用数学两方面的世界性权威竟然打断前者的话，不耐烦地 说这是平凡的事,你知道，这只不过是不动点定理Jsi Neumann看不准Nash研究成 果的价值，但是尔后经济科学、社会科学乃至生物学的发展却使人们充分认识冠以Nash 名字的Nash均衡在认识上的深刻性。这充分证明了科学的真理性检验是多么需要时间 与实践的投入。20世纪50年代中叶以后，研究博弈论的人逐渐不限于数学家，有许多经济学家，统 计学家对博弈论的进步作出了责献，并且在学术界出现了称为&博弈论家”的学者,其中最 有名的是Selten与Harsanyia前者提出了博弈精炼Nash均衡的概念,对动态博弈进行了 开拓性研究，对不完全信息动态博弈提出了颤抖手精煤均衡的概念，后者则对不完全信息 博弈提出了 Bayes Nash均衡的概念以及进行了深入的研究，并与前者一起探讨了均衡选 择的一般理论。他们两人由于成就卓越，在1994年与Nash 一道获得Nobel经济学奖除此之外,Scarf对于均衡计算的研究,Avmann对知识的公理化,Kteps与Wilson等 人对序贯均衡的研究,Timle对企业组织原理的探讨等等，都是博弈论的重要成果。在von Neumann时代,博弈论是一门数学,或者是运筹学的分枝 Nash本人是数学 家，他的研究与经济学有紧密的关系，但他的成果仍带有深刻的数学性质:公理化,逻辑的 Chi绪言 9严密性和结论的广泛性。Nash以后的博弈论已不再适宜于当作纯粹的数学，而与经济 学、社会学等有了紧密的结合，往往研究具体一类问题的模型、解的定义与算法，不去求应 用的广泛性与概念的抽象性。往往定义了很长一段话，作出来的结论并不很多口缺少 von Neumann,Nash那样言简意赅的结果。这或许表明，博弈论作为从数学中独立出来 的学科还处在方兴未艾的阶段。因此愿意对这门学科的发展进行努力的人，是会大有可 为的。10博弈论导论锹2 von Neumann经典理论 W W*垄 W*W W W-W本章介绍的内容是von Neumann和Morgenstern合著的书中最基本的一些内容，通 常也是运筹学教程中都涉及的内容，特称之为von Neumann经典理论。2.1矩阵博弈博弈可以按许多准则来分类。按局中人个数分为:单人博弈（即决策），两人博弈，多人博弈。按局中人决策的时间先后分为:静态博弈，动态博弈。前者是各个局中人同时决策或 虽然不同时但每个局中人并不知道其他所有局中人决策结果的情形,后者则是其它情形。按局中人可行方案集元素个数分为:有限博弈,非有限博弈。所有局中人的可行方案 集都只有有限个元素的便是有限博弈。按局中人收益函数之和分为:零和博弈,非零和博弈。按局中人信息的情况分为:完全信息博弈,不完全信息博弈。下面我们讨论静态、完全信息的两人零和有限博弈Q它是策略博弈其中N 与 1,2|。Ar=J是1的可行方案集，含m个不同的方案劭，而。Az9出，也|是2的可行方案集，含n个不同的方案仇，也Pk（ai9句）是局中人1取方案由而局中人2取方案与时局中人归的收益，i=1,j=k=1,2O对于r,称Aa的元素（即可行方案）为局中人k的纯策略。引入矩阵A=（P 1（。：,与CB2 von Neumann 经典理论此矩阵陈列了博弈r的全部信息，它的m行分别对应于局中人1的m个纯策略列 分别对应于局中人2的几个纯策略简记A的（Kj）元素为箝，3=1,，加,j=l,，noA 于是啊是局中人1取见而局中人2取名这种局势下局中人1的收益，也是同一局势下 局中人2的支出（或负收益给定两人零和有限博弈r,便可引出如上的矩阵Ao反之给定任一 mXn的矩阵,便可设想有如上的博弈r,为是局中人1在局势（勾，句）下的收益n按照此种对应关系,称r为矩阵博弈。所以，矩阵博弈就是静态、完全信息的两人有限零和博弈。博弈作为决策的问题，需要寻求“解”，对博弈模型的讨论,首先便是定义“解”，也就是 定义局中人选择什么策略对其而言是最优的。从实践出发，研究者提出如下的推则作为局中人选择自己策略的依据：假定自己每取一个为策略,对方恰巧取其纯策略使自己的收益聂小；于是选择自己的 纯策喀，使得此最小收益值尽可能地大。这是一种稳健的准则，常称最大最小准则。对于矩阵为A的矩阵博弈?（以下简称为矩阵博弈A）,由于局中人1与2的地位有 区别，最大最小准则的表述也有如下不同。对于局中人1,A元素%就是局势（见，与）下局中人1的收益，因此最大最小准则是：局中人1选择*,1=/&襁，满足】醺“N图%*=1,，亦即】嚷夕广吃嬲/而对于局中人2,收益是A元素的负值，最大最小准则就成为:局中人2选择/j 4箕，满足亦即 7 I尴，腮I骡川。定义1对于矩阵博弈A=如果存在加J&J*满足y=醺*j12博弈论导论则称(f*,/,)为 A 的一个鞍点(saddle point)c今设(产，/)为A的鞍点，于是由(1)与(3)得 minaj a7 o由(6)知,作为最大最小收益值,堂厅必定满足与广底糜中。作为鞍点，(6)也成立故必有/=a,/(与上面不等式矛盾，故局中人1的最大最小收益值不可能另有更大者。类似可以说明，局 中人2的最大最小收益(即最小最大支出的负值)也不可能有更大者。例1给定矩阵A=4 03 2、一 5 2251由于优=3,非=3,而求出各行最小值mmalj-mint4,0,2)0-min(3,2,5)=2rnmaj7=min(-5,2,1)=-5故知最大翼小值是=max(0,2,一5)=2=20类似地，泰谒垃竟值maxfln=max(4,3-5)=4xnai2=max(0,2,2)=2否然%3=max(2,5,l)=5故知最小言黄值是Ch2 von Neumann 经典理论13=min(4,2,5)=2 J*-2由于密第鹿邛产2=网/嘱故知（广，/）=（2,2）是A的鞍点，因之此博弈在最大最小准则下的解是（2，力2），即此博弈的解是：局中人1职其第2个纯策略，局中人2取其第2个纯策略。例2给定矩阵由于m=2,力=2,而max min=-2min max am二312 JrC2 J故此矩阵没有鞍点。例2表明，通过求鞍点来求博弈不总是可行的,因为矩阵可能不存在鞍点。然而通过随机化就会得到不同的结论。下面来说明之。给定两人零和策略博弈r=（|it2|tMHA2）,（pl,p2）此地Ai=卜1,%/2=也,也分别为局中人1.2的纯策略集（即可行方案集）c定义A1上的概率分布X 2（到,，工切）丁力r=L+打，2%=L为局中人1的混合策略，定义A；上的概率分布y 2（”,，弘）丁力y，O.j=1,兄3*=1为局中人2的混合策略。14博弈论导论为了进一步推演,提出如下两条公设。公设1在局中人的混合策略局势(X,Y)之下,局中人1的期望收益是A(X,Y)=XtAY其中A%=P(aibj)fi=1,，加，j=1,，九，局中人2的期望收益是-A(X,Y)=Xt(-A)Yo称A(X,Y)为局中人1的期望收益函数。显然它是局中人2的期望支出。当局中人1与2在行为上相互独立时，此公设自然成立。公设2(最大最小期望收益公设)局中人1的决策准则是求混合策略X*，使得nun A(X*,Y)=nwc min A(X,Y)(7)局中人2的决策准则是求混合策略V、使得maxA(X V*)=min maxA(X,Y)(8)X Y X称X”为局中人1的最优策略，称Y*为局中人2的最优策略，而称为此博弈的最优策略组。此地的最优都是在局中人1追求期望收益最大最小的准则下立言的，以后将发现，此(X J Y*)提供矩阵博弈一种“解在公设2中，涉及XW 是否存在的问题。在此公设中，呼n表示 min,Y=(31，产号，o.j=1H7=1即Y如此变化下的最小值，吸K表示max,产七次hi=1,+癖 m i=iCh2 von Neumann 经典理论15即X如此变化下的最大值，由于函数A（X.Y）=XtAY=X 金寓通i=i；=i在区域|，工：/0,3二1,，机、UR”1、占=1 Ji=和区域f 1的芸o，j=1，勺1 V=,，的）白 仁01 毕=1 1都是连续的，而这两个区域在喜自的空间里是紧致集（有界、闭集，故理M（x,y）和 峻（X.Y）都能够达到G在2.2的定理6中将说明呼M（X,y）是X的连续函数,峻（X,Y）是Y的连续函数，而X,Y分别在上述两个紧致集上变化,故公设2中所言 x*与y*都是可以取到的。因此公设2中所言的两个决策准则都是可行的。引入记号.（X）=min4（X,y）svx（丫）=maxA（Xf Y）,即m.“（X）=minXTAY min：Z 4产必,y Y i=k ie nvx（Y）=maxXMY 二 max2 2产田来证明以下两个定理。1 定理1对于所有可能的X,Y,有“（X）=minXA.j,z，x（Y）=maxA/i Y,l所式中,A.为A的第j歹U,A-为A的第？行c 证明来证前一式uy（X）=minXTAY16博弈论导论yinunXT(AdA”)*=呻汉丁母A.如 y j=i一方面由于融0-1,；H，2为=1，有j=1-nminX A.*=min 夕(X”,)、/v 产i Y=,min立A.j)y靠(*)(mhiXd)7=1 2=minX;CA.j,i 3另一方面由于乃=1及y妾OJ=1,1及集上最小值不大于子集上最小值，故有 j=iminXT.A。*=minW(X)另 y 尸i y六yeld,o.-帆。小XAP其=minXA.；,故叫/丁 E A必=昌胪力7，即证明了前一式:后一式证明类似0定理2rMx rmnA(Xt Y)W 叫n nixA(Xt Y)证明 对所有X=，石尸二1都有1=1A(X,Y)虱吸姐(X,Y),组因而对所有Y=61产,为/,苛/。，2%=I更有Ch2 von Neumann 经典理论17min4(X,Y)P0,VyeBG证明 记dG,幻为r到之的距离,此地之由于14B,故d(mz)0。因此 存在满足*)=minrf(j7,z)于是有18博弈论导论又有产/；-P0=宜(N：芍)之：PoJ-1 f=I=2(之：-工SX:q 十 一 I r=I LI=*(N：-工 0=I故对于丁这一个B的点有t：PK Poj=i下面说明对于所有B的点N,有之;H%P*用反证法。设存在；y G 3满足 r=，=1S 2.1考虑*与y的凸组合w=Ajj+(1-A)z*0 A 1由于B是凸集，故w 6 Sajr到笆的距离平方是函数/(4,w)=(J(xt w)2=.(石-应-(1-入)2：)2 而了对参数入的徽商是 Ch2 von Neumann 经典理论19“STSE 2 2=d/-dA（可一入乂 一（1 一九）n：）（一+Z：）-2Piz；十 2人身（；-）21=1 i=它是；I的连续函数，而If I=2大劭-2封?部3CM I=0 j=i|=J由于JjPa&P。，=i JV（=i故乳=。0充分小时/（L）/（JT,W）lA=0而入=0时f（x9w）=H（h，J）2，故有w E B使得d（1,惧）2 p（jo r=i 证毕。定理4（择一性定理）对于矩阵A=（。4 下二系统恰有一个有解Ai 九:*I.（A,G j=01冈，:0 产I 产I.:!串m-、M加J20博弈论导论AH ni 1:（十s Lm口水,此处0（+m）xi是并十加维的列向量，分量都是0。而（猫.，（，出，姑）?0表示左 方各分量 0但至少有一个 0。证明 设系统I有解。如果此时系统n也有解，设之为x=殳1，尸，由系统n的后加个不等式即1相 0,1得知Xj 0,i=1,，雨。对此X,一方面有XT(AJm)Mi平m另一1方面有AiXr(AJm)Xn 朴i=0,o o是不可能的,故此时n没有解设I无解，在火血中考虑由4的打个列向量A”,A.2,引出的集合Ch2 von Neumann 经典理论21X=（工一，工皿/X二安心叮，4K 2%=1j=1（即A.I，,A.巩的凸组合形成的集，或称凸胞）此X是有界.凸、闭集。而R机的061c之所以如此是由于若0 G A,则有以，,为，叼20,X叼=1,满足 j=iuiAi+1+即=0,力i即A；二0。因之一%（A4）%=；、（oJ有非负且非零的解叼1Q 00，这与I无解矛盾。故0庄五。据定理3,存在0及尸=（四，自）丁羊0,满足0=尸0，i=1 吗S 户总 Pq，Vy=611以）丁 Ac1=1由前一式知Pq=0,故理夕a 0.ac特别，令tM,i-1,痴22博弈论导论即令aU：=：=A.jJn J 讨 j得2 iQij 0,j=1 J*,oi-1又令|1 i=jy io,?=i,，加但？w/于是rwS pyi 1=L成为%o,此不等式对，=I,，m均成立。再令a=乙户j，厂I则a0。再令于是*4=1，*n I并且m l 2 d产，=_S abPiJ=i=i a t=i这就表明l,*,Woj*G 十 m）xl有解,即系统H有解。证毕。定理5（Minimax定理，或von Neumann定理）对于矩阵博弈 A=Ch2 von Neumann 经典理论23记vi=max minX7AY=max z?v(X),X Y Xvo=min maxXAY=min V),-y.v Y则必有Vi=f 2证明对于矩阵A,据择一性定理知下列两种情况必居其一。L系统I有解,即存在入1，入”+祈满足a 4为+儿+i=0,=1,，树，产为 0J=1,，+W,ft+M出i2.1统n有解,即存在二1，一，2田满足石 0 z=,m 为=1,ISiai0=1,”,力c先设;晟立。此时心，不会全为0,否则便有N=QJ=+I,-,/a+m 1使勺=1不可能成士。故4I,a不全为o,因之A=为 0D八1令勿=?J=1,，24博弈论导论则有一一 z,0,Kj忌k l 0据定理2的推论，命题(3其功)成立。上面又证明了命题(为40)V(S 0)成立,但是(02 W 0)V(ti 0)=(叼 WO)A(也 0),故命题(%0)不成立，即不等式组6*0 V2不成立。下面由此出发证明，不存在任何实数3满足64天 功。事实上，对于任何实数上 令与笃4T,?=1，加;j=1,速/=()而。于是对任何混合策略对(X,V),若记(石兀为所有元素为笈的相乂九矩阵，则xtby=xta-=xtay-kxT(iMXnY=XTAY-k记力(B)=max minYy,x 力2(日)公 minnmxXByoCh2 von Neumann 经典理论25易知iq(B)=k巧(h)=V2 k并且仿照前面的结果，知不等式组v(B)0 (B)不成立，即不等式组 v2不成立。由此得知不等式力 I 0为充分小的正数J“为R加内两点的欧氏距离c又设理nTTAY的解是 此集合，于是 fvy(X7)=rmnXz7AY=X?7AY而vy(X)-minXY XJV因之I w(k)-“(x。l I X，rrAYf-XrrAYf 二 I(x 一 x，t)ayj l X II,此处M为一充分大的正数，满足|AFII 0,取方，于是只要II X*-xz II 台，便有I“(M)-w(X)l p,jI1为12口豺；龛仃，-L，加。证明 据定理5和6知备弈解一定存在.下面证充分必要条件,先证必要性。设(XW)为解，于是力=nrwx rxurAY=nwc 跖min X aijTi因之加工:云 p,j=1,，打 类似可得S W =1,，5 再证去分性:设两组不等式成立，由W12工：为曲刃，=1,一，抑 t=l及y；0,J=1,，加得X*rAY*=.它风产:y；一一夕：=*/=1 7=1 j-i类似可得x*My*虱”故(X*,Y)满足X*7Y*=孙 因此是解。定理8若(XY)为矩阵博弈A的解，则X#,Y，满足XY*XYWX,X*tAY XtAY,V Yo 反之亦然。证明 设(XYD为解,来证明满足前一个不等式。事实上，设有X使 x*%y*X*tAY*即 已，=1这与定理6的结论矛盾。故对一切X有x*Tay*xtay同理后一个不等式也成立口反之，若两个不等式成立，据定理7的充分条件即可证明（X*,Y）是解，细节从略。下面将要证明的定理10在求解中有用先引入一个定义和证明与之有关的定理先定义3 设4=（柒1,，我）T=1,，p是p个力维向量，称集合C=jxlx=幺，A登 0,4=1,为由z-,乙生成的凸锥。定理9（Farkas引理）假设Z*=（跺”，）丁,*=1,，力+1是p+1个这样的 n维向量,若有Q”，如使得则必有S q为+1/）。=i在此前提下,Z*一定属于Z1,，4生成的凸锥C。证明设Z1 4 C。据定理3,存在数Q1，/，%+1使得q芦p+ij=屐41。河 e c显然0 C,故如x。假设有（si,，s，rE C使得S g gw+lo户i但a充分大时，以叼）=戊以 就非负得很厉害，以致必然有公%（啊），上=1,，力。由假设知笳%尸1但前面已知它gmc=叼，i=i局中人2有最优策略V满足400证明 先设博弈A的值已=也考虑如下阳+崖个总维向量=（1,01,0）丁,e2=（0,1,。）丁，e珊=（0,0,，1）,，5=许1避21，、1尸，“算-1 （11,T，&2.”-1，）口汛=（a 1,&2 通，,一。机彳浮）,-%要么在前根+n-1个点生成的凸锥C内，要么不在C内，二者必居而且只居其一。先设-EC,于是存在非负数丛，1 Nm，*，九河-1使得30博弈论导论j -1市=SA+入产0=1，m，=1/=1由之得知4一1+Q包=一出&0,=1g，加。，=1为一 九7，J 一人，门 1 1+2 Ai=1*&1yn=i-，1+Sa,z=i显然，Y*=6L，才尸是局中人2的混合策略。并且帚 尸rS%y；=S 3：+ainy*，=i=-（*以/+ain）0。再设-的庄C。据定理9中援引定理3所得结果,存在数叫5 使得 m2q&o,j=1,，根,?=1rSj o j=i,，能-1,i-lmS%（-“）0o 产iCh2 von Neumann 经典理论31*&0 1Xi=-,2=1,，加。则x*=(工,7；)丁是局中人1的混合策略。并且由第二组不等式知也是据定理7所证明到的，此X*是局中人I的最优策略。并且据第三组不等式得叫 1 j：S。后=(S 卬0)Ooi=i V i=i%以上证明用到了=0,如果守=AH0,考虑矩阵博弈B=(如讶，如=ak,i=1,，？n J=1,，九，则B 的值 v(B)=maxminXy x y=maxminXT(A-(k)mXn)Yx y=maxminXAY-maxminXT(4)次五“V 1y 士 y=七(A)-氏=0。并且，若(X,y*)为博弈A的解,据定理8知MA)=X*tAY Ry*,VXMa)=x#7Ay*vy于是易知MB)=xy=x*tay*-kXtAY-k-xtby/xMB)=XY*=X*TAy*-kX#TAY-k=XY,V Y又据定理7,(XY*)必为博弈B的解。反之，若(X*，丫)为博弈B的解，则仿上可证(X、y*)必为博弈A的解。综上所述，对于博弈B,下二者必居而且只居其一：局中人1有最优策略X*,它z；0=v(B),1=1局中人2有最优策略Yy：0o但是32博弈论导论1=1/=1=4产；_ kj：；i=l i=lm2。iM?-k j=t=-鲁（A）j=i故局中人1的最优策略X*满足天上小：0,即 i=I严2/泅；V（A）o1=1而y；0对B与A是同样成立的。这就完全地证明了定理10o不难明白,本定理结论中的下标若换成任一A G 1,仍然成立。在运用本定 理于求矩阵博弈的解时，如果有某右 开使得汽仇武；&,则据本定理知必有i-1 m m城=00而如果2见庐：=则必有2：0。或者,如果有y；0,则2%/：=口而若城=0,则必有好；/在2.3中将有例子说明定理10的应用。1=12.3 矩阵博弈求解矩阵博弈的解（X*,V*）由局中人1,2的最优混合策略X*,Y*组成，可通过线性 规划求得。对给定的矩阵博弈A,设值v（A）0。据定理7,局中人1的最优策略X=（X：,X；）,满足mZa产：町/=1,，兀，（7）局中人2豺篙优策略Y*=6；,）丁满足Ch2 von Neumann 经典理论332aM=1,(8)在(7、中令*K,1/-.,7=1,m,则u*20,=1,，帆.m 1S；*=一而。=哼x”(X)。故局中人1求最优策略的问题等价于求汽由=min的问题。于是引 出求局中人1最优策略的线性规划问题Wmin 2 Uii-1罚s.t.产I融l,j=1,，兀，i-IUi 算 0,i 1,，ni求出它的最优解td)以后，算出对策值A 1七二r,便可得最优策A=VU*T/=1,，加0类似地，局中人2求最优策略的线性规划问题是max加10矩阵的值又满足1p=-，砚；产此地(川，馍；)是线性规划问题(10)的最优解，而局中人2的最优策略是34博弈论导论3；-vw；,j=1,，0根据线性规划的对偶定理,（g）与（io）的最优值相等。故都等于七。如果七工0,直接按上面的方式作是行不通的。可以改而考虑矩阵博弈b=（如）,bij=%+=1,，加，/=1,其中M为充分大的正数，使得所有/Ou=1,=Id容易了解，博弈B的v 0,而A与B有相同的解。为求A的解,只需对B按上面的方式 去作，即解一对线性规划s.t,之6/冢=e!=?0,2=1.smax 2%e=lns.t,刑 0,j=1,，力。根据线性规划的对偶理论，这两个规划的最优值相等，就是十，局中人1的最优混合策略 是X 二（才 1，一,心）丁Xi m*9i=1.，m,5；,，以工）丁是上述极小值问题的最优解，局中人2的最优混合策略是Y=6i,，）,Yj-vw/,j=1,n（wf，加；）丁是上述极大值问题的最优解。对于任给的矩阵博弈A,在求解之前怎样判定v0呢?当A的元素全为正数时2 肯定是正数，当A的元素有正有负时，放可能是非正的数。据上所述，只要取充分大的M,就可保证B的方 0,而最优策略不变。求解的方法不惟一。为了求局中人1的最优混合策略（工：，,二：尸，也可以通过如 下模型Ch2 von Neumaim 经典理论35max As.t.-2a产：+入 W0,j=1，,2为=11=1毛麦0,?1,2而求局中人2最优混合策略（“*，第）的线性规划则对应为min 2ns.t.34M+m 0=1,，加,j=i；=iyj冢0=1,，葭。v=maxA=min*例3给定矩阵博弈a=C；M试求其解与值。斛 m=2,九=九局中人1的混合策略是二维的，容易求解，故先从之开始。线性规 划问题min iti+2s.t.2肛+4w2 13 町+2 1，1+6u2 N 1，5 14 I，1 y1 妄 0,2 委 0。运用图解法。在皿1仪2平面上此规划问题的可行域是图2.2中斜线区域口它有三个角点8岁，信周,(1,0)计算出相应的目标函数值,依次是3 T5 1736博弈论导把X三者中，最小值是品，它必是