第八章對策論gametheory

運籌學OperationsResearch8.1引言

8.2納什均衡8.3反應(yīng)函數(shù)法8.4有限二人零和對策

8.5有限二人非零和對策8.1引言Introduction對策論（Thegametheory）是運籌學的重要分支，它研究競爭、對抗、利益分配等方面的數(shù)量化方法，并提供尋求最優(yōu)策略的途徑。1944年，VonNeumaan和經(jīng)濟學家Q.Morgenstein在大量的研究和深入的總結(jié)的基礎(chǔ)上，寫成了《對策論與經(jīng)濟行為》一書，這是對策論這一分枝的經(jīng)典之作。在該書中，不僅建立了對策論的嚴格的公理化體系，而且對大量的經(jīng)濟活動進行了深入的分析。半個世紀以來，對策論在投資、價格制定、費用分攤、財政轉(zhuǎn)移支付、投標與拍賣、對抗與追蹤等方面獲得了廣泛的應(yīng)用。對策論（gametheory）亦稱博弈論，是研究具有對抗或競爭性質(zhì)現(xiàn)象的數(shù)學理論和方法，它既是數(shù)學的一個分支，也是運籌學的一個重要學科。對策論中有一個重要的概念即對策行為，對策行為是指具有競爭或?qū)剐再|(zhì)的行為，在這類行為中，參加斗爭或競爭的各方各自具有不同的利益和目標，各方需考慮對手的各種可能的行動方案,如何采取行動以及與對手互動對自己最為有利

許多游戲具有特征：（1）有一定的規(guī)則（2）有一個結(jié)果（3）有可供選擇的策略（4）策略與利益相互依存8.1.1對策論概述8.1引言對策論，不同于日常游戲，它具有理論性，應(yīng)用的范圍也不局限于游戲。對策是一些個人、對組或其它組織，面對一定的環(huán)境條件，在一定的規(guī)則下，同時或先后從各自允許的行為或策略中進行選擇并加以實施，各自取得相應(yīng)結(jié)果的過程。這些規(guī)則應(yīng)用到經(jīng)濟、軍事、政治等領(lǐng)域也有類似的特征。例如，市場競爭、經(jīng)營決策、投資分析、價格制定、費用分攤、財政轉(zhuǎn)移支付、投標與拍賣、對抗與追蹤、資源利用、談判、競選、戰(zhàn)爭

例如，戰(zhàn)國時代的田忌賽馬、三國時代的曹不興濺墨畫蠅、曹操兵敗華容道、北宋時期的丁渭挖河修皇宮等都是對策論成功應(yīng)用的例子。8.1引言

著名法國經(jīng)濟學家泰勒爾（JeanTirole）說：“正如理性預(yù)期使宏觀經(jīng)濟學發(fā)生革命一樣，對策論廣泛而深遠地改變了經(jīng)濟學家的思維方式”。

是研究決策主體的行為發(fā)生直接相互作用時的決策及這種決策的均衡問題。即它是研究聰明而又理智的決策者在沖突或合作中的策略選擇理論。它將成為當代經(jīng)濟管理學科的前沿領(lǐng)城。

對策論就是研究對策行為中斗爭各方是否存在著最合理的行動方案，以及如何找到這個合理方案的數(shù)學理論和方法。8.1引言一個對策需要3個基本要素：

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

(2)策略集(strategies):一局對策中，可供局中人選擇的一個實際可行的行動方案稱為一個策略。

(3)贏得函數(shù)（或支付函數(shù)payoffs）：

