運(yùn)籌學(xué)：第十二章 博弈論

第十二章博弈論第一節(jié)博弈論的基本概念 第二節(jié)純策略矩陣博弈第三節(jié)混合策略矩陣博弈第四節(jié)其它類型博弈簡(jiǎn)介博弈論------實(shí)際上就是多人決策！運(yùn)籌學(xué)前面所介紹的優(yōu)化管理方法，基本上是一個(gè)決策主體針對(duì)不同的實(shí)際內(nèi)部條件和外部環(huán)境在做決策！其中內(nèi)部條件的變化及外部環(huán)境的改變都是客觀進(jìn)行的，并非有意識(shí)地針對(duì)決策者！而博弈論是多人決策，決策的一方在選擇自己的方案或策略時(shí)，其他人也在選擇，并且會(huì)想方設(shè)法地讓自己選擇策略所獲得的好處大于對(duì)方獲得的好處！這樣自己做決策時(shí)就必然要猜測(cè)考慮對(duì)方的行為！

第一節(jié)博弈論的基本概念一、博弈現(xiàn)象的三個(gè)基本要素局中人策略支付函數(shù)見如下例子：

我國(guó)古代的“齊王賽馬”就是一個(gè)典型的博弈例子:戰(zhàn)國(guó)時(shí)期，齊國(guó)國(guó)王與大將田忌進(jìn)行賽馬比賽。

雙方約定：從各自的上、中、下三個(gè)等級(jí)的馬匹中各選一匹參加比賽，分三場(chǎng)進(jìn)行；每匹馬只能參加一次；每一場(chǎng)比賽中的負(fù)者付給勝者一千金。已知:田忌的三匹馬都略遜于齊威王相應(yīng)的三匹馬，但其上馬、中馬分別優(yōu)于齊威王的中馬和下馬。田忌的一個(gè)謀士孫臏給田忌出了個(gè)主意：用下馬對(duì)齊王的上馬，中馬對(duì)齊王的下馬，上馬對(duì)齊王的中馬。這樣田忌雖然輸?shù)袅艘粓?chǎng)比賽，但卻贏得了另兩場(chǎng)比賽，結(jié)果是贏得了一千金。1、局中人博弈中的決策者或參與者，用I表示局中人集合，如I={1,2,…,n}表示有n個(gè)局中人。局中人至少要有兩個(gè)，個(gè)人和集體都可以作為局中人，如“齊王賽馬”中的齊王和田忌。參與人的目的是通過選擇行動(dòng)或戰(zhàn)略(策略)以最大化自己的支付(效用)水平。一、博弈現(xiàn)象的三要素2、策略局中人在整個(gè)決策過程中一系列行動(dòng)的一個(gè)方案。如用（上、中、下）表示出場(chǎng)參賽的三匹馬依此為上馬、中馬和下馬，這就是局中人的一個(gè)策略。每個(gè)局中人

i的策略集合記為Si，如田忌和齊王的策略各有6個(gè)可供選擇：上中下（先出上等馬，再出中等馬，最后出下等馬）、上下中、中上下、中下上、下上中、下中上。每個(gè)局中人所出的一個(gè)策略形成的一個(gè)策略組為一個(gè)局勢(shì)。設(shè)si是局中人i的一個(gè)策略，則n個(gè)局中人的策略形成的策略組s=(s1,s2,…,sn)就是一個(gè)局勢(shì)。記S為全部局勢(shì)的集合，即S=S1×S2×…×Sn。3、贏得函數(shù)當(dāng)一個(gè)局勢(shì)s出現(xiàn)后，每個(gè)局中人有一個(gè)贏得值Hi(s)。顯然，Hi(s)是定義在S上的一個(gè)函數(shù)，稱為局中人i的贏得函數(shù)。如“齊王賽馬”中，國(guó)王選擇了上中下，而田忌選擇了下上中，則田忌將贏得這場(chǎng)比賽。田忌為何能贏這場(chǎng)？田忌一直能贏嗎？田忌的贏率是多少？如下為“田忌賽馬”游戲的支付矩陣。

