引言納什均衡NashEquilibrium反應(yīng)函數(shù)法參考課件

12.1引言12.2納什均衡

NashEquilibrium12.3反應(yīng)函數(shù)法

Methodofreactionfunction12.4有限二人零和博弈

Twopersonfinitezero-sumgame

12.5有限二人非零和博弈

Twopersonfinitenon-zero-sumgame

第12章博弈論gametheory1博弈論（gametheory）亦稱對策論，是研究具有對抗或競爭性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法，它既是數(shù)學(xué)、也是運(yùn)籌學(xué)的一個重要分支。

博弈行為是博弈論中一個重要的概念。博弈行為是指具有競爭或?qū)剐再|(zhì)的行為，在這類行為中，參加斗爭或競爭的各方各自具有不同的利益和目標(biāo)，各方需考慮對手的各種可能的行動方案，如何采取行動以及與對手互動對自己最為有利。12.1.1博弈論概述12.1引言2【例12-3】齊威王田忌賽馬

齊王：上中下田忌：下上中12.1.1博弈論概述3【補(bǔ)充例1】囚徒的困境（-1，-1）（-10，-1/4）抵賴（-1/4，-10）（-5，-5）坦白抵賴坦白囚徒2囚徒112.1.1博弈論概述4博弈：

是一些個人、團(tuán)隊或其它組織，面對一定的環(huán)境條件，在一定的規(guī)則下，同時或先后從各自允許的行為或策略中進(jìn)行選擇并加以實(shí)施，各自取得相應(yīng)結(jié)果的過程。博弈行為具有的共同特征：（1）有一定的規(guī)則（2）有一個明確的結(jié)果（3）有可供選擇的策略（4）策略與利益相互依存12.1.1博弈論概述5在現(xiàn)實(shí)社會、經(jīng)濟(jì)生活中很多活動都具有博弈的特征，例如：市場競爭、經(jīng)營決策、投資分析、價格制定、費(fèi)用分?jǐn)?、財政轉(zhuǎn)移支付、投標(biāo)與拍賣、對抗與追蹤、資源利用、談判、競選、戰(zhàn)爭等。又如，三國時代的曹不興濺墨畫蠅、曹操兵敗華容道、北宋時期的丁渭挖河修皇宮等都是博弈論成功應(yīng)用的例子。

12.1.1博弈論概述6博弈論研究的問題:參與博弈的各方是否存在最合理的策略以及如何找到合理的策略。

博弈論是研究決策主體的行為發(fā)生直接相互作用時的決策及這種決策的均衡問題。即它是研究聰明而又理智的決策者在沖突或合作中的策略選擇理論。它將成為當(dāng)代經(jīng)濟(jì)管理學(xué)科的前沿領(lǐng)城。著名法國經(jīng)濟(jì)學(xué)家泰勒爾（JeanTirole）說：“正如理性預(yù)期使宏觀經(jīng)濟(jì)學(xué)發(fā)生革命一樣，博弈論廣泛而深遠(yuǎn)地改變了經(jīng)濟(jì)學(xué)家的思維方式”。

12.1.1博弈論概述71944年美國普林斯特大學(xué)教授馮·諾伊曼、摩根斯坦的著作《博弈論和經(jīng)濟(jì)行為》的出版，是博弈論誕生的標(biāo)志。普林斯特大學(xué)對博弈論作出重大貢獻(xiàn)的還有塔克、庫恩、納什等。12.1.1博弈論概述

要想在現(xiàn)代社會做一個有文化的人，你必須對博弈論有一個大致的了解。——薩繆爾森812.1.1博弈論概述約翰·納什(JohnF.Nash)

1928年生于美國,1994年獲得諾貝爾經(jīng)濟(jì)學(xué)獎。在非合作博弈的均衡分析理論方面做出了開創(chuàng)性的貢獻(xiàn)，對博弈論和經(jīng)濟(jì)學(xué)產(chǎn)生了重大影響。

Nash對博弈論的主要貢獻(xiàn)有：（1）合作博弈中的討價還價模型，稱為Nash討價還價解；（2）非合作博弈的均衡分析。

9博弈論發(fā)展史上的五次諾貝爾經(jīng)濟(jì)學(xué)獎1994年，納什、海薩尼、塞爾頓，非合作博弈理論12.1.1博弈論概述10博弈論發(fā)展史上的五次諾貝爾經(jīng)濟(jì)學(xué)獎

