運籌學(xué)思想方法及應(yīng)用 ch5 博弈論的思想方法及其應(yīng)用

第五章博弈論的思想方法及其應(yīng)用

運籌學(xué)OperationalResearch要想在現(xiàn)代社會做一個有文化的人，你必須對博弈論有一個大致了解.——諾貝爾經(jīng)濟學(xué)獎獲得者

PaulSamuelson博弈論（TheGamesTheory)是運籌學(xué)學(xué)科的一個重要分支。具有競爭或?qū)剐再|(zhì)的行為稱為博弈行為，在這類行為中，參與斗爭或競爭的各方各自具有不同的目標和利益，為了達到各自的目的，各方必須考慮對手的各種可能的行動方案，并力圖選取對自己最為有利或最合理的方案。博弈論就是研究博弈行為中，斗爭各方是否存在最合理的行動方案，以及如何找到這個合理方案的理論和方法。5.1博弈論的基本概念5.2矩陣博弈的純策略5.3矩陣博弈的混合策略5.4矩陣博弈求解方法5.5納什均衡5.6合作博弈與效益分配5.7動態(tài)博弈與承諾行動5.8應(yīng)用舉例附錄博弈論與諾貝爾經(jīng)濟學(xué)獎5.1博弈論的基本概念5.1博弈論的基本概念1944年，數(shù)學(xué)家馮·諾伊曼(J.von-Neumann)和經(jīng)濟學(xué)家摩根施特恩（O.Morgenstern）寫成了《博弈論與經(jīng)濟行為》一書，這是博弈論這一分支的經(jīng)典之作.該書不僅建立了博弈論的嚴格的公理化體系，而且對大量的經(jīng)濟活動進行了深入的分析，奠定了博弈論的基礎(chǔ).

5.1博弈論的基本概念5.1博弈論的基本概念5.1博弈論的基本概念博弈論是矛盾和合作的規(guī)范研究，是系統(tǒng)研究決策主體的行為發(fā)生直接相互作用情況下的決策以及這種決策均衡的理論.也就是說，當一個決策主體的選擇受到其他決策主體選擇的影響，并且它的決策也影響其他決策主體的決策時的合理選擇問題.博弈論思想的主要特征是各參與人所實施的行為方案（策略）相互依存，各方在沖突或合作后所實現(xiàn)的得失結(jié)果不僅取決于自己所采用的行為方案，同時也依賴于其他參與人所采用的行為方案，它是各參與人行為方案組合的函數(shù).在現(xiàn)實生活中，經(jīng)?？梢钥吹揭恍┚哂袑购透偁幮缘默F(xiàn)象，如體育比賽、軍事斗爭中雙方兵力的對抗，各公司企業(yè)之間的經(jīng)濟談判以及為爭奪市場而進行的競爭等等。在競爭過程中，各方為了達到自己的目標和利益，必須考慮對手的各種可能的行動方案，并力圖選取對自己最為有利或最為合理的方案，也就是說要研究采取對抗其他競爭者的策略。從數(shù)學(xué)角度來說，博弈論就是研究競爭行為中的競爭各方是否存在著最合理的行動方案，以及如何找到這個合理的行動方案的數(shù)學(xué)理論和方法。5.1博弈論的基本概念博弈論認為：人是理性的，即人人都會在約束條件下最大化自身的利益；人們在交往合作中有沖突，行為互相影響，而且信息不對稱.5.1博弈論的基本概念5.1博弈論的基本概念囚徒困境問題甲和乙兩個小偷聯(lián)手作案，因私入民宅被警方抓住但未獲證據(jù)。警方將兩人分別置于兩間房間分開審訊，政策是若一人招供但另一人未招，則招者立即被釋放，未招者判入獄10年；若二人都招，則兩人各判刑8年；若兩人都不招，則未獲證據(jù)但因私入民宅各拘留1年。將這些數(shù)據(jù)列出，如下：

5.1博弈論的基本概念囚徒困境博弈盡管甲不知道乙是否招供，但他認為自己選“招”最好，因而甲會選擇“招”，乙也同樣會選擇“招”，結(jié)果各判8年；但若兩人都不招，結(jié)果是每人只被判1年，但在“人是理性的，即人人都會在約束條件下最大化自身的利益”的基本假設(shè)下，這種結(jié)果是不會出現(xiàn)的.5.1博弈論的基本概念甲和乙是參與博弈的人，稱為“局中人”.表中每一個小方格內(nèi)的數(shù)字被稱為局中人的支付，其中左邊的數(shù)字代表甲的支付，右邊的是乙的支付.表中的雙變量矩陣稱為博弈支付矩陣.局中人所選擇的戰(zhàn)略構(gòu)成的組合（招,招）被稱為博弈均衡.這個組合中前后兩個戰(zhàn)略分別表示甲和乙所選擇的戰(zhàn)略.5.1博弈論的基本概念如果甲和乙在決策時拋掉謹慎，加入一定的“瘋狂”，不約而同地采取“不招”的策略，其結(jié)果是每人只被判1年.顯然，這對甲、乙二人來說，比他們采取理性策略的結(jié)果“好”.

5.1博弈論的基本概念5.1博弈論的基本概念商家價格戰(zhàn)

出售同類產(chǎn)品的商家之間本來可以通過共同將價格維持在高位而獲利，但實際上卻是相互殺價，結(jié)果都賺不到錢.當一些商家共謀將價格抬高，消費者實際上不用著急，因為商家聯(lián)合維持高價的壟斷行為一般不會持久，可以等待壟斷的自身崩潰，價格就會掉下來.5.1博弈論的基本概念博弈論有三個基本假設(shè)：參與人是理性的；他們有這些理性的共同知識；他們知道博弈規(guī)則.任何一個博弈問題都包含如下三個要素：局中人、策略和支付函數(shù).5.1博弈論的基本概念（1）局中人(Players)在一場具有競爭性的決策中，有制定對付對手的行動與方案權(quán)，并有權(quán)作出決策的參加者稱為局中人，如囚徒困境問題中的甲和乙.局中人可理解為那些利益完全一致的集體或集團，局中人是有理智、聰明的，并有行動決定權(quán)的.我們稱只有兩個局中人的博弈現(xiàn)象為兩人博弈;而多于兩個局中人的博弈稱為多人博弈.在多人博弈中，局中人之間允許合作的稱為結(jié)盟博弈，不允許合作的稱為不結(jié)盟博弈.