齊王田忌上中下上下中中上下中下上下上中下中上上中下－3－1－11－1－1上下中－1－31－1－1－1中上下－1－1－3－1－11中下上－1－1－1－31－1下上中1－1－1－1－3－1下中上－11－1－1－1－3若雙方同時(shí)選擇策略，田忌的勝率只有1/6！當(dāng)局中人和策略是有限時(shí)，把贏利數(shù)字寫成矩陣形式，叫博弈矩陣的表示，其矩陣叫做博弈的支付矩陣。例如:“錘子、剪刀、布”游戲中，“錘子、剪刀、布”游戲，錘子擊敗剪刀，剪刀勝布，布勝錘子。參與雙方各有三種方案：方案1代表出錘子，方案2代表出剪刀，方案3代表出布。假定勝者得1分，負(fù)者得-1分，兩個(gè)局中人博弈的整個(gè)結(jié)果可用一個(gè)矩陣表示，該矩陣為局中人1的支付矩陣，見表12-1。參與者2參與者1錘子剪刀布錘子01-1剪刀-101布1-10博弈問題中還有一個(gè)很重要的概念:博弈問題的解。

經(jīng)濟(jì)學(xué)習(xí)慣把市場(chǎng)力量對(duì)持的結(jié)局稱為市場(chǎng)均衡。

如供不應(yīng)求將使價(jià)格上升；供大于求將使價(jià)格下降，供求力量對(duì)持的結(jié)果，會(huì)在一個(gè)價(jià)格水平達(dá)到市場(chǎng)供求均衡。

這個(gè)均衡就稱為博弈的解。表12-1二、博弈問題舉例及分類1.博弈問題舉例“囚徒困境”是一個(gè)經(jīng)典的博弈模型:警察抓住兩個(gè)合伙犯罪的犯人，但卻缺乏足夠的證據(jù)指證他們所犯的罪行。如果只要其中一人供任犯罪，就能確認(rèn)罪名成立。為了得到有用的口供，警察將兩人分別關(guān)押以防止他們串供結(jié)成攻守同盟，并給他們選擇的機(jī)會(huì):如果兩人都拒絕認(rèn)罪，則他們將會(huì)被輕判各判1年；如果兩人中有一個(gè)認(rèn)罪，則認(rèn)罪者從輕處理，立即釋放，而另一人則重判8年；如果兩人同時(shí)坦白認(rèn)罪，則他們將各判5年監(jiān)禁。囚徒一囚徒二坦白不坦白坦白不坦白囚徒一的支付矩陣1年5年釋放8年如果分別用-1、-5、-8表示罪犯被判1年、5年和8年的支付，用0表示立即釋放的支付，則囚徒1和囚徒2的支付矩陣分別表示為：囚徒2坦白不坦白囚徒1坦白-50不坦白-8-1囚徒2坦白不坦白囚徒1坦白-5-8不坦白0-1表12-2（b）囚徒2的收益矩陣表12-2(a)囚徒1的收益矩陣囚徒2坦白不坦白囚徒1坦白-5，-50，-8不坦白-8，0-1，-1第1個(gè)數(shù)字表示囚徒1的支付，第2數(shù)字表示囚徒2的支付。這個(gè)支付矩陣也稱為雙支付矩陣。表12-3

－5，－50，－8－8，0－1，－1因?yàn)椤扒敉嚼Ь场蹦Ｐ椭?，囚?的所得不等于囚徒2的所失，所以不是零和博弈，要用下面的雙支付博弈矩陣來表示囚徒1坦白不坦白囚徒2

坦白不坦白兩個(gè)囚徒在選擇自己的策略時(shí)，都是想讓自己效用最大化，但最終作出的選擇卻是對(duì)己對(duì)人都無好處！這就是所謂的囚徒困境！囚徒困境應(yīng)用1：搭便車分析假設(shè)：學(xué)生A和B同處一室，各有財(cái)產(chǎn)300元；夏季對(duì)風(fēng)扇的福利評(píng)價(jià)分別為100元（即風(fēng)扇給各自帶來的效用是100元），風(fēng)扇價(jià)格為160元，合伙買風(fēng)扇的收益為200-160=40元（各享受20）。學(xué)生B

