第四章_對策論

1、運運 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外運運 籌籌 學學 課課 件件對對 策策 論論Game TheoryGame Theory 第一節(jié)第一節(jié) 對策論的基本概念和分類對策論的基本概念和分類發(fā)發(fā) 展展 簡簡 史史1912年年E.Zermelo “關(guān)于集合論在象棋對策中的應用關(guān)于集合論在象棋對策中的應用”1921年年E.Borel 引入最優(yōu)策略引入最優(yōu)策略1928年年J.V.Neumann證明了一些猜想證明了一些猜想 博奕論博奕論( Game Theory)也就是運籌學中的對策論。也就是運籌學中的對策論。 對策思想最早產(chǎn)生于我國古代。對策思想最早產(chǎn)生于我國古代。 早在兩

2、千多年前的春秋時期，孫武在早在兩千多年前的春秋時期，孫武在孫子兵法孫子兵法中論述的軍事思想和治國策略，就蘊育了豐富和深中論述的軍事思想和治國策略，就蘊育了豐富和深刻的對策論思想。孫武的后代孫臏，為田忌謀劃，刻的對策論思想。孫武的后代孫臏，為田忌謀劃，巧勝齊王，這個著名的巧勝齊王，這個著名的“田忌賽馬田忌賽馬”，就是典型的，就是典型的對策思想的成功運用。對策思想的成功運用。 產(chǎn)生標志產(chǎn)生標志作為一門學科的創(chuàng)立，則是以美國數(shù)學家馮作為一門學科的創(chuàng)立，則是以美國數(shù)學家馮.諾依曼諾依曼(John Von Neumann)和經(jīng)濟學家奧斯卡和經(jīng)濟學家奧斯卡.摩根斯坦摩根斯坦(Oskar Morgenste

3、rn)合著的合著的博奕論與經(jīng)濟行為博奕論與經(jīng)濟行為(The Game Theory and Economic Behavior) (1944)一書出版為標志，他們奠定和形成了這門學科的理一書出版為標志，他們奠定和形成了這門學科的理論與方法論基礎(chǔ)。論與方法論基礎(chǔ)。 發(fā)展成熟發(fā)展成熟 Nash均衡、經(jīng)濟博奕論、信息不對稱對策和廣義均衡、經(jīng)濟博奕論、信息不對稱對策和廣義對策對策基本概念基本概念在策略型博奕中，一個對策有以下幾種基本要素：在策略型博奕中，一個對策有以下幾種基本要素：一局中人一局中人(players)： 即博奕的參與者，他們是博奕的決策主體。根據(jù)自己的利益即博奕的參與者，他們是博奕的決策

4、主體。根據(jù)自己的利益要求決定自己的決策，記第要求決定自己的決策，記第i個局中人為個局中人為i，局中人集合為，局中人集合為1,2,I，即共有，即共有I個局中人。我們將某個局中人以外的其它個局中人。我們將某個局中人以外的其它局中人稱為局中人稱為“i的對手的對手”，記為，記為-i。 對策中利益一致的參加者只能看成一個局中人，例：橋牌中對策中利益一致的參加者只能看成一個局中人，例：橋牌中的東、西兩方。的東、西兩方。 對策論中對局中人的一個重要假設(shè)：每個局中人都是對策論中對局中人的一個重要假設(shè)：每個局中人都是“理智理智的的”，即每一個局中人都不存在僥幸心理，不存在利用其他，即每一個局中人都不存在僥幸心理

5、，不存在利用其他局中人決策的失誤來擴大自身利益的行為。局中人決策的失誤來擴大自身利益的行為。在策略型博奕中，一個對策有以下幾種基本要素：在策略型博奕中，一個對策有以下幾種基本要素：一局中人一局中人 即指每個局中人在對策中可以選擇采用的行動即指每個局中人在對策中可以選擇采用的行動方案，但這個方案必須是一個完整的行動，而不是方案，但這個方案必須是一個完整的行動，而不是行動的某一步。每個局中人均有可供選擇的多種策行動的某一步。每個局中人均有可供選擇的多種策略。略。 二策略二策略(strategies)： 基本概念基本概念三支付或收益三支付或收益(payoffs): 二策略二策略一局中人一局中人在策略

6、型博奕中，一個對策有以下幾種基本要素：在策略型博奕中，一個對策有以下幾種基本要素： 是指一局博奕的得失?；蛘哒f是局中人從各種策是指一局博奕的得失?；蛘哒f是局中人從各種策略組合中獲得的效用，它是策略組合的函數(shù)。如果略組合中獲得的效用，它是策略組合的函數(shù)。如果局中人得失的總和為零，則稱這種對策為局中人得失的總和為零，則稱這種對策為零和對策零和對策（博弈）；（博弈）；否則，稱為否則，稱為非零和對策非零和對策(博奕博奕)。 基本概念基本概念局勢：局勢：一個對策中，每一個局中人所出策略形成的一個對策中，每一個局中人所出策略形成的策略組稱為一個局勢。策略組稱為一個局勢。 設(shè)設(shè)si是第是第i個局中人的一個策

