運籌學對策論基礎

運籌學（第三版）

《運籌學》教材編寫組編第14章對策論基礎清華大學出版社碩

納什簡介約翰·納什生于1928年6月13日。父親是電子工程師與教師，第一次世界大戰(zhàn)的老兵。納什小時孤獨內(nèi)向，雖然父母對他照顧有加，但老師認為他不合群不善社交。納什在上大學時就開始從事純數(shù)學的博弈論研究，1948年進入普林斯頓大學后更是如魚得水。他在普林斯頓大學讀博士時剛剛二十出頭，但他的一篇關于非合作博弈的博士論文和其他相關文章，確立了他博弈論大師的地位。在20世紀50年代末，他已是聞名世界的科學家了。特別是在經(jīng)濟博弈論領域，他做出了劃時代的貢獻，是繼馮·諾依曼之后最偉大的博弈論大師之一。1994年榮獲諾貝爾經(jīng)濟學獎他提出的著名的納什均衡的概念在非合作博弈理論中起著核心的作用。后續(xù)的研究者對博弈論的貢獻，都是建立在這一概念之上的。由于納什均衡的提出和不斷完善為博弈論廣泛應用于經(jīng)濟學、管理學、社會學、政治學、軍事科學等領域奠定了堅實的理論基礎。然而，正當他的事業(yè)如日中天的時候，30歲的納什得了嚴重的精神分裂癥。他的妻子艾利西亞———麻省理工學院物理系畢業(yè)生，表現(xiàn)出鋼鐵一般的意志：她挺過了丈夫被禁閉治療、孤立無援的日子，走過了惟一兒子同樣罹患精神分裂癥的震驚與哀傷……漫長的半個世紀之后，她的耐心和毅力終于創(chuàng)下了了不起的奇跡：和她的兒子一樣，納什教授漸漸康復，并在1994年獲得諾貝爾獎經(jīng)濟學獎。如今，納什已經(jīng)基本恢復正常，并重新開始科學研究。他現(xiàn)在是普林斯頓大學數(shù)學教授，但已經(jīng)不再任教。學校經(jīng)濟學系經(jīng)常會舉辦有關博弈論的論壇，納什有時候會參加，但是他幾乎從不發(fā)言，每次都是靜靜地來，靜靜地走。小約翰-納什是所有諾貝爾經(jīng)濟學獎得主中最不幸的，又是不幸中最萬幸的人。納什不是一個完人，他舉止古怪，離經(jīng)叛道。曾經(jīng)想放棄美國國籍，幾乎遺棄了同居女友和親生兒子，與深愛他的賢妻艾莉西亞離婚……

納什均衡納什均衡是指這樣一種均衡：在這一均衡中，每個博弈參與人都確信，在給定其他參與人戰(zhàn)略決定的情況下，他選擇了最優(yōu)戰(zhàn)略以回應對手的戰(zhàn)略?！币簿褪钦f，所有人的戰(zhàn)略都是最優(yōu)的。囚徒困境設有兩個嫌疑犯因涉嫌作案被警官拘留，警官分別對兩人進行審訊。根據(jù)法律，如果兩個人都承認此案是他們干的，則每人各判刑7年，如果兩人都不承認，則由于證據(jù)不足，兩人各判刑1年；如果只有一人承認并揭發(fā)對方，則承認者予以寬大釋放，而不承認者將判刑9年。因此，對兩個囚犯來說，面臨著一個在“承認”和“不承認”這兩個策略間進行選擇的難題。顯然最好的策略是雙方都抵賴，結(jié)果是大家都只被判1年。但是由于兩人處于隔離的情況下無法串供，按照亞當·斯密的理論，每一個人都是一個“理性的經(jīng)濟人”，都會從利己的目的出發(fā)進行選擇。這兩個人都會有這樣一個盤算過程：假如他招了，我不招，得坐9年監(jiān)獄，招了才7年，所以招了劃算；他要是不招，假如我招了，我就會寬大釋放，而他會坐9年牢，假如我不招，被判1年刑，也是招了劃算。綜合以上幾種情況考慮，不管他招不招，對我而言都是招了劃算。兩個人都會動這樣的腦筋，最終，兩個人都選擇了招，結(jié)果都被判7年刑期。原本對雙方都有利的策略(抵賴)和結(jié)局(被判1年刑)就不會出現(xiàn)。這就是著名的“囚徒困境”。它實際上反映了一個很深刻的問題，這就是個人理性與集體理性的矛盾。

第14章對策論基礎第1節(jié)引言

第2節(jié)矩陣對策的基本定理