買風(fēng)扇不買風(fēng)扇買風(fēng)扇320，320240，400

學(xué)生A

不買風(fēng)扇400，240300，300

囚徒困境應(yīng)用2：

廣告博弈－－高成本的納什均衡：納什均衡：兩煙草企業(yè)選擇（做廣告，做廣告）做廣告的成本很高，可能要降低原有的利潤(rùn)！煙草企業(yè)1煙草企業(yè)2囚徒困境應(yīng)用3——產(chǎn)品定價(jià)策略：

例、兩個(gè)生產(chǎn)相同產(chǎn)品的企業(yè)A、B，在決定自己產(chǎn)品的價(jià)格時(shí)，有高價(jià)、中價(jià)、低價(jià)三個(gè)策略。如A、B都選擇高價(jià)（中價(jià)、低價(jià)），則AB分別收益6、5、4元；如AB選擇不一致，則定價(jià)高的將會(huì)失去市場(chǎng)，如下表：低價(jià)高價(jià)低價(jià)6，60，100，810，00，88，08，04，4A企業(yè)B企業(yè)高價(jià)中價(jià)中價(jià)5，5求Nash均衡的方法（劃線法）-----推薦方法C1C2C3R1R2R3100，1000，050，10150，01，160，00，3000，0200，200用政策或法律解決“囚徒困境”舉例：治理污染不治理污染治理污染不治理污染10，103，1212，35，5某地有甲乙兩個(gè)企業(yè)，生產(chǎn)中都會(huì)污染環(huán)境，治理污染需要花費(fèi)資金，若大家都治理，環(huán)境好了，對(duì)雙方、對(duì)整個(gè)社會(huì)都有利，但若只有一家治理，花了錢，環(huán)境也不能變好，自己的利潤(rùn)將會(huì)下降。數(shù)據(jù)如上表：甲企業(yè)乙企業(yè)治理污染不治理污染治理污染不治理污染10，103，88，35，5甲企業(yè)乙企業(yè)很顯然上面的博弈甲乙兩個(gè)企業(yè)陷入了囚徒困境，其結(jié)果對(duì)兩企業(yè)自身、對(duì)整個(gè)社會(huì)都沒有好處。設(shè)X＝4>12-10，可表示為政府對(duì)污染企業(yè)的罰款。上表中企業(yè)不治理污染，利潤(rùn)將在12的基礎(chǔ)上減4。存在兩個(gè)納什均衡。通常，若存在多個(gè)納什均衡，理性的決策者都會(huì)選擇對(duì)己對(duì)人都好的那個(gè)均衡！獵手博弈：每個(gè)局中人的策略空間為（獵鹿，獵兔）獵人2

獵鹿獵兔獵鹿5，50，3

獵人1

獵兔3，03，3

在該獵手博弈中，有兩個(gè)Nash均衡（獵鹿，獵鹿），（獵兔，獵兔），到底應(yīng)該出現(xiàn)哪個(gè)呢？（獵鹿，獵鹿）是帕累托優(yōu)勢(shì)均衡，總效用最大!

（獵兔，獵兔）是風(fēng)險(xiǎn)上策均衡，期望效用（得益）最大，無風(fēng)險(xiǎn)！因每個(gè)獵手選擇獵鹿的期望效用為2.5，選擇獵兔的期望效用（實(shí)際效用）為3。

例、考試作弊（官員貪污）博弈9，99，99，90，30，8－10，33，08，03，－102，27，72，2甲作弊（貪污）不作弊（不貪污）乙

作弊（貪污）不作弊（不貪污）最常見2.博弈分類 第二節(jié)純策略矩陣博弈一、純策略意義下的解二、純策略意義下解的存在性一、純策略意義下的解

