博弈論Microsoft文檔

1、對策論(Theory of Games)第1、2講對策論也稱博弈論，是運籌學的一個重要分支。1928年馮諾意曼(J.von Neumann )等人由于經(jīng)濟問題的啟發(fā)，研究了一類具有某種特性的博弈問題，這是對策論的最早期的工作。在我國古代的戰(zhàn)國時期，“齊王與田忌賽馬”就是一個非常典型的對策論的例子。對策論所研究的主要對象是帶有斗爭性質(或至少含有斗爭成分)的現(xiàn)象。由于對策論研究的對象與政治、軍事、工業(yè)、農(nóng)業(yè)、交通、運輸?shù)阮I域有密切關系，處理問題的方法又有著明顯 的特色，所以越來越受到人們的注意。日常生活中，經(jīng)?？吹揭恍┚哂邢嗷ブg斗爭或競爭性質的行為，例如下棋、打牌、體育比賽等，還如戰(zhàn)爭活動中的

2、雙方， 都力圖選取對自己最為有利的策略，千方百計去戰(zhàn)勝對手，在政治方面，國際間的談判，各種政治力量之間的斗爭。各國際集團之間的斗爭等無一不具有斗爭的性質。 經(jīng)濟生活中，各國之間、 各公司之間的各種經(jīng)濟談判，企業(yè)為爭奪市場而進行的競爭等，舉不勝舉。具有競爭或對抗性質的行為，稱為對策行為。在這類行為中，參加斗爭或競爭的各方各自具有不同的目標和利益， 為了達到各自的目標和利益各方必須考慮對手的各種可能的行動 方案，并力圖選取對自己最為有利或最為合理的方案，對策論就是研究對策行為中斗爭各方是否存在著最合理的行動方案，以及如何找到這個合理的行動方案的數(shù)學理論和方法。在我國古代，“齊王賽馬”就是一個典型的

3、對策論研究的例子。戰(zhàn)國時期，齊王有一天提出要與大將田忌賽馬。雙方約定：從各自的上中下三個等級的馬中選一匹參賽。每匹馬均只能參賽一次； 每次比賽雙方各出一匹馬， 負者要付給勝者千金。 已經(jīng)知道，在同等級的馬中，田忌的馬不如齊王的馬，而如果田忌的馬比齊王的馬高一等級， 則田忌的馬可取勝。 當時，田忌手下的一個謀士給田忌出了個主意：每次比賽時先讓齊王牽出他要參賽的馬，然后用下馬對齊王的上馬，用中馬對齊王的下馬，用上馬對齊王的中馬。 比賽結果，田忌，二勝一負，可得千金，由此看來，兩人各采取什么樣的出馬次序，對勝負 是至關重要的。還如日常生活中，兒童或喝酒中不會猜拳的用 “石頭一剪子一布” 游戲也是帶有

4、競爭性 質的現(xiàn)象，大家都知道游戲的規(guī)定：第一，每人每局比賽中，只能在石頭、剪子、布三種出 法中選一種；第二，在一局比賽中，石頭對剪子認為石頭贏，剪子對布認為剪子贏，布對石 頭認為布方贏，如果雙方都是同一種，則認為沒有輸贏。這樣一局比賽中，各方是贏是輸， 不僅與自己所采取的發(fā)法 (亦稱策略)有關，而且與對方所采取的出法有關，下面介紹對策論中的矩陣對策。 1對策問題的三個基本要求以下稱具有對策行為的模型為對策模型或對策。對策模型的種類可以千差萬別，但本質上都必須包括如下三個基本要素：(1)局中人在一個對策行為(或一局對策)中，有權決定自己行動方案的對策參加者稱為局中人， 通常用I表示局中人的集合，