在一局對策中，各局中人選定的策略形成的策略組稱為一個局勢，當一個局勢出現(xiàn)后，對策的結(jié)果也就確定了，即局中人會獲得相應(yīng)的收益或損失，此收益或損失的值稱為支付。支付與策略間的對應(yīng)稱為支付函數(shù)。8.1.2對策三要素全體局勢的集合S可用各局中人的策略集的迪卡爾集表示8.1引言8.1.3對策的結(jié)構(gòu)和分類8.1引言對策模型的種類千差萬別，以二人有限零和對策為例：矩陣對策的基本模型設(shè)以甲方、乙方表示兩個局中人，以分別表示甲方、乙方的策略集，則S1與S2構(gòu)成m×n個局勢以aij表示甲方關(guān)于局勢（）的贏得，則所有aij構(gòu)成一個矩陣A稱為局中人甲的贏得矩陣，由于甲、乙方得失總和恒為零。所以A還稱為局中人乙的損失矩陣，即（-A）為乙方的贏得矩陣。矩陣對策基本模型記為：【例】田忌賽馬：其中：依題意，田忌贏得矩陣：矩陣對策基本模型記為：【例】囚徒的困境（二人非零和對策）－5，－50，－10－10，0－1，－1囚徒1囚徒2坦白不坦白坦白不坦白雙方如何采取對策使結(jié)果對自己最有利？8.1引言【例】雙寡頭削價競爭（兩個廠商）100，10020，150150，2070，70亞貿(mào)中南高價低價高價低價類似地，廣告投資、采用新技術(shù)等方面，廠商之間常常耗資巨大，但不一定有利可圖的爭奪戰(zhàn)；對公共資源的掠奪式使用等問題。我們的目的是如何利用這種困境達到有利于社會，合理利用和開發(fā)公共資源，保護環(huán)境。8.1引言多寡頭削價競爭（3個廠商:亞貿(mào),中南，中北)

）100，100，10020，150，20150，20，20130，130，20亞貿(mào)中南高價低價高價低價20，20，15020，130，130130，20，13070，70，70亞貿(mào)中南高價低價高價低價中北采用高價中北采用低價8.1引言【例8.1】1943年2月，日本統(tǒng)帥山本五十六大將計劃由南太平洋新不列顛群島的拉包爾出發(fā)，3天穿過俾斯麥海，開往新幾內(nèi)亞的萊城，支援困守的日軍。有兩條路線：北線和南線。盟軍統(tǒng)帥麥克阿瑟命令他麾下的太平洋戰(zhàn)區(qū)空軍司令肯尼將軍組織空中打擊。偵察機重點搜索有兩個方案：北線和南線。當時未來3天中：北線陰雨，能見度差；南線晴天，能見度佳。日美雙方各自應(yīng)采用哪種方案8.1引言北線南線

日軍盟軍北線（）南線()北線（）22南線（）13【解】局中人：盟軍、日軍；雙方策略：北線、南線，記為:盟軍的贏得矩陣如下：最優(yōu)策略是：,即都選擇北線。日軍艦隊受到重創(chuàng)，但未全殲。雙方選擇的策略是：在最不利中選擇最有利的策略。8.1引言下一節(jié)：納什均衡12.1引言8.2納什均衡NashEquilibrium8.2納什均衡Nash對對策論的貢獻有：（1）合作對策中的討價還價模型，稱為Nash討價還價解；（2）非合作對策的均衡分析。納什均衡（NashEquilibrium）假定有n個博弈方參加博弈，在給定其他博弈方策略的條件下，每個人選擇自己的最優(yōu)策略（個人最優(yōu)策略可能依賴也可能不依賴他人策略），一起構(gòu)成一個策略組合（StrategyProfile），而Nash均衡是這樣一種策略組合，由所有參與人的最優(yōu)策略組成，給定別人策略的條件下，沒有任何單個參與人有積極性選擇其他策略，從而沒有任何人有積極性打破這種均衡，Nash均衡是一種“僵局”：給定別人不動的情況下，沒有人有興趣動。約翰·納什(JohnF.Nash)

1928年生于美國,1994年獲得諾貝爾經(jīng)濟學獎在非合作博弈的均衡分析理論方面做出了開創(chuàng)性的貢獻，對博弈論和經(jīng)濟學產(chǎn)生了重大影響8.2.1納什均衡定義另一種解釋：假定所有博弈方事先達成一項協(xié)議，規(guī)定每個人的行為規(guī)則，在沒有外在的強制力約束時，當事人會自覺遵守這個協(xié)議，等于說這個協(xié)議構(gòu)成一個納什均衡：假定別人遵守協(xié)議的情況下，沒有人有積極性偏離協(xié)議規(guī)定的自己的行為規(guī)則。換句話說，如果一個協(xié)議不構(gòu)成納什均衡，它就不可能自動實施，因為至少有一個參與人會違背此協(xié)議，不滿足Nash均衡要求的協(xié)議是沒有意義的。8.2納什均衡用G表示一個對策，若一個對策中有n個局中人，則每個局中人可選策略的集合稱為策略集，分別用