5.1博弈論的基本概念（2）策略(Strategies)在一局博弈中，每個局中人都有一套可供選擇的指導(dǎo)自始至終如何行動的方案，以求爭取較好的結(jié)果，我們稱此行動方案為這個局中人的一個策略，而把這個局中人的策略全體稱為這個局中人的策略集.在一局博弈中，各個局中人選定的策略構(gòu)成的一個策略組，稱之為一個局勢.如果在一局博弈中，各個局中人只有有限的策略，我們稱之為有限博弈；否則稱為無限博弈.5.1博弈論的基本概念（3）支付函數(shù)(PayoffFunction)在一局博弈結(jié)束后，對每個局中人來說，其結(jié)果不外乎是贏（得）或輸（失）.顯然，這種輸贏局勢是隨局中人所選取的策略組的變化而變化的，局中人選定一個策略組，必然對應(yīng)著一個博弈結(jié)果.因此，我們可以用一個函數(shù)來表示輸贏（或得失）.將這個函數(shù)稱之為支付函數(shù).對應(yīng)所有策略組的支付函數(shù)的各個取值可以用一個矩陣來表示，稱之為支付矩陣.5.1博弈論的基本概念對于一個博弈問題，如果在每一個局勢中，全體局中人的得失相加都是零，則稱此博弈為零和博弈，否則稱為非零和博弈.5.1博弈論的基本概念博弈中有關(guān)局中人的策略集、支付函數(shù)等構(gòu)成了博弈的信息.按照局中人對信息掌握的情況，可分為完全信息博弈和不完全信息博弈。按照局中人采取行動的次序，當局中人同時采取行動或在互相保密情況下采取行動，稱這種情況為靜態(tài)博弈.如果局中人采取行動有先后，后采取行動的人可以觀察到前面人采取的行動，則屬于動態(tài)博弈。按照局中人是否結(jié)盟情況，還可以將博弈分為結(jié)盟博弈與不結(jié)盟博弈.5.1博弈論的基本概念5.1博弈論的基本概念二人有限零和博弈

在眾多博弈模型中，占有重要地位的是二人有限零和博弈，即在博弈只有兩個局中人，各自的策略集只含有限個策略，每局中兩個局中人的得失總和為零（即一個局中人的贏得恰為另一個局中人所輸?shù)舻闹担@類博弈又稱為矩陣博弈.5.1博弈論的基本概念5.1博弈論的基本概念【例5.1】田忌賽馬戰(zhàn)國時期（自公元前475周元王元年起，至公元前221年秦始皇吞并六國建立中國第一個統(tǒng)一的多民族的中央集權(quán)的封建國家為止，是我國歷史上的戰(zhàn)國時期）齊王與田忌賽馬.雙方約定：每人從自己的上、中、下三個等級的馬中，各選出一匹馬參賽，每一場比賽各出一匹馬，一共比三場，每匹馬只能參加一場比賽，每場比賽后輸者要付給贏者一千金.就同級的馬而言，齊王的馬都比田忌的馬強.解

在本問題中局中人為齊王和田忌。以馬出場的順序而言，齊王有六種博弈策略.例如先用上等馬，再用中等馬，最后下等馬，以（上、中、下）表示之.同樣，田忌也有六種博弈策略，即兩位局中人的策略集都含有六個策略.

可以用表5.2表示齊王的支付.5.1博弈論的基本概念5.1博弈論的基本概念表5.25.1博弈論的基本概念將表5.2中的數(shù)字表成矩陣稱為齊王的贏得矩陣.

這個博弈問題是一個二人有限零和博弈問題.形勢顯然對田忌不利.但是田忌的謀士孫臏建議，每場比賽前要齊王報他要出哪匹馬.孫臏讓田忌的下等馬對齊王的上等馬，用中等馬對齊王的下等馬，用上等馬對齊王的中等馬.結(jié)果反而贏了齊王一千金，這是一個典型的博弈問題.它表明在博弈問題中，局中人必須運用智慧，保守自己的秘密并設(shè)法獲得對方的情報，采取恰當?shù)牟呗苑侥苋〉幂^好的結(jié)果.5.1博弈論的基本概念本節(jié)知識要點

1.博弈論研究的問題

2.博弈論思想的主要特征

3.博弈論的基本概念

4.博弈論有三個基本假設(shè)

5.博弈論的分類

5.1博弈論的基本概念5.2矩陣博弈的純策略局中人Ⅰ從

中選一個策略

，同時局中人Ⅱ從

中選一個策略

，這樣就構(gòu)成一個局勢

對應(yīng)于策略集

和，一共有

個局勢.在局勢

下局中人Ⅰ的贏得記為，則局中人Ⅰ在m個策略下的贏得構(gòu)成一個矩陣.5.2矩陣博弈的純策略用Ⅰ，Ⅱ分別表示兩個局中人，設(shè)局中人Ⅰ有m個策略；局中人Ⅱ有n個策略；其策略集分別表示為，5.2矩陣博弈的純策略稱為局中人Ⅰ的贏得矩陣.

由于對策是零和的，

表示在同一局勢下局中人Ⅱ的贏得，故局中人Ⅱ的贏得矩陣為記這個博弈為

矩陣博弈的數(shù)學(xué)模型為：，其中5.2矩陣博弈的純策略5.2矩陣博弈的純策略在矩陣博弈中要討論的問題是：各局中人應(yīng)該如何選擇自己的策略，使自己在博弈中獲得最好的結(jié)果.下面用一個例子說明.5.2矩陣博弈的純策略【例5.2】設(shè)矩陣博弈局中人Ⅰ，Ⅱ應(yīng)如何選擇自己的策略，以保證自己在博弈中取得有利的地位？解:

對局中人Ⅰ而言，他的最大的收益是8，他理所當然地會選擇策略，同時，他希望局中人Ⅱ選擇策略。但是局中人Ⅱ發(fā)現(xiàn)，如果局中人Ⅰ采取策略，他不會愚蠢地選擇以致失去8。反之，他會選擇，這樣他僅失去1。然而，當局中人Ⅱ選擇時，局中人Ⅰ就會選擇，這樣做比選擇有利，可使收益由1增加到3。這時，局中人Ⅰ、Ⅱ都不愿再改變選擇，因為如果局中人Ⅱ改變選擇，失去的不是3，而是5或4，如果局中人Ⅰ改變選擇，其得到的不是3，而是1或2。顯然，這種狀態(tài)是一種平衡狀態(tài)。5.2矩陣博弈的純策略對應(yīng)于策略，局中人Ⅰ的贏得由5降到3，然后又由3升到4；對應(yīng)于策略，局中人Ⅰ的支付由1上升到3，然后又由3下降到2.中間這個數(shù)3，從第二行看來它形成一個凹槽，從第二列看它形成一個凸脊，正像一個馬鞍形，點3處于馬鞍的中心.5.2矩陣博弈的純策略上面解題的數(shù)學(xué)方法為：對局中人Ⅰ來講，先對矩陣A的每行元素取最小值：再從這些最小值中取最大值：。也就是說，局中人Ⅰ采取悲觀主義原則，從最壞的情況中，取得的最好結(jié)果是3，這時，他應(yīng)采取的策略是，不論局中人Ⅱ采取什么策略，都可以保證贏得不會少于3.5.2矩陣博弈的純策略5.2矩陣博弈的純策略注意到矩陣A中的元素反號后是局中人Ⅱ的贏得，故局中人Ⅱ采取悲觀主義原則時，應(yīng)先對矩陣A的每一列元素中取出最大值：再從這些最大值中取最小值：。因此，局中人Ⅱ應(yīng)采取策略，則不論局中人Ⅰ采取什么策略，最大損失不會大于3。5.2矩陣博弈的純策略因此，局中人Ⅰ、Ⅱ只有分別采取、時才是他們的最優(yōu)策略。為了與后面的概念相區(qū)別，我們稱、分別為局中人Ⅰ、Ⅱ的最優(yōu)純策略，而局勢稱為博弈的解，或博弈的納什均衡。5.2矩陣博弈的純策略一般地，對最優(yōu)純策略及純策略意義下的納什均衡有如下定義：考慮矩陣博弈如果成立等式則分別稱為局中人Ⅰ、Ⅱ的最優(yōu)純策略，對應(yīng)的策略組合即局勢稱為矩陣博弈在純策略意義下的納什均衡。數(shù)值稱為矩陣博弈的值?！纠?.3】

設(shè)矩陣博弈，其中5.2矩陣博弈的純策略求解納什均衡與博弈的值。解對局中人Ⅰ，先對矩陣A的每行求最小值，得到，再求其最大值得到3，即對局中人Ⅱ，先對矩陣A的每行求最大值，得到，再求其最大值得到3，即從而所以，該博弈的納什均衡為，博弈的值.可以看出：滿足不等式

將這個結(jié)論推廣，我們給出如下定理：5.2矩陣博弈的純策略5.2矩陣博弈的純策略

矩陣博弈在純策略意義下有納什均衡的充分必要條件是：存在策略，使得或，定理5.15.2矩陣博弈的純策略設(shè)矩陣博弈，其中

求解納什均衡與博弈的值.【例5.4】解對局中人Ⅰ，先對矩陣A的每行求最小值，得到，再求其最大值得到5，即.

對局中人Ⅱ，先對矩陣A的每列求最大值，得到，再求其最小值得到5，即從而

所以，局勢都是博弈的納什均衡，博弈值。5.2矩陣博弈的純策略本節(jié)知識要點

1.矩陣博弈的數(shù)學(xué)模型

2.博弈的納什均衡

3.矩陣博弈在純策略意義下有納什均衡的充分必要條件5.3矩陣博弈的混合策略

5.3矩陣博弈的混合策略上節(jié)討論了在純策略意義下有納什均衡的矩陣博弈問題。但是，并非所有的矩陣博弈在純策略意義下都有納什均衡。例如本章的齊王賽馬的博弈在純策略下沒有納什均衡。因為所以在齊王賽馬的博弈中，雙方都沒有最優(yōu)純策略，從而在純策略意義下就沒有納什均衡。5.3矩陣博弈的混合策略【例5.5】

設(shè)矩陣博弈，其中解

故此博弈不存在鞍點，從而雙方都沒有最優(yōu)純策略。5.3矩陣博弈的混合策略此時，我們可以設(shè)想局中人隨機地取純策略來進行博弈。例如，局中人Ⅰ以概率選取純策略，以概率選取純策略；局中人Ⅱ以概率選取純策略，以概率選取純策略。于是，對局中人Ⅰ來說，他的贏得可用期望值來描述：5.3矩陣博弈的混合策略由上式可以看出，當時，即局中人Ⅰ以概率選取純策略時，其期望值至少是4，但不能保證期望值超過4，這是因為局中人Ⅱ取時，即以概率選取純策略時，可以控制局中人Ⅰ的贏得不會超過4.

5.3矩陣博弈的混合策略從上述分析可以看出，每個局中人決策時，不是決定用哪一個純策略，而是決定用多大概率選擇每一個純策略。

