數(shù)學(xué)建模-對策論省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

GAMETHEORY

對策論第11章第1頁9/12/2023111矩陣對策6.1引言6.2對策論基本概念6.3矩陣對策概念及模型6.4矩陣對策純策略解（鞍點解）6.5矩陣對策混合策略解（mixedstrategicsolution）6.6矩陣對策解法第2頁9/12/20232OperationsResearch6.1.1何謂對策論（GameTheory）？6.1.2對策例子6.1.3對策論誕生與發(fā)展簡況6.1引言第3頁9/12/20233OperationsResearch6.1.1何謂對策論(GameTheory)？定義：對策論亦稱競賽論或博弈論，是研究含有斗爭或競爭性質(zhì)現(xiàn)象數(shù)學(xué)理論和方法。囚徒困境局中人2坦白不坦白局中人1坦白(-6,-6)(-1,-8)不坦白(-8,-1)(-2,-2)第4頁9/12/20234OperationsResearch齊王賽馬決斗問題：神雕俠侶中武林盟主大會6.1.2對策例子朱子柳霍都郭靖達(dá)爾巴郝大通金輪法王第5頁9/12/20235OperationsResearch6.1.3對策論誕生與發(fā)展簡況早期工作1912年E.Zermelo‘關(guān)于集合論在象棋對策中應(yīng)用’1921年E.Borel引入最優(yōu)策略1928年J.V.Neumann證實了一些猜測第6頁9/12/20236OperationsResearch6.1.3對策論誕生與發(fā)展簡況產(chǎn)生標(biāo)志

1944年J.V.Neumann和O.Morgenstern”對策論與經(jīng)濟行為”（TheoryofGamesandEconomicBehavior）發(fā)展成熟

Nash均衡、經(jīng)濟博奕論、信息不對稱對策和廣義對策第7頁9/12/20237OperationsResearch6.2對策論基本概念6.2.1局中人（Player）6.2.2策略（Strategy）6.2.3支付與支付函數(shù)第8頁9/12/20238OperationsResearch6.2.1局中人（Player）1、局中人：在一場競爭或斗爭中決議者稱為該局對策局中人通常，一局對策含有兩個或兩個以上---決議者，普通用I表示局中人集合：第9頁9/12/20239OperationsResearch6.2.1局中人（Player）2、對策分類：依據(jù)局中人數(shù)量，可將對策分為有限對策無限對策(n>2)對策無限零和對策無限非零和對策有限零和對策有限非零和對策第10頁9/12/202310OperationsResearch6.2.2策略（Strategy）1、策略與策略集局中人指導(dǎo)自己自始至終怎樣行動一個方案，稱為策略(Strategy)由全部策略組成集合，稱為策略集(StrategySet)第11頁9/12/202311OperationsResearch6.2.2策略（Strategy）2、策略集元素：對于局中人i,i∈I，都有自己策略集Si,通常每一局中人策略集中最少應(yīng)包含兩個策略對于例4包、剪、錘游戲。假設(shè)有兩個局中人I={甲，乙}，甲策略集為S甲={(包)、(剪)、(錘)}={a1、a2、a3};乙策略集為S乙={(包)、(剪)、(錘)}={b1、b2、b3};第12頁9/12/202312OperationsResearch6.2.3支付與支付函數(shù)1、局勢：各局中人所選定策略形成策略組2、策略組若si是第i個局中人一個策略，則n個局中人策略組s=(s1,s2,…,sn)就是一個局勢。第13頁9/12/202313OperationsResearch6.2.3支付與支付函數(shù)比如，對于包、剪、錘游戲。假設(shè)有兩個局中人I={甲，乙}，甲策略集為S甲={(包)、(剪)、(錘)}={(a1)、(a2)、(a3)};乙策略集為S乙={(包)、(剪)、(錘)}={(b1)、(b2)、(b3)};則甲一個策略ai，和乙一個策略bj就組成一個局勢sij.第14頁9/12/202314OperationsResearch6.2.3支付與支付函數(shù)3、贏得（支付）：當(dāng)每個局中人所采取策略確定后，他們就會得到對應(yīng)收益或損失，稱為局中人支付（Payoff）。若甲一個策略a3(錘)，乙一個策略b2(剪)，則組成一個局勢s32。在局勢s32下，甲支付為：乙支付第15頁9/12/202315OperationsResearch6.2.3支付與支付函數(shù)4、支付（贏得）函數(shù)：不一樣策略會造成不一樣支付，所以，支付是策略(準(zhǔn)確說應(yīng)該是局勢)函數(shù)，稱為支付函數(shù)(payofffunction)。對于例4，兩人支付函數(shù)分別記為：和比如，對于策略a3,b1第16頁9/12/202316OperationsResearch6.2.3支付與支付函數(shù)5、零和對策和非零和對策