5、如果有 n個局中人，則I=1 ,2n, 一般要求一個對策中 至少要有二個局中人，如在“齊王賽馬”例子中，局中人是齊王與田忌。當然，對策中關于局中人的概念是具有廣義性的，局中人除了可以理解為個人外，還可以理解為某一集體。需要補充的一點是，在對策中總是假定每一個局中人都是理智的，聰明的決策者或競爭者。即對任一局中人來講， 不存在利用其它局中人決策的失誤，來擴大自身利益的可能性或相反。（2）策略集一局對策中，可供局中人選擇的一個實際可行的完整的行動方案稱為一個策略，參加對策的每局中人，i CI都有自己的策略集 Si, 一般，每一局中人的策略集中至少應包括兩個 策略。在“齊王賽馬”例子中，如用（上、中

6、、下）表示以上馬、中馬、下馬依次參賽次序,這是一個完整的行動方案， 即為一個策略?？梢?，局中人齊王與田忌各自都有六個策略： （上、 中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、中、上）、（下、上、中）。（3）贏得函數(shù)（支付函數(shù)）在一局對策中，當局勢給定以后，就用一個數(shù)來表示得失（或輸贏），顯然，這種“得失”或“輸贏”是局勢的函數(shù)，稱為支付函數(shù)。例如，S是i個局中人的一個策略，則 n個局中人的策略組S ，S2 -Sn）是一個局勢，全體局勢的集合S可用各局人策略集的笛卡爾積表示，即S S1 X S2X X Sn當局勢出現(xiàn)后，對策結果也就確定了，即對任一局勢S S,局中人I可能得

7、到一個贏得H （s）。顯然H（s）是局勢S的函數(shù)，稱為第I個局中人的贏得函數(shù)（支付函數(shù)）齊王賽馬中，局中人集體 I=1.2齊王的策略集用 Si a 1，a 2，口 3, 口 4, a 5, a 6田忌的策略集用S2 3 i，3 2，3 3, 3 4，3 5，3 6表示這樣齊王的任一策略a i和田忌的任一策略3 j,就決定了一個局勢 Sj,如果a 1=（上、 中、下）、3 1 =（上、中、下）則在局勢Sii下齊王的贏得值為 Hi （Si） =3。田忌的贏得值為H2 （Sii） =-3 如此等等一般當這三個基本因素確定后，一個對策模型也就給定了，對策論的模型很多，如矩陣對策、連續(xù)對策、微分對策、陣

8、地對策、隨機對策等。又稱矩陣對策。矩陣對策在眾多對策模型中占有重要地位的是二人有限零和對策對策,是到目前為止在理論研究和求解方法方面比較完善的一類對策，而且這類對策的研究思想和理論結果又是研究其它類型對策模型的基礎，由于學時的限制，我們只能主要介紹矩陣對策 的基本理論和方法。 2矩陣對策我們來看幾個矩陣對策的例子。例i“我們稱石頭一剪子一布”游戲是一個對策問題，設參加游戲的是甲、乙兩人，他們的策略集合都是石頭、剪子、布，也就是說他們在每一局比賽中都只能采取各自策略集合中的一個策略，如果我們再規(guī)定，贏得的一方得一分，輸?shù)哪欠降?1分。顯然，這個問題是兩人有限零和對策，即矩陣對策。我們可以列出甲、

9、乙兩人在一局比賽中的各種局勢下的贏輸分數(shù)。因為這是零和對策，故只需知道甲、乙任何一方在各種局勢下的分數(shù)，就能夠知道對分的情況了。石頭01-1男子-101布1-10乙兩人在各種局勢下的得分情況如下表所示如把表中數(shù)字用矩陣形式表示，則有0 1 -1 A -1 011 -10我們稱A為甲的應得矩陣.例2、（齊王賽馬）戰(zhàn)國時期，齊王要與大將田忌賽馬，雙方約定：從自己的上、中、下三個等級的馬中各選出一匹進行比賽。每次比賽輸者要付給贏者千金。就同等級的馬而言，齊王的馬都比田忌的強，他們倆人的策略集合都是，（上、中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、上、中）、（下、中、上）并且 可