一般地，設(shè)矩陣博弈，其中5.3矩陣博弈的混合策略則將純策略集合對應(yīng)的概率向量分別稱為局中人Ⅰ與Ⅱ的混合策略，這里是局中人Ⅰ選取的概率，是局中人Ⅱ選取的概率，顯然，純策略可以看成是混合策略的一種特殊情況。又稱數(shù)學(xué)期望為局中人Ⅰ的贏得，為局中人Ⅱ的贏得，而稱為混合局勢。5.3矩陣博弈的混合策略對給定博弈，稱為博弈的混合擴充，其中為局中人Ⅰ的所有混合策略集；為局中人Ⅱ的所有混合策略集。5.3矩陣博弈的混合策略在混合擴充博弈中，局中人Ⅰ選取某種混合策略時，必定要想到局中人Ⅱ會針對性選取一種策略，使其期望贏得最小，于是局中人Ⅰ的目標就是尋求一種以概率選取的策略，使局中人Ⅱ不論采取何種策略時，都能使自己的期望贏得中最小的盡可能大，即局中人Ⅰ想找到一個最大的數(shù)，使其在以概率選取策略時，對局中人Ⅱ的每種策略都有(5.1)

我們稱為局中人Ⅰ的最優(yōu)混合策略，簡稱最優(yōu)策略。5.3矩陣博弈的混合策略同理，局中人Ⅱ也想以概率尋找最優(yōu)策略，使局中人Ⅰ不論采取何種策略時，都能使自己的期望損失中最大的盡可能小，即局中人Ⅱ想找到一個最小的數(shù)，使其在以概率選取策略時，對局中人Ⅰ的每種策略都有（5.2）

我們稱為局中人Ⅱ的最優(yōu)策略.5.3矩陣博弈的混合策略可以證明，在任何一個給定的二人零和博弈中，對局中人Ⅰ和Ⅱ分別存在最優(yōu)策略和，以及和，使得式（5.1）和（5.2）成立，且，我們稱為博弈的值，而混合局勢稱為在混合策略意義下的一個納什均衡。5.3矩陣博弈的混合策略定理5.2

設(shè)，則為的納什均衡的充要條件是：存在數(shù)，使得是線性不等式組

的解，是線性不等式組5.3矩陣博弈的混合策略定理5.2表明，局中人Ⅰ的期望贏得至少為，局中人Ⅱ的期望損失至多為，且；如果局中人Ⅰ選用其最優(yōu)策略，但局中人Ⅱ未選用其最優(yōu)策略，則局中人Ⅰ的期望贏得將高于；同樣，如果局中人Ⅱ選用其最優(yōu)策略而局中人Ⅰ未選用其最優(yōu)策略，則局中人Ⅱ的期望損失會低于.當局中人都采用其最優(yōu)策略時，則可以達到某種程度的平衡，即混合策略意義下的納什均衡.5.3矩陣博弈的混合策略定理5.3

任何一個給定的二人零和博弈一定存在混合策略下的納什均衡。定理5.4

設(shè)為二人零和博弈在混合策略下的一個納什均衡，，則（1）若，則；（2）若，則；（3）若，則；（4）若，則。本節(jié)知識要點

1.矩陣博弈的混合擴充

2.混合策略意義下的納什均衡

3.定理5.2---定理5.45.4矩陣博弈求解方法

5.4矩陣博弈求解方法1.代數(shù)解法【例5.6】求例5.1中齊王與田忌各自的最優(yōu)混合策略及博弈的值。解齊王的贏得矩陣

5.4矩陣博弈求解方法由于它沒有鞍點，不存在純策略解，由定理5.2可得到兩組不等式：（5.3）

（5.4）

5.4矩陣博弈求解方法這里，每個均大于零，換言之，每個純策略都可能被局中人選取。由定理5.3與定理5.4知，式（5.4）和（5.3）都應(yīng)當取等號，將不等式組求解轉(zhuǎn)化成線性方程組求解。將所有式子相加，便得：

由及其故得。代入其他各式解得5.4矩陣博弈求解方法齊王的最優(yōu)策略是；田忌的最優(yōu)策略是。博弈值。即比賽的雙方都很聰明，有理智，總的結(jié)果是齊王贏一千金。5.4矩陣博弈求解方法2.圖解法

用平面直角坐標圖解的方法來求出雙方的最優(yōu)策略。【例5.7】

用圖解法求解例5.5的博弈問題。解支付矩陣先考慮局中人Ⅰ：如果局中人Ⅱ取純策略，則局中人Ⅰ贏得的期望值為如果局中人Ⅱ取純策略，則局中人Ⅰ贏得的期望值為

5.4矩陣博弈求解方法現(xiàn)以策略和所取概率值和為橫坐標，贏得為縱坐標，分別畫出局中人Ⅱ取策略和時，局中人Ⅰ所能獲得的贏得的變動直線l1和l2。如圖5.4矩陣博弈求解方法這里注意到顯然，只有以直線l1和l2的交點M處相應(yīng)的概率值分別取策略和，才是局中人Ⅰ所選取的最優(yōu)混合策略，這時，局中人Ⅰ的贏得總是，而不論局中人Ⅱ選擇何種混合策略，由圖知所以局中人Ⅰ的最優(yōu)混合策略為顯然，只有以直線l1和l2的交點M處相應(yīng)的概率值分別取策略和，才是局中人Ⅰ所選取的最優(yōu)混合策略，這時，局中人Ⅰ的贏得總是，而不論局中人Ⅱ選擇何種混合策略，由圖知

所以局中人Ⅰ的最優(yōu)混合策略為當局中人Ⅰ取策略時，局中人Ⅱ損失的期望值為：用同樣的方法作圖，得局中人Ⅱ的最優(yōu)混合策略，博弈值。5.4矩陣博弈求解方法同理，考慮局中人取最優(yōu)策略的情況，當局中人Ⅰ取策略時，局中人Ⅱ損失的期望值為：5.4矩陣博弈求解方法【例5.8】設(shè)給定一個矩陣博弈，其中

求其最優(yōu)策略及博弈值。解