7、略，則個局中人的一個策略，則n個局中人的策略個局中人的策略形成的策略組形成的策略組s=s1,s2,sn,就是一個局勢。就是一個局勢。全部局勢的集合全部局勢的集合S記為：記為：nSSSS .21模模 型型局中人局中人 兩個或兩個以上兩個或兩個以上-決策者決策者策略集合策略集合 策略策略-決策決策 局勢局勢-狀態(tài)狀態(tài)支付函數(shù)支付函數(shù) 支付關(guān)于局勢的函數(shù)支付關(guān)于局勢的函數(shù)-決策依據(jù)和標準決策依據(jù)和標準 模型模型SsnisHi ,.,2 , 1);( IisHIiSNIii),(,.,2 , 1 niSi,.,2 , 1; ,.,2 , 1nI iniSS 1 分分 類類 局中人局中人 兩人對策、多人

8、對策兩人對策、多人對策 策略策略 有限對策、無限對策；非合作對策、合作對策有限對策、無限對策；非合作對策、合作對策 支付支付 零和對策、非零和對策零和對策、非零和對策 時間時間 單階段對策、多階段對策單階段對策、多階段對策對策模型眾多，但占有重要地位的是二人有限零和對策模型眾多，但占有重要地位的是二人有限零和對策（矩陣對策）。它是一類最簡單的對策模型，對策（矩陣對策）。它是一類最簡單的對策模型， 它的結(jié)果也是研究其他對策模型的基礎(chǔ)。它的結(jié)果也是研究其他對策模型的基礎(chǔ)。 第二節(jié)第二節(jié)二人有限零和對策模型二人有限零和對策模型 二人有限零和對策二人有限零和對策二人二人：參加對策的局中人有兩個；：參加

9、對策的局中人有兩個；有限有限：局中人的策略集都為有限集；：局中人的策略集都為有限集；零和零和：在任一局勢下，兩個局中人的贏得之和總等于在任一局勢下，兩個局中人的贏得之和總等于0，即，即，一個局中人的所得值恰好是另一個局中人的所失值，雙方的一個局中人的所得值恰好是另一個局中人的所失值，雙方的利益是完全對抗的。利益是完全對抗的。設(shè)局中人設(shè)局中人I和和II的策略集分別為的策略集分別為,.,211mS ,.,212nS 對任一純局勢對任一純局勢),(ji ，記局中人，記局中人I的贏得值為的贏得值為ija則則I的贏得矩陣為的贏得矩陣為 mnmmnnaaaaaaaaaA212222111211例：甲、乙各

10、出示一枚硬幣，在不讓對方看見的情況例：甲、乙各出示一枚硬幣，在不讓對方看見的情況下，將硬幣放在桌子上，若兩個硬幣都呈正面或都下，將硬幣放在桌子上，若兩個硬幣都呈正面或都呈反面則甲得呈反面則甲得1分，乙付出分，乙付出1分；若兩個硬幣一個呈分；若兩個硬幣一個呈正面另一個呈反面則乙得正面另一個呈反面則乙得1分，甲付出分，甲付出1分分局中人局中人：甲、乙：甲、乙 1111A甲的贏得矩陣為甲的贏得矩陣為例例（齊王與田忌賽馬）（齊王與田忌賽馬）這個問題中齊王和田忌各自擁有的策略為：這個問題中齊王和田忌各自擁有的策略為：S1=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下

11、中上),(下上中下上中)S2=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)則對應的齊王的贏得矩陣為則對應的齊王的贏得矩陣為 311111131111113111111311111131111113A例：甲乙兩人玩猜拳游戲，游戲中雙方同時分別出石例：甲乙兩人玩猜拳游戲，游戲中雙方同時分別出石頭、布或剪刀。規(guī)則是剪刀贏布，布贏石頭，石頭頭、布或剪刀。規(guī)則是剪刀贏布，布贏石頭，石頭贏剪刀，贏者得一分。若出的相同，算和局都不得贏剪刀，贏者得一分。若出的相同，算和局都不得分。試列出甲的贏得矩陣。分。試列出甲的贏得矩陣。石頭布剪刀石頭0-11布

12、10-1剪刀-110甲乙第三節(jié)第三節(jié)矩陣對策的純策略矩陣對策的純策略例：設(shè)有一矩陣對策例：設(shè)有一矩陣對策;,21ASSG 其中其中 6031019423816A解：對局中人解：對局中人I而言，最大贏得是而言，最大贏得是9，若想得到這個贏得，若想得到這個贏得，他要選擇純策略他要選擇純策略 ，由于局中人，由于局中人II也是理智的競爭也是理智的競爭者，他已考慮到局中人者，他已考慮到局中人I打算出打算出 的心理，則準備的心理，則準備以以 對付之，使局中人對付之，使局中人I不但得不到不但得不到9，反而失掉，反而失掉10.局中人局中人I當然也會猜到局中人當然也會猜到局中人II的心理，故而出的心理，故而出

13、來對付，使局中人來對付，使局中人II得不到得不到10，反而失掉，反而失掉6，3 3 3 4 如果雙方都不想冒險，都不存在僥幸心理，而是考慮到對方必然如果雙方都不想冒險，都不存在僥幸心理，而是考慮到對方必然會設(shè)法使自己所得最少這一點，就應該從各自可能出現(xiàn)的最不利會設(shè)法使自己所得最少這一點，就應該從各自可能出現(xiàn)的最不利的情形中選擇一個最有利的情形作為決策的依據(jù)，這就是所謂的的情形中選擇一個最有利的情形作為決策的依據(jù)，這就是所謂的“理智行為理智行為”，也是對策雙方實際上可以接受并采取的一種穩(wěn)妥，也是對策雙方實際上可以接受并采取的一種穩(wěn)妥方法。方法。對策雙方處于完全對抗的環(huán)境中，因此，各自都采取保守態(tài)