假設(shè)：1）局中人充分了解相互的得失；2）局中人是理性的；3）局中人間不允許存在任何協(xié)議。用I和II分別表示即兩個(gè)局中人。 局中人I有m個(gè)策略，S1={

1,

2,…,

m}；局中人II有n個(gè)策略，S2={

1,

2,…,

n}。 當(dāng)局中人I選策略

i，局中人II選策略

j，就形成了一個(gè)局勢(shì)(

i,

j)——純局勢(shì)。兩人有限博弈稱為矩陣對(duì)策。兩人：局中人為兩個(gè)，即n=2。有限：每個(gè)局中人的策略有限，即S1和S2為有限集。零和：在任一局勢(shì)下，兩個(gè)局中人的贏得值之和為零，即

H1(s)+H2(s)=0,

s

S非零和：在任一局勢(shì)下，兩個(gè)局中人的贏得值之和不為零，即

H1(s)+H2(s)≠0,

s

S 對(duì)任一局勢(shì)(

i,

j)，用aij記局中人I的贏得值，稱矩陣 為局中人I的贏得矩陣。對(duì)于零和對(duì)策，局中人II的贏得矩陣為-A。

設(shè)G={S1,S2;A}為一個(gè)矩陣對(duì)策，其中S1={

1,

2,…,

n}，S2={

1,

2,…,

n}，A=(aij)m×n。若 則稱該值為對(duì)策G的值，記為VG；使上式成立的純局勢(shì)(

i*,

j*)稱為對(duì)策G在純策略意義下的解；

i*和

j*，分別為局中人I和II的最優(yōu)純策略。例12.1設(shè)局中人1的策略為：；局中人2的策略為：；局中人1的支付矩陣為：求該矩陣博弈的鞍點(diǎn)及最優(yōu)策略。局中人I局中人III的最優(yōu)策略（行）II的最優(yōu)策略（列）如果局中人1選擇策略A1，則他至少可得：

如果局中人2選擇策略B1，則他至多失去：

如果雙方都不想冒險(xiǎn)，則都會(huì)從壞的打算出發(fā)，然后得到最好的結(jié)果?！?/p>

所以，如果局中人1選擇策略Ai，則他至少可以得到支付因此局中人1可以選擇i，使他得到的支付不小于

同理，如果局中人2選擇策略Bj，則他至多失去因此，局中人2可以選擇Bj，使他失去的不大于

二、純策略意義下解的存在性

定理12.1矩陣對(duì)策G={S1,S2;A}在純策略意義下有解的充要條件是：存在純局勢(shì)(

i*,

j*)，使得對(duì)任意i和j，有當(dāng)局中人1偏離策略(

i*,

j*)時(shí)，他的贏得變小，當(dāng)局中人2偏離策略(

i*,

j*)時(shí)，他的付出變大。證明:已知必要條件：已知另一方面：

充分條件：定理12.2.

如果和都是矩陣博弈:的鞍點(diǎn)，則和也是它的鞍點(diǎn)，且在鞍點(diǎn)處的值相等，

第三節(jié)混合策略矩陣博弈一、混合策略意義下的解二、混合策略意義下解的存在性三、均衡解的計(jì)算一、混合策略意義下的解 定義12.2

設(shè)G={S1,S2;A}為一個(gè)矩陣對(duì)策，其中S1={

1,

2,…,

m}，S2={

1,

2,…,

n}，A=(aij)m×n。

記S1*={x

Em|xi

0,i=1,2,…,m;

ixi=1}

S2*={y

En|yj

0,j=1,2,…,n;

jyj=1} 分別稱S1*和S2*為局中人I和II的混合策略集合；x

S1*和y

S2*稱為混合策略，(x,y)稱為混合局勢(shì)。純策略是混合策略的特例。定義12.3

對(duì)任意的x*

S1*和y*

S2*，如果存在x

S1*和y

S2*，使則稱是矩陣博弈混合策略意義下的一個(gè)鞍點(diǎn)（或均衡）。如果存在，使，則混合局勢(shì)稱為該矩陣博弈的最優(yōu)解。和分別稱為局中人1和局中人2的最優(yōu)混合策略。v為該矩陣博弈的均衡值。二、混合策略意義下解的存在性定理12.3