我們注意到矩陣的第2列各數(shù)大于第1列對應(yīng)各數(shù)，也就是無論局中人Ⅰ選取什么策略，局中人Ⅱ選取策略的損失都比選取策略的損失要大，故局中人Ⅱ絕不會去選取策略，他可以把從策略集中刪去，并把第2列從中刪去，即局中人Ⅱ只要用到策略，，，所以只要考慮下列矩陣就可以了。3.優(yōu)超法5.4矩陣博弈求解方法解

我們注意到矩陣的第2列各數(shù)大于第1列對應(yīng)各數(shù)，也就是無論局中人Ⅰ選取什么策略，局中人Ⅱ選取策略的損失都比選取策略的損失要大，故局中人Ⅱ絕不會去選取策略，他可以把從策略集中刪去，并把第2列從中刪去，即局中人Ⅱ只要用到策略，，，所以只要考慮下列矩陣就可以了。

此時再抹去中第3列得5.4矩陣博弈求解方法從局中人Ⅰ看來，中第2行各元素比第3行對應(yīng)各元素大，也就是無論局中人Ⅱ選取什么策略，局中人Ⅰ選取策略比選取策略有利，這樣，局中人Ⅰ刪去策略，同樣可刪去策略，得5.4矩陣博弈求解方法利用上例結(jié)果可得

局中人Ⅰ的最優(yōu)混合策略；局中人Ⅱ的最優(yōu)混合策略。以上降低支付矩陣維數(shù)的方法稱為優(yōu)超法。5.4矩陣博弈求解方法優(yōu)超法一般描述如下：在支付矩陣中，如果第i行元素都不小于第k行對應(yīng)各元素，即，，則稱局中人Ⅰ的策略優(yōu)超于策略，記為。這時局中人Ⅱ無論選取哪種策略，局中人Ⅰ選取總比選取好。那么可將第k行元素從支付矩陣中抹去，即將策略從策略集中刪去；如果中的第j列各元素都不大于第k列對應(yīng)的各元素，即，，則稱局中人Ⅱ的策略優(yōu)超于策略，記為。這時，局中人Ⅰ無論選取哪一種策略，局中人Ⅱ選取總比選取好。那么，可將第k列從中抹去，即將策略從策略集中刪去。5.4矩陣博弈求解方法定理5.5

設(shè)矩陣博弈，其中，，。如果被其余純策略中之一所優(yōu)超，由可以得到一個新矩陣博弈，其中，則有（1）；（2）中局中人Ⅱ的最優(yōu)策略就是中局中人Ⅱ的最優(yōu)策略；（3）如果是中局中人Ⅰ的最優(yōu)策略，則就是中局中人Ⅰ的最優(yōu)策略。5.4矩陣博弈求解方法4.線性規(guī)劃解法從定理5.2的表示形式可以看出，求解矩陣博弈混合策略意義下的納什均衡問題可以用線性規(guī)劃方法求解。因為求相當于解

（5.5）及（5.6）5.4矩陣博弈求解方法不妨設(shè)，引入新變量（5.5）化為線性規(guī)劃（5.6）化為線性規(guī)劃（5.7）（5.8）這兩個線性規(guī)劃的最優(yōu)解都存在，而且最優(yōu)值相等。5.4矩陣博弈求解方法【例5.9】設(shè)給定一個矩陣博弈，其中求其最優(yōu)策略及博弈值。解

此博弈既無鞍點，又不能用優(yōu)超法簡化，可用線性規(guī)劃求解。求解的線性不等式組為5.4矩陣博弈求解方法及5.4矩陣博弈求解方法故局中人Ⅰ的最優(yōu)混合策略為所以局中人Ⅱ的最優(yōu)混合策略為解得

同理，解得

本節(jié)知識要點

主要介紹矩陣博弈求解方法：

1.代數(shù)解法

2.圖解法

3.優(yōu)超法

4.線性規(guī)劃方法5.4矩陣博弈求解方法5.5納什均衡

5.5納什均衡在二人零和博弈中，雙方局中人尋求的最優(yōu)解是一種納什均衡。當達到這種均衡時，無論是純策略解還是混合策略解，只要其他局中人不改變自己的策略，則任何一方單獨改變自己的策略，只能帶來收益或效用的減少。納什均衡是一種策略組合，它是每個局中人的策略對其他局中人策略的最優(yōu)反應(yīng)。下面先給出個局中人博弈的標準式，然后給出相應(yīng)的納什均衡的定義。5.5納什均衡1.博弈的標準式在有n個局中人的博弈中，設(shè)第i個局中人的策略集為.用表示每個局中人選定某一個策略時形成的局勢.這里是相應(yīng)于該局勢的第i個局中人的支付函數(shù)，則稱為博弈的標準式.設(shè)有，如果對其他局中人所有可能策略組成的局勢均有不等式成立，則稱是對的嚴格劣戰(zhàn)略.5.5納什均衡2.納什均衡定義在有n個局中人的標準式博弈中，如果局勢滿足：對每一個局中人是至少不劣于他針對其他n-1個局中人所選策略的最優(yōu)反應(yīng)策略，則稱局勢是該博弈的一個納什均衡。即對任意的，有

或是最優(yōu)化問題

的解.

5.5納什均衡納什均衡是博弈論中最重要的概念。納什證明了在任何非合作的有限博弈（指局中人個數(shù)有限、每個局中人的策略集中的策略個數(shù)有限）中，都存在至少一個納什均衡。5.5納什均衡【例5.10】設(shè)有二人博弈，各自的策略和支付值如表所示。表中的每個數(shù)對表示局中人采用策略，局中人采用策略時，局中人的支付為，局中人的支付為。求其納什均衡解。5.5納什均衡解先判別是否存在劣策略，若有將其刪除。判別方法：比較A的第i個和第l個策略,如果有,而且其中至少有一個取“>”號，則稱l為劣策略；比較B的第j個和第k個策略，如果有,其中至少有一個取“>”號，則稱第k個策略為劣策略.5.5納什均衡在本例中，是劣策略，將其刪除得到