依據(jù)各局中人支付代數(shù)和是否為0，將對策分為零和對策和非零和對策(non-zero-sumgames)。若在任一局對策中，全體局中人支付總和為0，則該對策稱為零和對策，不然稱為非零和對策(non-zero-sumgames)。對于前例，顯然為零和對策，因為第17頁9/12/202317OperationsResearch6.2.3支付與支付函數(shù)6、對策分類依據(jù)局中人數(shù)目和支付函數(shù)代數(shù)和有限對策n人對策(n>2)對策合作對策非合作對策第18頁9/12/202318OperationsResearch6.3矩陣對策概念及模型1、定義：兩個人零和對策稱為矩陣對策例，“包、剪、錘”游戲中，甲、乙雙方各有三種不一樣策略，分別為：第19頁9/12/202319OperationsResearch6.3矩陣對策概念及模型甲支付情況以下表β1(包)β2(剪)β3(錘)α1(包)0-11α2(剪)10-1α3(錘)-110乙策略甲支付甲策略表6.1第20頁9/12/202320OperationsResearch6.3矩陣對策概念及模型齊王賽馬β1β2β3β4β5β6α1(上中下)31111-1α2(上下中)1311-11α3(中上下)1-13111α4(中下上)-111311α5(下中上)11-1131α6(下上中)111-113田忌策略齊王贏得齊王策略上中下上下中中上下中下上下中上下上中第21頁9/12/202321OperationsResearch6.3矩陣對策概念及模型表6.1中數(shù)字用矩陣形式表示A稱為甲支付矩陣。顯然，乙支付矩陣為-A。所以，該對策可記為：第22頁9/12/202322OperationsResearch6.3矩陣對策概念及模型2、矩陣對策模型普通地，若局中人Ⅰ，Ⅱ策略集分別為：為了與后面概念區(qū)分開來，我們稱αi為Ⅰ純策略，βj為Ⅱ純策略，對于純策略αi,βj組成策略偶(αi,βj)稱為純局勢。

第23頁9/12/202323OperationsResearch6.3矩陣對策概念及模型若Ⅰ支付矩陣為：αij表示局勢(αi,βj)下，局中人Ⅰ支付,則矩陣對策可記為G={S1,S2,A}：即矩陣對策模型。第24頁9/12/202324OperationsResearch6.4矩陣對策純策略解6.4.1矩陣對策純策略解例解過程6.4.2矩陣對策純策略解理論基礎(chǔ)6.4.3矩陣對策純策略解性質(zhì)第25頁9/12/202325OperationsResearch例5設(shè)二人零和對策G={S1,S2,A}，，其中6.4.1矩陣對策純策略解例解過程而且局中Ⅰ支付矩陣為：兩位局中人都想自己支付最大化。第26頁9/12/202326OperationsResearch6.4.1矩陣對策純策略解例解過程這里我們認(rèn)為局中人都是理智，從矩陣A進行邏輯推理可知：假如局中人Ⅰ采取α3作策略，雖有可能取得最大支付18，不過,局中人Ⅱ分析到Ⅰ這種心理，就會采取β3策略，使Ⅰ不但得不到最大值18，反而取得很壞結(jié)果-8；一樣，局中人Ⅱ為了得到最大支付+12(即局中人Ⅰ支付-12)，會采取β2作為策略,但局中人Ⅰ也會猜到Ⅱ這種心理,而采取α2作策略，這么局中人Ⅱ只能得到-3。第27頁9/12/202327OperationsResearch6.4.1矩陣對策純策略解例解過程從以上分析能夠看出，局中人Ⅰ選取最優(yōu)策略時應(yīng)該考慮到Ⅱ也是十分理智與精明，Ⅱ策略是要以Ⅰ支付最少為目標(biāo)，所以不能存在任何僥幸心理。局中人Ⅱ也應(yīng)作一樣考慮。

