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

GAME

THEORY

對(duì)策論第11章2/3/2023111矩陣對(duì)策6.1引言6.2對(duì)策論的基本概念6.3矩陣對(duì)策的概念及模型6.4矩陣對(duì)策的純策略解（鞍點(diǎn)解）6.5矩陣對(duì)策的混合策略解（mixedstrategicsolution）6.6矩陣對(duì)策的解法2/3/20232OperationsResearch6.1.1何謂對(duì)策論（GameTheory）？6.1.2對(duì)策的例子6.1.3對(duì)策論的誕生與發(fā)展簡(jiǎn)況6.1引言2/3/20233OperationsResearch6.1.1

何謂對(duì)策論(GameTheory)？

定義：對(duì)策論亦稱(chēng)競(jìng)賽論或博弈論，是研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法。囚徒困境局中人2坦白不坦白局中人1坦白(-6,-6)(-1,-8)不坦白(-8,-1)(-2,-2)2/3/20234OperationsResearch齊王賽馬決斗問(wèn)題：神雕俠侶中武林盟主大會(huì)6.1.2

對(duì)策的例子朱子柳霍都郭靖達(dá)爾巴郝大通金輪法王2/3/20235OperationsResearch6.1.3對(duì)策論的誕生與發(fā)展簡(jiǎn)況早期工作1912年E.Zermelo‘關(guān)于集合論在象棋對(duì)策中的應(yīng)用’

1921年E.Borel引入最優(yōu)策略

1928年J.V.Neumann證明了一些猜想2/3/20236OperationsResearch6.1.3對(duì)策論的誕生與發(fā)展簡(jiǎn)況產(chǎn)生標(biāo)志

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

Nash均衡、經(jīng)濟(jì)博奕論、信息不對(duì)稱(chēng)對(duì)策和廣義對(duì)策2/3/20237OperationsResearch6.2

對(duì)策論的基本概念6.2.1局中人（Player）6.2.2策略（Strategy）6.2.3支付與支付函數(shù)2/3/20238OperationsResearch6.2.1

局中人（Player）1、局中人：在一場(chǎng)競(jìng)爭(zhēng)或斗爭(zhēng)中的決策者稱(chēng)為該局對(duì)策的局中人通常，一局對(duì)策具有兩個(gè)或兩個(gè)以上---決策者，一般用I表示局中人集合：2/3/20239OperationsResearch6.2.1局中人（Player）2、對(duì)策分類(lèi)：依據(jù)局中人的數(shù)量，可將對(duì)策分為有限對(duì)策無(wú)限對(duì)策(n>2)對(duì)策無(wú)限零和對(duì)策無(wú)限非零和對(duì)策有限零和對(duì)策有限非零和對(duì)策2/3/202310OperationsResearch6.2.2

策略（Strategy）1、策略與策略集局中人指導(dǎo)自己自始至終如何行動(dòng)的一個(gè)方案，稱(chēng)為策略(Strategy)由所有策略構(gòu)成的集合，稱(chēng)為策略集(Strategy

Set)2/3/202311OperationsResearch6.2.2

策略（Strategy）2、策略集的元素：對(duì)于局中人i,i∈I，都有自己的策略集Si,通常每一局中人的策略集中至少應(yīng)包括兩個(gè)策略對(duì)于例4的包、剪、錘游戲。假設(shè)有兩個(gè)局中人I={甲，乙}，甲的策略集為S甲={(包)、(剪)、(錘)}={a1、a2、a3};乙的策略集為S乙={(包)、(剪)、(錘)}={b1、b2、b3};2/3/202312OperationsResearch6.2.3

支付與支付函數(shù)1、局勢(shì)：各局中人所選定的策略形成的策略組2、策略組若si是第i個(gè)局中人的一個(gè)策略，則n個(gè)局中人的策略組s=(s1,s2,…,sn)

就是一個(gè)局勢(shì)。2/3/202313OperationsResearch6.2.3

支付與支付函數(shù)例如，對(duì)于包、剪、錘游戲。假設(shè)有兩個(gè)局中人I={甲，乙}，甲的策略集為S甲={(包)、(剪)、(錘)}={(a1)、(a2)、(a3)};乙的策略集為S乙={(包)、(剪)、(錘)}={(b1)、(b2)、(b3)};

則甲的一個(gè)策略ai，和乙的一個(gè)策略bj就構(gòu)成一個(gè)局勢(shì)sij.2/3/202314OperationsResearch6.2.3

