第07章對策論模型7.1矩陣對策模型7.2雙矩陣對策模型7.3n人合作對策初步（ModelsofGameTheory）1-7.1矩陣對策模型例7.1田忌賽馬問題戰(zhàn)國時期，齊國國王齊王提出要與田忌賽馬，雙方約定從各自的上、中、下三個等級的馬中各選一匹參賽，每匹馬都只能參賽一次，每一次比賽雙方各出一匹馬，負者要付給勝者千金。已經(jīng)知道，在同等級別的馬中，田忌的馬不如齊王的馬，而如果田忌的馬比齊王的馬高一等級，則田忌的馬可取勝。當時，田忌手下的一個謀士給他出了一個主意：每次比賽時先讓齊王牽出他要參賽的馬，然后來用下馬對齊王的上馬，用中馬對齊王的下馬，用上馬對齊王的中馬。比賽結(jié)果，田忌二勝一負，奪得千金。2-對策模型的種類可以千差萬別，但本質(zhì)上都必須包括以下三個基本要素：局中人，是指參與對抗的各方，可以是一個人，也可以是一個集團。在例7.1中的齊王和田忌就是局中人。策略，是指局中人所擁有的對付其他局中人的手段、方案的集合。如例7.1中田忌共有（上、中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、中、上）和（下、上、中）六種策略。支付函數(shù)（或收益函數(shù)），是指一局對策后各局中人的得與失，通常用正數(shù)表示局中人的得，用負數(shù)表示局中人的失。例如，在例7.1的局中人齊王的支付函數(shù)如表7-1所示。3-田忌的策略齊王的策略b1(上,中,下)b2(上,下,中)b3(中,上,下)b4(中,下,上)b5(下,中,上)b6(下,上,中)a1(上,中,下)31111-1a2(上,下,中)1311-11a3(中,上,下)1-13111a4(中,下,上)-111311a5(下,中,上)11-1131a6(下,上,中)111-113表7-1當局中人得失總和為零時，稱這類對策為零和對策；否則稱為非零和對策。當局中人只有兩個，且對策得失總和為零，則稱為二人零和對策；若得失總和為常數(shù)，則稱為二人常數(shù)和對策；若得失總和是非常數(shù)，則稱為二人非常數(shù)和對策。若二人對策雙方的得失是用矩陣形式表示，則稱支付函數(shù)為支付矩陣，相應的對策稱為矩陣對策。通常，支付矩陣表示局中人A的支付函數(shù)。4-7.1.1對策的基本策略—鞍點對策例7.2設A,B兩人對策，各自擁有三個策略a1,a2,a3和b1,b2,b3，局中人A的支付（收益）矩陣如表7-2所示。試求A,B各自的最優(yōu)策略。b1b2b3mina11391a26575a38422max859表7-25-從直觀上來看，局中人A應該出策略al，因為這樣選擇，他有可能得到9。但局中人B看到了這一點，他出策略b1，這樣局中人A不能得到9，而只能得到1。因此，局中人A也充分認識到這一點，他應當出策略a3，這樣做，就有可能得到8，而這種情況下局中人B就要出策略b3，局中人A也只能得到2。這樣做下來，局中人A只能選擇策略a2，而局中人B也只能選擇策略b2，大家達到平衡，最后局中人A贏得的值為5，局中人B輸?shù)舻闹禐?。b1b2b3mina11391a26575a38422max859從上面的分析可以看出，無論局中人A選擇什么策略，他贏得的值總是小于等于5，而無論局中人B選擇什么策略，他輸?shù)舻闹悼偸谴笥诘扔?，5就是支付矩陣的鞍點。6-假設局中人I有m個策略，局中人II有n個策略，分別記為為局中人I的支付矩陣，而–A為局中人II的支付矩陣，矩陣對策記為或定義7.1設是一矩陣對策，若等式（7-1）成立，則記，并稱vG為對策G的值。稱使式(7-1)成立的純局勢為在純策略下的解（或平衡局勢），稱和分別為局中人I、II的最優(yōu)純策略。由定義7.1可知，在矩陣對策中兩局中人都采取最優(yōu)純策略（如果最優(yōu)純策略存在）才是理智的行動。7-例7.3求解矩陣對策，其中解：根據(jù)矩陣A，有