對于局中人來說，應(yīng)該是從最壞處著想向最好處努力。第28頁9/12/202328OperationsResearch6.4.1矩陣對策純策略解例解過程對局中人Ⅰ來講，各策略最壞結(jié)果分別為： min{-6,2,-7}=-7 min{5,3,6}=3 min{18,0,-8}=-8 min{-2,-12,7}=-12這些最壞情況中，最好結(jié)果是： max{-7,3,-8,-12}=3第29頁9/12/202329OperationsResearch6.4.1矩陣對策純策略解例解過程一樣，對局中人Ⅱ而言，各策略最壞結(jié)果分別為： max{-6,5,18,-2}=18 max{2,3,0,-12}=3 max{-7,6,-18,7}=7在這些最壞情況中，最好結(jié)果（損失最?。┦?min{18,3,7}=3第30頁9/12/202330OperationsResearch6.4.1矩陣對策純策略解例解過程β1β2β3α1-62-7-7α25363α3180-8-8α4-2-127-121837第31頁9/12/202331OperationsResearch6.4.1矩陣對策純策略解例解過程課堂練習(xí):求解對策 G=﹛S1,S2,A﹜已知：第32頁9/12/202332OperationsResearch定義1對于矩陣對策G=﹛S1,S2,A﹜,假如存在純局勢6.4.2矩陣對策純策略解理論基礎(chǔ)則稱局勢為對策G在純策略中解。亦稱其為G鞍點(saddlepoint):(列中最大，行中最小)使得對任意j=1,…，n,及任意i=1,…m有：第33頁9/12/202333OperationsResearch6.4.2矩陣對策純策略解理論基礎(chǔ)

分別稱為局中人Ⅰ，Ⅱ最優(yōu)純策略。稱為對策G值(value)，記為第34頁9/12/202334OperationsResearch6.4.2矩陣對策純策略解理論基礎(chǔ)定理1矩陣對策G={S1,S2,A}存在最優(yōu)純策略充分必要條件為：第35頁9/12/202335OperationsResearch6.4.2矩陣對策純策略解理論基礎(chǔ)求對G解和值。例6已知G={S1,S2,A}，其中,第36頁9/12/202336OperationsResearch6.4.2矩陣對策純策略解理論基礎(chǔ)β1β2β3β4α186866α2134-3-3α396766α4-31103-3961066解：依據(jù)A可得第37頁9/12/202337OperationsResearch6.4.2矩陣對策純策略解理論基礎(chǔ)因為：四個局勢均為G鞍點，且故知：第38頁9/12/202338OperationsResearch6.4.3矩陣對策純策略解性質(zhì)從上例可知，對策解能夠是不唯一，但對策值是唯一。對策解不唯一時，應(yīng)滿足下面兩條性質(zhì)：1.無差異性：若與

是矩陣對策G兩個解，則即對策值相等，它們在矩陣中元素相同。第39頁9/12/202339OperationsResearch6.4.3矩陣對策純策略解性質(zhì)2.可交換性：若與是矩陣對策G兩個解,則與也是對策解。第40頁9/12/202340OperationsResearch6.4.3矩陣對策純策略解性質(zhì)是不是每一個矩陣對策都有純策略解（鞍點）？β1β2β3α10-11-1α210-1-1α3-110-1111答案是否定。第41頁9/12/202341OperationsResearch6.5矩陣對策混合策略解6.5.1混合策略與混合擴充（mixedstrategicsolution）6.5.2解基本定理第42頁9/12/202342OperationsResearch6.5.1混合策略與混合擴充β1β2α1363α2544561、問題提出第43頁9/12/202343OperationsResearch6.5.1混合策略與混合擴充該對策問題表明不存在使對立雙方到達(dá)平衡局勢，所以，局中人采取任何一個純策略，都有一定風(fēng)險。所以，在這種情況下，局中人必須隱瞞自己選取策略意圖。第44頁9/12/202344OperationsResearch6.5.1混合策略與混合擴充2、問題處理方案設(shè)計這時我們能夠構(gòu)想局中人隨機地選取純策略來進行對策。即在一局對策中，局中人Ⅰ以概率

