數(shù)學(xué)建模-對(duì)策論

1、GAME THEORY對(duì) 策 論第11章9/27/2022111 矩陣對(duì)策6.1 引言6.2 對(duì)策論的基本概念6.3 矩陣對(duì)策的概念及模型6.4 矩陣對(duì)策的純策略解（鞍點(diǎn)解）6.5 矩陣對(duì)策的混合策略解（mixed strategic solution）6.6 矩陣對(duì)策的解法9/27/20222Operations Research6.1.1 何謂對(duì)策論（Game Theory）？6.1.2 對(duì)策的例子6.1.3 對(duì)策論的誕生與發(fā)展簡況6.1 引 言9/27/20223Operations Research6.1.1 何謂對(duì)策論(Game Theory)？ 定義：對(duì)策論亦稱競賽論或博弈論，是研

2、究具有斗爭或競爭性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法。 囚徒困境局中人2坦白不坦白局中人1坦白(-6,-6)(-1,-8)不坦白(-8,-1)(-2,-2)9/27/20224Operations Research齊王賽馬決斗問題：神雕俠侶中武林盟主大會(huì)6.1.2 對(duì)策的例子朱子柳霍 都郭 靖達(dá)爾巴郝大通金輪法王9/27/20225Operations Research6.1.3 對(duì)策論的誕生與發(fā)展簡況早期工作1912年E.Zermelo 關(guān)于集合論在象棋對(duì)策中的應(yīng)用 1921年E.Borel 引入最優(yōu)策略 1928年J.V.Neumann證明了一些猜想9/27/20226Operations Resea

3、rch6.1.3 對(duì)策論的誕生與發(fā)展簡況產(chǎn)生標(biāo)志 1944年J.V.Neumann和O.Morgenstern”對(duì)策論與經(jīng)濟(jì)行為” （Theory of Games and Economic Behavior）發(fā)展成熟 Nash均衡、經(jīng)濟(jì)博奕論、信息不對(duì)稱對(duì)策和廣義對(duì)策9/27/20227Operations Research6.2 對(duì)策論的基本概念6.2.1 局中人（Player）6.2.2 策略（Strategy）6.2.3 支付與支付函數(shù)9/27/20228Operations Research6.2.1 局中人（Player）1、局中人：在一場競爭或斗爭中的決策者稱為該局對(duì)策的局中人

4、通常，一局對(duì)策具有兩個(gè)或兩個(gè)以上-決策者，一般用I表示局中人集合：9/27/20229Operations Research6.2.1 局中人（Player）2、對(duì)策分類：依據(jù)局中人的數(shù)量，可將對(duì)策分為有限對(duì)策無限對(duì)策(n2)對(duì)策無限零和對(duì)策無限非零和對(duì)策有限零和對(duì)策有限非零和對(duì)策9/27/202210Operations Research6.2.2 策略（Strategy）1、 策略與策略集局中人指導(dǎo)自己自始至終如何行動(dòng)的一個(gè)方案，稱為策略(Strategy)由所有策略構(gòu)成的集合，稱為策略集(StrategySet)9/27/202211Operations Research6.2.2 策略

5、（Strategy）2、策略集的元素：對(duì)于局中人i,iI，都有自己的策略集Si,通常每一局中人的策略集中至少應(yīng)包括兩個(gè)策略對(duì)于例4的包、剪、錘游戲。假設(shè)有兩個(gè)局中人I=甲，乙，甲的策略集為S甲=(包)、(剪)、(錘)=a1、a2、a3;乙的策略集為S乙=(包)、(剪)、(錘) =b1、b2、b3;9/27/202212Operations Research6.2.3 支付與支付函數(shù)1、局勢：各局中人所選定的策略形成的策略組2、策略組 若si是第i個(gè)局中人的一個(gè)策略，則n個(gè)局中人的策略組 s=(s1,s2,sn) 就是一個(gè)局勢。9/27/202213Operations Research6.2.