矩陣博弈一定存在混合策略意義下的解。該定理是納什定理的特殊情況，納什定理是說：每一個(gè)有限博弈都至少存在一個(gè)混合策略納什均衡。有關(guān)納什均衡這里不在詳細(xì)討論，請(qǐng)讀者參考有關(guān)書籍。由混合策略意義下均衡的定義21.3，很容易得到如下定理。

定理12.4

設(shè)x*

S1*和y*

S2*，則(x*,y*)為對(duì)策G的解的充要條件是：存在數(shù)v，使得x*和y*分別是下列不等式組的解，且v=VG。定理12.5

設(shè)有兩個(gè)矩陣博弈G={S1,S2;A}和G={S1,S2;A}，其中A=(aij)m×n

，A=(aij+L)m×n，L為任意常數(shù)，則(1)vG

=vG+L；(2)G和G有相同的解集定理12.6

設(shè)有矩陣博弈G={S1,S2；A}和G={S1,S2；A}，其中A=(aij)m×n

，A=(

aij)m×n，

為任意正常數(shù)，則（1）vG=

vG；（2）G和G有相同的解集。三、均衡解的計(jì)算例12.2：設(shè)G={S1,S2;A}為一個(gè)矩陣對(duì)策，其中S1={

1,

2}，S2={

1,

2,

3}， 設(shè)局中人I的混合策略為(x,1-x)T，x

[0,1]。（一）作圖法 橫坐標(biāo)表示局中人I混合策略的x，縱坐標(biāo)表示局中人I的贏得值v。 根據(jù)定理3，對(duì)任意i=1,2,…,m和j=1,2,…,n， 得到

在直線的下方，找最大的v則本題的3條直線分別如下，其圍成的公共區(qū)域見圖12-1到圖12-4:

即x=3/11，v=49/11。111257230x*

1

2

3xI(v)II(v)

局中人I最優(yōu)混合策略(x*,1-x*)T=(3/11,8/11)T，贏得值VG=49/11。根據(jù)定理12.6得到局中人II最優(yōu)混合策略(y1*,y2*,y3*)T=(0,9/11,2/11)T

