1、第八章 對策論(Game Theory)引言 矩陣對策的基本理論 矩陣對策的解法 WinQSB軟件應用第一節(jié) 引言 對策論（Game Theory）亦稱博奕論或競爭論，主要研究對象是具有斗爭或競爭性質(zhì)的現(xiàn)象。一般認為，它是現(xiàn)代數(shù)學的一個新分支，也是運籌學中的一個重要學科。凡是具有斗爭或競爭性質(zhì)的行為稱為對策行為。 戰(zhàn)國時期，在齊國的貴族和大臣中風行賽馬，參賽雙方把各自的馬匹分成上、中、下三等，從每個等級中各選出一匹馬進行比賽。當時的齊國國王齊威王也經(jīng)常參加比賽，他的大臣田忌在與威王的比賽中屢次失敗。當時，孫臏還是田忌的家臣，他分析了當時的狀況，認為齊國的好馬多集中在威王的手中，田忌采用相同等級

2、的馬與威王比賽，自然是贏不了威王的；他建議田忌再與威王賽一次，每匹馬賭千金。結(jié)果，田忌按孫臏的策略，用他的上等馬對威王的中等馬、用中等馬對威王的下等馬、用下等馬對威王的上等馬，獲得了兩勝一負，最終贏得了千金。 對策論的發(fā)展歷史并不長，但由于它所研究的現(xiàn)象與政治、經(jīng)濟、科學、文化教育、軍事等活動乃至人們的日常生活有著密切的聯(lián)系，而分析問題和解決問題的方法又有鮮明的特色，所以，受到了人們?nèi)找鎻V泛的重視。一、對策行為的基本要素 對策行為有三個基本要素，即局中人、策略和贏得函數(shù)。分析對策行為首先必須清楚這三個基本要素。1局中人（Player） 在一局對策中，有權(quán)決定自己行動方案的參加者稱為局中人，通常

3、用 P 表示局中人的集合。 局中人：利益得失者,不是公證人、馬、謀士等，可以是團體、國家等； 聰明的，有理智的； 把那些利益完全一致的參加者們看作一個局中人； 兩人,多人,結(jié)盟,不結(jié)盟2策略（Strategy） 在一局對策中，可供局中人選擇的完整的行動方案稱為策略。所謂完整的行動方案是指一局對策中自始至終的全局規(guī)劃，而不是其中某一步或某幾步的安排。 把局中人的策略全體，稱做這個局中人的策略集合； 各局中人都有六個策略：(上、中、下)；(上、下、中)；(中、上、下)；(中、下、上)，(下、中、上)，(下、上、中)。這個策略全體就是局中人的策略集合。 例如，在齊王與田忌賽馬的例子中，如果一開始就要

4、把各人的三匹馬排好次序，然后依次出賽。 如果全體局中人的“得失”相加總是等于零時，這個對策就稱為零和對策。否則稱為“非零和對策”。 從每個局中人的策略集中各取一個策略，組成的策略組，稱作“局勢”?！暗檬А笔恰熬謩荨钡暮瘮?shù)。 3贏得函數(shù)（Score） 每個局中人在一局對策中的得失，通常不僅與其自身采取的策略有關(guān)，而且還與其他局中人所采取的策略有關(guān)。也就是說，每個局中人的得失是全體局中人所采取的一組策略的函數(shù)，這一函數(shù)稱為局中人的贏得函數(shù)。 二、對策的分類 按對策方式合作對策非合作對策完全理性有限理性按對策人數(shù)多人對策二人對策二人零和對策二人非零和對策按對策狀態(tài)靜態(tài)對策動態(tài)對策完全信息動態(tài)對策不完

5、全信息動態(tài)對策完全信息靜態(tài)對策不完全信息靜態(tài)對策第二節(jié) 矩陣對策的基本理論 有限二人零和對策，即參加對策的局中人只有兩個，而每個局中人都有有限個可供選擇的策略。而且在任一局勢中，兩個局中人的得失之和總等于零（一個局中人的所得即為另一個局中人的所失）。局中人的利益是沖突的，也稱為對抗對策。一、矩陣對策的數(shù)學模型用甲、乙表示兩個局中人，假設甲有 m 個策略，表示為: 乙有 n 個策略，表示為： 當甲選定策略i、乙選定策略j 后，就形成了一個局勢(i ,j )，可見這樣的局勢有 mn 個。對任一局勢(i ,j )，甲的贏得值為 aij ，即甲的贏得矩陣:通常將二人有限零和對策的數(shù)學模型記為： 為理解

6、二人有限零和對策的數(shù)學模型，仍以田忌賽馬為例進行說明。 齊威王共有六個策略，分別為：1(上、中、下)、2(上、下、中)、3(中、上、下)、4(中、下、上)、5(下、中、上)、6(下、上、中)。則齊威王的策略集 S1 為： 田忌也有六個策略，分別為：1(上、中、下)、2(上、下、中)、3(中、上、下)、4(中、下、上)、5(下、中、上)、6(下、上、中)。則田忌的策略集 S2 為： 當局中人齊威王、田忌分別采用純策略i 和j 時，就構(gòu)成了一個純局勢(i , j )，顯然這樣的純局勢共有66個。 據(jù)齊威王與田忌的賽馬規(guī)則及馬的優(yōu)劣，可得到齊威王的贏得矩陣為： 【例10-1】甲、乙兩名兒童玩猜拳游戲