6、3 支付與支付函數(shù)例如，對(duì)于包、剪、錘游戲。假設(shè)有兩個(gè)局中人I=甲，乙，甲的策略集為S甲=(包)、(剪)、(錘)=(a1)、(a2)、(a3);乙的策略集為S乙=(包)、(剪)、(錘) =(b1)、(b2)、(b3); 則甲的一個(gè)策略ai，和乙的一個(gè)策略bj就構(gòu)成一個(gè)局勢sij.9/27/202214Operations Research6.2.3 支付與支付函數(shù)3、贏得（支付）：當(dāng)每個(gè)局中人所采取的策略確定后，他們就會(huì)得到相應(yīng)的收益或損失，稱為局中人的支付（Payoff）。 若甲的一個(gè)策略a3(錘)，乙的一個(gè)策略b2(剪)，則構(gòu)成一個(gè)局勢s32 。在局勢s32下，甲的支付為：乙的支付9/27

7、/202215Operations Research6.2.3 支付與支付函數(shù)4、支付（贏得）函數(shù)：不同的策略會(huì)導(dǎo)致不同的支付，因此，支付是策略(準(zhǔn)確的說應(yīng)該是局勢)的函數(shù)，稱為支付函數(shù)(payoff function)。對(duì)于例4，兩人的支付函數(shù)分別記為： 和例如，對(duì)于策略a3, b19/27/202216Operations Research6.2.3 支付與支付函數(shù)5、零和對(duì)策和非零和對(duì)策 根據(jù)各局中人支付的代數(shù)和是否為0，將對(duì)策分為零和對(duì)策和非零和對(duì)策(non-zero-sum games)。 若在任一局對(duì)策中，全體局中人支付的總和為0，則該對(duì)策稱為零和對(duì)策，否則稱為非零和對(duì)策(non-

8、zero-sum games)。 對(duì)于前例，顯然為零和對(duì)策，因?yàn)?/27/202217Operations Research6.2.3 支付與支付函數(shù)6、對(duì)策分類 根據(jù)局中人的數(shù)目和支付函數(shù)代數(shù)和有限對(duì)策n人對(duì)策(n2)對(duì)策合作對(duì)策非合作對(duì)策9/27/202218Operations Research6.3 矩陣對(duì)策的概念及模型1、定義：兩個(gè)人零和對(duì)策稱為矩陣對(duì)策 例，“包、剪、錘”游戲中，甲、乙雙方各有三種不同的策略，分別為：9/27/202219Operations Research6.3 矩陣對(duì)策的概念及模型甲的支付情況如下表 1 (包)2(剪)3(錘)1 (包)0-112 (剪)10-

9、13(錘)-110乙的策略甲的支付甲的策略表6.19/27/202220Operations Research6.3 矩陣對(duì)策的概念及模型齊王賽馬 1234561 (上中下)31111-12 (上下中)1311-113(中上下)1-131114(中下上)-1113115(下中上)11-11316(下上中)111-113田忌策略齊王贏得齊王策略上中下上下中中上下中下上下中上下上中9/27/202221Operations Research6.3 矩陣對(duì)策的概念及模型表6.1中的數(shù)字用矩陣的形式表示A稱為甲的支付矩陣。顯然，乙的支付矩陣為-A。因此，該對(duì)策可記為： 9/27/202222Opera

10、tions Research6.3 矩陣對(duì)策的概念及模型2、矩陣對(duì)策的模型一般地，若局中人 ，的策略集分別為：為了與后面的概念區(qū)分開來，我們稱i為的純策略， j為的純策略，對(duì)于純策略i, j構(gòu)成的策略偶(i, j)稱為純局勢。 9/27/202223Operations Research6.3 矩陣對(duì)策的概念及模型若的支付矩陣為： ij表示局勢(i,j)下，局中人的支付,則矩陣對(duì)策可記為G=S1,S2,A：即矩陣對(duì)策模型。 9/27/202224Operations Research6.4 矩陣對(duì)策的純策略解6.4.1 矩陣對(duì)策的純策略解例解過程6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ)6.4.3

11、 矩陣對(duì)策的純策略解性質(zhì)9/27/202225Operations Research例5 設(shè)二人零和對(duì)策 G=S1, S2, A，其中 6.4.1 矩陣對(duì)策的純策略解例解過程而且局中的支付矩陣為： 兩位局中人都想自己的支付最大化。9/27/202226Operations Research6.4.1 矩陣對(duì)策的純策略解例解過程 這里我們認(rèn)為局中人都是理智的，從矩陣A進(jìn)行邏輯推理可知： 如果局中人采取3作策略，雖有可能獲得最大支付18，但是,局中人分析到的這種心理，就會(huì)采取3策略，使不僅得不到最大值18，反而取得很壞的結(jié)果-8； 同樣，局中人為了得到最大支付+12(即局中人的支付-12)，會(huì)采取