定義12.4:設(shè)矩陣對(duì)策G={S1;S2;A}，其中S1={α1,…,αm},S2={β1,…,βn}，A=(aij)(——局中人I的支付矩陣），若對(duì)一切j=1,…,n有：

ai0,j≥ak0,j即矩陣A的第i0行元素均不小于第k0行的對(duì)應(yīng)元素，則稱局中人I的純策略αi0優(yōu)超于αk0。同理，若對(duì)一切

i=1,…,m有ai,j0≤ai,k0

則稱局中人II的純策略βj0優(yōu)于βk0。行刪小，列刪大。（二）優(yōu)超法定理12.7:設(shè)矩陣對(duì)策G={S1;S2;A}，其中S1={α1,…,αm},S2={β1,…,βn}，A=(aij)，若純策略α1被其余純策略α2,…,αm中之一所優(yōu)超，由G可得到一個(gè)新的矩陣對(duì)策G={S`1;S`2;A`}，其中S`1={α2,…,αm},S2={β2,…,βn}，A`=(a`ij)，則有：（1）V`G=VG；（2）G`中局中人II的最優(yōu)策略就是G中的最優(yōu)策略（3）若(x2,x3,…,xm)是局中人I的最優(yōu)策略，則x=(0,x2,…,xm)是G的最優(yōu)策略。例12.3：設(shè)贏得矩陣為：求其均衡點(diǎn)例、如下是甲乙兩人的博弈矩陣。

雙方選擇策略的宗旨：從最壞處著眼，尋找最好的結(jié)果！是否所有的二人有限零和博弈矩陣都有鞍點(diǎn)？回答是否定的，見如下的矩陣：局中人A、B各有4個(gè)策略，矩陣中的數(shù)值是A的所得或B的所失。a1a2a3a4b1b2b3b4AB12003487該博弈矩陣沒有鞍點(diǎn)！即沒有純策略解，只能求混合策略解是否所有的二人有限零和博弈矩陣都有鞍點(diǎn)？為了求出混合策略解，需要先化簡(jiǎn)博弈矩陣采用優(yōu)勢(shì)原則（汰劣法或優(yōu)超法）a1a2a3a4b1b2b3b4AB比較矩陣的1，3，4行，發(fā)現(xiàn)c1j≧c3j，c1j≧c4j，因此可以劃去3，4行(a3,a4是A的劣勢(shì)策略）同理，可以劃去3，4列（b3，b4是B的劣勢(shì)策略）

原來的博弈矩陣就簡(jiǎn)化為2×2博弈矩陣，而對(duì)于這樣的矩陣，有多種方法可以求出其混合策略解（反應(yīng)函數(shù)法，線性規(guī)劃法，綜合求解法）下面介紹一種綜合求解法：a1a2b1b2X—局中人A采用a1的概率1－x—A采用a2的概率y1－y—B采用b2的概率B采用b1的概率令E（x，y）表示局中人A的期望贏得值

解得x＝1/4，y=1/2，A的贏得值（均衡值）為5/2（三）反應(yīng)函數(shù)法例12.4．局中人1、2玩撲克牌游戲，如果同時(shí)出紅色或黑色，則局中人1得-1分，局中人2得1分；如果同時(shí)出的顏色不同，則則局中人1得1分，局中人2得-1分?，F(xiàn)在設(shè)局中人1的混合策略是以的概率出紅牌和以的概率出黑牌；局中人2的混合策略是以的概率出紅牌和以的概率出黑牌。支付矩陣如下：計(jì)算在局中人1、2的混合策略分別是和時(shí)的最優(yōu)混合策略和期望支付是多少。紅黑紅黑局中人2局中人1-1，11，-1

1，-1-1，1局中人1的期望支付為：因?yàn)椋种腥?只能選擇p不能選擇q，所以當(dāng)時(shí)，局中人1把p選的越大越好，即:p=1當(dāng)時(shí)，局中人1把p選的越小越好，即:p=0當(dāng)時(shí)，局中人1可任意選擇p。所以，如果局中人2的混合策略是（q,1-q），局中人1的最佳反應(yīng)函數(shù)是：同理，局中人2的期望支付為：局中人2的最佳反應(yīng)函數(shù)是：以p為縱軸、以q為橫軸，把局中人1、2的反應(yīng)函數(shù)畫在Opq直角坐標(biāo)系中，兩個(gè)反應(yīng)函數(shù)交點(diǎn)，就得到混合策略的鞍點(diǎn)。所以，。故局中人１和局中人２的最優(yōu)混合策略均為：；在處的期望支付為：。（四）線性規(guī)劃法首先，選取一個(gè)適當(dāng)?shù)某?shù)c加到支付矩陣A的每個(gè)元素上，使得到的新矩陣的所有元素都是正數(shù)，即然后，轉(zhuǎn)化為線性規(guī)劃問題，即求解下列規(guī)劃：設(shè)最優(yōu)解是最優(yōu)函數(shù)值是。則局中人１最優(yōu)混合策略均衡值是

同理，求下列線性規(guī)劃：設(shè)最優(yōu)解是最優(yōu)函數(shù)值是局中人２的最優(yōu)混合策略均衡值是例12.5．用線性規(guī)劃法計(jì)算例12.4。

解：最優(yōu)混合策略是

求其對(duì)偶問題的解得局中人2的最優(yōu)策略：首先，取，則：

變?yōu)榈谒墓?jié)其它類型博弈簡(jiǎn)介一、多人非合作博弈二、非零和博弈一、多人非合作博弈定理12.8：每一個(gè)n人非合作博弈必存在納什均衡點(diǎn)。例12.6．求“囚徒困境”博弈模型(見表12-5)的Nash均衡。

解：由表12-5可得均衡點(diǎn)。其結(jié)果見表