Β

αβ1β2β3minjaijα1-72-9-9α24353*α315-2-4-4α4-406-4maxiaij153*6，G的解為（α2,β2），α2和β2分別是局中人I和II的最優(yōu)純策略。8-從例7.3可以看出，矩陣A的元素a22既是其所在行的最小元素又是其所在列的最大元素，即。將這一事實推廣到一般矩陣對策，可得如下定理。定理7.1矩陣對策在純策略意義下有解的充分必要條件是：存在純局勢使得(7-2)為了便于對更廣泛的對策情形進行分析，引進關于二元函數(shù)鞍點的概念。定義7.2設f(x,y)為一個定義在及上的實值函數(shù)，若存在，，使得(7-3)則稱為函數(shù)f(x,y)的一個鞍點。9-當矩陣對策的最優(yōu)解不惟一時，有如下定理。定理7.2(無差別性）若和是矩陣對策的兩個解，則定理7.3(可交換性）若和是矩陣對策的兩個解，則和也是矩陣對策的解。例7.4設矩陣對策，其中，，。支付矩陣A如下，試求對策的解。10-解：直接在提供的支付矩陣上計算有其中，，所以、、和四個局勢都是對策的解，且vG=5。11-7.1.2無鞍點的對策策略—混合對策如果支付矩陣有鞍點，選擇鞍點對策是最優(yōu)的對策策略，如果支付矩陣無鞍點，則需要選擇混合對策。再看例7.1，對于支付矩陣（見表7-1），有。沒有純最優(yōu)策略，因此無法用定理7.1來確定最優(yōu)策略。在此情況下，只能求相應的混合策略。類似于純策略，混合策略有如下定義和定理。定義7.3設有矩陣對策，稱（7-4）分別為局中人I和II的混合策略，稱為一個混合局勢,稱為局中人I的支付函數(shù)（贏得函數(shù)）。因此,稱為對策G的混合擴充。（7-5）12-定義7.4設是的混合擴充，若(7-7)則稱vG為對策G的值，稱使式(7-7)成立的混合局勢(x*,y*)為G在混合策略下的解，稱x*和y*分別為局中人I和II的最優(yōu)混合策略。定理7.4矩陣對策在混合策略意義下有解的充分必要條件是：存在，使(x*,y*)為函數(shù)的一個鞍點，即(7-8)該定理說明，如果一個局中人單方面不論采取何種純策略都不能增加自己的贏得，則該局勢為對策的解；反之亦然。13-定理7.5設，則(x*,y*)是對策G的解的充要條件是存在正數(shù)v使得x*,y*

分別是不等式組和的解，且v=vG定義7.5設，，，如果對任意j=1,2,…,n有，則稱局中人I的純策略優(yōu)超于純策略。類似地，可以定義局中人II的純策略優(yōu)超于。定理7.6對任一矩陣，對策一定存在混合策略意義下的解。14-定理7.7設，如果純策略被其余的純策略中之一所優(yōu)超,由G可得一個新矩陣對策,其中,(;)，則有（1）vG’=vG

；（2）G'

中局中人II的最優(yōu)策略就是其在G

中的最優(yōu)策略；（3）若是G'中局中人I的最優(yōu)策略，則就是局中人I在G中的最優(yōu)策略。推論：在定理7.7中，若不是為純策略中之一所優(yōu)超，而是為的某個凸線性組合所優(yōu)超，定理的結(jié)論仍然成立。15-定理7.7實際上給出了一個化簡支付（贏得）矩陣A的原則，稱為優(yōu)超原則。根據(jù)此原則，當局中人I的某純策略被其他純策略或純策略的凸線性組合所優(yōu)超時，可在矩陣A中劃去第i行而得到一個與原對策G等價但贏得矩陣階數(shù)較小的對策G'，而G'的求解往往比G的求解容易些，通過求解G'而得到G的解。類似地，對于局中人II來說，可以在贏得矩陣A中劃去被其他列或其他列的凸線性組合所優(yōu)超的那些列。16-7.1.3混合對策的線性方程組求解方法和設有矩陣對策，由定理7.6知一定存在混合策略意義下的解(x*,y*)，又由定理7.5得，(x*,y*)為G的解的充要條件是存在v使x*,y*分別為的解，且v=vG，而且可以證明：當時，x*,y*分別為

和的解。17-例7.5設贏得矩陣為A，求解此矩陣對策。解：由于第4行優(yōu)超于第1行，第3行優(yōu)超于第2行，故可以劃掉第1行和第2行，得到新的贏得矩陣對于A1，第1列優(yōu)超于第3列，第2列優(yōu)超于第4列，1/3(第1列)+2/3(第2列)優(yōu)超于第5列，因此去掉第3、4、5列，得到這時，第1行又優(yōu)超于第3行，故從A2中劃去第3行，得到18-對于A3，易知無鞍點存在，應用定理7.5，求解以下兩個不等式組首先考慮滿足和的非負解。求得解為，，。因此，原矩陣對策的一個解為19-練習1：求解下列矩陣對策根據(jù)贏得矩陣有所以G的解為20-練習2：求解下列矩陣對策由于第3行優(yōu)超于第2行，第4行優(yōu)超于第1行，故可劃去第1、2行，得到新的贏得矩陣對于A1，第2列優(yōu)超于第3、4、5列，得到對于A2，第1行優(yōu)超于第3行，故可劃去第3行，得到21-A3沒有鞍點，故求解所以原矩陣對策的一個解為：22-7.1.4混合對策的線性規(guī)劃求解方法設局中人I分別以的概率混合使用他的m種策略，局中人II分別以的概率混合使用他的n種策略。當I采用混合策略，II分別采用純策略，I的贏得分別為，依據(jù)最大最小原則，應有(7-9)其中vI是局中人I的贏得值。將問題(7-9)寫成線性規(guī)劃問題：(7-10)即線性規(guī)劃問題（7-10）的解就是局中人I采用混合策略的解。23-類似地，求局中人II的最優(yōu)策略轉(zhuǎn)化為求解下列線性規(guī)劃問題：s.t.因此，線性規(guī)劃問題(7-11)的解就是局中人II采用混合策略的解。(7-11)24-例：利用線性規(guī)劃方法求解如下的矩陣對策所以A所對應的支付矩陣沒有純對策。采用線性規(guī)劃方法求解其最優(yōu)混合策略，求解局中人I的最優(yōu)策略轉(zhuǎn)化為求解以下的LP問題局中人Ⅱ25-MODEL:sets:playerI/1..6/:x;playerII/1..6/;game(playerI,playerII):A;endsetsdata:A=31111-11311-111-13111-11131111-1131111-113;enddatamax=vI;@free(vI);@for(playerII(j):@sum(playerI(i):A(i,j)*x(i))>=vI);@sum(playerI:x)=1;END程序的第16行@free(vI)表示變量vI沒有非負約束，求得最優(yōu)解（只保留相關部分）：*例7.6用線性規(guī)劃方法求解例7.1的最優(yōu)混合策略。解：對于局中人齊王，按照線性規(guī)劃(7-10)寫出相應的LINGO程序26-Globaloptimalsolutionfound.Objectivevalue:1.000000Totalsolveriterations:3VariableValueReducedCostVI1.0000000.000000X(1)0.33333330.000000X(2)0.0000000.000000X(3)0.0000000.000000X(4)0.33333330.000000X(5)0.0000000.000000X(6)0.33333330.000000即齊王以1/3的概率出（上、中、下）、（中、下、上）、（下、上、中）中每種策略的一種，其贏得值為1，即在公平對策時，結(jié)局是齊王贏田忌，齊王贏得為1000兩黃金。對于局中人田忌的計算也會出現(xiàn)相同的結(jié)果。27-在此需要指出，對于一個具有鞍點的對策問題，同樣也可以采用線性規(guī)劃方法來進行求解。*例7.7用線性規(guī)劃方法求解例7.2。解：寫出的LINGO程序清單如下MODEL:sets:playerI/1..3/:x;playerII/1..3/;game(playerI,playerII):A;endsetsdata:A=139657842;enddatamax=vI;@free(vI);@for(playerII(j):@sum(playerI(i):A(i,j)*x(i))>=vI);@sum(playerI:x)=1;ENDGlobaloptimalsolutionfound.Objectivevalue:5.000000Totalsolveriterations:4VariableValueReducedCostVI5.0000000.000000X(1)0.0000002.000000X(2)1.0000000.000000X(3)0.0000001.00000028-7.2雙矩陣對策模型雙矩陣對策也稱為二人非常數(shù)和對策。在前面介紹的常數(shù)和（零和）對策中，均包含兩種情況，純策略和混合策略。對于非常數(shù)和對策，也包含這兩種策略。7.2.1純對策問題例7.8囚徒困境問題設有兩名嫌疑犯因同一樁罪行被捕，由于希望他們坦白并提供對方的犯罪證據(jù)，規(guī)定如果兩人均坦白各判刑3年；如果一方坦白另一方不坦白，坦白一方從輕釋放，不坦白一方判刑10年；如果兩人均不坦白，由于犯罪事實很多不能成立，只能各判1年。試分析甲、乙兩犯罪嫌疑人各自采用什么策略使自己的刑期最短。29-假設囚犯I與II的第一個策略都是坦白認罪，第二個策略則是拒不交代，以對它們判處監(jiān)禁的年數(shù)表示他們的贏得，則它們的贏得矩陣為通常規(guī)定，雙矩陣中，第一個元素是局中人I的贏得值，第二個元素是局中人II的贏得值。問題分析這是一個二人非常數(shù)和對策問題。從表面上看，兩犯罪嫌疑人拒不坦白，只能被判1年徒刑，結(jié)果是最好的。但仔細分析，卻無法做到這一點。因為犯罪嫌疑人I如果采用不坦白策略，他可能被判的刑期為1到10年，而犯罪嫌疑人II可能判的刑期為0到1年；而甲選擇坦白，他被判的刑期為0到3年，此時，犯罪嫌疑人II可能判的刑期為3到10年。因此，犯罪嫌疑人I一定選擇坦白?；谕瑯拥牡览?，犯罪嫌疑人II也只能選擇坦白。選擇坦白是他們最好的選擇，各自被判3年。30-設是局中人I和II的贏得值，則I和II采用的策略是對于一般純對策問題，局中人I、II的支付（贏得）矩陣如表7-4所示，其中局中人I有m個策略，局中人II有n個策略，分別記為31-為局中人I的支付（贏得）矩陣，為局中人II的支付（贏得）矩陣，矩陣對策記為，或定義7.6設是一雙矩陣對策，若等式(7-12)成立，則記，并稱vI

為局中人I的贏得值，記，并稱vII為局中人II的贏得值。稱為G在純策略下的解（或Nash平衡點），稱和分別為局中人I、II的最優(yōu)純策略。32-2.純對策問題的求解方法

例7.9夫妻愛好的爭執(zhí)問題由于夫妻雙方的愛好不同，經(jīng)常會有一些爭執(zhí)出現(xiàn)。例如一個新婚家庭中的丈夫（局中人I）業(yè)余時間愛好看足球賽（策略1），而妻子（局中人II）業(yè)余時間喜歡看電視大片（策略2）。在一段時間里，每個周末體育場都有精彩足球賽，同時電視臺也正上映妻子最喜歡的每周一次的精彩大片。由于夫婦倆都希望一起度周末，但各自的喜好不同，這就發(fā)生了爭執(zhí)。夫妻雙方究竟是一起看足球賽還是一起在家看大片，只要在一起就比分開好，對二人來說，在一起看自己喜歡的比看不喜歡的好。夫妻雙方的贏得矩陣為如果兩人每次選擇決策都不事先商量，則這對夫妻應該如何來選擇，即怎樣度過周末？解：由定義7.6可知，對于策略((1,0),(1,0))或策略((0,1),(0,1))均是Nash平衡點，也就是最優(yōu)解，即他們選擇共同看足球，或共同看大片。33-7.2.2混合對策問題1．混合對策問題的基本概念定義7.7在對策中，若存在策略，使得(7-13)則稱為G的一個非合作平衡點，記，，則稱分別為局中人I、II的贏得值。定理7.8每個雙矩陣對策至少存在一個非合作平衡點。定理7.9混合策略為對策的平衡點的充分必要條件是(7-14)34-VA=(14*X1*Y1+13*X1*Y2+12*X1*Y3+13*X2*Y1+12*X2*Y2+12*X2*Y3+12*X3*Y1+12*X3*Y2+13*X3*Y3);VB=(13*X1*Y1+14*X1*Y2+15*X1*Y3+14*X2*Y1+15*X2*Y2+15*X2*Y3+15*X3*Y1+15*X3*Y2+14*X3*Y3);B1B2B3A1(14,13)(13,14)(12,15)A2(13,14)(12,15)(12,15)A3(12,15)(12,15)(13,14)列出求解下列雙矩陣對策混合策略的不等式組14*Y1+13*Y2+12*Y3<=VA;13*Y1+12*Y2+12*Y3<=VA;12*Y1+12*Y2+13*Y3<=VA;13*X1+14*X2+15*X3<=VB;14*X1+15*X2+15*X3<=VB;15*X1+15*X2+14*X3<=VB;X1+X2+X3=1;Y1+Y2+Y3=1;35-2.混合對策問題的求解方法由定義7.7可知，求解混合對策就是求非合作對策的平衡點。進一步由定理7.9得到，求解非合作對策的平衡點，就是求解滿足不等式約束(7-14)的可行點。因此，混合對策問題的求解問題就轉(zhuǎn)化為求不等式約束(7-14)的可行點，而LINGO軟件可以很容易做到這一點。*例7.10有甲、乙兩支游泳隊舉行包括三個項目的對抗賽。這兩支游泳隊各有一名健將級運動員（甲隊為李，乙隊為王），在三個項目中成績很突出，但規(guī)則準許他們每個人分別只能參加兩項比賽，而每隊的其他兩名運動員則可參加全部三項比賽，各運動員的成績?nèi)绫?-5所示甲隊乙隊趙錢李王張孫100m蝶泳54.758.252.153.656.459.8100m仰泳62.263.458.256.559.761.5100m蛙泳69.170.565.367.868.471.336-解：分別用甲1、甲2和甲3表示甲隊中李姓健將不參加蝶泳、仰泳、蛙泳比賽的策略，分別用乙l、乙2和乙3表示乙隊中王姓健將不參加蝶泳、仰泳、蛙泳比賽的策略。當甲隊采用策略甲1，乙隊采用策略乙1時，在l00m蝶泳中，甲隊中趙獲第一、錢獲第三得6分，乙隊中張獲第二，得3分；在l00m仰泳中，甲隊中李獲第二，得3分，乙隊中王獲第一、張獲第三，得6分；在l00m蛙泳中，甲隊中李獲第一，得5分，乙隊中王獲第二、張獲第三，得4分。也就是說，對應于策略（甲1，乙1），甲、乙兩隊各自的得分為（14,13）。乙1乙2乙3甲1(14,13)(13,14)(12,15)甲2(13,14)(12,15)(12,15)甲3(12,15)(12,15)(13,14)甲隊乙隊趙錢李王張孫100m蝶泳54.758.252.153.656.459.8100m仰泳62.263.458.256.559.761.5100m蛙泳69.170.565.367.868.471.3表7-6中給出了在全部策略下各隊的得分。37-按照定理7.9，求最優(yōu)混合策略，就是求不等式約束(7-14)的可行解，相應的LINGO程序清單如下。MODEL:sets:optA/1..3/:x;optB/1..3/:y;AxB(optA,optB):Ca,Cb;endsetsdata:Ca=141312131212121213;Cb=131415141515151514;enddataVa=@sum(AxB(i,j):Ca(i,j)*x(i)*y(j));Vb=@sum(AxB(i,j):Cb(i,j)*x(i)*y(j));@for(optA(i):@sum(optB(j):Ca(i,j)*y(j))<=Va);@for(optB(j):@sum(optA(i):Cb(i,j)*x(i))<=Vb);@sum(optA:x)=1;@sum(optB:y)=1;@free(Va);@free(Vb);END38-Feasiblesolutionfound.Extendedsolversteps:0Totalsolveriterations:10VariableValueVA12.50000VB14.50000X(1)0.5000000X(2)0.000000X(3)0.5000000Y(1)0.000000Y(2)0.5000000Y(3)0.5000000即甲隊采用的策略是甲1、甲3方案各占50％，乙隊采用的策略是乙2、乙3方案各占50％，甲隊的平均得分為12.5分，乙隊的平均得分為14.5分。39-當純對策的解不惟一時，也存在混合對策的平衡點。*例7.11用混合對策方法求解例7.9。解：寫出求不等式(7-14)的LINGO程序如下：MODEL:sets:optA/1..2/:x;optB/1..2/:y;AxB(optA,optB):Ca,Cb;endsetsdata:Ca=3-1-11;Cb=1-1-13;enddataVa=@sum(AxB(i,j):Ca(i,j)*x(i)*y(j));Vb=@sum(AxB(i,j):Cb(i,j)*x(i)*y(j));@for(optA(i):@sum(optB(j):Ca(i,j)*y(j))<=Va);@for(optB(j):@sum(optA(i):Cb(i,j)*x(i))<=Vb);@sum(optA:x)=1;@sum(optB:y)=1;@free(Va);@free(Vb);END40-Feasiblesolutionfound.Extendedsolversteps:0Totalsolveriterations:8VariableValueVA0.3333333VB0.3333333X(1)0.6666667X(2)0.3333333Y(1)0.3333333Y(2)0.6666667計算得到混合對策的平衡點（(2/3,1/3),(1/3,2/3)），各自的贏得值為1/3。從上述分析來看，二人常數(shù)和對策是非常數(shù)和對策的特例，因此也可以用求解非常數(shù)和對策的方法求解常數(shù)和對策。41-例7.12兩家電視臺在黃金時段競爭100萬電視觀眾收看自己的電視節(jié)目，并且電視臺必須實時公布自己在下一時段的展播內(nèi)容。電視臺1可能選擇的展播方式及可能得到的觀眾如表7-7所示。電視臺2min西部片連續(xù)劇喜劇片電視臺1西部片35156015連續(xù)劇45585045喜劇片38147014max455870例如，兩家電視臺都選擇播放西部片，則表7-7表明，電視臺1可以爭得35萬觀眾，而電視臺2可以爭得100-35=65萬觀眾，即二人的常數(shù)和為100。試確定兩家電視臺各自的策略。表7-742-解：若完全采用二人常數(shù)和對策的方法確定最優(yōu)純策略，則由可得，電視臺1選擇播放連續(xù)劇，贏得45萬觀眾，電視臺2播放西部片，贏得100-45=55萬觀眾。*如果用求解非常數(shù)和對策的方法求解以上的問題，則相應的LINGO程序清單如下：sets:optA/1..3/:x;optB/1..3/:y;AxB(optA,optB):Ca,Cb;endsetsdata:Ca=351560455850381470;Cb=658540554250628630;enddataVa=@sum(AxB(i,j):Ca(i,j)*x(i)*y(j));Vb=@sum(AxB(i,j):Cb(i,j)*x(i)*y(j));@for(optA(i):@sum(optB(j):Ca(i,j)*y(j))<=Va);@for(optB(j):@sum(optA(i):Cb(i,j)*x(i))<=Vb);@sum(optA:x)=1;@sum(optB:y)=1;@free(Va);@free(Vb);END43-Feasiblesolutionfound.Extendedsolversteps:0Totalsolveriterations:24VariableValueVA45.00004VB55.00005X(1)0.000000X(2)1.000001X(3)0.000000Y(1)0.9999916Y(2)0.000000Y(3)0.8421006E-05即局中人I（電視臺1）采用第二種策略，贏得45萬觀眾，局中人II（電視臺2）采用第一種策略，贏得55萬觀眾，與前面計算的結(jié)果相同。44-7.3n人合作對策初步例7.13甲有一件廢舊物品，對他自己來說，已無任何價值，即價值為0元。甲將此廢舊物品拿到舊貨市場上進行出售，有乙和丙兩個買主分別出價20元和30元若購買此物品，即對乙和丙來說，此物品的價值分別是20元和30元。試建立三人合作對策，使得每人的利益最大。解：設甲、乙、丙三人的價值分別為x1,x2,x3，因此對于每個人來說，此廢舊物品的價值均為0，即v{1}=v{2}=v{3}=0。如果甲與乙合作，其價值為20，甲與丙合作，其價值為30，乙與丙合作，其價值仍為0。因此有。但三人合作的總價值為30，即