運籌學第8章對策論

1、 第八章第八章 二人有限非零和對策二人有限非零和對策8.1 8.1 二人有限非零和對策問題二人有限非零和對策問題8.2 8.2 非合作的二人有限非零和對策非合作的二人有限非零和對策8.3 8.3 合作的二人有限非零和對策合作的二人有限非零和對策http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策8.1 8.1 二人有限非零和對策問題二人有限非零和對策問題引例引例1 1： 囚犯兩難問題囚犯兩難問題1）1）1，1，（0)0) 10，10，（10）10）- -0，0， （9）9）9，9，（不坦白不坦白坦白坦白甲甲不坦白不坦白坦白坦白乙乙己所不欲，勿施于人己所不

2、欲，勿施于人http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策引例引例2 2：智豬博弈：智豬博弈（0 0，0 0）1 1）（9 9，（4 4，4 4）1 1）（5 5，等等候候按按鈕鈕大大豬豬等等候候按按鈕鈕小小豬豬免費搭車免費搭車http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策引例引例3 3：斗雞博弈：斗雞博弈（0 0，0 0）2 2）0 0，（2 2，0 0）3 3）- -3 3，- -（退退進進雞雞A A退退進進雞雞B B狹路相逢勇者勝。退一步海闊天空狹路相逢勇者勝。退一步海闊天空http:/天津大學管

3、理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策8.2 8.2 非合作的二人有限非零和對策非合作的二人有限非零和對策 一、非合作情形下的純策略解一、非合作情形下的純策略解1 1、優(yōu)勢策略、劣勢策略、優(yōu)勢策略、劣勢策略乙的優(yōu)勢策乙的優(yōu)勢策略坦白略坦白甲的優(yōu)勢策略甲的優(yōu)勢策略坦白坦白1）1）1，1，（0)0) 10，10，（10）10）- -0，0， （9）9）9，9，（不坦白不坦白坦白坦白甲甲不坦白不坦白坦白坦白乙乙如果某個局中人采取某個純策略，在另如果某個局中人采取某個純策略，在另一個局中人采取的任何純策略下的各個一個局中人采取的任何純策略下的各個贏得，都不小于該局中人選

4、擇其他純策贏得，都不小于該局中人選擇其他純策略的贏得，則稱該局中人所采取的策略略的贏得，則稱該局中人所采取的策略為其優(yōu)勢策略。為其優(yōu)勢策略。http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策（0 0，0 0）1 1）（9 9，（4 4，4 4）1 1）（5 5，等等候候按按鈕鈕大大豬豬等等候候按按鈕鈕小小豬豬小豬的嚴格劣小豬的嚴格劣勢策略按鈕勢策略按鈕將局中人的策略兩兩進行比較，如果將局中人的策略兩兩進行比較，如果某個策略的贏得都不大于另一個策略某個策略的贏得都不大于另一個策略的贏得，則稱這個策略為局中人的劣的贏得，則稱這個策略為局中人的劣勢策略。要是

5、存在嚴格小于的情況，勢策略。要是存在嚴格小于的情況，這樣的策略就是局中人的嚴格劣勢策這樣的策略就是局中人的嚴格劣勢策略。略。http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策納什均衡解：納什均衡解：（雞（雞A A進，雞進，雞B B退）退）（雞（雞B B進，雞進，雞A A退）退）（0 0，0 0）2 2）0 0，（2 2，0 0）3 3）- -3 3，- -（退退進進雞雞A A退退進進雞雞B B納什均衡解基本特征：博弈活動中局中人任何一方都納什均衡解基本特征：博弈活動中局中人任何一方都不敢輕易改變其策略的局勢。不敢輕易改變其策略的局勢。http:/天津大

6、學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策雙矩陣對策的解唯一嗎？值唯一嗎？雙矩陣對策的解唯一嗎？值唯一嗎？http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策2 2、純策略納什均衡解的求法、純策略納什均衡解的求法（1 1）反復剔除嚴格劣勢策略法）反復剔除嚴格劣勢策略法（2 2）劃線法）劃線法0 , 22 , 04 , 01 , 03 , 10 , 121321【例【例1 1】（0 0，0 0）1 1）（9 9，（4 4，4 4）1 1）（5 5，等等候候按按鈕鈕大大豬豬等等候候按按鈕鈕小小豬豬（0 0，0 0）2 2）0