來選取純策略,其中滿足

于是得到一個m維概率向量第45頁9/12/202345OperationsResearch6.5.1混合策略與混合擴充一樣對于局中人Ⅱ,有對應(yīng)一個n維概率向量滿足yj表示局中人Ⅱ選取純策略βj概率。第46頁9/12/202346OperationsResearch6.5.1混合策略與混合擴充3、混合策略概念引入定義:若給定一個矩陣對策G={S1,S2,A},其中則我們把純策略集對應(yīng)概率向量：與分別稱作局中人Ⅰ、Ⅱ混合策略，(X,Y)稱為一個混合局勢。第47頁9/12/202347OperationsResearch6.5.1混合策略與混合擴充假如局中人Ⅰ選取策略為

局中人Ⅱ選取

因為兩局中人分別選取策略

事件能夠看成使相互獨立4、混合策略局中人支付

假如局中人Ⅰ選取策略為第48頁9/12/202348OperationsResearch6.5.1混合策略與混合擴充就是局中人Ⅰ支付值。所以局勢(αi，βj)出現(xiàn)概率是xiyj。從而知局中人Ⅰ支付αij概率是xiyj。于是，數(shù)學(xué)期望值：第49頁9/12/202349OperationsResearch6.5.1混合策略與混合擴充令：則稱為G混合擴充。5、混合擴充第50頁9/12/202350OperationsResearch6.5.1混合策略與混合擴充定義2假如存在,滿足:對任意及都有：則稱為G（在混合策略下）解.

分別稱為局中人Ⅰ、Ⅱ最優(yōu)(混合)策略.稱為對策G（在混合意義下）值，記為第51頁9/12/202351OperationsResearch6.5.1混合策略與混合擴充例7設(shè)

,其中求它解及值。解：顯然該問題無鞍點解。設(shè)局中人Ⅰ、Ⅱ混合策略分別為：X=(x1,x2),Y=(y1,y2).則第52頁9/12/202352OperationsResearch6.5.1混合策略與混合擴充則局中人Ⅰ支付數(shù)學(xué)期望為：第53頁9/12/202353OperationsResearch6.5.1混合策略與混合擴充可見:當(dāng)?shù)?4頁9/12/202354OperationsResearch6.5.1混合策略與混合擴充顯然第55頁9/12/202355OperationsResearch6.5.1混合策略與混合擴充由定義1知：分別是局中人Ⅰ、Ⅱ最優(yōu)策略，且第56頁9/12/202356OperationsResearch6.5.2解基本定理定理2(基本定理)任意一個矩陣對策其中一定有解(在混合策略意義下),且假如G值是V,則以下兩組不等式解是局中人Ⅰ,Ⅱ最優(yōu)策略:第57頁9/12/202357OperationsResearch6.5.2解基本定理（11-1）（11-2）第58頁9/12/202358OperationsResearch6.5.2解基本定理（1）若則（G值）（2）若則（4）若,則（3）若,則可用例7驗證定理3

若是對策G(同前)最優(yōu)混合局勢,則對某一個i或j來說：第59頁9/12/202359OperationsResearch6.5.2解基本定理y1y2…ynβ1β2…βnx1α1a11a12…a1nV1’x2α2a21a22…a2nV2’…………………xmαmam1am2…amnVm’V1V2…Vn≤V≥V第60頁9/12/202360OperationsResearch6.6矩陣對策解法6.6.1圖解法6.6.2優(yōu)勢法6.6.3簡化計算法6.6.4線性規(guī)劃解法第61頁9/12/202361OperationsResearch6.6.1圖解法例8已知：其中求矩陣對策解和值。第62頁9/12/202362OperationsResearch解:設(shè)局中人Ⅰ混合策略為(x,1-x)T,x∈[0,1]。對局中人Ⅰ而言，他最少可能收入為局中人Ⅱ選取β1，β2所確定兩條直線(定理3知):6.6.1圖解法V1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10因為x1和x2一定大于0在x處縱坐標(biāo)中最小者.局中人Ⅰ用“最大最小”標(biāo)準(zhǔn)選取自己策略,即:第63頁9/12/202363OperationsResearchD點為極值點,D點坐標(biāo)為：