S1，S2，…，Sn表示；sij表示局中人i的第j個策略，其中j可取有限個值（有限策略對策），也可取無限個值（無限策略對策）；對策方i的得益則用hi表示；hi是各對策方策略的多元函數(shù)，n個局中人的對策G常寫成：【定義8.1】

在對策G={S1，S2…，Sn；h1，h2…h(huán)n}中，如果由各個對策方的各選取一個策略組成的某個策略組合（s1*，s2*…，sn*）中，任一對策方i的策略si*，都是對其余策略方策略的組合（s1*，…，s*i-1，s*i+1…，sn*）的最佳策略，即hi（s1*，…，s*i-1，si*，s*i+1…sn*）≥hi（s1*，…，s*i-1，sij，s*i+1…，sn*）對任意sij∈Si都成立，則稱（s1*，…，sn*）為G的一個純策略“納什均衡”（NashEquilibrium）．

G={S1，…，Sn；h1，…h(huán)n}8.2納什均衡各選取一個策略組成的某個策略組合構(gòu)成一個局勢，其最優(yōu)局勢稱為純策略意義下的最優(yōu)局勢．【例8.2】

假設(shè)有三個廠商在同一市場上生產(chǎn)銷售完全相同的產(chǎn)品，它們各自的產(chǎn)量分別用m1、m2和m3表示，再假設(shè)m1、m2和m3只能取1、2、3……等正整數(shù)值．市場出清價格一定是市場總產(chǎn)量Q=m1+m2+m3的函數(shù)，假設(shè)該函數(shù)為：

不妨先假設(shè)三個廠商開始時分別生產(chǎn)3單位，9單位和6單位產(chǎn)量，這時三廠商是否滿意各自的產(chǎn)量，要從利潤進行分析．由于產(chǎn)量不能超過20，則第i個廠商的利潤函數(shù)為

8.2納什均衡可算出在產(chǎn)量組合為（3，9，6）時，市場價格為2，三廠商的利潤分8，16和12，再作其它產(chǎn)量組合時亦會有不同的結(jié)果，如表8.2．

表8.2三廠商離散產(chǎn)量結(jié)合對應(yīng)價格和利潤

m1m2m3pπ1π2π3396261812386392418556420202455552525253331133333363384824248.2納什均衡下一節(jié)：有限二人零和對策

作業(yè)：教材P293T98.2納什均衡8.3有限二人零和對策矩陣對策就是二人有限零和對策。通常矩陣用來表示局中人1的贏得，局中人2的支付。8.3有限二人零和對策

用Ⅰ、Ⅱ表示兩個局中人，并設(shè)局中人Ⅰ有m個純策略，α1，α2，…，αm，局中人Ⅱ有n個純策略β1，β2，…，βn，則按對策論的相關(guān)要素定義，局中人Ⅰ、Ⅱ的策略集分別為：可以算出，局中人Ⅰ、Ⅱ所構(gòu)成的策略組合共有m×n個，記局中人Ⅰ在策略（αi,βj）下的贏得aij，則Ⅰ在每個策略的贏得構(gòu)成一個矩陣當局中人Ⅰ、Ⅱ的策略集S1,S2及I的贏得矩陣確定后，一個矩陣對策就給定了．通常將矩陣對策記為：

8.3有限二人零和對策

8.4.1數(shù)學定義8.3有限二人零和對策

稱A為局中人Ⅰ的贏得矩陣（或為Ⅱ的支付矩陣），由于對策為零和的，故局中人Ⅱ的贏得矩陣為－A。矩陣對策記為成立，，則稱VG為對策G的值，對應(yīng)的策略組合

8.4.2純策略矩陣對策【定義8.4】設(shè)G={S1，S2；A}為矩陣對策，其中S1={α1，α2，…，αn}，S2={β1，β2，…，βn}，若等式稱為該對策的納什均衡．8.3有限二人零和對策

【例8.3】求解矩陣對策，其中則有對策G的解為：【解】8.3有限二人零和對策

【定理8.1】矩陣對策G={S1，S2；A}在純策略定義下有納什均衡的充要條件是：存在策略組合使得對一切i=1，…，m,j=1，…，n,均有：

矩陣對策在純策略意義下有解且VG=ai*j*的充要條件是：ai*j*是A的鞍點，在對策論中，矩陣A的鞍點也稱為對策的鞍點．

8.3有限二人零和對策

【定義5】設(shè)f(x，y)為一個定義在x∈A及y∈B上的實函數(shù)，如果存在x*∈A及y*∈B,使得對一切x∈A及y∈B有則稱為函數(shù)f