支付與支付函數(shù)3、贏得（支付）：當(dāng)每個(gè)局中人所采取的策略確定后，他們就會(huì)得到相應(yīng)的收益或損失，稱(chēng)為局中人的支付（Payoff）。若甲的一個(gè)策略a3(錘)，乙的一個(gè)策略b2(剪)，則構(gòu)成一個(gè)局勢(shì)s32

。在局勢(shì)s32下，甲的支付為：乙的支付2/3/202315OperationsResearch6.2.3

支付與支付函數(shù)4、支付（贏得）函數(shù)：不同的策略會(huì)導(dǎo)致不同的支付，因此，支付是策略(準(zhǔn)確的說(shuō)應(yīng)該是局勢(shì))的函數(shù)，稱(chēng)為支付函數(shù)(payofffunction)。對(duì)于例4，兩人的支付函數(shù)分別記為：和例如，對(duì)于策略a3,b12/3/202316OperationsResearch6.2.3

支付與支付函數(shù)5、零和對(duì)策和非零和對(duì)策

根據(jù)各局中人支付的代數(shù)和是否為0，將對(duì)策分為零和對(duì)策和非零和對(duì)策(non-zero-sumgames)。若在任一局對(duì)策中，全體局中人支付的總和為0，則該對(duì)策稱(chēng)為零和對(duì)策，否則稱(chēng)為非零和對(duì)策(non-zero-sumgames)。對(duì)于前例，顯然為零和對(duì)策，因?yàn)?/3/202317OperationsResearch6.2.3

支付與支付函數(shù)6、對(duì)策分類(lèi)根據(jù)局中人的數(shù)目和支付函數(shù)代數(shù)和有限對(duì)策n人對(duì)策(n>2)對(duì)策合作對(duì)策非合作對(duì)策2/3/202318OperationsResearch6.3

矩陣對(duì)策的概念及模型1、定義：兩個(gè)人零和對(duì)策稱(chēng)為矩陣對(duì)策例，“包、剪、錘”游戲中，甲、乙雙方各有三種不同的策略，分別為：2/3/202319OperationsResearch6.3

矩陣對(duì)策的概念及模型甲的支付情況如下表β1(包)β2(剪)β3(錘)α1(包)0-11α2(剪)10-1α3(錘)-110乙的策略甲的支付甲的策略表6.12/3/202320OperationsResearch6.3

矩陣對(duì)策的概念及模型齊王賽馬

β1β2β3β4β5β6α1(上中下)31111-1α2(上下中)1311-11α3(中上下)1-13111α4(中下上)-111311α5(下中上)11-1131α6(下上中)111-113田忌策略齊王贏得齊王策略上中下上下中中上下中下上下中上下上中2/3/202321OperationsResearch6.3

矩陣對(duì)策的概念及模型表6.1中的數(shù)字用矩陣的形式表示A稱(chēng)為甲的支付矩陣。顯然，乙的支付矩陣為-A。因此，該對(duì)策可記為：2/3/202322OperationsResearch6.3

矩陣對(duì)策的概念及模型2、矩陣對(duì)策的模型一般地，若局中人Ⅰ，Ⅱ的策略集分別為：為了與后面的概念區(qū)分開(kāi)來(lái)，我們稱(chēng)αi為Ⅰ的純策略，βj為Ⅱ的純策略，對(duì)于純策略αi,βj構(gòu)成的策略偶(αi,βj)稱(chēng)為純局勢(shì)。

2/3/202323OperationsResearch6.3

矩陣對(duì)策的概念及模型若Ⅰ的支付矩陣為：αij表示局勢(shì)(αi,βj)下，局中人Ⅰ的支付,則矩陣對(duì)策可記為G={S1,S2,A}：即矩陣對(duì)策模型。2/3/202324OperationsResearch6.4

矩陣對(duì)策的純策略解6.4.1矩陣對(duì)策的純策略解例解過(guò)程6.4.2矩陣對(duì)策的純策略解理論基礎(chǔ)6.4.3矩陣對(duì)策的純策略解性質(zhì)2/3/202325OperationsResearch例5設(shè)二人零和對(duì)策