1996年，莫里斯和維克瑞，不對稱信息條件下激勵機(jī)制問題12.1.1博弈論概述11博弈論發(fā)展史上的五次諾貝爾經(jīng)濟(jì)學(xué)獎

2005年，羅伯特.奧曼，托馬斯.謝林，合作博弈理論12.1.1博弈論概述12博弈論發(fā)展史上的五次諾貝爾經(jīng)濟(jì)學(xué)獎

2007年，三名美國經(jīng)濟(jì)學(xué)家萊昂尼德.赫維奇，埃里克.馬斯金，羅杰.邁爾森，“機(jī)制設(shè)計理論”12.1.1博弈論概述13博弈論發(fā)展史上的五次諾貝爾經(jīng)濟(jì)學(xué)獎

2012年，美國經(jīng)濟(jì)學(xué)家阿爾文.羅思（AlvinE.Roth）和勞埃德.沙普利（LloydS.Shapley），“穩(wěn)定匹配理論和市場設(shè)計實(shí)踐”。

12.1.1博弈論概述14博弈模型的3個基本要素：

（1）局中人(players)：博弈的參加者，可以是一個人、一個團(tuán)隊、一個企業(yè)、交戰(zhàn)的一方等。假設(shè)每一個局中人都是“理智”的。（2）策略集(strategies)：策略是可供局中人選擇的實(shí)際可行的完整的行動方案。每個局中人的策略集（S）至少應(yīng)包括兩個策略。（3）得益（贏得）函數(shù)(payoffs)：當(dāng)每個局中人的策略確定后，他們就會得到相應(yīng)的收益或損失稱為局中人的得益，不同的策略會導(dǎo)致不同的得益，因此，得益是策略的函數(shù)。12.1.2博弈三要素15n人博弈全體局勢的集合S可用各局中人的策略集的迪卡爾集表示12.1.2博弈三要素局勢：每一個局中人各選擇一個策略形成的對局(策略組合)。

兩人博弈二人博弈的矩陣型表示:坦白抵賴坦白-5，-5-1/4，-10抵賴-10，-1/4-1，-1囚徒2囚徒116分類依據(jù)類型局中人數(shù)量兩人博弈，多人博弈，單人博弈策略數(shù)量有限博弈，無限博弈信息結(jié)構(gòu)完全信息博弈，不對稱信息博弈局中人間是否允許合作非合作博弈，合作博弈博弈過程靜態(tài)博弈，動態(tài)博弈，重復(fù)博弈得益情況零和博弈，常和博弈，變和博弈12.1.3博弈的結(jié)構(gòu)和分類1712.1.3博弈的結(jié)構(gòu)和分類18【例12-2】1943年2月，日本統(tǒng)帥山本五十六大將計劃由南太平洋新不列顛群島的拉包爾出發(fā)，3天穿過俾斯麥海，開往新幾內(nèi)亞的萊城，支援困守的日軍。有兩條路線：北線和南線。盟軍統(tǒng)帥麥克阿瑟命令他麾下的太平洋戰(zhàn)區(qū)空軍司令肯尼將軍組織空中打擊。偵察機(jī)重點(diǎn)搜索有兩個方案：北線和南線。當(dāng)時未來3天中：北線陰雨，能見度差；南線晴天，能見度佳。日美雙方各自應(yīng)采用哪種方案。12.1.3博弈的結(jié)構(gòu)和分類19北線南線20【解】局中人：盟軍、日軍雙方策略：北線、南線盟軍的贏得矩陣如下：日軍盟軍北線（）南線()北線（）22南線（）13最優(yōu)局勢是：即都選擇北線。日軍艦隊受到重創(chuàng)，但未全殲。