14、對策雙方處于完全對抗的環(huán)境中，因此，各自都采取保守態(tài)度，從最壞處著眼，并力爭較好的結(jié)局。所以，局中人度，從最壞處著眼，并力爭較好的結(jié)局。所以，局中人A采用采用maxmin準則，局中人準則，局中人B采用采用minmax準則。準則。相應于這種準則下，對策雙方采取的各自的策略稱為相應于這種準則下，對策雙方采取的各自的策略稱為對策的解對策的解。雙方采取上述策略，連續(xù)重復進行對策，其輸贏的平均值稱為雙方采取上述策略，連續(xù)重復進行對策，其輸贏的平均值稱為相應對策問題的對策值相應對策問題的對策值，記為，記為v對策問題選擇解的準則對策問題選擇解的準則maa ,.,1b1b2bna1c11c12c1na2c21

15、c22c2namcm1cm2cmn設(shè)局中人設(shè)局中人A的策略有的策略有 ，局中人，局中人B的策略有的策略有 ，A的贏得矩陣為的贏得矩陣為nbb ,.,1maxmin準則準則:當當A依據(jù)此原則選擇策略時，總考慮不管選哪一個策略依據(jù)此原則選擇策略時，總考慮不管選哪一個策略都將得到最壞的結(jié)局。即都將得到最壞的結(jié)局。即minmaxmin,.,min,minmax21ijjimjjjjjjiaccccv minmax準則準則:當當B依據(jù)此原則選擇策略時，總考慮不管選哪一個策略依據(jù)此原則選擇策略時，總考慮不管選哪一個策略都將得到最壞的結(jié)局（最大損失）。即都將得到最壞的結(jié)局（最大損失）。即maxminmax,