5.5納什均衡由于納什均衡是每個局中人策略對其他局中人策略的最優(yōu)反應(yīng)，對局中人A：當局中人B采用策略時，局中人A的最優(yōu)反應(yīng)是采取策略，支付為5，在5下面劃橫線；當局中人B采用策略時，局中人A的最優(yōu)反應(yīng)是采取策略支付為6，在6下面劃橫線；當局中人B采用策略時，局中人A的最優(yōu)反應(yīng)時采取策略.支付為4，在4下面劃橫線。5.5納什均衡對局中人B：當局中人A采用策略時，局中人B的最優(yōu)反應(yīng)是采取策略，支付為6，在6下面劃橫線；當局中人A采用策略時，局中人B的最優(yōu)反應(yīng)是采取策略，支付為6，在6下面劃橫線.對支付值都劃有橫線的組合，即為所求的納什均衡解.這種解法簡稱為劃線法.由上表可知，本例的納什均衡解為(4,6)，其對應(yīng)的策略組合為.該局勢是一種平衡局勢.5.5納什均衡【例5.11】以弱敵強博弈在戰(zhàn)爭史上，不乏以弱勝強的例子。例如在二戰(zhàn)中的諾曼底登陸戰(zhàn)的謀略策劃中，盟軍就面臨以弱敵強的問題。盟軍有兩個可以選擇的登陸目標地，一是多佛，二是諾曼底。德國守軍在人數(shù)上超過了盟軍，并且就軍事進攻而言，在人數(shù)相同的情況下，攻方與守方相比會處于不利的情形。下面，將這種情形模型化。假設(shè)有一支軍隊準備進攻一座城市，它有軍力兩個師；守城軍隊有三個師。通往城市有甲、乙兩條道路或方向。兩軍相遇時，人數(shù)居多的一方取勝，當兩方人數(shù)相等時，守方獲勝。并假定軍隊只能整師調(diào)動。5.5納什均衡攻方戰(zhàn)略：

a.兩個師集中沿甲方向進攻；

b.兵分兩路，一個師沿甲方向進攻，另一個師沿乙方向進攻；

c.兩個師集中沿乙方向進攻。守方戰(zhàn)略：

A.三個師集中守甲方向；

B.兩個師守甲方向，一個師守乙方向；

C.一個師守甲方向，兩個師守乙方向；

D.三個師集中守乙方向。5.5納什均衡用“+”、“－”，分別表示勝和敗，攻、守雙方布陣結(jié)果見下表

5.5納什均衡分析：進攻方無劣戰(zhàn)略，但守方有劣戰(zhàn)略，A劣于B，D劣于C，故守方不會采用戰(zhàn)略A和D，剔除后的博弈變?yōu)椋?.5納什均衡攻方知道守方不會選A和D，他由此知道博弈變成上圖所示。此時，攻方就有一個劣戰(zhàn)略b，他剔除b后得到新的博弈：

此時，兩方的形勢是相同的，即攻方盡管開始在軍力上劣于守方，但實際上它只要運用計謀，其獲勝的可能與守方是相同的。5.5納什均衡本節(jié)知識要點

1.n個局中人博弈的標準式

2.納什均衡與納什均衡解

3.求納什均衡解的劃線法

5.6合作博弈與效益分配5.6合作博弈與效益分配1.問題的提出

多人合作博弈中的效益分配或費用分攤問題與現(xiàn)實的經(jīng)濟活動有著密切的關(guān)系.最典型的例子有橫向經(jīng)濟聯(lián)合中的效益分配問題和資金重組過程中的利益分配；大氣污染總量控制優(yōu)化治理投資的費用分攤；聯(lián)合興建污水處理廠建設(shè)費用的分攤；聯(lián)合投資企業(yè)破產(chǎn)以后所發(fā)生的債務(wù)如何進行分擔(dān)等。這類問題由于涉及的資金數(shù)目較大，比較敏感，只有處理好才能夠保證合作項目的成功.本節(jié)以三人合作經(jīng)商為問題為例，介紹解決多人合作博弈中的效益分配或費用分攤問題的基本概念和方法.5.6合作博弈與效益分配設(shè)有A,B,C三人經(jīng)商.若各人單干，則每人僅能獲利1萬元；若A,B合作,可獲利7萬元，A,C合作可獲利5萬元，B,C合作可獲利4萬元，三人合作可獲利10萬元。問三人合作時應(yīng)如何合理分配10萬元的利益。由此可見，有A參加的合作，獲利最大，7+5=12；有B參加的合作，獲利次之，7+4=11；有C參加的合作，獲利最小，5+4=9.在合作中，A貢獻最大，B次之，C最小。故在分配利益時，應(yīng)考慮與貢獻聯(lián)系起來。具體如何分配，這類問題就是n人合作博弈問題.下面介紹n人合作博弈的一些概念，并建立該問題的數(shù)學(xué)模型。2.n人合作博弈與特征函數(shù)設(shè)有n個局中人的集合對任一子集定義一實函數(shù)滿足條件：（1）表示空集;（2）當，