12、 2作為策略,但局中人也會(huì)猜到的這種心理,而采取 2作策略，這樣局中人只能得到-3。9/27/202227Operations Research6.4.1 矩陣對(duì)策的純策略解例解過程從以上的分析可以看出，局中人選取最優(yōu)策略時(shí)應(yīng)該考慮到也是十分理智與精明的，的策略是要以支付最少為目的，所以不能存在任何僥幸心理。局中人也應(yīng)作同樣的考慮。 對(duì)于局中人來說，應(yīng)該是從最壞處著想向最好處努力。9/27/202228Operations Research6.4.1 矩陣對(duì)策的純策略解例解過程對(duì)局中人來講，各策略的最壞結(jié)果分別為：min-6,2,-7=-7 min5,3,6=3min18,0,-8=-8min

13、-2,-12,7=-12這些最壞的情況中，最好的結(jié)果是：max-7,3,-8,-12=39/27/202229Operations Research6.4.1 矩陣對(duì)策的純策略解例解過程同樣，對(duì)局中人而言，各策略的最壞的結(jié)果分別為：max-6,5,18,-2=18max2,3,0,-12=3max-7,6,-18,7=7在這些最壞的情況中，最好的結(jié)果（損失最小）是min18,3,7=39/27/202230Operations Research6.4.1 矩陣對(duì)策的純策略解例解過程1231-62-7-7253633180-8-84-2-127-1218379/27/202231Operatio

14、ns Research6.4.1 矩陣對(duì)策的純策略解例解過程課堂練習(xí):求解對(duì)策 G=S1,S2,A已知：9/27/202232Operations Research定義1 對(duì)于矩陣對(duì)策G=S1,S2,A,如果存在純局勢 6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ)則稱局勢 為對(duì)策G在純策略中的解。亦稱其為G的鞍點(diǎn)(saddle point): (列中最大，行中最小)使得對(duì)任意j=1, ，n,及任意i=1, m有： 9/27/202233Operations Research6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ) 分別稱為局中人，的最優(yōu)純策略。 稱 為對(duì)策G的值(value)，記為9/27/20223

15、4Operations Research6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ)定理1 矩陣對(duì)策G=S1,S2,A存在最優(yōu)純策略的充分必要條件為：9/27/202235Operations Research6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ)求對(duì)G的解和值。例6 已知 G=S1,S2,A，其中, 9/27/202236Operations Research6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ)12341868662134-3-33967664-31103-3961066解：根據(jù)A可得9/27/202237Operations Research6.4.2 矩陣對(duì)策的純策略解理論基礎(chǔ)由于： 四個(gè)局

16、勢均為G的鞍點(diǎn)，且 故知： 9/27/202238Operations Research6.4.3 矩陣對(duì)策的純策略解性質(zhì)從上例可知，對(duì)策的解可以是不唯一的，但對(duì)策的值是唯一的。對(duì)策解不唯一時(shí)，應(yīng)滿足下面兩條性質(zhì)：1. 無差別性：若 與 是矩陣對(duì)策G的兩個(gè)解，則即對(duì)策值相等，它們在矩陣中的元素相同。9/27/202239Operations Research6.4.3 矩陣對(duì)策的純策略解性質(zhì)2. 可交換性：若 與 是矩陣對(duì)策G的兩個(gè)解,則與 也是對(duì)策的解。 9/27/202240Operations Research6.4.3 矩陣對(duì)策的純策略解性質(zhì)是不是每一個(gè)矩陣對(duì)策都有純策略解（鞍點(diǎn)）？1

17、2310-11-1210-1-13-110-1111答案是否定的。9/27/202241Operations Research6.5 矩陣對(duì)策的混合策略解6.5.1 混合策略與混合擴(kuò)充（mixed strategic solution）6.5.2 解的基本定理9/27/202242Operations Research6.5.1 混合策略與混合擴(kuò)充1213632544561、問題提出 9/27/202243Operations Research6.5.1 混合策略與混合擴(kuò)充該對(duì)策問題表明不存在使對(duì)立雙方達(dá)到平衡的局勢，因此，局中人采取任何一種純策略，都有一定的風(fēng)險(xiǎn)。所以，在這種情況下，局中人必

