第十二章 对策论(运筹学讲义)

第十章对策论由“齐王赛马”引入§1对策论的例子§2矩阵对策论的基本概念§3矩阵对策的最优纯策略§4矩阵对策的混合策略§5其他类型的对策对策论或博弈论(GameTheory)是研究具有对抗和竞争性行为问题的数学理论与方法。是运筹学的重要分支学科经济学领域一般称博弈论，是经济学领域近几十年发展起来一门新兴学科对策论从理论上作严格的讨论却起始于二十世纪：1912年，德国数学家E.Zermelo证明了国际象棋的3种着法必定存在一种；1921年，法国数学家E.Borel引入了“最优策略”等概念；1928年，美籍匈牙利人J.VonNeumann证明了对策论的基本定理----最大值最小值定理；1944年，VonNeumann和O.Morgenstern合写了《对策论与经济行为》一书，建立起对策论的基本理论，奠定了对策论研究的基础。对策问题举例例1猜单和猜双的博弈。两个人同时出一个指头或两个指头，如果两人出的指头相同，则局中人1从局中人2处赢得五元；如果出的不一样，局中人1就要支付给局中人2五元。两个对手都可以采取两个策略：出一个手指和出两个手指，下表是局中人1的赢得矩阵(二指莫拉问题)策略局中人2出1指出2指局中人1出1指5－5出2指－55局中人1从局中人2该如何选择策略，已获得利益？例2囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在不同的屋子里审讯。警察告诉他们：如果两人都坦白，各判刑8年；如果两人都抵赖，由于证据不充分，两人将各判刑2年；如果其中一人坦白，，另一人抵赖，则坦白者立即释放，抵赖者判刑10年。在这个例子中两人嫌疑犯都有两种策略：坦白或抵赖。可以用一个矩阵表示两个嫌疑犯的策略的损益策略囚徒2坦白抵赖囚徒1坦白(－8,－8)(0,－10)抵赖(－10,0)(－2,－2)囚徒该如何选择策略？囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性例3田忌与齐王赛马战国时期，齐威王与大将田忌赛马，双方约定：从各自的上、中、下三个等级的马中各选一匹马出场比赛，负者要付给胜者一千金。已知田忌的马要比齐王同一等级的马差一些，但比齐王等级较低的马却要强一些。因此，如用同等级的马对抗，田忌必连输三场，失三千金无疑。田忌的谋士孙膑给田忌出了个主意：每局比赛前先了解齐王参赛马的等级，再采用下等马对齐王上等马、中等马对齐王下等马、上等马对齐王中等马的策略。比赛结果，田忌二胜一负，反而赢得一千金。由此可见，双方各采取什么样的出马次序对胜负至关重要。“齐王赛马”齐王在各局势中的益损值表(单位：千金)齐王和田忌可以任意选择三匹马出场的顺序§1对策论的基本概念对策模型的三个基本要素：1.局中人(Players)：参与对抗的各方；2.策略集(Strategices):局中人选择对付其它局中人的行动方案称为策略；某局中人的所有可能策略全体称为策略集3.一局势对策的益损值：局中人各自使用一个对策就形成了一个局势，一个局势决定了各局中人的对策结果（量化）称为该局势对策的益损值。赢得函数(payofffunction)：定义在局势上，取值为相应益损值的函数4.纳什均衡：纳什均衡指所有局中人最优策略组成的一种局势，既在给定其他局中人策略的情况下，没有任何局中人有积极性去选择其他策略对策的分类对策按对策方式合作对策非合作对策完全理性有限理性两人对策零和对策非零和对策多人对策结盟对策不结盟对策按对策人数静态对策完全信息静态对策不完全信息静态对策动态对策完全信息动态对策不完全信息动态对策按对策状态二人有限零和对策（又称矩阵对策）：局中人为2；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。通常将矩阵对策记为:G={S1,S2,A}局中人甲的策略集：局中人乙的策略集：甲的赢得矩阵：矩阵对策112{,,,}mS212{,,,}nS111212122212mmmmmnaaaaaaAaaaaij为局中人甲在局势下的赢得(,)ij其中：齐王的策略集:S1={1,2,3,4,5,6}，田忌的策略集：S2={1,2,3,4,5,6}。下面矩阵称齐王的赢得矩阵：3111-1113111-1A=1-13111-111311111-13111-1113“齐王赛马”是一个矩阵策略。§2矩阵对策的最优纯策略例4甲、乙两队进行球赛，双方各可排出三种不同的阵容。设甲队为局中人Ⅰ，乙队为局中人Ⅱ，每一种阵容为一个策略，有S1=｛α1,α2,α3｝，S2=｛β1,β2,β3｝。根据以往两队比赛的记录，甲队得分情况的赢得矩阵为415306213A问：这次比赛中，双方应如何对阵？在如此反复对策的过程中，各局中人如果不想冒险，就应该考虑从自身可能出现的最坏情况下着眼，去选择一种尽可能好的结果，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。这就是所谓“理智行为”。称为最小最大准则，按照这个各方均避免冒险的观念，就形成如下的推演过程。415306213A解从A中可以看出，Ⅰ最多可得6分。于是，Ⅰ为得6分而选α2。但是Ⅱ推测Ⅰ会有此心理，从而选β3来对付，使得Ⅰ非但得不到6分，反而要失去3分。当然Ⅰ也会料到Ⅱ会有此心理，从而改选α3，以使Ⅱ欲得3分而反失4分。矩阵A中每行的最小元素分别为1，-3，-5。在这些最少赢得中最好的结果是1，故局中人Ⅰ会采取策略1，无论对手采取何策略，局中人Ⅰ至少得1分。对于局中人Ⅱ，{1，2，3}可能带来的最少赢得，即A中每列的最大元素，分别为6，1，4。局中人Ⅱ会采取2策略，确保局中人Ⅰ不会超过1分。1和2分别称为局中人Ⅰ、Ⅱ的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。§2矩阵对策的最优纯策略326035141AMin1－3－56Max14123123定义1设有矩阵对策G=｛S1,S2;A｝,其中，A=[aij]m×n，若有vaaajiijijijji**maxminminmax则局势(αi*，βj*)称为G在纯策略意义下的解，也称为G的鞍点；αi*、βj*分别称为局中人Ⅰ和Ⅱ的最优纯策略；v称为G的值，也称对策值。对于例4，G的解(鞍点)为(α1,β2)，α1、β2分别为Ⅰ、Ⅱ的最优策略。对策值v=10，反映优势在Ⅰ方(对Ⅰ有利)；若v0，则优势在Ⅱ方(对Ⅱ有利)；当v=0时，称为公平对策。112{,,,}mS212{,,,}nS矩阵对策有解的条件现在，讨论矩阵对策在纯策略意义下有解的充分必要条件。定理1设G=｛S1,S2；A｝，其中，，A=[aij]m×n，G在纯策略意义下有解的充要条件是：存在纯局势(αi*，βj*)，使得对一切i(i＝1,…,m)和j(j＝1,…,n)有112{,,,}mS212{,,,}nS****ijijijaaa****maxminijijijjiaaaijjijiijijaaaminmaxmaxmin**证先证充分性设对任意i和j，均有****ijijijaaa*1minmax{min,min}maxminjmjijijjjjjiiaaaa又因为1*minmaxmin{max,max}maxijiinijjjiiiiaaaai*行最小元，j*列中最大元i*行最小元1行最小元****minmaxmaxminmaxmin(1)ijijijijijjjjiiiaaaaa另一方面(P209引理)，对于任意i和j有minmaxijijijjiaaa1122max,max,,maxiiiiininiiiaaaaaa故maxminminmax(2)ijijjjiiaa综合(1)和(2)式，有**maxminminmaxijijijjjiiaaav所以，G在纯策略意义下有解i行中最小元j列中最大元所以有minminmaxijijjjiaa从每列最大元中取最小元12minmin{,,,}maxijiiinijjiaaaaa证明必要性设G在纯策略意义下有解，即成立vaaajiijijijji**maxminminmaxjijijijjiaaa**minminmax**minmaxmaxijijijjiiaaa****ijijijaaaminijja因在i=i*时达到最大，即ijjamax在j=j*时达到最小，即同样定理1说明了G在纯策略意义下有解的充分必要条件是：A中存在这样一个元素，既是所在行的最小元素，也是所在列的最大元素。换言之，有纯策略解与存在鞍点等价，这正是VonNeumann当年所证明的。这个著名结论所体现的基本理性思想，就是：“做最坏的打算，寻求最好的结果”。1342A例5已知矩阵对策G,其中：问：G是否存在鞍点？解因maxmin2,minmax3ijijjjiiaa不符合鞍点条件，故G的鞍点不存在。但是否每个矩阵对策一定存在鞍点呢？回答是否定的。现在考察下例。例6求解矩阵对策，其中：111101A解容易得到由此可见，G的解可以不唯一，但G的值必是唯一的。3;2,11****jiavjimaxminminmaxijijjjiiaa定义2设有矩阵对策G={S1,S2;A},其中:A=[aij]m×n,概率向量112{,,,}mS212{,,,}nS当矩阵对策G在纯策略意义下无解时，由于不存在鞍点，即不存在平衡局势，各局中人的决策总有一定的风险。因此，无理由只取某个策略而舍弃其余策略，也就是局中人应考虑，按照预先确定的一组概率来选取其所有可能采用的策略。§3矩阵对策的混合策略121121,,,1,0,1,2,,,,,1,0,1,2,,mTmiiinTnjjjXxxxxximYyyyyyjn　　AYXyaxYXETminjjiji11,分别称X,Y为局中人Ⅰ和Ⅱ的“混合策略”。向量组(X,Y)称为混合局势。数学期望称为局中人Ⅰ的赢得。(4)X、Y的全体分别构成Ⅰ、Ⅱ的混合策略集，记作称为G的混合扩充。**12,;GSSE*｛｝纯策略对策是混合策略对策的特例，此时，概率向量为单位向量。一个混合策略可理解为：如果进行多次对策G的话，局中人Ⅰ分别选取纯策略α1,α2,…,αm采的频率。如果只进行一次对策，则反映局中人Ⅰ对各种纯策略的偏好程度。12,,,TmXxxx*1121{,,,|1,0,1,2,,}mTmiiiSXxxxxxim*2121{,,,|1,0,1,2,,}nTnjjjSYyyyyyjn*1121{,,,|1,0,1,2,,}mTmiiiSXxxxxxim例7掷硬币投注的对策两个局中人之间开展有裁判的掷硬币游戏，无论出现正面还是反面，裁判将结果告诉局中人甲，局中人甲看完结果后，有两种选择：(1)放弃投注并支付给局中人乙5美元。如果局中人甲放弃，游戏就结束了。但如果局中人甲投注(beton),游戏继续，这时局中人乙也有两种选择：(1)放弃投注并支付5美元给局中人甲；(2)跟着下注。如果局中人乙选择下注，裁判将投币结果展示给乙看，如果是正面，局中人乙支付10美元给局中人甲；如果是反面，则局中人甲支付给局中人乙10美元。（1）试写出对策中各局中人的策略集（2）建立局中人甲的赢得矩阵（3）判断对策是否存在鞍点（4）求解此矩阵对策解（1）分析对策双方可能采取的策略情况，投币的情况有两种可能，甲根据看到情况做出反映，乙根据甲的的选择做出反映。对于局中人甲，可能的策略有4个，每个都是他对裁判给他看的硬币出现正、反面两种结果后分别做出的