16、.,max,maxmin21ijijiniiiiijbccccv 均均 衡衡 解解按照這個定義，例中的均衡解為按照這個定義，例中的均衡解為),(22 繼續(xù)分析前例繼續(xù)分析前例:此時的平衡局勢此時的平衡局勢 ，對應的值，對應的值 既是其所在既是其所在行的最小元素，又是其所在列的最大元素，即有行的最小元素，又是其所在列的最大元素，即有),(22 22a3 , 2 , 1;4 , 3 , 2 , 1,2222 jiaaaji一般地，有如下定義和結(jié)論：一般地，有如下定義和結(jié)論：證明：證明： 略略注注以上定理的對策意義為：一個平衡局勢以上定理的對策意義為：一個平衡局勢 應該應該具有這樣的性質(zhì)：當局中人具

17、有這樣的性質(zhì)：當局中人A選擇了策略選擇了策略 后，后，局中人局中人B為了使其損失最小，只能選擇策略為了使其損失最小，只能選擇策略 ，否，否則就可能損失更多；反之，當局中人則就可能損失更多；反之，當局中人B選擇了策略選擇了策略 后，局中人后，局中人A為了得到最大贏得也只能選擇策略為了得到最大贏得也只能選擇策略 否則就會贏得較少，雙方的競爭在局勢否則就會贏得較少，雙方的競爭在局勢 下達下達到了一個平衡狀態(tài)。到了一個平衡狀態(tài)。),(*jiba*ia*jb*jb*ia),(*jiba例例 子子例例 子子例例 求下面的矩陣對策的解求下面的矩陣對策的解 26205758124156565maxminmin

18、max* jiijijijjiccc解：計算解：計算此時，此時，i*=1,3;j*=2,4所以，所以，(a1,b2),(a1,b4),(a2,b2),(a2,b4)都是對策的解。都是對策的解。由以上例子知，對策的均衡解不見得唯一，當解不唯由以上例子知，對策的均衡解不見得唯一，當解不唯一時，解之間的關(guān)系有以下性質(zhì)：一時，解之間的關(guān)系有以下性質(zhì)：性質(zhì)性質(zhì)1（無差別性）若（無差別性）若 和和 是對策是對策G的兩個的兩個解，則解，則),(11ji ),(22ji 2211jijiaa 性質(zhì)性質(zhì)2（可交換性）若（可交換性）若),(11ji ),(22ji 是對策是對策G的兩個解的兩個解則則),(21ji

19、 ),(12ji 也是對策的解。也是對策的解。 第三節(jié)第三節(jié) 優(yōu)勢原則優(yōu)勢原則和具有混和策略的矩陣對策和具有混和策略的矩陣對策對一個矩陣對策對一個矩陣對策;,21ASSG 由前面討論知，局中人由前面討論知，局中人I能保證的至少贏得為能保證的至少贏得為ijjiavminmax1 局中人局中人II能保證的至多損失為能保證的至多損失為ijijavmaxmin2 所以，總有所以，總有21vv 當當21vv 時，對策在純策略意義下有解時，對策在純策略意義下有解21vvv 當當21vv 時，對策在純策略意義下沒有解，此時情況時，對策在純策略意義下沒有解，此時情況如以下例中所述。如以下例中所述。例：如下是二

20、人零和對策的支付矩陣例：如下是二人零和對策的支付矩陣b1b2a114a232分析發(fā)現(xiàn)：分析發(fā)現(xiàn)：2)2 , 3min(),4 , 1maxmin( av3)2 , 4max(),3 , 1minmax( bv此時若還使用純策略，雙方按照從最不利情形中選擇此時若還使用純策略，雙方按照從最不利情形中選擇最有利情形的原則，應分別選擇最有利情形的原則，應分別選擇a2和和b1,此時局中人此時局中人I的的贏得是贏得是3，比至少贏得多了，比至少贏得多了1，這是因為局中人，這是因為局中人II選擇了選擇了b1，才使得局中人，才使得局中人I得到了不該得到的贏得，顯然局中得到了不該得到的贏得，顯然局中人會考慮出人會

21、考慮出b2,讓局中人讓局中人I的贏得變?yōu)榈内A得變?yōu)?，而此時局中人，而此時局中人I又又會選擇會選擇a1，使得自己的贏得為，使得自己的贏得為4，如此下去就會出現(xiàn)不穩(wěn)定狀態(tài)。如此下去就會出現(xiàn)不穩(wěn)定狀態(tài)。解決此問題的想法很自然，既然局中人都沒有最優(yōu)策略解決此問題的想法很自然，既然局中人都沒有最優(yōu)策略可出，可否給出一個選擇不同策略的概率分布，以達到可出，可否給出一個選擇不同策略的概率分布，以達到一種平衡狀態(tài)呢，這就是混合策略。一種平衡狀態(tài)呢，這就是混合策略。定義：混和策略定義：混和策略設(shè)有矩陣對策設(shè)有矩陣對策G=S1,S2;A,其中其中nmijnmcAbbSaaS )(,.,.,12111;,.,1,

22、 01*1 miiimxmixExS1;,.,1, 01*2 niiinyniyEyS記記則稱則稱*2*1,SS為局中人為局中人A，B的的混和策略集混和策略集，稱，稱x,y為為混混和策略和策略，（，（x,y）為）為混和局勢混和局勢。局中人。局中人A的贏得函數(shù)為：的贏得函數(shù)為： minjjiijyxcyxE11),(稱稱;,*2*1*ESSG 為對策為對策G的的混和擴充混和擴充。定義：混和策略意義下的解定義：混和策略意義下的解設(shè)設(shè)如果如果則稱則稱VG為對策為對策G的的值值，稱使得上式成立的混和局勢，稱使得上式成立的混和局勢;,*2*1*ESSG 是矩陣對策是矩陣對策G=S1,S2;A的混和擴充。

23、的混和擴充。GSxSySySxVyxEyxE ),(maxmin),(minmax*1*2*2*1（x*,y*）為）為G在混和策略意義下的在混和策略意義下的解（平衡局勢解（平衡局勢），），稱稱x*,y*分別為局中人分別為局中人A和和B的的最優(yōu)混和策略最優(yōu)混和策略。注注：當局中人：當局中人A選擇混和策略選擇混和策略x時，他的預期所得時，他的預期所得（按最小）是（按最?。┦?,(minmax*2*1yxEvSySxa ),(min*2yxESy 因此局中人因此局中人A應選取應選取*1Sx 使得使得同理，同理，B可保證損失的期望值可保證損失的期望值至多是至多是),(maxmin*1*2yxEvSxS

24、yb 顯然成立：顯然成立：bavv 和純策略類似，混合策略意義下同樣有解存在的鞍和純策略類似，混合策略意義下同樣有解存在的鞍點型充要條件：點型充要條件：定理定理1:矩陣對策在混和策略下有解的充要條件是：存在矩陣對策在混和策略下有解的充要條件是：存在*2*1*,SySx 使得對任意使得對任意*2*1,SySx 有有),(),(),(*yxEyxEyxE 例：考慮矩陣對策例：考慮矩陣對策;,21ASSG 4563A解：易知解：易知G在純策略意義下無解，所以，設(shè)在純策略意義下無解，所以，設(shè)),(),(2121yyyxxx 表示局中人表示局中人I，II的混合策略，則的混合策略，則1, 0,),( 1,

25、 0,),( 21212122121211 yyyyyySxxxxxxS局中人局中人I的贏得的期望是的贏得的期望是29)21)(41(4)1)(1(4)1(5)1(634563),(111111111122122111 yxyxyxyxyxyxyxyxyxyxE取取)21,21(),43,41( yx則則29),(),(,29),( yxEyxEyxE所以所以)21,21(),43,41( yx分別為局中人分別為局中人I，II的最優(yōu)策略。的最優(yōu)策略。若記若記 miiijnjjijxcjxEycyiE11),( ,),(則則E(i,y)為局中人為局中人A取純策略取純策略ai時的贏得值；時的贏得值

26、；E(x,j)為局為局中人中人B取純策略取純策略bj時的贏得值時的贏得值,且有且有 miiminjijijminjjiijxyiExycyxcyxE11111),()(),( njjnjmijiijminjjiijyjxEyxcyxcyxE11111),()(),(則得到一個和定理則得到一個和定理1等價的定理等價的定理2混合策略意義下求解方法的相關(guān)理論混合策略意義下求解方法的相關(guān)理論定理定理2:*2*1*,SySx (*).,(),(),(*jxEyxEyiE 則則),(*yx為對策為對策G的解的充要條件的解的充要條件為：對任意的為：對任意的i=1,2,m;j=1,2,n,有有證明：設(shè)證明：設(shè)

27、為對策為對策G的解，則由定理的解，則由定理1，成立，成立因為純策略是混合策略的特例，所以，（因為純策略是混合策略的特例，所以，（*）成立。）成立。),(*yx),(),(),(*yxEyxEyxE 反之，若（反之，若（*）成立，則）成立，則定理定理2說明：要驗證說明：要驗證),(*yx為對策為對策G的解時，只需要的解時，只需要對上式給出的有限個（對上式給出的有限個（mn）不等式進行驗證即可，）不等式進行驗證即可，大大簡化了驗證過程。大大簡化了驗證過程。如此，便有了下面的等價定理定理如此，便有了下面的等價定理定理3),(),(),(),( yxExyxExyiEyxEiiii),(),(),()

28、,( yxEyyxEyjxEyxEjjjj定理定理2得證。得證。定理定理3:*2*1*,SySx 則則),(*yx為：存在數(shù)為：存在數(shù)v，使得，使得為對策為對策G的解的充要條件的解的充要條件*, yx分別為不等式組分別為不等式組(1),(2)的解的解,且且v=VG)1.(,.,2 , 1, 01,.,2 , 1 ,11 mixxnjvxcimiimiiij)2.(,.,2 , 1, 01,.,2 , 1 ,11 njyymivycjnjjnjjij定理定理4:任一矩陣對策任一矩陣對策G，一定存在混和策略意義下，一定存在混和策略意義下的解。的解。證明證明:由定理由定理2知，只需證明存在知，只需證

29、明存在*2*1*,SySx 使得（使得（*）式成立。所以，考慮如下規(guī)劃問題）式成立。所以，考慮如下規(guī)劃問題 mixxnjwxcwPimiimiiij,.,2 , 1 , 01,.,2 , 1 ,max)(11 njyymivycvDjnjjnjjij,.,2 , 1 , 01,.,2 , 1 ,min)(11易知，規(guī)劃問題（易知，規(guī)劃問題（P）和（）和（D）互為對偶問題，且）互為對偶問題，且jjmTcwEx1min,)0,.,0 , 1( 1max,)0,.,0 , 1(iinTcvEy 分別為（分別為（P）和（）和（D）的一個可行解。由對偶定理知，）的一個可行解。由對偶定理知，他們都存在最優(yōu)

30、解，且最優(yōu)目標值相等。即，存在他們都存在最優(yōu)解，且最優(yōu)目標值相等。即，存在*2*1*,SySx 和和*wv 使得對任意的使得對任意的i=1,2,m;j=1,2,n有有 miiijnjjijxcvyc1*1*或或),(),(*jxEvyiE 又由又由*),(),(vxvxyiEyxEiiii *),(),(vyvyjxEyxEjjjj 得得),(*yxEv 所以所以,(*)得證。得證。定理定理5:設(shè)設(shè)),(*yx是矩陣對策是矩陣對策G的解，的解，v=VG，則，則vycxnjjiji 1*, 01則）若（vxcymiiijj 1*, 02則）若（0,3*1* injjijxvyc則）若（0,4*1

31、* jmiiijyvxc則）若（證明證明:由由),(max*1yxEvSx 有有0),(),(max*1 yiEyxEycvSxjjij又因為又因為0)(* ijjiijjjijiiyxcvycvx所以，當所以，當0* ix時，必有時，必有vycjjij *當當vycjjij *時，必有時，必有0* ix同理，可證（同理，可證（2），（），（4）。）。優(yōu)優(yōu) 超（優(yōu)勢原則）超（優(yōu)勢原則）給定矩陣對策給定矩陣對策,21ASS ，A是是nm 的矩陣，如果的矩陣，如果 njaaljkj,.,2 , 1, 則稱局中人則稱局中人 1 的策略的策略 k 優(yōu)超于策略優(yōu)超于策略 l。如果如果 miaailik,

32、.,2 , 1, 則稱局中人則稱局中人 2 的策略的策略 k 優(yōu)超優(yōu)超于策略于策略 l。 注注：局中人：局中人 1 的策略的策略 k 優(yōu)超于策略優(yōu)超于策略 l 則說明對局中人則說明對局中人 1 而言當其采用策略而言當其采用策略 k，無論局中人，無論局中人 2 采用和中策略，其采用和中策略，其 獲得都比采用策略獲得都比采用策略 l 來的好。來的好。因而策略出現(xiàn)的概率為因而策略出現(xiàn)的概率為 0， 可以在支付矩陣中刪除該策略對應的行可以在支付矩陣中刪除該策略對應的行. 算算 例例考慮矩陣對策的支付矩陣為考慮矩陣對策的支付矩陣為 8040243432430423 由于矩陣第三行的元素總是大于等于第一行

33、的對應元素，由于矩陣第三行的元素總是大于等于第一行的對應元素， 所以對于局中人所以對于局中人 1 而言策略而言策略 3 優(yōu)超于策略優(yōu)超于策略 1，因而策略，因而策略 1 出現(xiàn)的概率為出現(xiàn)的概率為 0，可以在支付矩陣中刪除該策略對應的行，可以在支付矩陣中刪除該策略對應的行， 對應的矩陣為對應的矩陣為 804024343243 簡簡 化化由由于于矩矩陣陣第第一一列列的的元元素素總總是是大大于于等等于于第第三三列列的的對對應應元元素素，所所以以對對于于局局中中人人 2 而而言言策策略略 3 優(yōu)優(yōu)超超于于策策略略 1， 因因而而策策略略 1 出出現(xiàn)現(xiàn)的的概概率率為為 0，可可以以在在支支付付矩矩陣陣中

34、中刪刪除除該該策策略略對對應應的的列列，對對應應的的矩矩陣陣為為 804243324 由由于于矩矩陣陣滿滿足足 )4 , 3 , 4()4 , 3 , 4()4 , 3 , 4(2121。所所以以對對于于局局中中人人 2 而而言言純純策策略略2優(yōu)優(yōu)超超于于混混合合策策略略)2/1 , 2/1 , 0 , 0(， 因因而而策策略略1出出現(xiàn)現(xiàn)的的概概率率為為0，可可以以在在支支付付矩矩陣陣中中刪刪除除該該策策略略對對應應的的列列，對對應應的的矩矩陣陣為為 802432 簡簡 化化由于矩陣滿足由于矩陣滿足 )8 , 0(2/1)2 , 4(2/1)3 , 2( 所以對于局中人所以對于局中人1而言策略

35、而言策略1被混合策略被混合策略)2/1 , 2/1 , 0 , 0(優(yōu)優(yōu)超，因而策略超，因而策略 1 出現(xiàn)的概率為出現(xiàn)的概率為 0，可以在支付矩陣中刪，可以在支付矩陣中刪除該策略對應的行，對應的矩陣為除該策略對應的行，對應的矩陣為 8024 該矩陣對策為最簡單對策，不能再簡化。該矩陣對策為最簡單對策，不能再簡化。 第四節(jié)第四節(jié) 混和策略的解法混和策略的解法方法方法1：圖解法：圖解法以分別表示局中人的第以分別表示局中人的第1、2純策略；表示局中人純策略；表示局中人的第的第1、2、3個純策略。個純策略。21,aa321,bbbAB設(shè)局中人采用混合策略，這里，當設(shè)局中人采用混合策略，這里，當代表純策

36、略；代表純策略。代表純策略；代表純策略。A)1 ,(xxX10 x1x1a0 x2a若局中人若局中人 采用純策略，當時，局中上人采用純策略，當時，局中上人A獲得的期望獲得的期望支付為，當支付為，當 時，局中人時，局中人A獲得的期望支付為獲得的期望支付為 ，連接直線，連接直線，則線段則線段 上點的縱坐標表示局中人采用混合策略上點的縱坐標表示局中人采用混合策略 ，而，而局中人采用純策略時的期望支付。局中人采用純策略時的期望支付。1xB1ba0 xdadadA)1 ,(xxXB1b 同樣同樣 ,和上點的縱坐標分別表示局中人采用混合策略和上點的縱坐標分別表示局中人采用混合策略 ，而局中人采用純策略和時

37、的期望支付。，而局中人采用純策略和時的期望支付。becf)1 ,(xxXAB2b3babcdfex1-x局中人局中人A局中人局中人B)(1b)(3b)(2bA B A 圖圖4-1對于局中人的每一個混合策略，他至少得到三條直線在對于局中人的每一個混合策略，他至少得到三條直線在處縱坐標的最小值，即處縱坐標的最小值，即圖圖4-1中的粗折線表示中的粗折線表示 這個最小值函數(shù)。這個最小值函數(shù)。AXx2131.31minminiiijjjjxaXA局中人希望選擇一個，使上面這個最小值盡可能大，從圖局中人希望選擇一個，使上面這個最小值盡可能大，從圖中可以看出，他應當選擇點所代表的，這時最小值為最大。中可以看

38、出，他應當選擇點所代表的，這時最小值為最大。這就是對策的值。這就是對策的值。AXAX2131.31minminmax2iiijjjjSXxaXABA在圖在圖41中，點是和兩直線的交點，只要解兩個二元一中，點是和兩直線的交點，只要解兩個二元一次聯(lián)立方程，就可以求出的坐標和次聯(lián)立方程，就可以求出的坐標和 的值，由圖也可以看出的值，由圖也可以看出，局中人的最策略不涉及他的純策略，因此只要解矩陣對，局中人的最策略不涉及他的純策略，因此只要解矩陣對策策AadcfA*xx BAB2b22fdca 就能得到局中人的最優(yōu)策略。就能得到局中人的最優(yōu)策略。B 定理定理9jnjSXTSXSYTSYSXXAXAYXA

39、YVmmnnm1minmaxmaxminminmax證明：證明：（1）證明：。）證明：。jnjSXTSYSXXAXAYmnm1minmaxminmax因為對任意給的，有因為對任意給的，有mSX jTSYXAXAYn.minnj,.,2 , 1 所以對任意給的，有所以對任意給的，有mSX jnjTSYXAXAYn.1minmin 從而，有從而，有jnjSXTSYSXXAXAYmnm.1minmaxminmax（2）證明：。）證明：。jnjSXTSXSYXAXAYmmn.1minmaxmaxmin 因為對任意的，有因為對任意的，有mSX nSY nnTyyyXAXAXAXAY.),.,(21.2

40、.1 .jnjnjjjnjjnjjnjjnjjXAyXAyXAyXA.11.11.11.min)min()min()( 所以對任意的，有所以對任意的，有nSY jnjSXTSXXAXAYmm.1minmaxmax 從而，有從而，有jnjSXTSXSYXAXAYmmn.1minmaxmaxmin綜上可知，定理成立。綜上可知，定理成立。這種圖解法可以推廣應用到一切的矩陣對策。這種圖解法可以推廣應用到一切的矩陣對策。n2一、矩陣對策的圖解法的步驟一、矩陣對策的圖解法的步驟n2設(shè)矩陣對策的支付矩陣為設(shè)矩陣對策的支付矩陣為n2nnLLLKKK . . 2121第一步第一步，在直角坐標系里，繪出局中人采用

41、混合策略，在直角坐標系里，繪出局中人采用混合策略，局中人采純策略的期望支付直線。，局中人采純策略的期望支付直線。AxX()1 ,xBjb),.,2 , 1(njLKjj第二步第二步，在圖中標出表示函數(shù)，在圖中標出表示函數(shù)的折曲線。的折曲線。niiijnjjnjxaXA11.1minminjnjLAAAK 121.第三步第三步，找出折曲線的最高點（可是或），找出折曲線的最高點（可是或），并求的橫坐標及縱坐標，則，并求的橫坐標及縱坐標，則 是局中人的最優(yōu)策略，是局中人的最優(yōu)策略，是對策的值。是對策的值。jnjLAAAK 121.iAjKjL *xiA*y)1 ,(*xx*y第四步第四步，在原支付矩

42、陣中保留構(gòu)成交點的兩直線對應于局中，在原支付矩陣中保留構(gòu)成交點的兩直線對應于局中人的二純策略所對應的兩列得矩陣對策。求解該矩陣對人的二純策略所對應的兩列得矩陣對策。求解該矩陣對策，即可得局中人的最優(yōu)策略。策，即可得局中人的最優(yōu)策略。iAB2222B下面下面 ，再來討論矩陣對策的圖解法。以的情形加以說，再來討論矩陣對策的圖解法。以的情形加以說明：明：2m3m設(shè)矩陣對策的支付矩陣為設(shè)矩陣對策的支付矩陣為23fedcba 設(shè)局中人設(shè)局中人 采用混合策略采用混合策略 ，圖，圖4-2中粗折線的縱中粗折線的縱坐標是：坐標是：B10),1 ,(yyyY2131.31maxmaxjjijiTiiyaYAfB

43、圖圖4-2aecbdYXA10局中人要找使這個最大值盡可能小的，在圖上就是點所局中人要找使這個最大值盡可能小的，在圖上就是點所代表的，這時代表的，這時這就是對策的值。這就是對策的值。BYAYTiiSYYABA.31maxmin2注：局勢平衡分析注：局勢平衡分析設(shè)局中人設(shè)局中人B使用最優(yōu)策略使用最優(yōu)策略Y*,而局中人而局中人A使用某一個混使用某一個混和策略和策略X，此時，此時A的收入將降至折線的收入將降至折線ABC上離開上離開B的某一點；又設(shè)局中人的某一點；又設(shè)局中人A使用最優(yōu)策略使用最優(yōu)策略X*,而局中而局中人人B使用某一混和策略使用某一混和策略Y，此時，此時，B的損失將升高到的損失將升高到折

44、線折線CDE上離開上離開D點的某一點。當雙方都堅持使用點的某一點。當雙方都堅持使用最優(yōu)混和策略時。局勢得以平衡。最優(yōu)混和策略時。局勢得以平衡。 矩陣對策的解矩陣對策的解22下面，分兩種情形討論：下面，分兩種情形討論： 第一種情形第一種情形，如果對策有純策略意義下的鞍點，則立即得到純，如果對策有純策略意義下的鞍點，則立即得到純策略解。策略解。 第二種情形第二種情形，如果沒有鞍點，則通過兩行或兩列互換，可以變，如果沒有鞍點，則通過兩行或兩列互換，可以變成滿足：成滿足： 設(shè)矩陣對策的支付矩陣是設(shè)矩陣對策的支付矩陣是dcba 22方法方法2這時對策必然有混合策略解。這時對策必然有混合策略解。cdbdc

45、aba , , 設(shè)分別是局中人和的最優(yōu)混合策設(shè)分別是局中人和的最優(yōu)混合策略，其中略，其中)1 ,(),1 ,(*yyYxxXAB10 ; 10*yx 若設(shè)表示對策的值，則由最優(yōu)策略的性質(zhì)必有若設(shè)表示對策的值，則由最優(yōu)策略的性質(zhì)必有VVYAVYAVAXVAXTT*. 2*. 12 .*1 .*, , 即即VydcxVybayVxdbxVxcax)1 (, )1 ()1 (, )1 (*解之得，解之得，cbdacdx*cbdabdy*cbdabcadV說明：說明：上述公式對于的情形同樣適用。上述公式對于的情形同樣適用。cdbdcaba, 例例4-6設(shè)矩陣對策的支付矩陣是設(shè)矩陣對策的支付矩陣是228

46、 02 4試求對策的解及對策的值。試求對策的解及對策的值。 解：解：因為因為 ，所以由公式有，所以由公式有28 , 08 , 04 , 245/4108028408*cbdacdx5/3106028428*cbdabdy5/1602840284cbdabcadV故局中人的最優(yōu)策略為故局中人的最優(yōu)策略為 ；局中人的最優(yōu)策略為；局中人的最優(yōu)策略為；對策的解是；對策的解是 ，對策的值是。，對策的值是。A)5/1 , 5/4(*XB)5/2 , 5/3(*Y),(*YX5/16 例例4-7 已知已知 矩陣對策的支付矩陣是矩陣對策的支付矩陣是試求對策的解及對策的值。試求對策的解及對策的值。421 2 1

47、 23 4 3 3解：解：因為，故劃掉原矩陣的第因為，故劃掉原矩陣的第3列得矩陣對策，列得矩陣對策，2423321 1 23 3 3又因，故劃掉第又因，故劃掉第1列得矩陣對策，列得矩陣對策，1323221 13 3由于由于 ，由矩陣對策的求解公式得，由矩陣對策的求解公式得31 , 11 , 33 , 132241)3() 1(13) 1(1*cbdacdx21)3() 1(13)3(1*cbdabdy0)3() 1(13)3() 1(31cbdabcadV故矩陣對策中局中人的最優(yōu)策略是故矩陣對策中局中人的最優(yōu)策略是 ，局中人的，局中人的最優(yōu)策略是，對策的值是，又因這個矩陣對策是原來最優(yōu)策略是，

48、對策的值是，又因這個矩陣對策是原來的矩陣對策的第的矩陣對策的第1，2行及第行及第2，4列組成的子矩陣，故原來矩陣對策列組成的子矩陣，故原來矩陣對策中局中人和的最優(yōu)策略分別是：中局中人和的最優(yōu)策略分別是：22A)4/3 , 4/1 (B)2/1 , 2/1 (0VBA)2/1 , 0 , 2/1 , 0()4/3 , 4/1 (*YX即對策的解是，對策的值是。即對策的解是，對策的值是。),(*YX0V 例例4-8 設(shè)矩陣對策的支付矩陣是設(shè)矩陣對策的支付矩陣是試求對策的解及對策的值。試求對策的解及對策的值。242 01 00 20 1 解：解：因為，劃去原矩陣中的第因為，劃去原矩陣中的第2,4行得

49、行得 矩陣矩陣對策矩陣矩陣對策)2, 0() 1, 0(),0 , 2()0 , 1(221 00 1由矩陣對策的計算公式得由矩陣對策的計算公式得2221001101*cbdacdx21001101*cbdabdy21001100) 1() 1(cbdabcadV故矩陣對策中局中人故矩陣對策中局中人A和和B的最優(yōu)策略分別是：的最優(yōu)策略分別是：(1/2,1/2,)，（1/2,1/2）。）。22 又因這個矩陣對策是由原來矩陣對策中劃去第又因這個矩陣對策是由原來矩陣對策中劃去第2,4行得到的行得到的，故原來的矩陣對策中局中人，故原來的矩陣對策中局中人A和和B的最優(yōu)策略分別是：的最優(yōu)策略分別是：；對策

50、的解是，對策的值是。對策的解是，對策的值是。22)0 , 2/1 , 0 , 2/1 (*X)2/1 , 2/1 (*Y),(*YX21V方法方法3：方程組法：方程組法由定理由定理3知，求矩陣對策的解等價于求解不等式方程知，求矩陣對策的解等價于求解不等式方程組（組（1），（），（2）。又由定理）。又由定理4和和5知，若最優(yōu)策略中知，若最優(yōu)策略中的的 均不為均不為0，則可將以上的兩個不等式組的，則可將以上的兩個不等式組的求解問題轉(zhuǎn)化為下面兩個方程組的求解問題：求解問題轉(zhuǎn)化為下面兩個方程組的求解問題：*,jiyx miimiiijxnjvxc111,.,2 , 1 , njjnjjijymivyc

51、111,.,2 , 1 ,注：注：此方法要求此方法要求 均不為均不為0，所以，當最優(yōu)策略，所以，當最優(yōu)策略的某些分量實際為的某些分量實際為0時，以上兩個方程組可能無解。時，以上兩個方程組可能無解。這說明此方法在實際應用中有一定的局限性。這說明此方法在實際應用中有一定的局限性。*,jiyx特別：特別：對對22的矩陣，若局中人的贏得矩陣沒有鞍點的矩陣，若局中人的贏得矩陣沒有鞍點時，各局中人的最優(yōu)策略中的時，各局中人的最優(yōu)策略中的 都大于都大于0。即。即對于這種問題，是可以采用方程組法求解的。對于這種問題，是可以采用方程組法求解的。*,jiyx例：求解矩陣對策例：求解矩陣對策G，其中，其中A為為 3

52、880667864959379520503043解：解：利用優(yōu)勢原則，化簡矩陣：利用優(yōu)勢原則，化簡矩陣：因為因為a4優(yōu)超于優(yōu)超于a1，a3優(yōu)超于優(yōu)超于a2，所以化簡為，所以化簡為 3880667864959375431aaaA又因為又因為b1優(yōu)超于優(yōu)超于b3，b2優(yōu)超于優(yōu)超于b4,b5，所以化簡為，所以化簡為210664373212bbaaaA 又因為又因為a1優(yōu)超于優(yōu)超于a3，化簡為，化簡為216437213bbaaA 容易看出矩陣容易看出矩陣A3沒有鞍點，所以可以用方程組法解之。沒有鞍點，所以可以用方程組法解之。對應的方程組為：對應的方程組為： 16347434343xxvxxvxx 16437212121yyvyyvyy求解，得求解，得5,21,21,32,31*2*1*4*3 vyyxx所以，以矩陣所以，以矩陣A為贏得矩陣的對策的一個解為為贏得矩陣的對策的一個解為5,)0 , 0 , 0 ,21,21(,)0 ,32,31, 0 , 0(* GTTVyx例例（齊王與田忌賽馬）（齊王與田忌賽馬）這個問題中齊王和田忌各自擁有的策略為：這個問題中齊王和田忌各自擁有的策略為：S1=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)S2=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(