G={S1,S2,A}，，其中6.4.1矩陣對(duì)策的純策略解例解過(guò)程而且局中Ⅰ的支付矩陣為：兩位局中人都想自己的支付最大化。2/3/202326OperationsResearch6.4.1矩陣對(duì)策的純策略解例解過(guò)程這里我們認(rèn)為局中人都是理智的，從矩陣A進(jìn)行邏輯推理可知：如果局中人Ⅰ采取α3作策略，雖有可能獲得最大支付18，但是,局中人Ⅱ分析到Ⅰ的這種心理，就會(huì)采取β3策略，使Ⅰ不僅得不到最大值18，反而取得很壞的結(jié)果-8；同樣，局中人Ⅱ?yàn)榱说玫阶畲笾Ц?12(即局中人Ⅰ的支付-12)，會(huì)采取β2作為策略,但局中人Ⅰ也會(huì)猜到Ⅱ的這種心理,而采取α2作策略，這樣局中人Ⅱ只能得到-3。2/3/202327OperationsResearch6.4.1矩陣對(duì)策的純策略解例解過(guò)程從以上的分析可以看出，局中人Ⅰ選取最優(yōu)策略時(shí)應(yīng)該考慮到Ⅱ也是十分理智與精明的，Ⅱ的策略是要以Ⅰ支付最少為目的，所以不能存在任何僥幸心理。局中人Ⅱ也應(yīng)作同樣的考慮。

對(duì)于局中人來(lái)說(shuō)，應(yīng)該是從最壞處著想向最好處努力。2/3/202328OperationsResearch6.4.1矩陣對(duì)策的純策略解例解過(guò)程對(duì)局中人Ⅰ來(lái)講，各策略的最壞結(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}=32/3/202329OperationsResearch6.4.1矩陣對(duì)策的純策略解例解過(guò)程同樣，對(duì)局中人Ⅱ而言，各策略的最壞的結(jié)果分別為：

max{-6,5,18,-2}=18 max{2,3,0,-12}=3 max{-7,6,-18,7}=7在這些最壞的情況中，最好的結(jié)果（損失最小）是

min{18,3,7}=32/3/202330OperationsResearch6.4.1矩陣對(duì)策的純策略解例解過(guò)程β1β2β3α1-62-7-7α25363α3180-8-8α4-2-127-1218372/3/202331OperationsResearch6.4.1矩陣對(duì)策的純策略解例解過(guò)程課堂練習(xí):求解對(duì)策 G=﹛S1,S2,A﹜已知：2/3/202332OperationsResearch定義1對(duì)于矩陣對(duì)策G=﹛S1,S2,A﹜,如果存在純局勢(shì)6.4.2矩陣對(duì)策的純策略解理論基礎(chǔ)則稱(chēng)局勢(shì)為對(duì)策G在純策略中的解。亦稱(chēng)其為G的鞍點(diǎn)(saddlepoint):

(列中最大，行中最小)使得對(duì)任意j=1,…，n,及任意i=1,…m有：2/3/202333OperationsResearch6.4.2矩陣對(duì)策的純策略解理論基礎(chǔ)

分別稱(chēng)為局中人Ⅰ，Ⅱ的最優(yōu)純策略。稱(chēng)

為對(duì)策G的值(value)，記為2/3/202334OperationsResearch6.4.2矩陣對(duì)策的純策略解理論基礎(chǔ)定理1矩陣對(duì)策G={S1,S2,A}存在最優(yōu)純策略的充分必要條件為：2/3/202335OperationsResearch6.4.2矩陣對(duì)策的純策略解理論基礎(chǔ)求對(duì)G的解和值。例6已知G={S1,S2,A}，其中,2/3/202336OperationsResearch6.4.2矩陣對(duì)策的純策略解理論基礎(chǔ)β1β2β3β4α186866α2134-3-3α396766α4-31103-3961066解：根據(jù)A可得2/3/202337OperationsResearch6.4.2矩陣對(duì)策的純策略解理論基礎(chǔ)由于：四個(gè)局勢(shì)均為G的鞍點(diǎn)，且故知：2/3/202338OperationsResearch6.4.3矩陣對(duì)策的純策略解性質(zhì)從上例可知，對(duì)策的解可以是不唯一的，但對(duì)策的值是唯一的。對(duì)策解不唯一時(shí)，應(yīng)滿足下面兩條性質(zhì)：1.無(wú)差別性：若與