第3節(jié)矩陣對策的解法

第4節(jié)*其他類型對策簡介第1節(jié)

引言1.1對策行為和對策論對策論亦稱競賽論或博弈論，是研究具有斗爭或競爭性質(zhì)現(xiàn)象的數(shù)學理論和方法。一般認為，它是現(xiàn)代數(shù)學的一個新分支，是運籌學的一個重要學科。對策論發(fā)展的歷史并不長，但由于它研究的問題與政治、經(jīng)濟、軍事活動乃至一般的日常生活等有著密切聯(lián)系，并且處理問題的方法具有明顯特色，所以日益引起廣泛注意。

在日常生活中，經(jīng)?？梢钥吹揭恍┚哂邢嗷ザ窢幓蚋偁幮再|(zhì)的行為，如下棋、打牌、體育比賽等。還有企業(yè)間的競爭、軍隊或國家間的戰(zhàn)爭、政治斗爭等，都具有對抗的性質(zhì)。這種具有競爭或?qū)剐再|(zhì)的行為稱為對策行為。

在這類行為中，各方具有不同的目標和利益。為實現(xiàn)自己的目標和利益，各方必須考慮對手可能采取的行動方案，并力圖選擇對自己最為有利或最為合理的行動方案。

對策論就是研究對策行為中斗爭各方是否存在著最合理行動方案，以及如何找到最合理行動方案的數(shù)學理論和方法。

我國戰(zhàn)國時期的田忌賽馬是典型的對策行為。具體參見P380.

1.2對策行為的三個基本要素

以下稱具有對策行為的模型為對策模型或?qū)Σ?。對策模型的種類可以千差萬別，但本質(zhì)上都包括以下三個基本要素：1.局中人

在一個對策行為中，有權(quán)決定自己行動方案的對策參加者。

局中人必須理性：不能利用對局中不利條件或其他局中人決策的失誤來擴大自身利益的可能性。

2.策略集

1）在一局對策中，可供局中人選擇的一個實際可行的完整的行動方案稱為一個策略。

2）一個局中人全體策略構(gòu)成的集合，稱為此局中人的策略集。一般，每一局中人的策略集中至少應包括兩個策略。

3.贏得函數(shù)（支付函數(shù)）

1）各局中人分別選定自己的策略構(gòu)成的策略組稱為一個局勢。

2）當一個局勢出現(xiàn)后，對策的結(jié)果也就確定了。

對于局勢s，局中人i可以得到一個贏得Hi(s)，它是局勢s的函數(shù),稱為局中人i的贏得函數(shù)。以上討論了局中人、策略集和贏得函數(shù)這三個概念。當這三個基本要素確定后，一個對策模型也就給定了。1.3對策問題舉例及對策的分類對策論在經(jīng)濟管理的眾多領域中有著十分廣泛的應用，下面列舉幾個可以用對策論思想和模型進行分析的例子。例1（市場購買力爭奪問題）據(jù)預測，某鄉(xiāng)鎮(zhèn)下一年的飲食品購買力將有4000萬元。鄉(xiāng)鎮(zhèn)企業(yè)和中心城市企業(yè)飲食品的生產(chǎn)情況是：鄉(xiāng)鎮(zhèn)企業(yè)有特色飲食品和低檔飲食品兩類，中心城市企業(yè)有高檔飲食品和低檔飲食品兩類產(chǎn)品。他們爭奪這一部分購買力的結(jié)局如下表（表中數(shù)字的單位是萬元），問題是鄉(xiāng)鎮(zhèn)企業(yè)和中心城市企業(yè)應如何選擇對自己最有利的產(chǎn)品策略。表鄉(xiāng)鎮(zhèn)企業(yè)所得鄉(xiāng)鎮(zhèn)企業(yè)策略中心城市企業(yè)策略出售高檔飲食品出售低檔飲食品出售特色飲食品出售一般飲食品

200010003000

3000例2（費用分攤問題）假設沿某一河流有相鄰的3個城市A,B,C,各城市可單獨建立水廠，也可以合作興建一個大水廠。經(jīng)估算，合建一個大水廠，加上敷設管道的費用，要比單獨建3個小水廠的總費用少。但合建大廠的方案能否實施，要看總的建設費用分攤得是否合理。如果某個城市分攤到的費用比它單獨建設水廠的費用還多的話，它顯然不會接受合作的方案。問題是應如何合理地分攤費用，使合作興建大水廠的方案得以實現(xiàn)？例3（囚犯難題）設有兩個嫌疑犯因涉嫌作案被警官拘留，警官分別對兩人進行審訊。根據(jù)法律，如果兩個人都承認此案是他們干的，則每人各判刑7年，如果兩人都不承認，則由于證據(jù)不足，兩人各判刑1年；如果只有一人承認并揭發(fā)對方，則承認者予以寬大釋放，而不承認者將判刑9年。因此，對兩個囚犯來說，面臨著一個在“承認”和“不承認”這兩個策略間進行選擇的難題。