雙方選擇策略的思路：在最不利中選擇最有利的策略。12.1.3博弈的結(jié)構(gòu)和分類兩人有限零和博弈21【補(bǔ)充例2】雙寡頭削價競爭（兩個廠商）類似地，廣告投資、采用新技術(shù)等方面，廠商之間常常耗資巨大，但不一定有利可圖的爭奪戰(zhàn)；對公共資源的掠奪式使用等問題。我們的目的是如何利用這種困境達(dá)到有利于社會，合理利用和開發(fā)公共資源，保護(hù)環(huán)境。12.1.3博弈的結(jié)構(gòu)和分類中南亞貿(mào)高價低價高價（100，100）（30，150）低價（150，30）（70，70）兩人有限非零和博弈22多寡頭削價競爭（3個廠商：亞貿(mào)，中南，中北）中北采用高價中北采用低價12.1.3博弈的結(jié)構(gòu)和分類中南亞貿(mào)高價低價高價(100,100,100)(20,150,20)低價(150,20,20)(130,130,20)中南亞貿(mào)高價低價高價(20,20,150)(20,130,130)低價(130,20,130)(70,70,70)23【補(bǔ)充例3】動態(tài)博弈：甲向乙借一萬元錢經(jīng)營，甲許諾經(jīng)營成功后分給乙總利潤（4萬）的一半，乙是否借給甲？乙甲借不借乙分不分(2，2)(1，0)打乙不打(0，4)(1，0)(－1,0)有法律保障法律保障不足12.1.3博弈的結(jié)構(gòu)和分類完全信息動態(tài)博弈24約束與激勵、核嚇阻、公共資源的悲劇路徑依賴民航禁折令2002年國家郵政總局“64號文件”宇宙法則：78/22法則博傻理論膽小博弈膽大博弈12.1.3博弈的結(jié)構(gòu)和分類25下一節(jié)：納什均衡12.1引言2612.2納什均衡納什均衡（NashEquilibrium）:

假定有n個博弈方參加博弈，在給定其他博弈方策略的條件下，每個人選擇自己的最優(yōu)策略（個人最優(yōu)策略可能依賴也可能不依賴他人策略），從而使自己利益最大化，所有局中人的策略一起構(gòu)成一個策略組合。而Nash均衡是這樣一種策略組合，由所有參與人的最優(yōu)策略組成，給定別人策略的條件下，沒有任何單個參與人有積極性選擇其他策略，從而沒有任何人有積極性打破這種均衡，Nash均衡是一種“僵局”：給定別人不動的情況下，沒有人有興趣動。12.2.1納什均衡定義27另一種解釋：

假定所有博弈方事先達(dá)成一項協(xié)議，規(guī)定每個人的行為規(guī)則，在沒有外在的強(qiáng)制力約束時，當(dāng)事人會自覺遵守這個協(xié)議，等于說這個協(xié)議構(gòu)成一個納什均衡：假定別人遵守協(xié)議的情況下，沒有人有積極性偏離協(xié)議規(guī)定的自己的行為規(guī)則。換句話說，如果一個協(xié)議不構(gòu)成納什均衡，它就不可能自動實(shí)施，因?yàn)橹辽儆幸粋€參與人會違背此協(xié)議，不滿足Nash均衡要求的協(xié)議是沒有意義的。12.2納什均衡2812.2納什均衡“納什均衡”改變了經(jīng)濟(jì)學(xué)的語言和表達(dá)方法。在進(jìn)化博弈論方面相當(dāng)有造詣的坎多利（Kandori，1997）對保羅·薩繆爾森（PaulSamuelson）的名言“你甚至可以使一只鸚鵡變成一個訓(xùn)練有素的經(jīng)濟(jì)學(xué)家，因?yàn)樗仨殞W(xué)習(xí)的只有兩個詞，那就是‘供給’和‘需求’”，曾做過一個幽默的引申，他說，“現(xiàn)在這只鸚鵡需要再學(xué)一個詞，那就是‘納什均衡’”。2912.2納什均衡你正在圖書館枯坐，一位陌生美女主動過來和你搭訕，并要求和你一起玩?zhèn)€數(shù)學(xué)游戲。美女提議：“讓我們各自亮出硬幣的一面，或正或反。如果我們都是正面，那么我給你3元，如果我們都是反面，我給你1元，剩下的情況你給我2元就可以了?！蹦敲丛摬辉摵瓦@位姑娘玩這個游戲呢？

30用G表示一個博弈，若一個博弈中有n個局中人，則每個局中人可選策略的集合稱為策略集，分別用S1，S2，…，Sn表示sij表示局中人i的第j個策略，其中j可取有限個值（有限策略博弈），也可取無限個值（無限策略博弈）；博弈方i的得益則用hi表示；hi是各博弈方策略的多元函數(shù)，n個局中人的博弈G常寫成：

G={S1，…，Sn；h1，…h(huán)n}12.2納什均衡31純策略納什均衡【定義12.1】

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

12.2納什均衡

各選取一個策略組成的某個策略組合構(gòu)成一個局勢，其最優(yōu)局勢稱為純策略意義下的最優(yōu)局勢（納什均衡）。32【例12-1】

假設(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)量，要從利潤進(jìn)行分析，由于產(chǎn)量不能超過20，則第i個廠商的利潤函數(shù)為