即Ⅰ最優(yōu)混合策略為：

ED(1/4,16?)VV1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10

xF從上圖能夠看出：就是折線EDF.第64頁9/12/202364OperationsResearch6.6.1圖解法同理，對局中人Ⅱ而言有V=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y最小最大點為:即Ⅱ最優(yōu)解為：對策值為：第65頁9/12/202365OperationsResearch6.6.1圖解法FG(5/8,16?)HYV=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y第66頁9/12/202366OperationsResearch6.6.1圖解法課堂練習(xí)p145-10.4-3：求解以下矩陣對策，已知贏得矩陣為：第67頁9/12/202367OperationsResearch6.6.1圖解法例9已知：其中求對策解和值。解：顯然無鞍點，作混合擴充：第68頁9/12/202368OperationsResearch6.6.1圖解法對局中人Ⅰ而言，若Ⅱ選取時，Ⅰ最小可能收入為以下四條直線在x處縱坐標(biāo)中最小者v=2x+4(1-x)=4-2x (1)v=3x+(1-x)=2x+1 (2)v=x+6(1-x)=-5x+6 (3)v=5x (4)第69頁9/12/202369OperationsResearch6.6.1圖解法從圖上能夠看出B點坐標(biāo)即為所求極值點.AB(2)(3)(1)(4)B點坐標(biāo)為:即Ⅰ最優(yōu)解為第70頁9/12/202370OperationsResearch6.6.1圖解法同理可得： v=2y1+3y2+y3+5y4 (5) v=4y1+y2+6y3 (6) 由上節(jié)定理3求出Ⅱ最優(yōu)解將分別代入方程(1)～(4)得：第71頁9/12/202371OperationsResearch6.6.1圖解法定理3(4)定理3(2)定理3(2)定理3(4)第72頁9/12/202372OperationsResearch6.6.1圖解法代入(5)、(6)得：解之得：故Ⅱ最優(yōu)策略為第73頁9/12/202373OperationsResearch6.6.2優(yōu)勢法對于普通矩陣對策其中定義3若對固定i、k有若對固定j和l，有則稱優(yōu)超，記為則稱優(yōu)超，記為第74頁9/12/202374OperationsResearch6.6.2優(yōu)勢法(1)定理4

設(shè)G中某個被其余之一優(yōu)超,由G可得，其中于是有(2)中局中人Ⅱ最優(yōu)策略就是G中Ⅱ最優(yōu)策略；第75頁9/12/202375OperationsResearch6.6.2優(yōu)勢法若是Ⅰ在中最優(yōu)解，則為Ⅰ在G中最優(yōu)解.(3)第76頁9/12/202376OperationsResearch6.6.2優(yōu)勢法例10已知某矩陣對策G支付矩陣為：求解這個矩陣對策。第77頁9/12/202377OperationsResearch6.6.2優(yōu)勢法解：顯然無鞍點，因為A階數(shù)為圖解法失效。由定義可知由定理1可將該問題簡化為:第78頁9/12/202378OperationsResearch6.6.2優(yōu)勢法可用圖解法求得最優(yōu)解和值分別為：由又可看出：從又可看出：，所以得：第79頁9/12/202379OperationsResearch6.6.2優(yōu)勢法即可得到對策G解為：值為V=5。第80頁9/12/202380OperationsResearch6.6.3簡化計算法定理5若矩陣對策其中d為常數(shù)，則G1與G2有相同解，且對策值相差一個常數(shù)d，即：第81頁9/12/202381OperationsResearch6.6.3簡化計算法推論1若矩陣對策其中k>0為常數(shù)，則G1與G2有相同解,且第82頁9/12/202382OperationsResearch6.6.3簡化計算法例11已知某矩陣對策G支付矩陣以下：解：由推論1可取得同解矩陣：第83頁9/12/202383Opera