上面幾個例子都可看成是一個對策問題，所不同的是有些是二人對策，有些是多人對策，有些是有限對策，有些是無限對策；有些是零和對策，有些是非零和對策；有些是合作對策，有些是非合作對策等等。為了便于對不同的對策問題進行研究，可以根據(jù)不同方式進行分類，通常的分類方式有：（1）根據(jù)局中人的個數(shù)，分為二人對策和多人對策；（2）根據(jù)各局中人的贏得函數(shù)的代數(shù)和是否為零，分為零和對策與非零和對策；（3）根據(jù)各局中人之間是否允許合作，分為合作對策和非合作對策；（4）根據(jù)局中人的策略集中的策略個數(shù)，分為有限對策和無限對策。當然，還有其他的分類方式。我們主要討論二人有限零和對策，又稱為矩陣對策。第二節(jié)矩陣對策的基本定理例1設有一矩陣對策,其中具體分析見P384。對于一般矩陣對策，有如下定義。定義1設為矩陣對策。其中

,,若等式成立，記。則稱為對策的值，稱使（14-1）式成立的純局勢為在純策略下的解（或平衡局勢），與分別稱為Ⅰ，Ⅱ的最優(yōu)純策略。例2求解矩陣對策，其中解根據(jù)矩陣A，有由定義1，,的解為,與分別是局中人Ⅰ和Ⅱ的最優(yōu)純策略。從例2可以看出，矩陣A的元素a22既是其所在行的最小元素，又是其所在列的最大元素，即

將這一事實推廣到一般矩陣對策，可得到如下定理。定理1矩陣對策在純策略意義下有解的充分必要條件是：存在純局勢使得對一切都有2.2矩陣對策的混合策略由上節(jié)的討論可知，對矩陣對策來說，局中人Ⅰ有把握的至少贏得是

局中人Ⅱ有把握的至多損失是一般，局中人Ⅰ的贏得值不會多于局中人Ⅱ的所失值，即總有v1≤v2.當v1=v2時，矩陣對策G存在純策略意義下的解，且VG=

v1=v2.然而，一般情形不總是如此，實際中出現(xiàn)的更多情形是v1<v2，這樣根據(jù)定義1，對策不存在純策略意義下的解。例3

下面給出矩陣對策混合策略的定義定義3設有矩陣對策則和分別稱為局中人Ⅰ和Ⅱ的混合策略集；和分別稱為局中人Ⅰ和Ⅱ的混合策略；對，，稱為一個混合局勢，局中人Ⅰ的贏得函數(shù)記成這樣得到的一個新的對策記成,稱

為對策的混合擴充。定義4

設是矩陣對策的混合擴充，如果記其值為。則稱為對策的值，稱使（14-9）式成立的混合局勢為在混合策略意義下的解，和分別稱為局中人Ⅰ和Ⅱ的最優(yōu)混合策略。定理2矩陣對策在混合策略意義下有解的充要條件是：存在，使為函數(shù)的一個鞍點，即對一切，，有例3

考慮矩陣對策，其中定理4

設，則為的解的充要條件是：存在數(shù)，使得和分別是不等式組（Ⅰ）和（Ⅱ）的解，且.例4

考慮矩陣對策，其中矩陣對策解集的性質(zhì)性質(zhì)1

設有兩個矩陣對策

G1＝{S1,S2;A1}，G2＝{S1,S2;A2}其中A1＝(aij)，A2＝(aij+L)，L為任一常數(shù)。則(1)G1與G2同解；(2)VG2＝VG1+L矩陣對策解集的性質(zhì)性質(zhì)2

設有兩個矩陣對策

G1＝{S1,S2;A}，G2＝{S1,S2;aA}其中a>0為任一常數(shù)。則(1)G1與G2同解；(2)VG2＝aVG1定義5

設有矩陣對策G＝{S1,S2;A}，其中

S1＝{α1,α2,…,αm}，S2={β1,β2,…,βn}，

A＝(aij)m×n

如果對一切j＝1,2,…,n，都有ai1j≥ai2j,即矩陣A的第i1行元素均大于等于第i2行的對應元素，則稱局中人Ⅰ的純策略αi1優(yōu)超于αi2；

同樣，若對一切i