對(duì)策理論謝家平

對(duì)策理論謝家平第1頁(yè)/共41頁(yè)2第10章

對(duì)策理論

理解對(duì)策模型的三大要素了解矩陣對(duì)策的基本定理

通曉純策略和混合策略

掌握矩陣對(duì)策方程組法理解納什定理和平衡偶掌握雙矩陣對(duì)策的求解第2頁(yè)/共41頁(yè)3“田忌賽馬”對(duì)策論（GameTheory），亦名“博弈論”

研究具有斗爭(zhēng)或競(jìng)爭(zhēng)性質(zhì)現(xiàn)象的數(shù)學(xué)理論第1節(jié)對(duì)策論簡(jiǎn)介具有競(jìng)爭(zhēng)或?qū)剐再|(zhì)的行為研究對(duì)策行為中競(jìng)爭(zhēng)各方是否存在最合理行動(dòng)方案,以及如何找到最合理行為方案的管理優(yōu)化理論和方法一個(gè)決策主體,面對(duì)不確定環(huán)境下的收益最大化行為第3頁(yè)/共41頁(yè)4對(duì)策模型三要素局中人：在一個(gè)對(duì)策行為(或一局對(duì)策)中，有權(quán)決定自己行動(dòng)方案的對(duì)策參加者。I={1,2,...,n}。理性人（有很好定義的偏好，在給定的約束下最大化偏好）策略集：指一局對(duì)策中,可供局中人選擇的實(shí)際、可行、完整的行動(dòng)方案，Si贏得函數(shù)：對(duì)任一局勢(shì)s,局中人i可以得到一個(gè)贏得值Hi(s)。顯然,Hi(s)是局勢(shì)的函數(shù),稱為第個(gè)局中人的贏得函數(shù)(或支付函數(shù))。第4頁(yè)/共41頁(yè)5對(duì)策問(wèn)題的分類二人對(duì)策，多人對(duì)策零和對(duì)策，非零和對(duì)策合作對(duì)策，非合作對(duì)策有限對(duì)策，無(wú)限對(duì)策根據(jù)對(duì)策模型的數(shù)學(xué)特征：第5頁(yè)/共41頁(yè)6第2節(jié)矩陣對(duì)策一、矩陣對(duì)策的數(shù)學(xué)模型設(shè)局中人Ⅰ有個(gè)純策略,局中人II有個(gè)純策略,則局中人Ⅰ、Ⅱ的策略集分別為當(dāng)局中人Ⅰ選定純策略和局中人II選定純策略后,就形成了一個(gè)純局勢(shì)?？梢?jiàn)這樣的純局勢(shì)共有個(gè)。對(duì)任一純局勢(shì),記局中人Ⅰ的贏得值為。矩陣對(duì)策（二人有限零和對(duì)策,finitetwo-personzero-sumgame）第6頁(yè)/共41頁(yè)為局中人I的贏得矩陣(或?yàn)榫种腥薎I的支付矩陣)第7頁(yè)/共41頁(yè)其中：齊王的策略集:S1={1,2,3,4,5,6}，田忌的策略集：S2={1,2,3,4,5,6}。下面矩陣稱齊王的贏得矩陣：8例10-1“田忌賽馬”齊王在各局勢(shì)中的益損值表（單位：千金）第8頁(yè)/共41頁(yè)第9頁(yè)/共41頁(yè)當(dāng)贏得矩陣A=(ark)中等式成立時(shí)，雙方才有最優(yōu)純策略并把（r,k）稱為最優(yōu)純局勢(shì)或?qū)Σ逩在純策略下的解，又稱鞍點(diǎn)。把其值v稱之為對(duì)策G={S1，S2，A}的值。稱G為有鞍點(diǎn)的對(duì)策。10矩陣對(duì)策的純策略悲觀準(zhǔn)則第10頁(yè)/共41頁(yè)11乙甲β1β2β3min(aij)α1-71-8-8α23242α316-1-3-3α4-305-3max(aij)1625例10-2甲方“小中取大”，乙方“大中取小”=a22=2鞍點(diǎn)（2,2）對(duì)策G={S1，S2，A}的值v=2。第11頁(yè)/共41頁(yè)矩陣對(duì)策的混合策略設(shè)矩陣對(duì)策G={S1,S2,A}。當(dāng)時(shí)，不存在最優(yōu)純策略。例11-412第12頁(yè)/共41頁(yè)對(duì)甲（乙）給出一個(gè)選取不同策略的概率分布，以使甲（乙）在各種情況下的期望贏得最多（損失最少）--即混合策略。ⅡⅠβ1β2概率xiα136x1α254x2概率yjy1y2第13頁(yè)/共41頁(yè)14取,則故和分別為局中人Ⅰ和Ⅱ的最優(yōu)策略,對(duì)策值(局中人Ⅰ的贏得期望值)。第14頁(yè)/共41頁(yè)二階矩陣對(duì)策的通解公式乙甲β1β2甲方概率xiα1acx1α2bdx2乙方概率yjy1y2第15頁(yè)/共41頁(yè)16第16頁(yè)/共41頁(yè)二、矩陣對(duì)策的基本原理當(dāng)局中人Ⅰ取純策略時(shí),記其相應(yīng)的贏得函數(shù)為當(dāng)局中人Ⅱ取純策略時(shí),記其相應(yīng)的贏得函數(shù)為則是G的解的充要條件是：第17頁(yè)/共41頁(yè)則是G的解的充要條件是：存在數(shù)v,使得和分別是不等式組(Ⅰ)和(Ⅱ)的解,且。(Ⅰ)(Ⅱ)第18頁(yè)/共41頁(yè)矩陣對(duì)策及其解的性質(zhì)定理1：對(duì)任一矩陣,一定存在混合策略意義下的解。定理2：設(shè)是矩陣對(duì)策G的解,,則：(1)若,則；（2)若,則；(3)若,則；(4)若,則。第19頁(yè)/共41頁(yè)第20頁(yè)/共41頁(yè)21記矩陣對(duì)策G的解集為T(G),關(guān)于對(duì)策解集的性質(zhì)有如下三個(gè)定理：定理3：設(shè)有兩個(gè)矩陣對(duì)策