是矩陣對(duì)策G的兩個(gè)解，則即對(duì)策值相等，它們?cè)诰仃囍械脑叵嗤?/3/202339OperationsResearch6.4.3矩陣對(duì)策的純策略解性質(zhì)2.可交換性：若與是矩陣對(duì)策G的兩個(gè)解,則與也是對(duì)策的解。2/3/202340OperationsResearch6.4.3矩陣對(duì)策的純策略解性質(zhì)是不是每一個(gè)矩陣對(duì)策都有純策略解（鞍點(diǎn)）？β1β2β3α10-11-1α210-1-1α3-110-1111答案是否定的。2/3/202341OperationsResearch6.5矩陣對(duì)策的混合策略解6.5.1混合策略與混合擴(kuò)充（mixedstrategicsolution）6.5.2解的基本定理2/3/202342OperationsResearch6.5.1混合策略與混合擴(kuò)充β1β2α1363α2544561、問(wèn)題提出2/3/202343OperationsResearch6.5.1混合策略與混合擴(kuò)充該對(duì)策問(wèn)題表明不存在使對(duì)立雙方達(dá)到平衡的局勢(shì)，因此，局中人采取任何一種純策略，都有一定的風(fēng)險(xiǎn)。所以，在這種情況下，局中人必須隱瞞自己選取策略的意圖。2/3/202344OperationsResearch6.5.1混合策略與混合擴(kuò)充2、問(wèn)題處理方案設(shè)計(jì)這時(shí)我們可以設(shè)想局中人隨機(jī)地選取純策略來(lái)進(jìn)行對(duì)策。即在一局對(duì)策中，局中人Ⅰ以概率

來(lái)選取純策略,其中的滿足

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

局中人Ⅱ選取

由于兩局中人分別選取策略

的事件可以看成使相互獨(dú)立4、混合策略的局中人支付

如果局中人Ⅰ選取的策略為2/3/202348OperationsResearch6.5.1混合策略與混合擴(kuò)充就是局中人Ⅰ的支付值。所以局勢(shì)(αi，βj)出現(xiàn)的概率是xiyj。從而知局中人Ⅰ支付αij的概率是xiyj。于是，數(shù)學(xué)期望值：2/3/202349OperationsResearch6.5.1混合策略與混合擴(kuò)充令：則稱(chēng)為G的混合擴(kuò)充。5、混合擴(kuò)充2/3/202350OperationsResearch6.5.1混合策略與混合擴(kuò)充定義2

如果存在,滿足:對(duì)任意及均有：則稱(chēng)為G（在混合策略下的）解.

分別稱(chēng)為局中人Ⅰ、Ⅱ的最優(yōu)(混合)策略.稱(chēng)為對(duì)策G（在混合意義下的）值，記為2/3/202351OperationsResearch6.5.1混合策略與混合擴(kuò)充例7

設(shè)

,其中求它的解及值。解：顯然該問(wèn)題無(wú)鞍點(diǎn)解。設(shè)局中人Ⅰ、Ⅱ的混合策略分別為：

X=(x1,x2),Y=(y1,y2).則2/3/202352OperationsResearch6.5.1混合策略與混合擴(kuò)充則局中人Ⅰ支付的數(shù)學(xué)期望為：2/3/202353OperationsResearch6.5.1混合策略與混合擴(kuò)充可見(jiàn):當(dāng)2/3/202354OperationsResearch6.5.1混合策略與混合擴(kuò)充顯然2/3/202355OperationsResearch6.5.1混合策略與混合擴(kuò)充由定義1知：分別是局中人Ⅰ、Ⅱ的的最優(yōu)策略，且2/3/202356OperationsResearch6.5.2

解的基本定理定理2(基本定理)

任意一個(gè)矩陣對(duì)策其中一定有解(在混合策略意義下),且如果G的值是V,則以下兩組不等式的解是局中人Ⅰ,Ⅱ的最優(yōu)策略:2/3/202357OperationsResearch6.5.2

解的基本定理（11-1）（11-2）2/3/202358OperationsResearch6.5.2

解的基本定理（1）若則（G的值）（2）若則（4）若,則（3）若,則可用例7驗(yàn)證定理3

若

是對(duì)策G(同前)的最優(yōu)混合局勢(shì),則對(duì)某一個(gè)i或j來(lái)說(shuō)：2/3/202359OperationsResearch6.5.2

解的基本定理y1y2…ynβ1β2…βnx1α1a11a12…a1nV1’x2α2a21a22…a2nV2’…………………xmαmam1am2…amnVm

