運(yùn)籌學(xué) 對(duì)策論

1、第第1頁頁運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外運(yùn)運(yùn) 籌籌 學(xué)學(xué) 課課 件件對(duì)對(duì) 策策 論論Game TheoryGame Theory第第2頁頁 概論概論 解的概念解的概念 矩陣對(duì)策的解法矩陣對(duì)策的解法 合作對(duì)策合作對(duì)策對(duì)對(duì) 策策 論論第第3頁頁概概 論論 名稱名稱 Game Theory 博奕論博奕論 發(fā)展歷史發(fā)展歷史 對(duì)策論模型對(duì)策論模型 分分 類類 例例 子子第第4頁頁發(fā)發(fā) 展展 簡簡 史史 早期工作早期工作1912年年E.Zermelo “關(guān)于集合論在象棋對(duì)策中的應(yīng)用關(guān)于集合論在象棋對(duì)策中的應(yīng)用”1921年年E.Borel 引入最優(yōu)策略引入最優(yōu)策略192

2、8年年J.V.Neumann證明了一些猜想證明了一些猜想 產(chǎn)生標(biāo)志產(chǎn)生標(biāo)志1944年年J.V.Neumann和和O.Morgenstern “對(duì)策論與經(jīng)濟(jì)對(duì)策論與經(jīng)濟(jì)行為行為” 發(fā)展成熟發(fā)展成熟Nash均衡、經(jīng)濟(jì)博奕論、信息不對(duì)稱對(duì)策和廣義對(duì)策均衡、經(jīng)濟(jì)博奕論、信息不對(duì)稱對(duì)策和廣義對(duì)策第第5頁頁模模 型型 局中人局中人 兩個(gè)或兩個(gè)以上兩個(gè)或兩個(gè)以上-決策者決策者 策略集合策略集合 策略策略-決策決策 局勢局勢-狀態(tài)狀態(tài) 支付函數(shù)支付函數(shù) 支付關(guān)于局勢的函數(shù)支付關(guān)于局勢的函數(shù)-決策依據(jù)和標(biāo)準(zhǔn)決策依據(jù)和標(biāo)準(zhǔn) 模型模型SsnisHi ,.,2 , 1);( IisHIiSNIii),(,.,2 ,

3、1 niSi,.,2 , 1; ,.,2 , 1nI iniSS 1 第第6頁頁分分 類類 局中人局中人 兩人對(duì)策、多人對(duì)策兩人對(duì)策、多人對(duì)策 策略策略 有限對(duì)策、無限對(duì)策；非合作對(duì)策、合作對(duì)策有限對(duì)策、無限對(duì)策；非合作對(duì)策、合作對(duì)策 支付支付 零和對(duì)策、非零和對(duì)策零和對(duì)策、非零和對(duì)策 時(shí)間時(shí)間 單階段對(duì)策、多階段對(duì)策單階段對(duì)策、多階段對(duì)策第第7頁頁例例 子子 兩個(gè)參加者甲、乙各出示一枚硬幣，在不讓對(duì)方看見兩個(gè)參加者甲、乙各出示一枚硬幣，在不讓對(duì)方看見的情況下，將硬幣放在桌子上，若兩個(gè)硬幣都呈正面的情況下，將硬幣放在桌子上，若兩個(gè)硬幣都呈正面或都呈反面則甲得或都呈反面則甲得1分，乙付出分，乙付

4、出1分；若兩個(gè)硬幣一個(gè)分；若兩個(gè)硬幣一個(gè)呈正面另一個(gè)呈反面則乙得呈正面另一個(gè)呈反面則乙得1分，甲付出分，甲付出1分。分。 局中人局中人：甲、乙：甲、乙策略策略：, 2 , 1; iSi正面，反面正面，反面 局勢局勢： S （正，反） （正，正） （反，正） （反，反）（正，反） （正，正） （反，正） （反，反） 支付函數(shù)支付函數(shù)：正，反）正，反）(1H= =- -1 1，正，正）正，正）(1H=1=1，反，正）反，正）(1H= =- -1 1，反，反）反，反）(1H=1=1； 反，正）反，正）(2H=1=1，正，正）正，正）(2H= =- -1 1，反，正）反，正）(2H=1=1，反，反）反

5、，反）(2H= =- -1 1。該問題是一個(gè)兩人單階段非合作零和對(duì)策。該問題是一個(gè)兩人單階段非合作零和對(duì)策。 第第8頁頁解解 的的 概概 念念 矩陣對(duì)策矩陣對(duì)策 對(duì)抗對(duì)策對(duì)抗對(duì)策 N人有限對(duì)策人有限對(duì)策 混合策略混合策略第第9頁頁矩矩 陣陣 對(duì)對(duì) 策策 設(shè)定設(shè)定 最穩(wěn)妥策略最穩(wěn)妥策略 性質(zhì)性質(zhì) 對(duì)策的解對(duì)策的解 例子例子第第10頁頁設(shè)設(shè) 定定 兩人有限零和對(duì)策兩人有限零和對(duì)策 局中人：局中人：兩人兩人 策略集策略集: 局勢集：局勢集： 支付函數(shù)：支付函數(shù)： 矩陣表示：矩陣表示：,.,211mS ,.,212nS ,.,2 , 1;,.,2 , 1),(21njmiSSji ijjiaH ),(

6、1 和和ijjiaH ),(2 mnmnmnaaaa111111 第第11頁頁最最 穩(wěn)穩(wěn) 妥妥 策策 略略最穩(wěn)妥策略最穩(wěn)妥策略：給定矩陣對(duì)策給定矩陣對(duì)策,21ASS ，如果，如果 jijijjiaa0minminmax 則局中人則局中人 1 的最穩(wěn)妥策略為的最穩(wěn)妥策略為0i 。如果。如果 0maxmaxminijiijijaa 則局中人則局中人 2 的最穩(wěn)妥策略為的最穩(wěn)妥策略為0j 。 第第12頁頁性性 質(zhì)質(zhì)性質(zhì)性質(zhì) 1 給定矩陣對(duì)策給定矩陣對(duì)策 ,21ASS ， 00minmaxjiijjiaaijijamaxmin。 性質(zhì)性質(zhì) 2 給定矩陣對(duì)策給定矩陣對(duì)策,21ASS ， 如果， 如果 i

7、jjiaminmaxijijamaxmin，則則 00minmaxjiijjiaaijijamaxmin 性質(zhì)性質(zhì) 3 給定矩陣對(duì)策給定矩陣對(duì)策,21ASS ， ijjiaminmaxijijamaxmin的充的充要條件是存在局勢要條件是存在局勢),(*ji 使得使得 njmiaaajijiij,.,2 , 1,.2 , 1,* 第第13頁頁均均 衡衡 解解定義定義 對(duì)于矩陣對(duì)策對(duì)于矩陣對(duì)策,21ASS ，如果存在局勢，如果存在局勢),(*ji 使得使得 njmiaaajijiij,.,2 , 1,.2 , 1,* 則稱局勢則稱局勢),(*ji 為對(duì)策的解，策略為對(duì)策的解，策略*,ji 分別為

8、局分別為局中人中人 1 和和 2 的最優(yōu)策略，的最優(yōu)策略，*jiav 為對(duì)策的值。為對(duì)策的值。 第第14頁頁例例 子子例例 求求下下面面的的矩矩陣陣對(duì)對(duì)策策的的解解 242046352321 顯顯然然對(duì)對(duì)于于22a滿滿足足上上述述要要求求， 所所以以局局勢勢),(22 就就是是對(duì)對(duì)策策的的解解。 第第15頁頁對(duì)對(duì) 抗抗 對(duì)對(duì) 策策兩人零和對(duì)策兩人零和對(duì)策引引理理 9.2.1 設(shè)設(shè)f為為RYX 上上的的有有界界函函數(shù)數(shù)，YX,是是兩兩個(gè)個(gè)集集合合，則則 ),(infsup),(supinfyxfyxfYyXxXxYy 定定理理 9.2.2 對(duì)對(duì)抗抗對(duì)對(duì)策策,21HSS ，H是是21SS 上上的的

9、有有界界函函數(shù)數(shù)，則則 ),(supmin12 HSS 和和),(infmax21 HSS 存存在在且且相相等等的的充充要要條條件件是是存存在在策策略略2*1*,SS 使使得得 ),(),(),(* HHH 21,SS 定定義義 9.2.2 對(duì)對(duì)抗抗對(duì)對(duì)策策,21HSS ，如如果果存存在在策策略略2*1*,SS 使使得得 ),(),(),(* HHH 21,SS 則則稱稱局局勢勢),(* 為為該該對(duì)對(duì)策策的的解解，策策略略2*1*,SS 分分別別稱稱為為局局中中人人的的最最優(yōu)優(yōu)策策略略，),(* Hv 為為對(duì)對(duì)策策的的值值。 第第16頁頁例例 子子例例 9.2.3 求求解解對(duì)對(duì)抗抗對(duì)對(duì)策策,2

10、1HSS ，其其中中101 xxS， 10 yySy，222),(yxyxH 解解： 12min),(supmin2212 yyxHSySxSy 112max),(infmax2121 xyxHSxSySx 所所以以該該對(duì)對(duì)抗抗對(duì)對(duì)策策為為（1，1） 。 第第17頁頁N 人人 有有 限限 對(duì)對(duì) 策策N 人有限對(duì)策人有限對(duì)策 IisHIiSNIii),(,.,2 , 1，其中，其中策略集合為有限集，記策略集合為有限集，記,.,.,)()1()()1()2()1()(niiiissssssss 。 定義定義 N 人有限對(duì)策人有限對(duì)策 IisHIiSNIii),(,.,2 , 1，如果，如果存在局勢

11、存在局勢,.,)()2()1(nssss 使得使得 iiiiiSsIisHssH )()(,),()( 則稱局勢則稱局勢,.,)()2()1(nssss 為為對(duì)策的均衡局勢對(duì)策的均衡局勢。 注：注：均衡局勢如果存在，就會(huì)被大家所接受，任何一方不會(huì)單均衡局勢如果存在，就會(huì)被大家所接受，任何一方不會(huì)單獨(dú)改變策略。但均衡策略不一定存在。獨(dú)改變策略。但均衡策略不一定存在。 矩陣對(duì)策和對(duì)抗對(duì)策的解就是他們的平衡局矩陣對(duì)策和對(duì)抗對(duì)策的解就是他們的平衡局勢。勢。 第第18頁頁混混 合合 策策 略略 混合擴(kuò)充混合擴(kuò)充 矩陣對(duì)策擴(kuò)充 N人有限對(duì)策 混合平衡解混合平衡解 矩陣對(duì)策 N人有限對(duì)策 均衡解的存在性均衡

12、解的存在性第第19頁頁混混 合合 擴(kuò)擴(kuò) 充充矩陣對(duì)策矩陣對(duì)策策策略略集集 ,.,2 , 1, 0, 1),.,(121*1mixxxxxXSimiim ,.,2 , 1, 0, 1),.,(121*2njyyyyyYSjnjjn 支支付付函函數(shù)數(shù) minjjiijyxaYXE11),( 混合擴(kuò)充混合擴(kuò)充：,),(,*2*1*2*1*SySxyxESS 第第20頁頁混混 合合 擴(kuò)擴(kuò) 充充N人有限對(duì)策N 人有限對(duì)策人有限對(duì)策 IisHIiSNIii),(,.,2 , 1 策略集策略集： ,.,2 , 1, 0, 1),.,(121*iijmjijimiiiimjxxxxxxSii ，Ii 局勢局勢

13、：niSxxxxxiin,.,2 , 1,),.,(21 支付函數(shù)支付函數(shù)： 112221211112121*),()(mjmjmjnjjjinjjjinnnnsssHxxxxH 混合擴(kuò)充為混合擴(kuò)充為： IixHIiSNIii),(,.,2 , 1* 第第21頁頁混合平衡解混合平衡解-矩陣對(duì)策混合擴(kuò)充混合擴(kuò)充：,),(,*2*1*2*1*SySxyxESS 如果存在如果存在混合局勢混合局勢*2*1,),(SySxyxx 使得：使得： ),(),(),(yxEyxEyxE ，*2*1,SySx , 則稱混合局勢則稱混合局勢*2*1,),(SySxyxx 為該矩陣對(duì)策的為該矩陣對(duì)策的混合平衡局勢。

14、混合平衡局勢。 第第22頁頁混合平衡解混合平衡解- N人有限對(duì)策N 人人有有限限對(duì)對(duì)策策的的混混合合擴(kuò)擴(kuò)充充 IixHIiSNIii),(,.,2 , 1*， 如如果果存存在在混混合合局局勢勢niSxxxxxiin,.,2 , 1,),.,(*21 使使得得： niSxxxHxHiiiii,.,2 , 1,),()(* 則則稱稱混混合合局局勢勢niSxxxxxiin,.,2 , 1,),.,(*21 為為該該對(duì)對(duì)策策的的 混混合合平平衡衡局局勢勢。 第第23頁頁混混 合合 平平 衡衡 局局 勢勢 的的 存存 在在 性性 引理引理1 定理定理1 N人有限對(duì)策的混合擴(kuò)充存在平衡局勢人有限對(duì)策的混合

15、擴(kuò)充存在平衡局勢. 定理定理2 矩陣對(duì)策的混合擴(kuò)充存在平衡局勢矩陣對(duì)策的混合擴(kuò)充存在平衡局勢.對(duì)對(duì) N 人有限對(duì)策的混合擴(kuò)充人有限對(duì)策的混合擴(kuò)充 IixHIiSNIii),(,.,2 , 1*niSxxxxxiin,.,2 , 1,),.,(*21 是平衡局勢的充要條件是平衡局勢的充要條件是是nimjSssxHxHiiijijii,.,2 , 1,.,2 , 1,),()(* 。 第第24頁頁矩矩 陣陣 對(duì)對(duì) 策策 的的 解解 法法 問題的簡化問題的簡化 優(yōu)超優(yōu)超 算例算例 線性規(guī)劃方法線性規(guī)劃方法 基本思想基本思想 算例算例第第25頁頁優(yōu)優(yōu) 超超給定矩陣對(duì)策給定矩陣對(duì)策,21ASS ，A是是

16、nm 的矩陣，如果的矩陣，如果 njaaljkj,.,2 , 1, 則稱局中人則稱局中人 1 的策略的策略 k 優(yōu)超于策略優(yōu)超于策略 l。如果如果 miaailik,.,2 , 1, 則稱局中人則稱局中人 2 的策略的策略 k 優(yōu)超優(yōu)超于策略于策略 l。 注注：局中人：局中人 1 的策略的策略 k 優(yōu)超于策略優(yōu)超于策略 l 則說明對(duì)局中人則說明對(duì)局中人 1 而言當(dāng)其采用策略而言當(dāng)其采用策略 k，無論局中人，無論局中人 2 采用和中策略，其采用和中策略，其 獲得都比采用策略獲得都比采用策略 l 來的好。來的好。因而策略出現(xiàn)的概率為因而策略出現(xiàn)的概率為 0， 可以在支付矩陣中刪除該策略對(duì)應(yīng)的行可以

17、在支付矩陣中刪除該策略對(duì)應(yīng)的行. 第第26頁頁算算 例例考慮矩陣對(duì)策的支付矩陣為考慮矩陣對(duì)策的支付矩陣為 8040243432430423 由于矩陣第三行的元素總是大于等于第一行的對(duì)應(yīng)元素，由于矩陣第三行的元素總是大于等于第一行的對(duì)應(yīng)元素， 所以對(duì)于局中人所以對(duì)于局中人 1 而言策略而言策略 3 優(yōu)超于策略優(yōu)超于策略 1，因而策略，因而策略 1 出現(xiàn)的概率為出現(xiàn)的概率為 0，可以在支付矩陣中刪除該策略對(duì)應(yīng)的行，可以在支付矩陣中刪除該策略對(duì)應(yīng)的行， 對(duì)應(yīng)的矩陣為對(duì)應(yīng)的矩陣為 804024343243 第第27頁頁簡簡 化化由由于于矩矩陣陣第第一一列列的的元元素素總總是是大大于于等等于于第第三三列

18、列的的對(duì)對(duì)應(yīng)應(yīng)元元素素，所所以以對(duì)對(duì)于于局局中中人人 2 而而言言策策略略 3 優(yōu)優(yōu)超超于于策策略略 1， 因因而而策策略略 1 出出現(xiàn)現(xiàn)的的概概率率為為 0，可可以以在在支支付付矩矩陣陣中中刪刪除除該該策策略略對(duì)對(duì)應(yīng)應(yīng)的的列列，對(duì)對(duì)應(yīng)應(yīng)的的矩矩陣陣為為 804243324 由由于于矩矩陣陣滿滿足足 )4 , 3 , 4()4 , 3 , 4()4 , 3 , 4(2121。所所以以對(duì)對(duì)于于局局中中人人 2 而而言言純純策策略略2優(yōu)優(yōu)超超于于混混合合策策略略)2/1 , 2/1 , 0 , 0(， 因因而而策策略略1出出現(xiàn)現(xiàn)的的概概率率為為0，可可以以在在支支付付矩矩陣陣中中刪刪除除該該策策略

19、略對(duì)對(duì)應(yīng)應(yīng)的的列列，對(duì)對(duì)應(yīng)應(yīng)的的矩矩陣陣為為 802432 第第28頁頁簡簡 化化由于矩陣滿足由于矩陣滿足 )8 , 0(2/1)2 , 4(2/1)3 , 2( 所以對(duì)于局中人所以對(duì)于局中人1而言策略而言策略1被混合策略被混合策略)2/1 , 2/1 , 0 , 0(優(yōu)優(yōu)超，因而策略超，因而策略 1 出現(xiàn)的概率為出現(xiàn)的概率為 0，可以在支付矩陣中刪，可以在支付矩陣中刪除該策略對(duì)應(yīng)的行，對(duì)應(yīng)的矩陣為除該策略對(duì)應(yīng)的行，對(duì)應(yīng)的矩陣為 8024 該矩陣對(duì)策為最簡單對(duì)策，不能再簡化。該矩陣對(duì)策為最簡單對(duì)策，不能再簡化。 第第29頁頁基基 本本 思思 想想矩陣對(duì)策矩陣對(duì)策,21ASS ，局勢，局勢),(

20、*yx是混合平衡局勢是混合平衡局勢 njmixayxayamiiijminjjiijnjjij,.,2 , 1,.,2 , 1;1*11*1* njmixaVyamiiijnjjij,.,2 , 1,.,2 , 1;1*1* njmiyxnjxVxamiyVyajimiimiiijnjjnjjij,.,2 , 1,.,2 , 1; 0, 0,.,2 , 1; 1;,.,2 , 1; 1;1111 第第30頁頁 mixnjxVxatsVimiimiiij,.,2 , 1; 0,.,2 , 1; 1.max11 和和 njymiyVyaVjnjjnjjij,.,2 , 1; 0,.,2 , 1;

21、1;min11 miVxnjVVxVxatsVimiimiiij,.,2 , 1; 0/,.,2 , 1;/1)/(1)/(.max11 njVymiVVyVyaVjnjjnjjij,.,2 , 1; 0/,.,2 , 1;/1)/(; 1)/(min11 第第31頁頁 mixxatsximiiijmii,.,2 , 1; 01.min11 njVyyayjnjjijnjj,.,2 , 1; 0/; 1max11 第第32頁頁算算 例例給定矩陣對(duì)策的支付矩陣給定矩陣對(duì)策的支付矩陣 223124331A 求最優(yōu)策略和值。求最優(yōu)策略和值。 解解：等價(jià)于求線性規(guī)劃：等價(jià)于求線性規(guī)劃 0,123122

22、3134.min321321321321321xxxxxxxxxxxxtsxxx 和和 0,1223124133.max321321321321321yyyyyyyyyyyytsyyy 第第33頁頁結(jié)結(jié) 果果利利用用 LinDo 計(jì)計(jì)算算結(jié)結(jié)果果為為 X1 0.142857 X2 0.000000 X3 0.285714 和和 Y1 0.142857 Y2 0.000000 Y3 0.285714 所所以以最最優(yōu)優(yōu)策策略略為為（1/3，0，2/3）和和（1/3，0，2/3） ， 最最優(yōu)優(yōu)值值為為 7/3。 第第34頁頁合合 作作 對(duì)對(duì) 策策 特征函數(shù)特征函數(shù) 分配分配 核心核心 穩(wěn)定集穩(wěn)定集

23、核仁核仁 Shapley值值第第35頁頁特特 征征 函函 數(shù)數(shù)聯(lián)聯(lián)盟盟：N 人人有有限限對(duì)對(duì)策策 IisHIiSNIii),(,.,2 , 1 的的一一些些局局中中人人集集合合 R，為為了了獲獲得得最最大大的的利利益益集集合合 R 中中的的 局局中中人人聯(lián)聯(lián)合合對(duì)對(duì)局局，他他們們的的策策略略集集為為 RiiRSS。 聯(lián)聯(lián)盟盟的的獲獲得得：他他們們能能獲獲得得（或或可可分分配配）的的收收益益為為： HiiSSHRVRIR),(minmax)(* 特特征征函函數(shù)數(shù)：給給定定聯(lián)聯(lián)盟盟IR 就就有有 V(R)，如如果果令令0)( V，就就得得 到到一一個(gè)個(gè)定定義義在在局局中中人人集集的的子子集集合合的

24、的函函數(shù)數(shù)，表表征征了了每每個(gè)個(gè)聯(lián)聯(lián)盟盟的的 最最好好的的獲獲得得，也也就就是是每每個(gè)個(gè)聯(lián)聯(lián)盟盟可可分分配配的的獲獲得得。 第第36頁頁分分 配配如果對(duì)于每個(gè)局中人的收入如果對(duì)于每個(gè)局中人的收入ix，Ii 滿足滿足 )(),(IVxIiiVxIiii 則稱向量則稱向量),.,(21nxxxx 為為對(duì)策的分配對(duì)策的分配，X 表表示分配的全體。示分配的全體。 第第37頁頁核核 心心優(yōu)優(yōu)超超：設(shè)設(shè)),.,(21nxxxx 和和),.,(21nyyyy 是是合合作作對(duì)對(duì)策策,VI 的的兩兩個(gè)個(gè)分分配配，聯(lián)聯(lián)盟盟S是是I的的非非空空子子集集，如如果果滿滿足足條條件件： SixySVyiiSii,)( 則

25、則稱稱 y 關(guān)關(guān)于于 S 優(yōu)優(yōu)超超于于 x，記記為為xyS；如如果果存存在在一一個(gè)個(gè)聯(lián)聯(lián)盟盟 S 使使得得xyS就就稱稱 y 優(yōu)優(yōu)超超于于 x，記記為為xy。 定定義義：合合作作對(duì)對(duì)策策,VI 有有一一分分配配集集合合 C 滿滿足足：如如果果Cx 就就不不存存在在分分配配 y 優(yōu)優(yōu)超超于于 x，則則稱稱 C 是是對(duì)對(duì)策策,VI 的的核核心心。 定定理理： 設(shè)設(shè) C 是是合合作作對(duì)對(duì)策策,VI 的的核核心心， 則則分分配配Cx 的的充充要要條條件件是是對(duì)對(duì)任任何何聯(lián)聯(lián)盟盟S，都都有有 )(SVxSii . 第第38頁頁穩(wěn)穩(wěn) 定定 集集設(shè)設(shè) V 是合作對(duì)策是合作對(duì)策,VI 的部分分配組成的集合，

26、如果的部分分配組成的集合， 如果它滿足它滿足 1 內(nèi)部穩(wěn)定性：內(nèi)部穩(wěn)定性：Vyx ,則則 y 不優(yōu)超于不優(yōu)超于 x； 2 外部穩(wěn)定性：外部穩(wěn)定性：Vx ，則存在，則存在Vy 使得使得xy。 則稱則稱 V 是合作對(duì)策是合作對(duì)策,VI 的的穩(wěn)定集穩(wěn)定集 性質(zhì)性質(zhì)：合作對(duì)策：合作對(duì)策,VI 有非空的核心有非空的核心 C，且它的穩(wěn)定，且它的穩(wěn)定集集 V 存在，則存在，則VC 。 第第39頁頁核核 仁仁超超出出值值：合合作作對(duì)對(duì)策策,VI ，聯(lián)聯(lián)盟盟IS ，),.,(21nxxxx 是是對(duì)對(duì)策策的的分分配配則則在在該該分分配配處處的的超超出出值值為為 SiixSVxSe)(),( 反反映映了了聯(lián)聯(lián)盟盟IS 對(duì)對(duì)分分配配),.,(21nxxxx 的的態(tài)態(tài)度度，越越小小越越易易接接受受。 字字典典序序： 給給定定分分配配， 對(duì)對(duì)所所有有聯(lián)聯(lián)盟盟的的超超出出值值從從大大到到小小排排序序得得到