12.2納什均衡33

可算出在產(chǎn)量組合為（3，9，6）時，市場價格為2，三廠商的利潤分別為6，18和12，再作其它產(chǎn)量組合時亦會有不同的結(jié)果。表12-2三廠商離散產(chǎn)量組合對應(yīng)價格和利潤

m1m2m3pπ1π2π339626181238639241855642020245555252525554630302433311333333633848242412.2納什均衡最穩(wěn)定的產(chǎn)量組合，是一個納什均衡34【定義12.2】在博弈G={S1，…，Sn；h1，…，hn}中，局中人i的策略集為Si={si1，…，sik}，則他以概率分布pi=（pi1，…，pik）隨機(jī)在其k個可選策略中選擇的“策略”稱為一個混合策略，其中0≤pij≤1對j＝1，…，k都成立，且pi1+…+pik=1。純策略是混合策略的特殊情形，只是選擇相應(yīng)純策略的概率服從（0-1）分布。一個混合策略可理解為：如果進(jìn)行多局博弈G的話，局中人i分別選取純策略的頻率；若只進(jìn)行一次博弈，則反映了局中人i對各純策略的偏愛程度?；旌喜呗约{什均衡12.2納什均衡35【定義12.3】如果一個博弈G={S1，…，Sn，h1，…，hn}中，參予者i的策略集為Si={si1，…，sik}，如果由各個博弈方的策略組成策略集合G*={s1*，s2*，…，sn*}，其中都是對其余博弈方策略組合的最佳策略，即hi(s1*,s2*,…,si-1*,si*,si+1*…sn*)≥hi(s1*,s2*,…,si-1*,sij,si+1*,…sn*)對任意sij∈Si都成立，則稱(s1*,…，sn*)為G的一個混合策略納什均衡．12.2納什均衡36下一節(jié)：反應(yīng)函數(shù)法作業(yè)：教材P293T1012.2納什均衡NashEquilibrium37

當(dāng)?shù)靡媸遣┺牡亩嘣B續(xù)函數(shù)時，求出每個博弈方的反應(yīng)函數(shù)，而各個反應(yīng)函數(shù)的交點(diǎn)就是納什均衡。12.3反應(yīng)函數(shù)法38【例12-4】設(shè)A，B兩廠家生產(chǎn)同樣產(chǎn)品，廠商A產(chǎn)量為q1，B產(chǎn)量為q2，市場總產(chǎn)量為Q=q1+q2，市場出清價格是市場總產(chǎn)量的函數(shù)P＝6－Q。設(shè)產(chǎn)品產(chǎn)量的邊際成本相等，C1=C2=2。求解兩廠商的納什均衡（假設(shè)產(chǎn)量連續(xù)可分）。分析：這是一個連續(xù)產(chǎn)量的古諾模型，不難看出，該博弈中兩廠商各自的利潤分別為各自的銷售收益減去各自成本，即：12.3反應(yīng)函數(shù)法q1q139作反應(yīng)函數(shù)納什均衡：(4/3,4/3)12.3反應(yīng)函數(shù)法(0,4)（0,2)(2,0)(4,0)(4/3,4/3)R1R240【例12-5】考慮上述模型的另一種情況，即各廠商所選擇的是價格而不是產(chǎn)量，假設(shè)產(chǎn)量與價格的函數(shù)關(guān)系為：其它條件不變，邊際成本為C1、C2，試求解其納什均衡?！窘狻扛髯缘牟呗钥臻g為兩方的得益就是各自的利潤12.3反應(yīng)函數(shù)法41為該博弈唯一的納什均衡

12.3反應(yīng)函數(shù)法42【例12-6】設(shè)有3個農(nóng)戶一起放牧羊群，現(xiàn)有一可供大家自由放牧的草地，由于草地面積有限，只能供有限只羊群吃飽，否則就會影響到羊群的產(chǎn)出，假設(shè)每只羊的產(chǎn)出函數(shù)為成本C=8，且每個農(nóng)戶在決定自己放牧羊群數(shù)的時候并不知道其它農(nóng)戶的決策，試求出該決策問題的納什均衡?！窘狻扛鬓r(nóng)戶的得益函數(shù)分別為12.3反應(yīng)函數(shù)法4312.3反應(yīng)函數(shù)法反應(yīng)函數(shù)