7、0，（2 2，0 0）3 3）- -3 3，- -（退退進進雞雞A A退退進進雞雞B Bhttp:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策二、非合作情形下的混合策略解二、非合作情形下的混合策略解0, 1|),.(0, 1|),.(11*211*1jnjjTnimiiTmyyyyYSxxxxXS分別為局中人甲和乙的混合策略集分別為局中人甲和乙的混合策略集http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策1 1、解的概念與存在性定理、解的概念與存在性定理*1212*, (,)TTTTXSYSXSYSXAYXAYXB

8、YXBYXYG設(shè)若對任何和任何， 有 則稱為雙矩陣對策的平衡局勢。*,(,)(,)TTXYXAYXBYGUV平衡局勢（）對應的二局中人的期望收益就是的值，記為。http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策定理定理1 1：任何雙矩陣對策至少存在一個平衡局勢。：任何雙矩陣對策至少存在一個平衡局勢。*,max . .1,0,1TTTnTmTTmnmnXYGpqXYpqX AYX BYpqAYpEX BqEstE XE YX YEE（）為雙矩陣對策 的一個平衡局勢的充要條件是存在數(shù)和使 是下述問題的一個解： （）其中為分量為的向量。定理定理2 2：htt

9、p:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策2 2、2 22 2雙矩陣對策的解法雙矩陣對策的解法 當當A A和和B B均為均為2 22 2階時，階時， 相應的雙矩陣對策可表示為相應的雙矩陣對策可表示為: :1111121221212222(,) (,)(,) (,)abababab 1y11y11x1x I I II II1112111221 2221 22 ,aabbABaabb上上的的極極大大點點。在在和和在在應應分分別別是是和和由由均均衡衡局局勢勢的的定定義義，是是均均衡衡局局勢勢，若若*2*1*),(SByxSAyxyxyxTThttp:/天津

10、大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策*11121*11*21221*111221221221212221221 1 1 ()()()TaayX AYxxaayaaaayaaxaaay而11112212222212 AaaaaAaa記*1*112*1112*1120, 0 0,1,01, 0TX AYxA yAxA yAA yA則使達到極大的 應滿足當中任意值 當當（1）http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策11121*1121221*111221221222112212221 b 1 b1 ()()(

11、)TbyXBYxxbybbbbxbbybbbx11112212222221 BbbbbBbb記*1*1 12*11 12*1 120, 0 0,1,01, 0TXBYyB xByB xBB xB則使達到極大的 應滿足當中任意值 當當（2）http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策：種種條條件件），如如下下表表所所示示各各種種符符號號時時的的取取和和、和和種種情情形形（即即一一分分析析的的結(jié)結(jié)果果各各分分為為局局勢勢。將將這這），由由此此便便可可得得到到平平衡衡，共共點點即即（）的的軌軌跡跡。二二軌軌跡跡的的公公的的解解）（不不妨妨稱稱為為點點來

12、來說說可可能能成成為為平平局局勢勢的的的的軌軌跡跡和和對對于于局局中中人人）的的解解），（妨妨稱稱為為成成為為平平衡衡局局勢勢的的點點（不不來來說說可可能能對對局局中中人人縱縱軸軸的的坐坐標標系系中中確確定定出出為為橫橫軸軸、和和），可可在在以以）和和式式（根根據(jù)據(jù)式式（99,212121*1*1*111*111BBAAyxyxyxyxhttp:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策條件序號條件序號條件條件解解圖示圖示1 12 23 3P264P264http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策【例【例

13、2 2】（夫婦之爭）夫婦倆商量晚上去哪里消遣。】（夫婦之爭）夫婦倆商量晚上去哪里消遣。丈夫喜歡看足球比賽，而妻子喜歡去看芭蕾舞表丈夫喜歡看足球比賽，而妻子喜歡去看芭蕾舞表演，夫婦希望同往。演，夫婦希望同往。12111211()()(1)()(1-).xxyy 解 現(xiàn)將問題歸為一個雙矩陣對策。記丈夫為局中人I， 其策略為看芭蕾 、看足球 ，相應混合策略 ； 妻子為局中人II，其策略為看芭蕾 、 （看足球），相應 混合策略 設(shè)得失矩陣為：(1,4) (0,0)(0,0) (4,1) III(,)ijijijab矩陣中位于第 行 列的括號即http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人

14、有限非零和對策二人有限非零和對策8.3 8.3 合作的二人有限非零和對策合作的二人有限非零和對策1 1、合作思路、合作思路采用聯(lián)合隨機策略采用聯(lián)合隨機策略在非合作的夫婦之爭的例子中，若夫婦希望在得失在非合作的夫婦之爭的例子中，若夫婦希望在得失值（值（4,14,1）和（）和（1,41,4）中權(quán)衡，即協(xié)商選擇概率）中權(quán)衡，即協(xié)商選擇概率 ，及期望得失值：，及期望得失值：(1,4)(1)(4,1)（ 實際可看作是每次行動中采用的幾率）,稱這樣的合作問題為采用聯(lián)合隨機策略的雙矩陣對策。http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策2 2、合作的可行收益區(qū)域

15、、合作的可行收益區(qū)域( , )U V設(shè)局中人 、 的期望收益為，以夫婦之爭為例，在非合作的情形，丈夫的11111111 10( ,1)5444041yUxxx yxyy妻子的11111111 40( ,1)51011yVxxx yxyy11110,1“”xyU Vx yU V當 和 在上變動時，相應的- 平面上的點（如當 = =1時，(, )=(1,4)）構(gòu)成非合作對策的 可行收益 區(qū)域，如圖：http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策(1,4)(1)(4,1)1/2,2.5,2.51/3,3,2AB而在合作時，表示連接 、 的線段，當相應于（

16、）當相應于（）(1,4)A(4,1)B440UV說明合作時的可行收益域大于非說明合作時的可行收益域大于非合作時的，且可使雙方得到更好合作時的，且可使雙方得到更好的收益。的收益。(1,4)A(4,1)B440UVhttp:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策?直觀上，哪一段上的點“最好” AB線段(,),U VUUVVAB因為，找不到另外的，使得且且至少有一嚴格成立。而上的點之間不可比較，和多目標規(guī)劃有效解的概念類似。(1,4)A(4,1)B440UVhttp:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策 英語英

17、語 專業(yè)課專業(yè)課1 專業(yè)課專業(yè)課2A 80 75 88 B 75 81 85 C 76 78 89 D 85 82 92 E 79 74 86 絕對最優(yōu)解絕對最優(yōu)解有效解有效解有效解有效解有效解有效解劣解劣解http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策3 3、ParetoPareto最優(yōu)點與最優(yōu)點與NashNash談判集談判集(1) Pareto(1) Pareto最優(yōu)點最優(yōu)點( , ),)( , )( , )ParetoU VU VU VUUVVU V對于可行收益域中的點，若不存在(使得且，則稱為對策的最優(yōu)點。幾何意義：可行收益域的幾何意義：可

18、行收益域的“東北方東北方”邊界。邊界。顯然顯然, ,雙方感興趣的點至少是雙方感興趣的點至少是ParetoPareto最優(yōu)。此外最優(yōu)。此外, ,雙方還雙方還自然要求收益不低于在不合作時自己保證能得到的最低自然要求收益不低于在不合作時自己保證能得到的最低水平，即水平，即12(, )(, )TTE X YX AYEX YX BYhttp:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策00(,)U V 稱為安全點，表示收益的“下限”。*21*120102maxmin(, )maxmin(, )Y SX SX SY SUUE X YVVEX Yhttp:/天津大學管理

19、與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策(2) Nash(2) Nash談判集談判集00Pareto( , )UUVVU V滿足且的點的全體。顯然，最優(yōu)點應從顯然，最優(yōu)點應從NashNash談判集中產(chǎn)生，稱為談判集中產(chǎn)生，稱為NashNash談判解。談判解。AB0U00,UV（）Vhttp:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策4 4、求解合作雙矩陣對策、求解合作雙矩陣對策NashNash談判解的步驟談判解的步驟：001122122111 2212 21001112212211122122(,)2 2,ABU VABa a

20、a ab bb bUVaaaabbbb由雙矩陣 和 求安全點，當 、 為階時，可由求得。00(,)*max(,)max(,)max(,)(,)U VUVf U Vf U Vf U VUV若不存在，則用或求。*00Nash( , )()()(,)NashShapley)f U VUUVVU V在談判集中，求的最大點即談判解（也稱最大最小解或沙普利（解）。ParetoNash求出最優(yōu)點集和談判集。2 2(,)ijija b求出可行收益域，對階，即以為頂點的四邊形。http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策(1,4) (0,0)( , )(0,0)

21、(4,1)A B 合作的夫婦之爭合作的夫婦之爭解解 可行收益域如圖，安全點：可行收益域如圖，安全點：001 40 041 00454 1 0 04400 15UV (4,1)A(1,4)B0UVNashNash談判集為談判集為ABAB。http:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策過過ABAB的直線表達式為：的直線表達式為：411 44 1VU 5VU 即24444( ,)()()()(5)555584 525f U VUVUUUU *55250, , 522UfUUVU 令*1(,)Nash2U V即為談判解，相應于的合作隨機策略。(4,1)A(1,4)B0UVhttp:/天津大學管理與經(jīng)濟學部天津大學管理與經(jīng)濟學部二人有限非零和對策二人有限非零和對策求求 的的NashNash談判解談判解(1,2) (4,5)( ,