其中,,L為任一常數(shù),則有(1)(2)第21頁(yè)/共41頁(yè)定理4設(shè)有兩個(gè)矩陣對(duì)策其中為任一常數(shù)。則(1)(2)

定理5設(shè)為一矩陣對(duì)策,且為斜對(duì)稱矩陣(亦稱對(duì)稱對(duì)策)，則(1)(2),其中和分別為局中人Ⅰ和Ⅱ的最優(yōu)策略集。第22頁(yè)/共41頁(yè)23矩陣對(duì)策的優(yōu)超策略定義：設(shè)有矩陣對(duì)策,其中,,如果對(duì)一切都有,則稱局中人Ⅰ的純策略優(yōu)超于；若對(duì)一切

,都有，則稱局中人Ⅱ的純策略優(yōu)超于第23頁(yè)/共41頁(yè)24

優(yōu)超原則：設(shè)為矩陣對(duì)策,其中,,,

如果純策略被其余純策略中之一所優(yōu)超，由G可得到一個(gè)新的矩陣對(duì)策G’,,其中：于是有：(1)(2)G’中局中人Ⅱ的最優(yōu)策略就是其在G中的最優(yōu)策略;(3)若G是G’中局中人Ⅰ的最優(yōu)策略,則便是其在G中的最優(yōu)策略。若不是為純策略中之一所優(yōu)超,而是為的某個(gè)凸線性組合所優(yōu)超，定理的結(jié)論仍然成立。第24頁(yè)/共41頁(yè)例10-5第25頁(yè)/共41頁(yè)第26頁(yè)/共41頁(yè)27三、矩陣對(duì)策的解法方程組法例10-6：求解矩陣對(duì)策——“田忌賽馬”解：已知齊王的贏得矩陣為易知,A沒(méi)有鞍點(diǎn),即對(duì)齊王和田忌來(lái)說(shuō)都不存在最優(yōu)純策略。設(shè)齊王和田忌的最優(yōu)混合策略為和，從矩陣A的元素來(lái)看,每個(gè)局中人選取每個(gè)純策略的可能性都是存在的,故可事先假定和,于是求解線性方程組：第27頁(yè)/共41頁(yè)28(I)(II)得到：，故齊王和田忌的最優(yōu)混合策略為雙方都以1/6的概率選取每個(gè)純策略。第28頁(yè)/共41頁(yè)線性規(guī)劃法(Ⅰ)(Ⅱ)第29頁(yè)/共41頁(yè)第30頁(yè)/共41頁(yè)(Ⅰ)(Ⅱ)第31頁(yè)/共41頁(yè)32例10-7：利用線形規(guī)劃方法求解贏得矩陣為A的矩陣對(duì)策