的有關(guān)鞍點。矩陣對策在純策略意義下的解且的充要條件是是A的鞍點。8.3有限二人零和對策

【解】

直接在贏得表上計算，有

可知=5，i*=1,3，j*=2,4．故（α1，β2）（α1，β4）（α2，β2）（α2，β4）為對策的納什均衡，VG=5．8.3有限二人零和對策

【例8.4】

設(shè)有矩陣對策G={S1，S2；A}，贏得矩陣為求納什均衡【性質(zhì)8.1】

無差別性．若和為G的兩個解，則：【性質(zhì)8.2】

可交換性．若和為G的兩個解，則以上方法也稱“上策均衡法”(Dominant-strategeEqyilibrium)8.3有限二人零和對策

也是對策的解．及【例8.5】

甲、乙兩個企業(yè)同時生產(chǎn)一種電子產(chǎn)品（假設(shè)市場上只有這兩家，為一雙寡頭競爭局面），兩個企業(yè)都想通過改革管理獲取更多的銷售份額，甲企業(yè)的策略措施有：（1）降低產(chǎn)品價格；（2）提高產(chǎn)品質(zhì)量；（3）推出新產(chǎn)品．乙企業(yè)措施為：（1）增加廣告費用；（2）增設(shè)網(wǎng)點；（3）改進產(chǎn)品性能，通過預(yù)測，兩個企業(yè)市場份額變動情況如表12－4所示，試確定最優(yōu)策略．

乙企業(yè)123min甲企業(yè)112－13－1213103335855*max13105*

【解】則對策最優(yōu)解為VG=5，納什均衡為（α3，β3）．甲企業(yè)采用推出新產(chǎn)品策略，乙企業(yè)采用改進產(chǎn)品性能策略，結(jié)果甲企業(yè)贏得5％的市場份額．8.3有限二人零和對策

8.3.3混合策略矩陣對策

純策略矩陣對策的滿足納什均衡是滿足局中人Ⅰ有把握的至少贏得是局中人Ⅱ有把握的至多損失即：

當V1≠V2

時，這時不存在純策略意義下的納什均衡。

田忌齊王上中下上下中中上下中下上下上中下中上上中下3，－31，－11，－11，－1－1，11，－1上下中1，－13，－31，－11，－11，－1－1，1中上下1，－1－1，13，－31，－11，－11，－1中下上－1，11，－11，－13，－31，－11，－1下上中1，－11，－11，－1－1，13，－31，－1下中上1，－11，－1－1，11，－11，－13，－38.3有限二人零和對策

利用最大最小和最小最大原則，發(fā)現(xiàn)不存在使得成立的點．8.3有限二人零和對策

例：對局中人1來說，v1=－2，i*=2，對局中人2來說，v2=3，j*=1，v1≠v2。沒有鞍點?！径x8.6】設(shè)矩陣對策，其中記8.3有限二人零和對策

則分別稱為局中人Ⅰ、Ⅱ的混合策略集；、分別稱為局中人1、2的混合策略，為一個混合局勢。稱為G的混合擴充。E是贏得期望值?！径x】當時，稱為局中人Ⅰ、Ⅱ在混合策略中的納什均衡。稱為局中人Ⅰ在選取混合策略S*1時的贏得函數(shù)

【定理8.2】矩陣對象G={S1，S2；A}在混合策略意義下有解的充要條件是：存在x*∈S1*，y*∈S2*，使（x*，y*）為函數(shù)E（x，y）的一個鞍點，即對一切x∈S1*，y∈S2*有E（x，y*）≤E（x*，y*）≤E（x*，y）8.3有限二人零和對策

【例8.6】

考慮矩陣對策G={S1，S2；A}，其中局中人1的贏得期望值：取，滿足試求納什均衡．

【解】

純策略納什均衡不存在．設(shè)x=（x1，x2）為局中人Ⅰ的混合策略，y=(y1，y2)為局中人Ⅱ的混合策略，則：8.3有限二人零和對策

分別為局中人Ⅰ和Ⅱ的最優(yōu)策略．即該對策的納什均衡。

8.4.4納什均衡存在定理【定理8.3】設(shè)x*∈S1*，y*∈S2*,則（x*，y*）為對策G的納什均衡的條件是：對任意i=1,…，m，j=1,…，n，有E(i,y*)≤E(x*,y*)≤E(x*,j)其中：8.3有限二人零和對策