因此該博弈的納什均衡為（18，18，18）44用反應(yīng)函數(shù)法求納什均衡的步驟：1.建立得益函數(shù)；2.求反應(yīng)函數(shù)：即對得益函數(shù)求偏導(dǎo)數(shù)；3.解反應(yīng)函數(shù)方程組。反應(yīng)函數(shù)方程組的解即為納什均衡。12.3反應(yīng)函數(shù)法45下一節(jié)：有限二人零和博弈

作業(yè)：教材P293T912.3反應(yīng)函數(shù)法4612.4二人有限零和博弈

兩人有限零和博弈也稱矩陣博弈，在眾多博弈模型中占有重要地位，也是最簡單、理論和算法都比較完善的一類。齊威王田忌賽馬，例12-2均為矩陣博弈。47

12.4.1數(shù)學(xué)模型

模型：

S1={α1,α2,…，αm}——局中人Ⅰ的純策略集S2={β1,β2,…，βn}——局中人Ⅱ的純策略集aij——局中人Ⅰ在局勢（αi,βj）下的贏得值

——局中人Ⅰ的得益矩陣

(局中人Ⅱ的得益矩陣為-A)

G={S1，S2；A}Ⅰ:Ⅱ:12.4二人有限零和博弈

48

建立齊王田忌賽馬的數(shù)學(xué)模型S1={(上中下）,（上下中）,（中上下）,（中下上）,（下上中）,（下中上)}S2={(上中下）,（上下中）,（中上下）,（中下上）,（下上中）,（下中上)}12.4.1數(shù)學(xué)模型

田忌齊王上中下上下中中上下中下上下上中下中上上中下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，－34912.4.1數(shù)學(xué)模型

齊王的贏得矩陣50【例12-7】求解矩陣博弈，其中博弈G的解（納什均衡）為：【解】12.4.2純策略矩陣博弈

局中人Ⅰ的最優(yōu)策略是α2

,局中人Ⅱ的最優(yōu)策略是β2S1={α1,α2,α3,α4}S2={β1,β2,β3}51【定義12.4】設(shè)G={S1，S2；A}為矩陣博弈，其中S1={α1，α2，…，αm}，S2={β1，β2，…，βn}，若等式成立，，則稱VG為博弈G的值，對應(yīng)的策略組合稱為該博弈的純策略納什均衡。

12.4.2純策略矩陣博弈

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

當(dāng)局中人Ⅰ選定純策略αi*后，局中人Ⅱ?yàn)榱耸蛊渌ё钌?，只能選擇純策略βj*，否則就可能損失得更多；反之，當(dāng)局中人Ⅱ選定純策略βj*后，局中人Ⅰ為了得到最大的贏得也只能選擇純策略αi*，否則就會贏得更少，雙方的競爭在局勢（αi*,,βj*）下達(dá)到了一個平衡狀態(tài)。即納什均衡。12.4.2純策略矩陣博弈

53【定義12.5】設(shè)f(x，y)為一個定義在x∈A及y∈B上的實(shí)函數(shù)，如果存在x*∈A及y*∈B,使得對一切x∈A及y∈B有則稱為函數(shù)f的一個鞍點(diǎn)。矩陣博弈在純策略意義下有解且的充要條件是：12.4.2純策略矩陣博弈

是A的鞍點(diǎn)。（αi*,βj*）54【例12-9】

設(shè)有矩陣博弈G={S1，S2；A}，贏得矩陣為求納什均衡12.4.2純策略矩陣博弈

S1={α1,α2,α3,α4}S2={β1,β2,β3，β4

}55納什均衡為：(α1,β2

)，(α1,β4

)，(α3,β2

)，(α3,β4

)博弈值VG=5局中人Ⅰ的最優(yōu)純策略為α1，α3局中人Ⅱ的最優(yōu)純策略為β2，β412.4.2純策略矩陣博弈

A=α1α2α3α4

β1

β2

β3β4【解】56【性質(zhì)12.1】無差別性。若和為G的兩個解，則：【性質(zhì)12.2】可交換性。若和為G的兩個解，則和也是博弈的解．12.4.2純策略矩陣博弈

57

應(yīng)用舉例：

某單位采購員在秋天時要決定冬季取暖用煤的采購量。已知在正常氣溫條件下需要煤15噸，在較暖和較冷氣溫條件下分別需要煤10噸和20噸。假定冬季的煤價隨天氣寒冷程度而變化，在較暖、正常、較冷氣溫條件下每噸煤的價格分別為100元、150元和200元。又設(shè)秋季時每噸煤的價格為100元，在沒有關(guān)于當(dāng)年冬季氣溫情況準(zhǔn)確預(yù)報的條件下，秋季時應(yīng)采購多少噸煤能使總支出最少？試建立該問題的矩陣對策模型，并求解。12.4.2純策略矩陣博弈