10、以知道，在每一局比賽結束時，齊王和田忌任何一方贏得的千金數(shù)恰是對方輸丟的千金數(shù)。 可見這是兩人有限零的對策。即矩陣對策。齊王得千金數(shù)、尸忌策略31（上、中、下）32（上、下、中）33（中、 上、下）34（中、 下、上）35（下、中、上）36（下、上、中）卜表列出齊王在各種局勢下贏得千金的數(shù)值,（表中-1表齊王輸一千金）a 1 （上、中、下）31111-1（X 2 （上、下、中）1311-11a 3 （中、上、下）1-13111a 4 （中、下、上）-111311a 5 （下、中、上）11-1131（X 6 （下、上、中）111-113（矩陣）3 廣 1 11 -11 3 1 1 -1 1A=

11、1 -1 3 1 1 1-11131111-1131111-113稱作齊王的贏得矩陣般情必設兩個局中人分別記為）l、II ,局中人I有m個策略a 1, a 2，a m；局中人II有n個策他3 1, 3 2, 邛口。用&表示局中人I的策略集合，&表示局中人II的策略 集合，即S2 3 1, 3 2,3 n為了與后面的概念區(qū)分開來，稱ai為I的純策略，3 j為II的純策略，對于純策略構成布局勢（a i , 3 j）稱為純局勢。 局中人I的贏得矩陣記為a a11 a12. aj .ama21a22 a2j a2nai1 ai2- aij a in am1 am2 amj a mnj）下局中人I得分，

12、也表示在同一局勢下，局中人A中的木素a ij表示在純局勢（a i,II得分為-a ij o我們把矩陣對策記為G I , n； s1, s2； A或 G s1, s2； A矩陣對策模型給定后，各局中人面臨的問題是：如何選擇對自己最為有利的純策略，以謀取最大的贏得（或最少損失），這就是所謂矩陣對策的最優(yōu)純策略。第3、4講（一）矩陣對策的最優(yōu)純策略。我們用一個例子來說明最優(yōu)純策略的概念。例 3、設有一矩陣對策G s1,s2；A,其中 &“1,a2,a3,”4,S2 3 1, 32, 3 3-6 1 83 2 4A 9 -1 -10-3 0 61234從A可看出，姆中人I的最大贏得是9,要想得到這個贏

13、得，他就得選擇純策略a3。由于，假定局中人II也是理智的，他考慮到了局中人I打算出a 3的心理于是侵準備以3 3對付之。使局中人不但得不到9,反而失掉10,局中人I當然也會猜到局中人II的這一心理，故想出a 4來對付，使局中人II得不到10而失掉6，所以，如果雙方都不想冒險， 都不存在僥幸心理，而是考慮到對方必然會設法使自己的所得最少這一點，就應該從各自可能出現(xiàn)的最不利的情形中選擇一種最為有利的情形作為決策的依據(jù)，這就是所謂“理智行 為”，也是對策雙方實際上都能接受的一種隱妥方法。例3中，局中人I分析出純策略a 1, a 2, a 3, a 4可能帶來的最少贏得（矩陣 A中每 行的最小元素）分

14、別為：-8 ,，-10 , -3max -8 , 2, -10 , -3=2在這些最少贏得（最不利的情形）中最好的結果（最有利的情形）是贏得為2。因此，局中人I只要以a 2參加對策，無論局中人II取什么樣的純策略， 都能保證局中人I的收入 不會少于2,而出其它純策略，其收入都有可能小于 2,甚至輸給對方。因此，對局中人 II 來說，各純策略3 1, 3 2, 3 3可能帶來的對其最不利的結果（矩陣 A中每列中最大元素）分別為:9,，6min 9 , 2, 6=2在這些最不利的結果中，最好的結果（輸?shù)米钌伲┮彩?,即局中人II只要選擇純策略3 2（無論局中人I采取什么純策略，都能保持自己的支付不