(稱為超可加性)。我們把稱為一個n人合作博弈(也稱結(jié)盟；稱為I的特征函數(shù)，它描述合作的效益。5.6合作博弈與效益分配5.6合作博弈與效益分配從（2）式可見，合作規(guī)模擴大，獲益不會減少.使（2）式等式成立的博弈稱為非本質(zhì)的，因為這種合作沒有帶來任何效益；使（2）式嚴格不等式成立的博弈稱為本質(zhì)的，因為這種合作對局中人確實有利，對局中人有吸引力.博弈論重點討論這種合作.5.6合作博弈與效益分配在3人經(jīng)商問題中，5.6合作博弈與效益分配3.簡單博弈

在博弈中，若對任意只取值0或1，則稱為簡單博弈。使的稱為獲勝結(jié)盟，使的稱為失敗結(jié)盟。5.6合作博弈與效益分配例如，在3人經(jīng)商問題中

（1）若,，則此簡單博弈記為.即三人合作獲利1萬元，單干或兩兩合作無獲利.（2）若,，

，則此簡單博弈記為.即有,兩人參加獲利1萬元，其他合作無獲利.（3）若，

，則此簡單博弈記為.即有參加獲利1萬元，無參加則無獲利.5.6合作博弈與效益分配4.總體合作所獲利益的分配原則n人合作博弈的解是指對總體結(jié)盟所獲利益的一個分配方案。若用表示局中人i從合作V中獲得報酬，為一個分配方案，則至少應(yīng)滿足：（1）個體合理性：

，.即合作優(yōu)于單干；（2）總體合理性：.解決n人合作博弈問題的任務(wù)，是如何獲得一個合理的分配方案：5.6合作博弈與效益分配5.Shapley值1953年美國運籌學(xué)家夏普利（L.S.Shapley）采用邏輯建模方法研究了這一問題。首先，他歸納出了幾條合理分配原則，即應(yīng)當滿足的基本性質(zhì)（用公理形式表示），進而證明滿足這些基本性質(zhì)的合作對策是唯一存在的，從而妥善地解決了問題。

5.6合作博弈與效益分配（1）對稱性原則每個局中人獲得的分配與他被賦予的記號無關(guān)，設(shè)

為I的一個排列，則.其中為重排序后的特征函數(shù)，為重排后原局中i人的新編號。5.6合作博弈與效益分配（2）有效性原則

①若局中人對他所參加的任一合作都無貢獻,則給他的分配應(yīng)為0。即若任意

，則

②完全分配5.6合作博弈與效益分配（3）可加性原則對I上任意兩個特征函數(shù)U與V，若此n個人同時進行兩項互不影響的合作，則兩項合作的分配也應(yīng)互不影響，每人的分配額即兩項合作單獨進行時應(yīng)分配數(shù)的和。滿足上述三公理的稱為Shapley值。5.6合作博弈與效益分配Shapley證明了：對任一n人合作博弈，Shapley值是唯一存在的，且

其中為集合S的元素個數(shù)，可看做這種貢獻的權(quán)因子，可視為局中人i在合作S中所作的貢獻.5.6合作博弈與效益分配Shapley值的分解算法：設(shè)，現(xiàn)有合作V：把合作V分解為簡單博弈的線性組合系數(shù)可通過解方程組確定。這是一個函數(shù)恒等式，故對自變量的每個取值都應(yīng)成立，其自變量為的各子集.5.6合作博弈與效益分配5.6合作博弈與效益分配把簡單博弈表5.5中各行的數(shù)據(jù)代入式(5.9)，并求解，得：5.6合作博弈與效益分配解這個方程組，有5.6合作博弈與效益分配可知：

分別表示A,B,C單干時的效益；

分別表示A與B,A與C,B與C合作時新增效益；

表示A,B,C三人合作時新增的效益，這是因為從第7個方程看出

【注】不要求非負.5.6合作博弈與效益分配在分配時，對兩人合作新增的效益應(yīng)各分1/2，對三人合作新增效益應(yīng)各分1/3，于是

而且5.6合作博弈與效益分配【例5.12】在3人經(jīng)商問題中，根據(jù)所給條件代入系數(shù)公式可以求出從而所以由公式（5.11）有利益分配方案

5.6合作博弈與效益分配【例5.13】有三個位于某河流同側(cè)的城市,從上游到下游依次為A,B,C，這三個城市的污水必須經(jīng)處理后才能排入河中.A與B距離為20km,B與C距離38km，如圖.設(shè)為污水流量Q(單位：),L為管道長度(km).建污水廠費用的經(jīng)驗公式為(單位：萬元),而建管道費用的經(jīng)驗公式為(單位：萬元).已知三城市的污水流量分別為，問應(yīng)該怎樣處理(單獨設(shè)廠還是聯(lián)合設(shè)廠)，才可使總開支最少？又每一城鎮(zhèn)負擔(dān)的費用應(yīng)各為多少?5.6合作博弈與效益分配分析思路：合作可省錢→把省錢視作獲利→計算獲利的分配→導(dǎo)出費用的分擔(dān).同時注意到：由于河流的走向，只要是合作建廠，就不可能建在A處.同理，B與C合作建廠，也不可能建在B處.5.6合作博弈與效益分配值解

下面計算各種情況的建廠費用(以下單位費用均是萬元，不再注明.計算時保留小數(shù)點后四位)：方案1：A,B,C各自建廠A自建廠的投資

B自建廠的投資

C自建廠的投資

方案2：A與B合作，在B處建廠；C單獨建廠

A與B合作投資

C自建廠的投資

總費用為

5.6合作博弈與效益分配方案3：A與C合作，在C處建廠；B自建廠

A與C合作投資

B自建廠的投資

總費用為

方案4：B與C合作，在C處建廠；A自建廠

B與C合作投資

A自建廠的投資

總費用為

5.6合作博弈與效益分配方案5：A,B,C合作，在C處建廠

總費用為

綜合上述，得到的最佳方案是：三城合作建廠.該方案實施的關(guān)鍵是如何分擔(dān)費用：

在合作建廠的洽談過程中，C城提出合作建廠費用按照污水量比例5:3:5分擔(dān)，污水管道費用由A與B城分擔(dān)；B城同意C城提出的合作建廠費用按照污水量比例分擔(dān)，并提議由A城到B城的污水管道費用由A城承擔(dān)，由B城到C城的污水管道費用由A與B城按污水量比例5:3分擔(dān)；A城覺得他們的建議似乎合理.5.6合作博弈與效益分配A城承擔(dān)的總費用

B城承擔(dān)的總費用

C城承擔(dān)的總費用

因此，A城自然不會同意B城、C城提出的方案.5.6合作博弈與效益分配為使合作成功，我們?yōu)樗麄兲岢鲆粋€合理分擔(dān)費用的方案。由于三城合作建廠可節(jié)省現(xiàn)把三城合作建廠節(jié)省的錢作為獲利，問題轉(zhuǎn)化為如何合理分配節(jié)約出的萬元。由于5.6合作博弈與效益分配5.6合作博弈與效益分配從而由公式(5.9)可把合作V分解為:代入公式(5.11)得A,B,C三個城市的獲利分配方案為