58【解】局中人I（采購員）：S1={10噸，15噸，20噸}局中人II（大自然）：S2={較暖，正常，較冷}納什均衡為（α3，β3），博弈值VG=-2000既采購員在秋天購煤20噸較好。12.4.2純策略矩陣博弈

5912.4.3混合策略矩陣博弈矩陣博弈滿足純策略納什均衡是指：

滿足局中人Ⅰ有把握的至少贏得是局中人Ⅱ有把握的至多損失，即

當(dāng)V1≠V2時，這時不存在純策略意義下的納什均衡。60利用最小最大和最大最小原則，發(fā)現(xiàn)不存在使得成立的點(diǎn)，即不存在純策略納什均衡。12.4.3混合策略矩陣博弈齊王田忌賽馬61【定義12.6】設(shè)矩陣博弈，其中記12.4.3混合策略矩陣博弈則分別稱為局中人Ⅰ、Ⅱ的混合策略集；、分別稱為局中人Ⅰ、Ⅱ的混合策略，為一個混合局勢。稱為G的混合擴(kuò)充。E是局中人Ⅰ的贏得期望值62純策略與混合策略的關(guān)系純策略是混合策略的特殊情形。一個混合策略X=(x1,x2,…，xm)可理解為：如果進(jìn)行多局博弈的話，局中人I分別選取純策略α1,α2,…，αm的頻率；若只進(jìn)行一次博弈，則反映了局中人I對各純策略的偏愛程度。12.4.3混合策略矩陣博弈63【定理12.2】矩陣博弈G={S1，S2；A}在混合策略意義下有解的充要條件是：存在x*∈S1*，y*∈S2*，使（x*，y*）為函數(shù)E(x,y)的一個鞍點(diǎn)，即對一切x∈S1*，y∈S2*有E（x，y*）≤E（x*，y*）≤E（x*，y）12.4.3混合策略矩陣博弈稱為局中人Ⅰ的贏得函數(shù)，VG稱為G*的值。

【定義12.6′】設(shè)G*={S1*,S2*,E}是矩陣博弈G={S1,S2,A}的混合擴(kuò)充，當(dāng)時，稱為局中人Ⅰ、Ⅱ在混合策略中的納什均衡。64【例12-11】考慮矩陣博弈G={S1，S2；A}，其中試求納什均衡【解】純策略納什均衡不存在。設(shè)x=（x1，x2）為局中人Ⅰ的混合策略，y=(y1，y2)為局中人Ⅱ的混合策略，則：局中人Ⅰ的贏得期望值：12.4.3混合策略矩陣博弈x1x2y1y265該博弈的納什均衡為：(x*,y*)其中局中人Ⅰ和Ⅱ的最優(yōu)策略分別為：x*,y*博弈值

12.4.3混合策略矩陣博弈取，，則6612.4.4納什均衡存在定理【定理12.3】設(shè)x*∈S1*，y*∈S2*,則（x*，y*）為博弈G的納什均衡的條件是：對任意i=1,…，m，j=1,…，n，有E(i,y*)≤E(x*,y*)≤E(x*,j)【定理12.4】設(shè)x*∈S1*，y*∈S2*，則（x*，y*）是博弈G的納什均衡的充要條件是：存在數(shù)V，使得x*，y*分別滿足：且V=VG

67【定理12.5】對任一矩陣博弈G={S1，S2；A}，一定存在混合策略意義下的納什均衡。12.4.4納什均衡存在定理定理12.4-12.6說明了矩陣博弈總是有解的，并給出了解所應(yīng)滿足的條件?！径ɡ?2.6】設(shè)（x*，y*）為矩陣博弈G的一個納什均衡，V=VG，則（1）若xi*＞0，則

（2）若yj*＞0，則

（3）若，則

（4）若，則68例12-1112.4.4納什均衡存在定理6912.4.4納什均衡存在定理【定理12.7】設(shè)有兩個矩陣博弈G1={S1，S2；A},G2={S1，S2；kA}其中k＞0為一常數(shù)。則G1與G2有相同的解，且：【補(bǔ)充定理】

G1={S1，S2；A1=(aij)m×n}G2={S1，S2；A2=(aij+d)m×n}

