重庆工商大学数学建模算法讲义第07章 对策论

-154-第七章对策论§1引言社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法来解决这样的问题开始于17世纪的科学家，如C.，Huygens和W.，Leibnitz等。现代对策论起源于1944年J.，VonNeumann和O.，Morgenstern的著作《TheoryofGamesandEconomicBehavior》。对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。§2对策问题对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。先考察一个实际例子。例1（囚徒的困境）警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以持有大量伪币罪被各判刑18个月；如果双方都供认伪造了钱币，将各被判刑3年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列于表1。表1嫌疑犯B供认不供认嫌疑犯A供认不供认（3，3）（0，7）（7，0）（1.5，1.5）表1中每对数字表示嫌疑犯BA、被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。从这一简单实例中可以看出对策现象中包含有的几个基本要素。2.1对策的基本要素（i）局中人在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局中人。通常用I表示局中人的集合．如果有n个局中人，则},,2,1{nIL=。一般要求一个对策中至少要有两个局中人。在例1中，局中人是BA、两名疑犯。（ii）策略集一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人i，Ii∈，都有自己的策略集iS。一般，每一局中人的策略集中至少应包括两个策略。-155-（iii）赢得函数（支付函数）在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若is是第i个局中人的一个策略，则n个局中人的策略组),,,(21nssssL=就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔积表示，即nSSSS×××=L21当局势出现后，对策的结果也就确定了。也就是说，对任一局势，Ss∈，局中人i可以得到一个赢得)(sHi。显然，)(sHi是局势s的函数，称之为第i个局中人的赢得函数。这样，就得到一个向量赢得函数))(,),(()(1sHsHsHnL=。本节我们只讨论有两名局中人的对策问题，其结果可以推广到一般的对策模型中去。2.2零和对策（矩阵对策）零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双方的利益是激烈对抗的。设局中人Ⅰ、Ⅱ的策略集分别为},,{11mSααL=，},,{12nSββL=当局中人Ⅰ选定策略iα和局中人Ⅱ选定策略jβ后，就形成了一个局势),(jiβα，可见这样的局势共有mn个。对任一局势),(jiβα，记局中人Ⅰ的赢得值为ija，并称⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=mnmmnnaaaaaaaaaALLLLLLL212222111211为局中人Ⅰ的赢得矩阵（或为局中人Ⅱ的支付矩阵）。由于假定对策为零和的，故局中人Ⅱ的赢得矩阵就是A−。当局中人Ⅰ、Ⅱ和策略集1S、2S及局中人Ⅰ的赢得矩阵A确定后，一个零和对策就给定了，零和对策又可称为矩阵对策并可简记成};,{21ASSG=。例2设有一矩阵对策};,{21ASSG=，其中},,{3211ααα=S，},,,{43212ββββ=S，⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−−−=16100610182142230612A从A中可以看出，若局中人Ⅰ希望获得最大赢利30，需采取策略1α，但此时若局中人Ⅱ采取策略4β，局中人Ⅰ非但得不到30，反而会失去22。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果，局中人Ⅰ采取策略321ααα、、时，最坏的赢得结果分别为-156-22}22,30,6,12min{−=−−2}10,18,2,14min{=10}16,10,0,6min{−=−−其中最好的可能为2}10,2,22max{=−−。如果局中人Ⅰ采取策略2α，无论局中人Ⅱ采取什么策略，局中人Ⅰ的赢得均不会少于2。局中人Ⅱ采取各方案的最大损失为14}6,14,12max{=−，2}0,2,6max{=−，30}10,18,30max{=−，和16}16,10,22max{=−。当局中人Ⅱ采取策略2β时，其损失不会超过2。注意到在赢得矩阵中，2既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减少损失，称这样的局势为对策的一个稳定点或稳定解。定义1设),(yxf为一个定义在Ax∈及By∈上的实值函数，如果存在Ax∈*，By∈*，使得对一切Ax∈和By∈，有)*,(*)*,(*),(yxfyxfyxf≤≤则称*)*,(yx为函数f的一个鞍点。定义2设};,{21ASSG=为矩阵对策，其中},,,{211mSαααL=，},,,{212nSβββL=，nmijaA×=)(。若等式**maxminminmaxjiijijijjiaaa==（1）成立，记**jiGaV=，则称GV为对策G的值，称使（1）式成立的纯局势),(**jiβα为对策G的鞍点或稳定解，赢得矩阵中与),(**jiβα相对应的元素**jia称为赢得矩阵的鞍点，*iα与*jβ分别称为局中人Ⅰ与Ⅱ的最优纯策略。给定一个对策G，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。定理1设};,{21ASSG=，记ijjiaminmax=μ，ijijamaxmin−=ν，则必有0≤+νμ。证明)(minmaxijija−=ν，易见μ为Ⅰ的最小赢得，ν为Ⅱ的最小赢得，由于G是零和对策，故0≤+νμ必成立。定理2零和对策G具有稳定解的充要条件为0=+νμ。证明：（充分性）由μ和ν的定义可知，存在一行例如p行，μ为p行中的最小元素，且存在一列例如q列，ν−为q列中的最大元素。故有μ≥pqa且ν−≤pqa又因0=+νμ，所以νμ−=，从而得出μ=pqa，pqa为赢得矩阵的鞍点，),(qpβα为G的稳定解。（必要性）若G具有稳定解),(qpβα，则pqa为赢得矩阵的鞍点。故有pqpjjijjiaaa=≥=minminmaxμpqiqiijijaaa=≤=−maxmaxminν-157-从而可得0≥+νμ，但根据定理1，0≤+νμ必成立，故必有0=+νμ。上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一，当解不唯一时，解之间的关系具有下面两条性质：性质1无差别性。即若),(11jiβα与),(22jiβα是对策G的两个解，则必有2211jijiaa=。性质2可交换性。即若),(11jiβα和),(22jiβα是对策G的两个解，则),(21jiβα和),(12jiβα也是解。§3零和对策的混合策略具有稳定解的零和问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是0≠+νμ的情况。由于赢得矩阵中不存在鞍点，此时在只使用纯策略的范围内，对策问题无解。下面我们引进零和对策的混合策略。设局中人Ⅰ用概率ix选用策略iα，局中人Ⅱ用概率jy选用策略jβ，∑∑====minjjiyx111，记Tmxxx),,(1L=，Tnyyy),,(1L=，则局中人Ⅰ的期望赢得为AyxyxET=),(。记*1S：策略mαα,,1L*2S：策略nββ,,1L概率mxx,,1L概率nyy,,1L分别称*1S与*2S为局中人Ⅰ和Ⅱ的混合策略。下面简单地记}1;,,1,0|),,{(11*1==≥=∑=miiiTmxmixxxSLL，}1;,,1,0|),,{(11*2∑===≥=njjjTnynjyyySLL定义4若存在m维概率向量x和n维概率向量y，使得对一切m维概率向量x和n维概率向量y有AyxyAxyAxTyTxTminmax==则称),(yx为混合策略对策问题的鞍点。定理3设*1Sx∈，*2Sy∈，则),(yx为};,{21ASSG=的解的充要条件是：⎪⎪⎩⎪⎪⎨⎧=≥=≤∑∑==njyAxxamiyAxyaTimiijTnjjij,,2,1,,,2,1,11LL定理4任意混合策略对策问题必存在鞍点，即必存在概率向量x和y，使得：-158-AyxAyxyAxTxyTyxTmaxminminmax==。使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策问题的特殊情况，相当于以概率1选取其中某一策略，以概率0选取其余策略。例3BA、为作战双方，A方拟派两架轰炸机Ⅰ和Ⅱ去轰炸B方的指挥部，轰炸机Ⅰ在前面飞行，Ⅱ随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰炸机飞至B方上空，受到B方战斗机的阻击。若战斗机阻击后面的轰炸机Ⅱ，它仅受Ⅱ的射击，被击中的概率为0.3(Ⅰ来不及返回攻击它)。若战斗机阻击Ⅰ，它将同时受到两架轰炸机的射击，被击中的概率为0.7。一旦战斗机未被击中，它将以0.6的概率击毁其选中的轰炸机。请为BA、双方各选择一个最优策略，即：对于A方应选择哪一架轰炸机装载炸弹？对于B方战斗机应阻击哪一架轰炸机？解双方可选择的策略集分别是},{21αα=AS，1α：轰炸机Ⅰ装炸弹，Ⅱ护航2α：轰炸机Ⅱ装炸弹，Ⅰ护航},{21ββ=BS，1β：阻击轰炸机Ⅰ2β：阻击轰炸机Ⅱ赢得矩阵22)(×=ijaR，ija为A方采取策略iα而B方采取策略jβ时，轰炸机轰炸B方指挥部的概率，由题意可计算出：82.0)6.01(3.07.011=−+=a112=a，121=a58.0)6.01(7.03.022=−+=a即赢得矩阵⎥⎦⎤⎢⎣⎡=58.01182.0R易求得82.0minmax==ijjiaμ，1maxmin−=−=ijijaν。由于0≠+νμ，矩阵R不存在鞍点，应当求最佳混合策略。现设A以概率1x取策略1α、以概率2x取策略2α；B以概率1y取策略1β、以概率2y取策略2β。先从B方来考虑问题。B采用1β时，A方轰炸机攻击指挥部的概率期望值为21182.0)(xxE+=β，而B采用2β时，A方轰炸机攻击指挥部的概率的期望值为21258.0)(xxE+=β。若)()(21ββEE≠，不妨设)()(21ββEE，则B方必采用1β以减少指挥部被轰炸的概率。故对A方选取的最佳概率1x和2x，必满足：⎩⎨⎧=++=+158.082.0212121xxxxxx即⎩⎨⎧=++=[phone]xxxaxaxaxa-159-由此解得7.01=x，3.02=x。同样，可从A方考虑问题，得⎩⎨⎧=++=+158.082.0212121yyyyyy即⎩⎨⎧=++=[phone]yyyayayaya并解得7.01=y，3.02=y。B方指挥部被轰炸的概率的期望值874.0=GV。记零和对策G的解集为)(GT，下面三个定理是关于对策解集性质