15、會多于2,而采取其它任何策略，都有可能使自己的所失多于2。上面的分析表明，局中人I、II的“理智行為”分別是，選擇純策略a 2和3 2,這時局中人I的贏得值和局中人II的所失值的絕對值相等（都是2）,局中人I是按最大最小原則。局中人 II是按最小最大原則選擇各自的純策略，這對雙方來 說都是一種最為穩(wěn)妥白行為，因此，a2, 3 2分別為局中人I、II的最優(yōu)純策略。于是我們引出矩陣對策解的概念：定義1設G s 1, S2； A為矩陣對策，其中S1 “1, “2,ahS2 3 1, 32, 3 n。 A=aij mx n 若等式i j ji成立，記Vga*r ,則稱V為對策G的值，上式稱為成立的純局

16、勢（“/，3 j*）為G在純策略下的解（或平衡局勢）。ai*, 3 j*分別稱為局中人I、II的最優(yōu)純策略。由定義1可知，在矩陣對策中兩個局中人都采取最優(yōu)純策略（如果最優(yōu)純策略存在）才是理智的行動。例3中，對策解為（a 2, 32）,對策值為Vg=2。例4,求解矩陣對策 G S1, S2; A,其中-7廠 1 -813 2 4A= 16 -1 -3-3 05313 23 3min a ija 1-71-8-8a 23242a 316-1-3-34 4-305-3max aij1625解：根據(jù)矩陣A有于是maXmin aj) min(max aj) 2i j j i由定義1Vg=2, G的解為(

17、a 2, 3 2), a 2, 3 2分別是局中人|和|的最優(yōu)純策略。從例4可以看出，矩陣 A的元素a22既是所在行的最小元素，又是所在列的最大元素， 即ai2 a22a2 ji=1,2,3,4； j=1,2,3將這一事實推廣到一般矩陣對策，可得如下定理：定理1 矩陣對策 G S1、S2； A在純策略意義下有解的充要條件是：存在純局勢(a，*),使得對一切i=1,2,m,j=1,2,n均有證(略)為了便于對更為廣泛的對策情況進行分析，現(xiàn)引進關于二元函數(shù)鞍點的概念：定義2 設f (x, y)為一個定義在xC A及yC B上的實值函數(shù)，如果存在 x* C A, y* C B,使得對一切，xC A和

18、y C B,有f (x,y* ) f (x*,y* ) 4= a22 = V1選擇純策略時，應分別選取a于是，當雙方各根據(jù)最不利情形中選最有利結果的原則,2和31此時局中人I將贏得5,比預期贏得V1=4還多，原因就在于局中人II選擇了 3 1,使他的對手多得了原來不該得的贏得，故3 1對局中人II來說并不是最優(yōu)的，因而也會考慮32,局中人I亦會采取相應的辦法，改出a 1以使贏得為6,而局中人II又可能仍取策略3 1 來對付局中人I的策略a 1,這樣，局中人I出“1或a 2的可能性及局中人II出3 1或3 2的 可能性都不能排除，對兩個局中人來說，不存在一個雙方均可接受的平衡局勢，或者說當V10

19、 i=1,2, ，m;&與 Y（y1,y 2, yn） T y j 0 j=1,2,n;i 1Yj分別稱作局中人I、II的混合策略。（x,y ）稱一個混合店如。一個混合策略 X（x1, x2xm） T可設想成兩個當局人多次重復進行對策G時，局中人I分別采取純策略a 1, a 2- a m的頻率。純策略也可以看成是混合策略的特殊情況。例如局中人取純策略a i,則對應于局中人I的混合策略為（0,0,1,0o）T所以有時把混合策略簡稱為策略 ，（只進行一次對策，混合 對策x= （x2，xm） 可設想成局中人I對各純策略的偏愛程度）。如果局中人I選取的策略為X （X1,X2, ,Xm）T局中人II選取