d為常數(shù)，則G1與G2有相同的解，且：【補(bǔ)充例】求解矩陣博弈701.線性方程組法若最優(yōu)策略中和均不為零時，根據(jù)定理12.6，有

12.4.5矩陣博弈求解方法注意：（1）應(yīng)用此方法的條件是所有策略的概率大于零。（2）對于2×2的矩陣博弈當(dāng)不存在純策略鞍點(diǎn)時，容易證明，各局中人的最優(yōu)策略中xi，yj均大于零，可采用此法求解。71【例12-14】求解矩陣博弈【解】設(shè)x=(x1,x2,x3),y=(y1,y2,y3),xi>0,yj>0,

i,j=1,2,3建立方程組x*=(0.525，0.275，0.2)y*=(0.2，0.05，0.75)該矩陣博弈的納什均衡為（x*,y*）,搏弈值VG=－0.4512.4.5矩陣博弈求解方法722.優(yōu)超原則法（嚴(yán)格下策反復(fù)消去法）

優(yōu)超原則：P311【定義12.7】,【定理12.8】【例12-12】

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

求納什均衡

12.4.5矩陣博弈求解方法73【解】12.4.5矩陣博弈求解方法74該矩陣博弈的納什均衡為：(x*,y*)

VG=4.8

12.4.5矩陣博弈求解方法75

3.圖解法

【補(bǔ)充例1】用圖解法求解

【解】設(shè)x=(x1,1-x1)，y=(y1,1-y1)對于局中人Ⅰ：如果局中Ⅱ人選取β1，則有V=20-15x1

如果局中Ⅱ人選取β2，則有V=25x1+10

12.4.5矩陣博弈求解方法點(diǎn)B(1/4,65/4)為局中人Ⅰ的極值點(diǎn)l1l2CBAox1v176

同理V=35-30y1V=10+10y1解得

12.4.5矩陣博弈求解方法該矩陣博弈的納什均衡為：(x*,y*)

VG=16.25

77

【補(bǔ)充例2】某公司有甲、乙兩個工廠，每年的稅額是400萬元和1200萬元。對于每個工廠，公司可如實(shí)申報稅款，或者篡改賬目，聲稱稅額為零，而稅務(wù)局由于人力所限，每年只能檢查一個工廠的賬目，如果稅務(wù)局發(fā)現(xiàn)工廠偷稅，則不但要工廠如數(shù)繳納稅款，而且還要繳納相當(dāng)于一半稅款的罰金。（1）試將該問題表示為一個矩陣博弈模型；（2）求出稅務(wù)局和公司的最優(yōu)策略及稅務(wù)局從公司征收稅款（含罰金）。12.4.5矩陣博弈求解方法【解】稅務(wù)局：S1={查甲工廠，查乙工廠}公司：S2={甲乙都實(shí)報，甲乙都報零，甲實(shí)報乙報零，甲報零乙實(shí)報}78利用定理12.7及補(bǔ)充定理化簡設(shè)x=(x1,1-x1)y=(y1,y2,y3,y4)V=6(1)

V=-6x1+7(2)V=-9x1+9(3)V=3x1+4(4)點(diǎn)B(1/3,5)為局中人Ⅰ的極值點(diǎn)x1l1l2l4l3CBAov1D497617=579點(diǎn)B(1/3,5)不滿足方程（1）、（3），由定理12.6y1=y3=0解(5)(6)組成的方程組同理可得V=6y1+y2+7y4

(5)V=6y1+7y2+9y3+4y4

(6)該矩陣博弈的納什均衡為：(x*,y*)

稅務(wù)局最優(yōu)策略是以1/3的概率檢查甲公司，2/3的概率檢查乙公司，這樣至少能征收到1400萬元的稅款80【補(bǔ)充例2】用圖解法求解12.4.5矩陣博弈求解方法【解】設(shè)x=(x1,1-x1)y=(y1,y2,y3,y4)則V=4-2x1

(1)

V=2x1+1(2)V=-5x1+6(3)V=5x1

(4)點(diǎn)B(5/7,17/7)為局中人Ⅰ的極值點(diǎn)l1l2l4l3CBAox1v1V=17/78112.4.5矩陣博弈求解方法同理可得V=2y1+3y2+y3+5y4(5)V=4y1+y2+6y3(6)將x1=5/7代人方程（1）—（4）由定理12.6知y1=y4=0,y2>0,y3>0解方程組得該博弈的納什均衡為(x*,y*)