18、須隱瞞自己選取策略的意圖。 9/27/202244Operations Research6.5.1 混合策略與混合擴(kuò)充2、問題處理方案設(shè)計(jì)這時(shí)我們可以設(shè)想局中人隨機(jī)地選取純策略來進(jìn)行對(duì)策。即在一局對(duì)策中，局中人以概率 來選取純策略 ,其中的 滿足 于是得到一個(gè)m維的概率向量 9/27/202245Operations Research6.5.1 混合策略與混合擴(kuò)充同樣對(duì)于局中人,有相應(yīng)的一個(gè)n維的概率向量 滿足 yj表示局中人選取純策略j的概率。9/27/202246Operations Research6.5.1 混合策略與混合擴(kuò)充3、混合策略概念引入定義:若給定一個(gè)矩陣對(duì)策G=S1,S2,

19、A ,其中則我們把純策略集對(duì)應(yīng)的概率向量： 與 分別稱作局中人、的混合策略，(X,Y)稱為一個(gè)混合局勢。 9/27/202247Operations Research6.5.1 混合策略與混合擴(kuò)充如果局中人選取的策略為 局中人選取 由于兩局中人分別選取策略 的事件可以看成使相互獨(dú)立4、混合策略的局中人支付 如果局中人選取的策略為 9/27/202248Operations Research6.5.1 混合策略與混合擴(kuò)充就是局中人的支付值。 所以局勢(i，j)出現(xiàn)的概率是xiyj。從而知局中人支付ij的概率是xiyj。于是，數(shù)學(xué)期望值： 9/27/202249Operations Researc

20、h6.5.1 混合策略與混合擴(kuò)充令： 則稱 為G的混合擴(kuò)充。 5、混合擴(kuò)充9/27/202250Operations Research6.5.1 混合策略與混合擴(kuò)充定義2 如果存在 ,滿足:對(duì)任意 及 均有： 則稱 為G（在混合策略下的）解. 分別稱為局中人、的最優(yōu)(混合)策略. 稱為對(duì)策G（在混合意義下的）值，記為 9/27/202251Operations Research6.5.1 混合策略與混合擴(kuò)充例7 設(shè) ,其中 求它的解及值。解：顯然該問題無鞍點(diǎn)解。設(shè)局中人、 的混合策略分別為： X=(x1,x2),Y=(y1,y2).則9/27/202252Operations Research

21、6.5.1 混合策略與混合擴(kuò)充則局中人支付的數(shù)學(xué)期望為：9/27/202253Operations Research6.5.1 混合策略與混合擴(kuò)充可見:當(dāng) 9/27/202254Operations Research6.5.1 混合策略與混合擴(kuò)充顯然 9/27/202255Operations Research6.5.1 混合策略與混合擴(kuò)充由定義1知： 分別是局中人、的的最優(yōu)策略，且 9/27/202256Operations Research6.5.2 解的基本定理定理2 (基本定理) 任意一個(gè)矩陣對(duì)策 其中 一定有解(在混合策略意義下),且如果G的值是V,則以下兩組不等式的解是局中人,的最

22、優(yōu)策略: 9/27/202257Operations Research6.5.2 解的基本定理（11-1）（11-2）9/27/202258Operations Research6.5.2 解的基本定理（1）若 則 （G的值） （2）若 則 （4）若 ,則 （3）若 ,則 可用例7驗(yàn)證定理3 若 是對(duì)策G(同前)的最優(yōu)混合局勢,則對(duì)某一個(gè)i或j來說：9/27/202259Operations Research6.5.2 解的基本定理y1y2yn12nx11a11a12a1nV1x22a21a22a2nV2 xmmam1am2amnVm V1V2VnVV9/27/202260Operations

23、 Research6.6 矩陣對(duì)策的解法6.6.1 圖解法6.6.2 優(yōu)勢法6.6.3 簡化計(jì)算法6.6.4 線性規(guī)劃解法9/27/202261Operations Research6.6.1 圖解法例8 已知： 其中 求矩陣對(duì)策的解和值。 9/27/202262Operations Research解: 設(shè)局中人 的混合策略為 (x,1-x)T,x0,1。對(duì)局中人而言，他的最少可能收入為局中人選取1，2所確定的兩條直線(定理3知): 6.6.1 圖解法V1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10 因?yàn)閤1和x2一定大于0在x處的縱坐標(biāo)中的最小者. 局中人