求最優(yōu)解及值。第32頁(yè)/共41頁(yè)（P)解：此題無(wú)鞍點(diǎn),設(shè)局中人Ⅰ、局中人Ⅱ的混合策略分別為：并記對(duì)策的值為V。則此問(wèn)題可化為：（D)第33頁(yè)/共41頁(yè)解得即原問(wèn)題的解為：由第34頁(yè)/共41頁(yè)35第3節(jié)雙矩陣對(duì)策

雙矩陣對(duì)策（二人有限非零和對(duì)策）的數(shù)學(xué)模型局中人I選擇,局中人II選擇,則對(duì)策局勢(shì)為,與這個(gè)局勢(shì)相應(yīng)的局中人I的收入為aij,局中人II的收入不再是-aij,而是bij,記作(aij,bij)。對(duì)這種對(duì)策,通常用G={I,II;S1,S2;A,B}表示,其中A={aij},B={bij}分別是局中人I與II的支付矩陣。第35頁(yè)/共41頁(yè)

囚徒B

坦白抵賴

坦白囚徒A

抵賴（囚徒A，囚徒B）

-8，-80，-10-10，0-1，-1囚徒困境第36頁(yè)/共41頁(yè)雙矩陣對(duì)策的解法平衡偶在非零和對(duì)策中,設(shè)EI=(X,Y)與EII=(X,Y)分別是局中人I與II的收入,這里X∈S1,Y∈S2為任意策略。如果存在一對(duì)策略X*∈S1,Y*∈S2使得EI=(X,Y*)≤EI=(X*,Y*),EI=(X*,Y)≤EI=(X*,Y*)對(duì)任意的X∈S1,Y∈S2均成立,則稱策略(X*,Y*)為雙矩陣對(duì)策G的一個(gè)平衡偶納什定理：（美國(guó)科學(xué)家納什,1951年）任何具有有限個(gè)純策略的二人對(duì)策(包括零和對(duì)策與非零和對(duì)策),至少有一個(gè)平衡偶第37頁(yè)/共41頁(yè)38例10-8：智豬博弈籠子里面有兩只豬,一只大一只小?；\子很長(zhǎng),一頭有一個(gè)踏板,另一頭是飼料的出口和食槽。每踩一下踏板,在遠(yuǎn)離踏板的豬圈一邊的投食口就會(huì)落下少量的食物。如果有一只豬去踩踏板,另一只豬就有機(jī)會(huì)搶先吃到另一邊落下的食物。按一下按鈕會(huì)有10個(gè)單位的豬食進(jìn)槽,但是誰(shuí)按按鈕就會(huì)首先付出2個(gè)單位的成本。若大豬先到槽邊,大小豬吃到食物的比例是9∶1；若大小豬同時(shí)到槽邊進(jìn)食,它們吃到食物的比例是7∶3；若小豬先到槽邊,它們吃到食物的比例是6∶4。如表10—2所示,那么,在兩頭豬都有智慧的前提下,最終結(jié)果是什么呢？智豬博弈雙矩陣： 小豬按等待大豬按（5,1）（4,4）等待（9，-1）（0,0）第38頁(yè)/共41頁(yè)解:以智豬博弈為例,說(shuō)明純策略下的納什均衡的求取。(1)當(dāng)小豬選擇按按鈕時(shí),如果大豬也選擇按按鈕,大豬的贏得是5；如果大豬選擇等待,大豬的贏得是9,所以在第一列的9下面劃線；(2)當(dāng)小豬選擇等待時(shí),如果大豬選擇按按鈕,大豬的贏得是4；如果大豬也選擇等待,大豬的贏得是0,所以在第二列的第一個(gè)分量4下面劃線；(3)當(dāng)大豬選擇按按鈕時(shí),如果小豬選擇按按鈕,小豬的贏得是1；如