7、，游戲中雙方的策略集均為拳頭（代表石頭）、手掌（代表布）和兩個手指（代表剪刀）。如果雙方所選策略相同，算和局，雙方均不得分。試建立兒童甲的贏得矩陣。 解：根據(jù)題意有下表： 布剪刀石頭布剪刀石頭 乙 甲01-1-1011-10即兒童甲的贏得矩陣為： 矩陣對策模型給定后，各局中人面臨的問題便是如何選取自己最為有利的策略，以謀取最大的贏得或最小的損失。 二、矩陣對策的純策略 【例10-2】設矩陣對策 ，其中： ， 試求出雙方的最優(yōu)純策略和對策值。 解：由 A 可以看出，局中人甲的最大贏得是8，要想得到這個贏得，他就得選擇純策略3 。 局中人乙考慮到局中人甲打算選擇純策略 3 的心理，于是他選擇 3

8、策略，使局中人甲不單得不到8反而失掉10。 局中人甲當然會猜到局中人乙的這一心理，故想出選擇純策略 4 來對付 ，使局中人乙不單得不到10反而失掉6。 雙方都不應冒險，都不存在僥幸心理，而是考慮到對方必然想辦法使自己的所得最少這一點，就應該采取理智行為。638各列最大值max-3-10-6各行最小值(min)3 對本例而言，贏得矩陣A的各行最小元素的最大值與各列最大元素的最小值相等，即： “理智行為”就是從最壞處著想，去爭取盡可能好的結(jié)果。 由于假設兩個局中人都是理智的，所以每個局中人都必須考慮到對方會設法使自己的贏得最少，誰都不能存在僥幸心理。 若用數(shù)學語言，可表示為： 甲的贏得值： 乙的支

9、付值： 定義1：設G=S1,S2;A為矩陣對策，其中雙方的策略集和贏得矩陣分別為 、 、 。若有等式： 成立，則稱 為對策G的值，局勢（ ）為對策G的解或平衡局勢。 和 分別稱為局中人甲、乙的最優(yōu)策略。 定理1：矩陣對策G=S1,S2;A在純策略意義上有解的充分必要條件是存在著局勢( )使得對于一切 i =1,2,m 和j=1,2,n均有下式成立。-3-10-63638-3-10-63638 對于本例而言，可表示為： 定義2：設 f(x,y)為定義在 xA及 yB上的實函數(shù)，若存在x*A、y*B，使得一切 xA和 yB滿足： 則稱(x*,y*)為函數(shù) f(x,y) 的一個鞍點?！纠?0-3】矩

10、陣對策G=S1,S2;A，其中贏得矩陣 957各列最大值-155各行最小值-45解：于是： 其中 i* =1,3；j* =2,4。 由此例可知，矩陣對策的解可以是不唯一的。當矩陣對策具有不唯一解時，各解之間的關(guān)系具有這樣的性質(zhì)： 故(1,2)、(1,4)、(3,2)和(3,4 )四個局勢均為對策的解，且：可交換性：若是G的解，則也是G的解。 三、矩陣對策的混合策略 由前面的討論可知，對于矩陣對策G=S1,S2;A來說，局中人甲有把握的最少贏得是： 局中人乙有把握的最多損失是： 當 v1=v2時，矩陣對策G=S1,S2;A存在純策略意義上的解。 然而，并非總有 v1=v2，實際問題出現(xiàn)更多的情形

11、是 v10。令 ，則不等式組： 根據(jù)定理8，有 于是不等式組（10.28）等價于下式所示的線性規(guī)劃問題： (P) 同理，令 ，則不等式組： 根據(jù)定理8，有 于是不等式組（10.30）等價于下式所示的線性規(guī)劃問題： (D) 于是： 【例10-10】利用線性規(guī)劃求解矩陣對策，其中解：構(gòu)造兩個互為對偶的線性規(guī)劃問題： 1001641u300103161u20000111j0014521u10u3u2u1y3y2y1bYBCB000111cj1-2/30-116/301/3u3101/601/21/611/6y100-1/601/25/60j0-1/31314/302/3u103/16-1/80-3/

12、16101/16y21-1/323/16017/32015/32y11-5/32-1/16021/3200j-7/81/4131/8003/8u109/62-7/623/620105/62y1111/12419/124-17/12400113/124y21-1/124-13/124-21/124000j-7/312/318/311003/31y31利用單純形法求解第二個線性規(guī)劃問題，迭代過程見表10-3。則：故： 解：該矩陣不存在鞍點，也不能用超優(yōu)原則將其縮減，故擬用線性規(guī)則方法求解。 從矩陣可見，對局中人甲而言，其最小最大值為-1，因而其對策值有可能是非正的，因此取常數(shù) k2，則贏得矩陣變?yōu)椋?對局中人甲而言，求解 使：【例】求解如下矩陣對策： 對局中人乙而言，求解 使：用單純形法求解局中人乙的最優(yōu)策略，得最終單純形表如下： yBby1y2y3u1u2u3y16/2510019/25-3/50-2/25y33/25001-3/2511/50-1/25y24/25010-2/25-1/257/25j000-6/25-3/25-4/25原矩陣對策的對策值為： 第五節(jié) WinQSB軟件應用 WinQSB軟件需要調(diào)用子程序：De