20、的策略為 Y （丫,丫2 , ,Yn）T由于兩個局中人分別選取純策略a,3 j的事這件可以看成是相互獨立的（隨機事件）所以局勢(a i, 3 j)出現(xiàn)的概率是xiyj,從而局中人I贏彳導au的概率是x, g,于是數(shù)學 期望。 m nE (X,Y)aKyj就是局中人I/屈導值m記 S X (Xi,X2, ,Xm)T,Xi0,i1,2, ,m;Xi1*i 1E E (x,y ) |X e Si , YC S2 *則稱 G = Si , S2; E為G的混合擴充設兩個局中人仍象前面一樣地進行有理智的對策，當局中人 I采取混合策略 X時。他 只能希望獲得(最不利的情形)。min E (x,y)因此局中

21、人應選取 xCS*,使上式取極大值(最不利當中的最有利情形)，即局中人I可 保證取贏利的期望值不少于V1 = max ( min E (x,y)y e S2 x e si同理，局中人n可保證自己所失期望值至多是V2 = min (maxE(x,y)y C S2 x C si注意到上二式vi、V2表達式是有意義的，且是 Si*、$2*上的連續(xù)函數(shù)，仍然有 Vi 0 x 1+x2=1(概率和為 1) 一*S2 =(y 1 ,y 2) y 1,y 2 0 y 1 y2=1局中人I的贏得期望是：由此式可知當 x1 1/4 , x2 1-1/4=3/4 時，E(X,Y) 9/2,就是說，當局中人I以概率

22、1/4選取純策略1,以概率3/4選取純策略 2時他的贏得至少是9/2 ,同樣局中人n只有取X 1/2 , 丫2 =1-1/2=1/2，才能保證他的輸出不會多于9/2。一*T*T取 X(1/4,3/4)Y (1/2,1/2)則 E(X ,Y ) 9/2E(X ,Y) E(X,Y ) 9/2即有 E(X,Y ) E(X ,Y ) E(X,Y)TT故 X (1/4,3/4) 和 Y (1/2,1/2) 分別為局中人I和n的最優(yōu)策略，對策值(局中人I的贏得期望值)VG 9/2一般矩陣對策在純策略意義下的解，往往是不存在的，但是可以證明，般矩陣在混合策 略意義下的解，卻總是存在的，這一系列定理我們略表不

23、講了，但在一個構造性的證明中, 引出了矩陣對策的基本方法一線性規(guī)劃方法。這是給出一個矩陣對策優(yōu)超純策略的定義：定義5設有矩陣對策G S1, S2； A其中 S1= a 1, a 2,a S2 = 3 1, 3 2,，3 nA (aj)mn如果對一切j=1,2,n都有即矩陣A的第i 0行元均不少于第k 0行的對應元，則稱局中人I的純策略aio優(yōu)超于同樣，若對一切i=1,2,m,都有即矩陣A的第I0列元均不少于第jo列的對應元，則稱局中人II的純策略3 J優(yōu)超于3 l0 定理10,設G S1, S2； A為矩陣對策其中S1 a 1, a 2, ,a mS2 3 1, 32, 3 nA (a0)mn

24、如果純策略a 1被其余純策略a 2, a 3,a m中之所優(yōu)超，由 G可 得到一個新的純陣對策G :其中 GS1 ,S2 ; ASa2, 3,，m mA =( a ij ) (m 1) nAja。i=2,m ,j=1,2, n于是有(1) VgVg(2) G中局中人II的最優(yōu)策略就是其在 G中的最優(yōu)策略：.* 、 TT(3)若(x2,x3,.,xm)是G中局中人I的最優(yōu)策略，則X (0,x1 ,x2,.,xm)是其在G中的最優(yōu)策略。例9,設贏得矩陣為2(2 0 3 05 0 2 5 9A= 7 3 9 5 94 6 8 7 5.56 0 8 8 3求解這個矩陣對策。解：由于第4行優(yōu)于第1行、第

25、3行優(yōu)于第2行，故可劃在第1行和第2行，得到新的贏得矩陣。7 /959、Ai46875.56 0883由于Ai第1列優(yōu)超于第3歹U,第2列優(yōu)超于第4列1/3 X （第1歹U） +2/3 X （第2歹U）優(yōu)超于第5歹U,因此去掉第 3、4、5歹U,得到7 3A24 68 0這時第1行又優(yōu)超于第3行，故從4中劃在第3行，得到9 3A 4 6對于A3 ,易知無鞍點存在，應用定理 4,求解不等式組7x3+4x4 v7y1+3yzW v3x3+6x4 v4y1+6y2W v(I) x3+x4=1(iiy1+y2=1x3,x 4 0y1,y 0首先考慮滿足7x3+4x4=v7y1+3y2=v3x3+6x4

26、=v4y1+6y2=vx3+x4=1y1+y2=1的非負解，求得解為*X31/3*X42/3于是原矩陣對策的一個解就是：第7、8講（三）矩陣對策的解法（1）2 X2對策的公式法所謂2X2對策是指局中人I的贏得矩陣為2X2階的，即如果A有鞍點，則很快可求出各局中人的最優(yōu)純策略；如果A沒有鞍點，則可以證明各局中人最優(yōu)混合策略中的Xi , yj均大于零。于是由定理6可知，為求最優(yōu)混合策略可求下列方程組：aiixi+a2iX2=v(I) aiixi+a22X2=vXi+X2=iaiixi+a12y2=v(II) a2iyi+a22y2=vyi+y2=i當矩陣A不存在鞍點時，可以證明上面等式組(I) (

27、II ) 一定有嚴格非負解 * tX (Xi,X2)* tY(Yi ,丫2 ),其中a22-a 2i* Xi (aii+a22)-(a i2+a2i)aii-a i2(aii+a22)-(a i2+a2i)a22-a i2(aii+a22)-(a i2+2i)aii-a 2i(aii+a22)-(a i2+a2i)a11a22-a 12a2i(aii+a22)-(a i2+a2i)例10求解矩陣對策，G=si, S2； A,其中1 3A 4 2解 易萬A沒有諭點，由上通解公式，計算得到最優(yōu)解為對策值為5八2(2) 2 x n或mK2對策的圖解法。(3)線性方程組法據(jù)定理，求解矩陣對策解(x*,

28、y*)的問題，在價于求解下面兩個方程組的問題：(假設取優(yōu)策%中的Xj , yi均不為零)n aijXi =v j=1,2,nni 1aij yi =v i=1,2,mjM試算過程是無固定規(guī)則可循的，所以實際應用中具有一定的局限性。例12求解矩陣對策一一“齊王賽馬”解已知齊王賽馬的贏得矩陣為3 iiii-11 311-111 -13111-11131111-11311 11-113易知，A沒有鞍點，即對齊王和田忌來說都不存在最優(yōu)純策略。設齊王和田忌的最優(yōu)混合策略為，*、TX=(X1 ,X2,X3 ,X4 ,X5 ,X6 )T*=(y；,y2*,y3*,y；,y5* ,y6*)T從矩陣A的元素來看

29、，每個局中個選取每個純策略的可能性都是存在的，故可事先假定Xi*0,yj*0, i=1,2,6, j=1,2,6于是求解線性分程組廣。3X1+X2+X3-X 4+X5+X6=VX1 + 3X2-X 3+X4+X5+X6=VX1+X3+3X3+X4-X 5+X6=VX1+X2+X3+3X4+X5-X 6=VX1-X 2+X3+X4+3X5+X6=VX1+X2+X3+X4+X5+3X6=VX1+X2+X3+X4+X5+X6=1 V和3y1+y2+y3+y4+y5-y 檸Vy1+3y2+y3+y4-y 5+y6=Vy 1-y 2+3y3+y4+y5+y6=Vy1+y2+y3 + 3y4+y5+y6=Vy1+y2-y 3+y4+3y5+y6=Vy1+y2+y3-y 4+y5+3y6=Vy1+y2+y3+y4+y5+y6=1得至、x i=1/6i=1