城市A

城市B

城市C5.6合作博弈與效益分配從而得到參考決策：A,B,C三城市合作，在處投資建廠，A,B,C三城市的分擔(dān)方案為(單位：萬元)：

城市A

城市B

城市C注意：在對實際問題作最后決策的時候，還應(yīng)考慮在城市C建廠的征地費用及產(chǎn)生的就業(yè)效益等.本節(jié)知識要點

1.n人合作博弈與特征函數(shù)

2.簡單博弈及相關(guān)概念

3.總體合作所獲利益的分配原則

4.Shapley值與合理分配原則

5.Shapley值的分解算法5.6合作博弈與效益分配5.7動態(tài)博弈與承諾行動5.7動態(tài)博弈與承諾行動

如果局中人在進行行動選擇時有先后順序之分，這種博弈就被稱為動態(tài)博弈.【例5.14】有兩個房地產(chǎn)開發(fā)商A和B分別決定在同一地段上開發(fā)一棟寫字樓。由于市場需求有限，如果他們都開發(fā)，則在同一地段會有兩棟寫字樓，超過了市場對寫字樓的需求，難以完全出售，空置房太多導(dǎo)致各自虧損100萬.當只有一家開發(fā)商在這個地段開發(fā)一棟寫字樓時，它可以全部售出，賺得利潤100萬.假定A先決策，B在看見A的決策后再決策是否開發(fā)寫字樓.在圖中，用“博弈樹”表示博弈過程：5.7動態(tài)博弈與承諾行動5.7動態(tài)博弈與承諾行動在圖5.5中每一條“路徑”的末端用向量給出A和B的支付，稱為支付向量.下面用“逆向歸納法”可以求解這個博弈.在B進行決策的兩個“決策結(jié)”上，B在左邊的決策結(jié)上選擇“不開發(fā)”；而在右邊的決策結(jié)上選擇“開發(fā)”.即給定A開發(fā)，B就不開發(fā)；給定A不開發(fā)，B就開發(fā).B應(yīng)避免同時與A都選擇開發(fā)而蒙受損失.在這種情況下，A在自己的決策結(jié)上當然選擇“開發(fā)”，因為他預(yù)計當自己選擇“開發(fā)”后，B會選擇“不開發(fā)”，自己就凈賺一百萬.當B威脅A說：“不管你是否開發(fā)，我都會在這里開發(fā)寫字樓.”倘若A將B的話當了真，A就不敢開發(fā)，讓B單獨開發(fā)寫字樓占便宜.5.7動態(tài)博弈與承諾行動但是，B的威脅是“不可置信”的.當A不理會B的威脅而果斷地開發(fā)出一棟寫字樓時，B其實不會將事前的威脅付諸實施.因為“識時務(wù)者為俊杰”，在A已開發(fā)的情況下，B的最優(yōu)決策是“不開發(fā)”而不是“開發(fā)”.但是，如果B在向A發(fā)出威脅的同時又當著A的面與第三者C打賭一定要在該地段上開發(fā)出一棟寫字樓，否則輸給C二百萬元.B與C為此簽定合同并加以公證有效.這時，博弈變成圖5.6所示的動態(tài)博弈.5.7動態(tài)博弈與承諾行動5.7動態(tài)博弈與承諾行動稱B的這種行動為“承諾行動”，它使原來不可置信的威脅變?yōu)榭梢灾眯?這時，A就不得不相信B一定要開發(fā)寫字樓的威脅了，于是放棄開發(fā)寫字樓的計劃，讓B如愿以償單獨開發(fā)寫字樓。B不僅未向C支付2百萬元，反而凈賺1百萬.我們可以運用“承諾行動”的原理來分析許多經(jīng)濟及軍事現(xiàn)象.5.7動態(tài)博弈與承諾行動【例5.15】

歐共體在空中客車與波音公司的競爭中對空中客車公司的戰(zhàn)略性補貼.歐共體為了打破美國波音公司對全球民航業(yè)的壟斷，曾放棄歐洲傳統(tǒng)的自由競爭精神而對與波音公司進行競爭的空中客車公司進行補貼.當雙方都未獲得政府的補貼時，兩個公司都開發(fā)新型飛機會因市場飽和而虧損，但若一家公司開發(fā)而另一家公司不開發(fā)時，則開發(fā)的那家公司會獲巨額利潤.未補貼時的博弈矩陣為下表.此時有兩個納什均衡，即一家開發(fā)而另一家不開發(fā).5.7動態(tài)博弈與承諾行動5.7動態(tài)博弈與承諾行動下面考慮歐共體對空中客車進行補貼20個貨幣單位的情況.此時，當兩家都開發(fā)時，空中客車仍然盈利10貨幣單位而不是虧損，博弈矩陣為下表。這時只有一個納什均衡，即波音公司不開發(fā)和空中客車公司開發(fā)的均衡（不開發(fā),開發(fā)），這有利于空中客車。在這里，歐共體對空中客車的補貼就是使空中客車一定要開發(fā)（無論波音是否開發(fā)）的威脅變得可置信的一種“承諾行動”.5.7動態(tài)博弈與承諾行動5.8應(yīng)用舉例5.8應(yīng)用舉例1.俾斯麥海的?？諏梗?）相關(guān)背景資料：

1943年2月，第二次世界大戰(zhàn)中的日本，在太平洋戰(zhàn)區(qū)已處于明顯的劣勢.為扭轉(zhuǎn)戰(zhàn)局，日軍統(tǒng)帥山本五十六統(tǒng)率下的一支艦隊策劃了一次軍事行動：由集結(jié)地——南太平洋新不列顛群島的拉包爾