24、用“最大最小”原則選取自己的策略,即:9/27/202263Operations ResearchD點(diǎn)為極值點(diǎn),D點(diǎn)坐標(biāo)為： 即 的最優(yōu)混合策略為： ED(1/4,16 )VV1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10 xF從上圖可以看出： 就是折線EDF. 9/27/202264Operations Research6.6.1 圖解法同理，對(duì)局中人而言有 V=5y+35(1-y)=35-30y V=20y+10(1-y)=10+10y最小最大點(diǎn)為: 即 的最優(yōu)解為 ：對(duì)策值為： 9/27/202265Operations Research6.6.1 圖解

25、法FG(5/8,16 )HYV=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y9/27/202266Operations Research6.6.1 圖解法課堂練習(xí)p145-10.4-3：求解下列矩陣對(duì)策，已知贏得矩陣為：9/27/202267Operations Research6.6.1 圖解法例9 已知： 其中 求對(duì)策的解和值。 解：顯然無鞍點(diǎn)，作混合擴(kuò)充： 9/27/202268Operations Research6.6.1 圖解法對(duì)局中人而言，若選取 時(shí)，的最小可能收入為以下四條直線在x處縱坐標(biāo)中的最小者 v=2x+4(1-x)=4-2x (1)v=3x

26、+(1-x)=2x+1 (2)v=x+6(1-x)=-5x+6 (3)v=5x (4)9/27/202269Operations Research6.6.1 圖解法從圖上可以看出 B點(diǎn)坐標(biāo)即為所求的極值點(diǎn). AB(2)(3)(1)(4)B點(diǎn)坐標(biāo)為:即 的最優(yōu)解為 9/27/202270Operations Research6.6.1 圖解法同理可得： v=2y1+3y2+y3+5y4 (5) v=4y1+y2+6y3 (6)由上節(jié)的定理3求出的最優(yōu)解 將 分別代入方程(1)(4)得：9/27/202271Operations Research6.6.1 圖解法定理3的(4)定理3的(2)定理3

27、的(2)定理3的(4)9/27/202272Operations Research6.6.1 圖解法代入(5)、(6)得： 解之得：故的最優(yōu)策略為9/27/202273Operations Research6.6.2 優(yōu)勢法對(duì)于一般的矩陣對(duì)策 其中 定義3 若對(duì)固定的i、k有若對(duì)固定的j和l，有 則稱優(yōu)超，記為則稱優(yōu)超，記為9/27/202274Operations Research6.6.2 優(yōu)勢法(1) 定理4 設(shè)G中的某個(gè) 被其余的 之一優(yōu)超, 由G可得 ，其中 于是有 (2) 中局中人的最優(yōu)策略就是G中的最優(yōu)策略；9/27/202275Operations Research6.6.2

28、優(yōu)勢法若 是在 中的最優(yōu)解，則 為在G中的最優(yōu)解. (3) 9/27/202276Operations Research6.6.2 優(yōu)勢法例10 已知某矩陣對(duì)策G的支付矩陣為： 求解這個(gè)矩陣對(duì)策。 9/27/202277Operations Research6.6.2 優(yōu)勢法解：顯然無鞍點(diǎn)，由于A的階數(shù)為 圖解法失效。由定義可知 由定理1可將該問題簡化為:9/27/202278Operations Research6.6.2 優(yōu)勢法可用圖解法求得最優(yōu)解和值分別為： 由又可看出：從又可看出：，因此得： 9/27/202279Operations Research6.6.2 優(yōu)勢法即可得到對(duì)策G的解為： 值為V=5。9/27/202280Operations Research6.6.3 簡化計(jì)算法定理5 若矩陣對(duì)策 其中d為常數(shù)，則G1與G2有相同的解，且對(duì)策的值相差一個(gè)常數(shù)d，即： 9/27/202281Operations Research6.6.3 簡化計(jì)算法推論1 若矩陣對(duì)策 其中k0為常數(shù)，則G1與G2有相同的解,且9/27/202282Operations Research6.6.3 簡化計(jì)算法例11 已知某矩陣對(duì)策G的支付矩陣如下： 解：由推論1可取 得同解矩陣：