博弈值為VG=17/7823.線性規(guī)劃方法

任意矩陣博弈的求解均等價于一對互為對偶的線性規(guī)劃問題，而定理12.4表明，博弈G的解等價于下面兩個不等式組的解．

12.4.5矩陣博弈求解方法83則局中人Ⅰ、Ⅱ的最優(yōu)策略等價于線性規(guī)劃問題：

12.4.5矩陣博弈求解方法【定理12.9】設(shè)矩陣博弈的值為v，則：

84

令，當(dāng)V>0時，有局中人Ⅰ：12.4.5矩陣博弈求解方法85同理,令有局中人Ⅱ：12.4.5矩陣博弈求解方法8612.4.5矩陣博弈求解方法注意：（1）用線性規(guī)劃法求解的必要條件是V>0。如何判斷V>0，可以證明，當(dāng)aij≥0時，V>0。（2）若某個aij≤0，可對A的各元素加上適當(dāng)?shù)臄?shù)d>0，使所有的aij≥087【例12-12】利用線性規(guī)劃方法求解贏得矩陣為

的矩陣博弈的納什均衡．

【解】此問題可化為兩個互為對偶的線性規(guī)劃問題：12.4.5矩陣博弈求解方法88最優(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.3912.4.5矩陣博弈求解方法89有無純策略解無優(yōu)超原則和定理12.7化簡1.A2×n或Am×2，圖解法。2.A2×2，圖解法，方程組法，代數(shù)法。3.LP法（aij≥0)12.4.5矩陣博弈求解方法解矩陣博弈的一般步驟90下一節(jié)：有限二人非零和博弈

9112.5.1數(shù)學(xué)定義假設(shè)：彼此了解對方的純策略集和贏得函數(shù)，但不合作，并且局中人在選擇自己策略時不知道對方的選擇。數(shù)學(xué)模型：Γ={S1,S2;(A1,A2)},其中S1={α1,α2，…，αm}，S2={β1,β2,…，βn}A1=(aij)m×n,A2=(a′ij)m×n,A1+A2≠0兩人有限非零和博弈也稱為雙矩陣博弈。

記局中人Ⅰ的混合策略為x=(x1,x2,…,xm)，局中人Ⅱ的混合策略為y=(y1,y2,…,ym)，相應(yīng)的策略集分別記為12.5二人有限非零和博弈9212.5.1數(shù)學(xué)定義【補(bǔ)充例1】囚徒的困境（-1，-1）（-10，-1/4）抵賴（-1/4，-10）（-5，-5）坦白抵賴坦白

囚徒2囚徒19312.5.1數(shù)學(xué)定義【例11.16】市場上有兩企業(yè)生產(chǎn)同樣商品，甲企業(yè)與乙企業(yè)的贏得矩陣分別為矩陣A1和A2合并為雙矩陣【例11.16】市場上有兩企業(yè)生產(chǎn)同樣商品，甲企業(yè)與乙企業(yè)的贏得矩陣分別為【例11.16】市場上有兩企業(yè)生產(chǎn)同樣商品，甲企業(yè)與乙企業(yè)的贏得矩陣分別為矩陣A1和A2合并為雙矩陣【例11.16】市場上有兩企業(yè)生產(chǎn)同樣商品，甲企業(yè)與乙企業(yè)的贏得矩陣分別為矩陣A1和A2合并為雙矩陣94【定義12.8】對于某個二人有限非零和博弈，其局中人Ⅰ的贏得（混合策略下）為局中人Ⅱ的贏得為12.5.1數(shù)學(xué)定義9512.5.2二人有限非零和博弈納什均衡【定理12.10】（納什定理）任何矩陣博弈及有限二人非零和博弈至少有一個納什均衡?！径x12.9】在有限二人非零和博弈中,設(shè)分別是局中人Ⅰ和Ⅱ的贏得，為任意策略，如果有一博弈滿足，則稱為該博弈的納什均衡，稱為博弈的贏得值。961.反應(yīng)函數(shù)法12.5.32×2二人有限非零和博弈的求解【例12.17】解雙矩陣博弈【解】（1）局中人1的贏得(期望值)為局中人2的贏得為

（2）對e1,e2分別求偏導(dǎo)數(shù)x*=(1/2,1/2)Y*=(2/5,3/5)博弈值(u*,v*)=(2.4,2.5)972.圖解法12.5.32×2二人有限非零和博弈的求解【例11.17】圖解下列非零和博弈【解】（1）作出坐標(biāo)系圖