’V1V2…Vn≤V≥V2/3/202360OperationsResearch6.6

矩陣對(duì)策的解法6.6.1圖解法6.6.2優(yōu)勢(shì)法6.6.3

簡(jiǎn)化計(jì)算法6.6.4

線性規(guī)劃解法2/3/202361OperationsResearch6.6.1圖解法例8

已知：其中求矩陣對(duì)策的解和值。2/3/202362OperationsResearch解:設(shè)局中人Ⅰ的混合策略為(x,1-x)T,x∈[0,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)中的最小者.局中人Ⅰ用“最大最小”原則選取自己的策略,即:2/3/202363OperationsResearchD點(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.2/3/202364OperationsResearch6.6.1

圖解法同理，對(duì)局中人Ⅱ而言有V=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y最小最大點(diǎn)為:即Ⅱ的最優(yōu)解為：對(duì)策值為：2/3/202365OperationsResearch6.6.1

圖解法FG(5/8,16?)HYV=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y2/3/202366OperationsResearch6.6.1

圖解法課堂練習(xí)p145-10.4-3：求解下列矩陣對(duì)策，已知贏得矩陣為：2/3/202367OperationsResearch6.6.1

圖解法例9

已知：其中求對(duì)策的解和值。解：顯然無(wú)鞍點(diǎn)，作混合擴(kuò)充：2/3/202368OperationsResearch6.6.1

圖解法對(duì)局中人Ⅰ而言，若Ⅱ選取時(shí)，Ⅰ的最小可能收入為以下四條直線在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)2/3/202369OperationsResearch6.6.1

圖解法從圖上可以看出B點(diǎn)坐標(biāo)即為所求的極值點(diǎn).AB(2)(3)(1)(4)B點(diǎn)坐標(biāo)為:即Ⅰ的最優(yōu)解為2/3/202370OperationsResearch6.6.1

圖解法同理可得：

v=2y1+3y2+y3+5y4 (5) v=4y1+y2+6y3 (6) 由上節(jié)的定理3求出Ⅱ的最優(yōu)解將分別代入方程(1)～(4)得：2/3/202371OperationsResearch6.6.1

圖解法定理3的(4)定理3的(2)定理3的(2)定理3的(4)2/3/202372OperationsResearch6.6.1

圖解法代入(5)、(6)得：解之得：故Ⅱ的最優(yōu)策略為2/3/202373OperationsResearch6.6.2

優(yōu)勢(shì)法對(duì)于一般的矩陣對(duì)策其中定義3

若對(duì)固定的i、k有若對(duì)固定的j和l，有則稱(chēng)優(yōu)超，記為則稱(chēng)優(yōu)超，記為2/3/202374OperationsResearch6.6.2

優(yōu)勢(shì)法(1)定理4

設(shè)G中的某個(gè)被其余的之一優(yōu)超,由G可得，其中于是有

(2)中局中人Ⅱ的最優(yōu)策略就是G中Ⅱ的最優(yōu)策略；2/3/202375OperationsResearch6.6.2

優(yōu)勢(shì)法若是Ⅰ在中的最優(yōu)解，則為Ⅰ在G中的最優(yōu)解.(3)2/3/202376OperationsResearch6.6.2

優(yōu)勢(shì)法例10已知某矩陣對(duì)策G的支付矩陣為：求解這個(gè)矩陣對(duì)策。2/3/202377OperationsResearch6.6.2

優(yōu)勢(shì)法解：顯然無(wú)鞍點(diǎn)，由于A的階數(shù)為圖解法失效。由定義可知由定理1可將該問(wèn)題簡(jiǎn)化為:2/3/202378OperationsResearch6.6.2

優(yōu)勢(shì)法可用圖解法求得最優(yōu)解和值分別為：由又可看出：從又可看出：，因此得：2/3/202379OperationsResearch6.6.2

優(yōu)勢(shì)法即可得到對(duì)策G的解為：值為V=5。2/3/202380OperationsResearch6.6.3簡(jiǎn)化計(jì)算法定理5若矩陣對(duì)策其中d為常數(shù)，則G1與G2有相同的解，且對(duì)策的值相差一個(gè)常數(shù)d，即：2/3/202381OperationsResearch6.6.3簡(jiǎn)化計(jì)算法推論1若矩陣對(duì)策其中k>0為常數(shù)，則G1與G2有相同的解,且2/3/202382OperationsResearch6