【定理8.4】設(shè)x*∈S1*，y*∈S2*，則（x*，y*）是對策G的納什均衡的充要條件是：存在數(shù)V，使得x*，y*分別滿足：且V=VG.【定理8.5】對任一矩陣對策G={S1，S2；A}，一定存在混合策略意義下的納什均衡．8.3有限二人零和對策

【定理8.6】設(shè)（x*，y*）為矩陣對策G的一個納什均衡，V=VG，則(1)若xi*＞0，則

(2)若yi*

＞0，則

(3)若，則

(4)若,則8.3有限二人零和對策

例8.3有限二人零和對策

【定理8.7】設(shè)有兩個矩陣對策

G1={S1，S2；A},G2={S1，S2；αA}則(1)VG2=αVG1(2)T(G1)=T(G2)其中α＞0為一常數(shù)，T(G1)、T(G2)為兩個對策的解集合1.優(yōu)超原則法【例8.7】

設(shè)贏得矩陣A為:

求納什均衡．

【解】第4行優(yōu)于第1行，第3行優(yōu)于第2行，故可劃去第1行和第2行，得到新的贏得矩陣，x1=x2=08.3有限二人零和對策

8.4.5矩陣對策求解方法“嚴格下策反復(fù)消去法”(IteratedEliminationofStrictly

DominatedStrategies)對于A1第1列優(yōu)于第3列，第2列優(yōu)于第4列，(1/2)×（第1列）+(1/2)×（第2列）優(yōu)超于第5列，因此去掉第3列，第4列和第5列，y3=y4=y5=0，得到A2：

又由于第1行優(yōu)超于第3行，所以從A2中劃去第3行，x5=0，得到A3

，解方程組：該矩陣對策的納什均衡為：

VG=4.8

8.3有限二人零和對策

2.線性方程組法若最優(yōu)策略中和均不為零時，有

8.3有限二人零和對策

【例12.14】求解矩陣對策【解】建立方程組求解得：x=(0.525，0.275，0.2),y=(0.2，0.05，0.75);VG=－0.453.線性規(guī)劃方法任意矩陣對策的求解均等價于一對互為對偶的線性規(guī)劃問題，而定理12.4表明，對策G的解等價于下面兩個不等式的解．

【定理8.9】設(shè)矩陣對策的值為v，則：

8.3有限二人零和對策

則局中人Ⅰ、Ⅱ的最優(yōu)策略等價于線性規(guī)劃問題：

8.3有限二人零和對策

令

有局中人Ⅰ：8.3有限二人零和對策

同理,令有局中人Ⅱ：8.3有限二人零和對策

【例8.8】

利用線性規(guī)劃方法求解贏得矩陣為

的矩陣對策的納什均衡．

【解】

此問題可化為兩個互為對偶的線性規(guī)劃問題：8.3有限二人零和對策

最優(yōu)解：X＝(0.1065，0.1448，0.0437),Y＝(0.1093，0.1038，0.0819)；w＝0.29508．利用變換

得到x*=(0.36，0.49，0.15)，y*=(0.37，0.35，0.28)；v=3.398.3有限二人零和對策

下一節(jié)：有限二人非零和對策

8.3有限二人零和對策

作業(yè)：教材P292T3、4、5、6、88.4有限二人非零和對策8.4有限二人非零和對策8.5.1數(shù)學定義【例8.8】市場上有兩企業(yè)生產(chǎn)同樣商品，甲企業(yè)與乙企業(yè)的贏得矩陣分別為矩陣A1和A2合并為雙矩陣依然在混合擴充意義下考慮有限二人非零和對策，記局中人1的混合策略為x，局中人2的混合策略為y，相應(yīng)的策略集記為8.4有限二人非零和對策【定義8.8】對于某個有限二人非零和對策，其局中人1的贏得（混合策略下）為局中人2的贏得為8.4有限二人非零和對策8.5.2有限二人非零和對策納什均衡分別是局中人1和2的贏得，，和如果有一對策略為任意策略，滿足則稱為該對策的納什均衡，稱為對策的納什均衡解（或贏得）【定理12.10】（納什定理）任何矩陣對策及有限二人非零和對策至少有一個納什均衡【定義8.9】在有限二人非零和對策中,設(shè)8.4有限二人非零和對策1.圖解法8.