第 6 章 博弈論基礎(chǔ)

1、博弈論基礎(chǔ) （對應(yīng)教材第6章） 現(xiàn)代博弈論開始于1928年馮諾伊曼的工作 本章學(xué)習(xí)要點(diǎn) ? 理解博弈論的基本概念 ?參與人，策略，收益（收益矩陣）?最佳應(yīng)對，占優(yōu)策略?納什均衡 ?混合策略，混合策略均衡?帕累托最優(yōu)，社會最優(yōu) ? 幾種典型博弈的類型 ? 體會“情景博弈求解”過程中的思想 博弈從一個例子開始? “復(fù)習(xí)考試”還是“準(zhǔn)備報告”？ ?假設(shè)在截止日期前一天，你有兩件要做的事情：一是復(fù)習(xí)（為了參加考試），二是準(zhǔn)備（給一個報告）。你只能選擇做一項。 ?考試成績可以預(yù)計 ? 如果復(fù)習(xí)，則考試成績92分，沒復(fù)習(xí)，則80分 ?報告需要你和你的拍檔合作完成 ? 如果你和拍檔都準(zhǔn)備報告，則每人都是10

2、0分 ? 如果只有一人準(zhǔn)備報告，則每人都是92分 ? 如果兩人都沒準(zhǔn)備報告，則每人都是84分 ?那么你該選擇做什么呢？（假設(shè)你和拍檔各自獨(dú)立考慮這個問題） 例子：“考試-報告”博弈? 設(shè)你們都追求平均成績的最大化： ?你和搭檔都準(zhǔn)備報告，則平均成績均為(80+100)/2 = 90分 ?你和搭檔都準(zhǔn)備?考試成績可以預(yù)期： ? 如果復(fù)習(xí)，則考試成績92分 ? 如果沒復(fù)習(xí)，則考試成績80分 ?報告是你和你的拍檔合作完成的： ? 如果你和拍檔都準(zhǔn)備報告，則每人100分 ? 如果只有一人準(zhǔn)備報告，則每人92分 ? 如果兩人都沒準(zhǔn)備報告，則每人84分 考試，則平均成 ? 若一方復(fù)習(xí)考試，另一方準(zhǔn)備報告：

3、? 準(zhǔn)備報告一方的得：(80+92)/2 =86分 (92+84)/2 = 88分 ? 復(fù)習(xí)的一方得：(9292)/2 = 92分收益矩陣（表達(dá)收益的一種直觀方式）你的拍檔準(zhǔn)備報告復(fù)習(xí)考試你準(zhǔn)備報告復(fù)習(xí)考試90, 9092, 8686, 9288, 88?其中第一個數(shù)字是“你”的收益，第二個是“拍檔”的 收益（也稱“回報”，payoff）博弈的基本要素? 一般情況下，博弈具有三個要素：?（1） 參與者（至少兩個）；?（2） 策略集：每個參與者都有一組關(guān)于如何行為的備選項，此處備選項指參與者的可能策略。?（3）收益（回報）：每個策略行為的選擇，都會使參與人得到一個收益。 ? 這個收益結(jié)果還受互動

4、中他人策略選擇的影響。 ? 同一組策略，不同參與人的收益可能不同 通常，收益的記號：P1(S,T), P2(S,T) 博弈行為推理的幾點(diǎn)基本假設(shè)? 每個參與人對博弈結(jié)構(gòu)（收益矩陣）有充分了解。 ? 參與人都是理性的（ra:onal） ?追求自己的收益最大化（盡量大） ?也知道其他參與人也是如此 ? 決策的獨(dú)立性 ?不商量 ? 嚴(yán)格占優(yōu)策略（strictly dominant strategy）：對一個參與人（A）來說，若存在一個策略，無論另一個參與人（B）選擇何種行為策略，該策略都是最佳選擇，則這個策略就稱為是A的嚴(yán)格占優(yōu)策略。 ? 這個例子中，“復(fù)習(xí)考試”對雙方都是嚴(yán)格占優(yōu)策略。 “考試-報

5、告”博弈中的行為推理你的拍檔準(zhǔn)備報告復(fù)習(xí)考試你準(zhǔn)備報告復(fù)習(xí)考試90, 9092, 8686, 9288, 88“囚徒困境”? 假設(shè)有兩個疑犯被警察抓住。并且被分開關(guān)押在不同的囚室。 ? 警察強(qiáng)烈懷疑他們和一場搶劫案有關(guān)。但是，沒有充足的證據(jù)。然而，他們都拒捕的事實也是可判刑的。 ? 兩個疑犯都被告知以下結(jié)果： ? “如果你坦白，而另外一人抵賴，則你馬上釋放；另外一人將承擔(dān)全部罪行，將會被 判刑10年 ? 如果你們都坦白，你們的罪行將被證實。但由于你們有認(rèn)罪的表現(xiàn)判刑4年。 ? 如果你們都不坦白，那么沒有證據(jù)證明你們的搶劫罪，我們將以拒捕罪控告你們判刑1年。 ? 另外一方也正在接受這樣的審訊。你

6、是坦白還是抵賴？”? 疑犯1和疑犯2的嚴(yán)格占優(yōu)策略都是“坦白” ? 盡管如果兩人都抵賴會都判得少些 ?刻畫了“有關(guān)個體私利前，建立合作是十分困難”的模型。 “囚徒困境”的收益矩陣疑犯2抵賴坦白疑犯1抵賴坦白-1, -10, -10-10, 0-4, -4 ? 這種類型通常稱為軍備競賽。競爭雙方為保持彼此實力相當(dāng)，都會選擇生產(chǎn)更具危險性的武器，盡管對自己內(nèi)部會有傷害 ?運(yùn)動員傷害身體，國家影響民生。“興奮劑”博弈運(yùn)動員2沒服用服用運(yùn)動員1沒服用服用3, 34, 11, 42, 2關(guān)于“收益”的討論（收益決定選擇）? “考試-報告”博弈，如果降低考試難度：只要復(fù)習(xí)了，就會得到100分；否則，也可得

7、到96分。 你的拍檔準(zhǔn)備報告復(fù)習(xí)考試你準(zhǔn)備報告復(fù)習(xí)考試98, 9896, 9494, 9692, 92囚徒困境類似，如果改變收益矩陣，情況也可不一樣最佳應(yīng)對與占優(yōu)策略? 設(shè)S是參與人甲的一個選擇策略，T是參與人乙的一個選擇策略。在收益矩陣中的某個單元格對應(yīng)這策略組（S，T）。 ?P1(S，T)：表示參與人甲從這組決策獲得的收益 ?P2(S，T)：表示參與人乙從這組決策獲得的收益 ? 最佳應(yīng)對：針對參與人乙的策略T，若參與人甲采用策略S產(chǎn)生的收益大于或等于自己的任何其他策略，則稱參與人甲的策略S是參與人乙的策略T的最佳應(yīng)對。 P1(S，T) P1(S，T), 其中， S是參與人甲除S外的任何其他

8、策略。嚴(yán)格最佳應(yīng)對? 嚴(yán)格最佳應(yīng)對：若S會產(chǎn)生比任何應(yīng)對策略T的其他策略都更高的收益，則稱參與人甲的策略S是對于參與人乙的策略T的嚴(yán)格最佳應(yīng)對。 P1（S，T） P1（S，T） 其中，S是參與人甲的所有其他策略。 ? 注：最佳應(yīng)對的概念是針對對方的某一個策略（T），相對于自己的所有策略而言的 ? 對于同一個T，最多只可能有一個嚴(yán)格最佳應(yīng)對 ? 對于不同的T，最佳應(yīng)對可能相同，也可能不同 占優(yōu)策略與嚴(yán)格占優(yōu)策略? 定義：（從最佳應(yīng)對角度給出） ?參與人甲的占優(yōu)策略S，是指該策略對于參與人乙的每一策略都是最佳應(yīng)對。 ?參與人甲的嚴(yán)格占優(yōu)策略S，是指該占優(yōu)策略對于參與人乙的每一策略都是嚴(yán)格最佳應(yīng)對。

9、 ? 如果參與人有嚴(yán)格占優(yōu)策略，則可預(yù)期他會采取該策略（與基本假設(shè)的一致性）。 ? 注：占優(yōu)策略的概念是相對于對方所有策略而言的。 并不是每人總有嚴(yán)格占優(yōu)策略? 例子：“營銷戰(zhàn)略”博弈 ?假設(shè)有兩家公司，分別要規(guī)劃生產(chǎn)并銷售同一種新產(chǎn)品。該產(chǎn)品有兩款可能的規(guī)格：廉價（低檔）或高檔。如何決策？ ?設(shè)顧客總體被分成兩個市場：一部分消費(fèi)群體（60%）只購買廉價商品，另一部分消費(fèi)群體（40%）只購買高檔次商品。 ?每家公司從廉價或高檔次商品所得利潤是等同的（因此利潤僅取決于市場占有率）。 ?每家公司都追求利潤最大化?！盃I銷戰(zhàn)略”博弈? 假設(shè) ? 若兩家公司分別定位生產(chǎn)不同類型的產(chǎn)品，則每家公司都會得到

10、該商品市場的全部份額。 ? 公司1品牌形象更佳。因此，若這兩家公司在同一市場（廉價或高檔次）中競爭，則公司1可以得到80%的市場銷售量，公司2只能得到20的市場。 公司2廉價高檔次公司1廉價高檔次0.48, 0.120.4, 0.60.6, 0.4 0.32, 0.08? 可以預(yù)測此博弈的發(fā)展趨向。即公司1將會采取廉價策略，公司2將會采取高檔次策略。博弈的行為推理? 如果參與人都有嚴(yán)格占優(yōu)策略，則可以預(yù)計他們均會采取嚴(yán)格占優(yōu)策略； ? 如果只有一個參與人有嚴(yán)格占優(yōu)策略，則這個參與人會采取嚴(yán)格占優(yōu)策略，而另一方會采取此策略的最佳應(yīng)對。 ? 如果兩個參與人都沒有嚴(yán)格占優(yōu)策略呢？無占優(yōu)策略例子（三客

11、戶博弈）? 假設(shè)有兩家公司，都希望和A、B、C三個大客戶之一洽談生意。每家公司都有三種可能的策略：是否找客戶A、B或C。 ? 他們決策的條件如下所示：? 若兩家公司都找同一個客戶，則該客戶會給每個公司一半的業(yè)務(wù)。? 公司1規(guī)模太小，以至于不能靠自身找到客戶源。所以，只要它和公司2分別尋找不同的客戶洽談生意，則公司1獲得的收益將會是0（生意做不成）。? 假設(shè)公司2單獨(dú)尋找客戶B或C洽談生意，則會得到客戶B或C的全部業(yè)務(wù)。但是A 是一個大客戶。尋找客戶A洽談生意時，必須和其它公司合作才能接下業(yè)務(wù)。 ? 因為A是一個大客戶，和它做生意的收益是8（假設(shè)兩家公司合作，則每家公司會得到收益4）。但是，和B

12、或C做生意的收益價值是2（合作的話，每個公司收益是1）“三客戶”博弈的推理? 收益矩陣 公司2ABCA公司1 BC4, 40，00，00, 21, 10, 20, 20, 21, 1? 兩家公司都沒有嚴(yán)格占優(yōu)策略 納什均衡? 假定參與人甲選擇策略S，參與人乙選擇策略T。若S是T的最佳應(yīng)對，且T也是S的最佳應(yīng)對，則稱策略組（S ，T）是一個納什均衡。 ?在均衡狀態(tài)，任何參與人都沒有動機(jī)（理性的理由）去換一種策略。 ?納什均衡可以被看成是一種信念上的均衡 ? 互為最佳應(yīng)對，誰也不可能通過單方面改變策略而得到額外好處，盡管如果兩人都改變可能都會更好（相比都不改變而言） ? 存在納什均衡：(A，A)

13、? 尋找納什均衡的兩種途徑： ?一是，檢查每一個策略組，看它們中的每一項是否是彼此間策略的最佳應(yīng)對策略。 ?二是，找出每個參與人對于對方每個策略的最佳應(yīng)對，然后發(fā)現(xiàn)互為最佳應(yīng)對的策略組?！叭蛻簟辈┺牡募{什均衡公司2ABCA公司1 BC4, 40，00，00, 21, 10, 20, 20, 21, 1多重均衡：協(xié)調(diào)博弈? 多重均衡存在多個均衡 ? 例子：協(xié)調(diào)博弈 ?假設(shè)你和你拍檔都為一個合作項目準(zhǔn)備幻燈片簡報（雙方不能通過電話等方式聯(lián)系商量）。 ?你必須決定是用微軟的PPT或是用蘋果的Keynote軟件來制作你負(fù)責(zé)的半份幻燈片。 ?假設(shè)你們使用同樣的軟件來設(shè)計，那就比較容易合并你們的幻燈片。

14、? 存在兩個納什均衡：（PPT，PPT），（Keynote，Keynote）。 ? 如何預(yù)測協(xié)調(diào)博弈中參與人的行為？ ? 托馬斯 謝林（獲得2005年諾貝爾經(jīng)濟(jì)學(xué)獎）提出一種聚點(diǎn)的想法，利用一些其他外部因素，例如社會習(xí)俗。協(xié)調(diào)博弈的推理你的拍檔PPTKeynote你PPTKeynote1, 10，00，01，1? 謝林的聚點(diǎn)理論表明，可以預(yù)測到參與人會精選策略，傾向于收益情況更好的均衡。 不對等協(xié)調(diào)博弈? 假設(shè)你和項目拍檔都更喜歡使用蘋果軟件。 你的拍檔PPTKeynote你PPTKeynote1, 10，00，02，2? 此時很難預(yù)測具體哪種均衡會被采取。 ? 可以通過了解他們之間平常發(fā)生沖

15、突時解決的慣例來預(yù)測。兩人的喜好不同呢? 假設(shè)你和你的拍檔喜歡的軟件不同。 你的拍檔PPTKeynote你PPTKeynote1, 20，00，02，1 ? 選擇何種均衡？要在高收益和由于另一方不合作而造成損失之間進(jìn)行權(quán)衡。 獵鹿博弈? 假設(shè)兩獵人外出獵物。若他們合作，則可以獵到鹿（這可以給獵者帶來最高的收益）。 ? 獵人若分開單干，都能獵到兔。 ? 若一方想單獨(dú)獵鹿，則收益是0。另一方依然能獵到兔。 獵人2獵鹿獵兔獵人1獵鹿4，40，3獵兔3，03，3多重均衡：鷹鴿博弈? 假設(shè)兩只動物要決定一塊食物在彼此之間何如分配。 ? 每種動物都可以選擇爭奪行為（鷹派策略）或分享行為（鴿派策略）。 ?若

16、兩種動物都選擇分享行為，他們將會均勻的分配食物，各自的收益是3。 ?若一方行為表現(xiàn)為爭奪，另一方行為表現(xiàn)是分享，則爭奪方會得到大多數(shù)食物，獲得收益是5，分享方只能得到收益為1。 ?當(dāng)兩只動物都表現(xiàn)為爭奪行為，由于在爭奪中踐踏了食物，則它們得到的收益將為0。? 很難預(yù)測參與者的行為 ? 納什均衡概念能有助于縮小合理的預(yù)測范圍，但它并不能給出唯一的預(yù)測。鷹鴿博弈推理動物2鴿派鷹派動物1鴿派鷹派3, 35，11，50，0幾種典型多均衡博弈類型對比動物2鴿派鷹派鴿派鷹派3，35，11，50，0你的拍檔PPTKeynotePPTKeynote1，10，00，02，2你的拍檔PPTKeynotePPTKe

17、ynote1，20，00，02，1獵人2獵鹿獵兔獵鹿獵兔4，43，00，33，3簡單博弈的推理思路? 如果雙方都有嚴(yán)格占優(yōu)策略，則都會采用之 ? 如果只有一方有嚴(yán)格占優(yōu)策略，則可以預(yù)測另一方會采用此策略的最佳應(yīng)對 ? 如果不存在嚴(yán)格占優(yōu)策略，則尋找納什均衡 ?存在一個納什均衡，該均衡對應(yīng)合理結(jié)果 ?存在多個納什均衡（需要額外信息輔助決策） ? 協(xié)調(diào)博弈，鷹鴿博弈 ?均衡有助于縮小考慮范圍，但不保證有效預(yù)測 ? 如果不存在納什均衡，該怎么辦？ ? 此時，不存在一組互為最佳應(yīng)對（納什均衡）混合策略? 例子：硬幣配對“零和博弈”（zero sum game） ? 兩個參與人各持一枚硬幣，同時選擇手中

18、硬幣的正反面。 ? 若他們硬幣的朝向相同，參與人乙將贏得參與人甲的硬幣。反之，則參與人甲將贏得參與人乙的硬幣。 參與人乙正面H反面T參與人甲正面H反面T-1，+1 +1，-1+1，-1-1，+1混合策略的引入? 引入隨機(jī)性，考慮參與人將以一定的概率分布在不同策略間進(jìn)行選擇，一種分布對應(yīng)一個“混合策略”（此時，選擇策略就是選擇分布）? 對于雙策略（H和T）博弈，混合策略則可簡略表示為一個概率。純策略就是概率為（0,1）的混合策略。? 通常，我們說? 參與人1的策略是概率p，是指參與人1以概率p執(zhí)行H；以概率1-p執(zhí)行T? 參與人2的策略是概率q，是指參與人2以概率q執(zhí)行H，以概率1-q執(zhí)行T混合

19、策略的收益? 采用收益期望作為策略的回報測度 ? 設(shè)參與人1采用概率p執(zhí)行H，1-p執(zhí)行T，則： ? 若參與人2采用H，則其收益期望是 ? 若參與人2采用T，則其收益期望是 類似地，可討論參與人2采用概率混合策略的情形 P 2(p,H)= p!P 2(H,H)+(1 p)!P 2(T,H)P 2(p,T)= p!P 2(H,T)+(1 p)!P 2(T,T)混合策略的均衡? 混合策略的納什均衡：它是一對混合策略，彼此都是對方的最佳應(yīng)對（期望收益）? 納什的奠基性貢獻(xiàn)：證明了具有有限參與者和有限純策略集的博弈一定存在納什均衡（包括混合策略均衡） ? 一般來說，找到混合策略的納什均衡是很困難的，但

20、在某些特定條件下可能有系統(tǒng)的方法。 雙人雙策略、沒有含純策略均衡的博弈中的混合策略納什均衡求解? 給定H，T：基本純策略。按照納什定理，存在一個混合策略的納什均衡（p,q），即p是q的最佳應(yīng)對，q也是p的最佳應(yīng)對。如何求p和q？ ? “沒有含純策略的均衡”的前提意味著p，q都是嚴(yán)格在0和1之間。 ? 確定參與人2采用的q的方法（確定p的方法對稱） ? 基于q和收益矩陣中的值，分別寫出參與人1采用H和采用T的收益期望（q的函數(shù)），即P1(H,q)和P1(T,q)，也就是相當(dāng)于P1(1,q)和P1(0,q) ? 下面的關(guān)鍵是要認(rèn)識到此時必定有：P1(1,q)P1(0,q)，從而可以借助這等式求出q

21、 P1(1,q)P1(0,q)：在兩個端點(diǎn)“無差異”原理? 推理的思路是 ? 若等式不成立，例如 P1(1,q) P1(0,q)，則將導(dǎo)致H（即p=1）是參與人1的最佳應(yīng)對的結(jié)論，即（H,q）是一個納什均衡，這與“不含純策略納什均衡”的前提矛盾 ? 直觀上，若 P1(T,q) P1(H,q)，參與人1在應(yīng)對q的時候采用H就是最好，將任何機(jī)會（概率）分給T都只會導(dǎo)致較低收益 ?數(shù)學(xué)上就是 P1(p,q) = pP1(H,q)+(1-p)P1(T,q) P1(H,q), for p1/3，則損失會比較大 ? 為什么進(jìn)攻方在均衡的拋球概率只有p=1/3，但防守方還要更多的防守拋球？ ? 由于拋球?qū)M(jìn)

22、攻方更有利，需要加大防守力度 防守方進(jìn)攻方拋球(1/3)持球(2/3)防守拋球(2/3)0，0 5，-5攔斷持球 (1/3)10，-100，0例子：罰點(diǎn)球博弈? 2002年，有人做了一項有關(guān)罰點(diǎn)球研究 ?射手要決定從球門的左側(cè)或是右側(cè)進(jìn)球。 ?守門員則是要決定是撲向左側(cè)或是右側(cè)攔斷進(jìn)球。 ?兩人需要同時做選擇。 守門員LR射球方LR0.58，-0.58 0.93，-0.930.95，-0.950.70，-0.70統(tǒng)計數(shù)據(jù)。可以看到，罰球方總是有贏頭（符合實際）。? 計算得到的均衡： 0.58q+0.95(1-q)=0.93q+0.70(1-q)，q=0.42 -0.58p-0.93(1-p)=

23、-0.95p-0.70(1-p)，p=0.39 ? 實戰(zhàn)統(tǒng)計得到的數(shù)據(jù)：q=0.42, p=0.40混合策略均衡守門員L(q)R射球方L(p)R0.58，-0.58 0.93，-0.930.95，-0.950.70，-0.70? 除了兩個純策略均衡（PPT,PPT）和（Keynote,Keynote）外，還存在一個混合策略均衡：q=2(1-q), q=2/3；p=2(1-p), p=2/3 兼具純策略和混合策略均衡的博弈? 例子：不平衡的協(xié)調(diào)博弈 你的拍檔PPT(q)Keynote你PPT(p)Keynote1，10，00，02，2關(guān)于混合策略均衡的一般性推理? 若雙人雙策略博弈存在混合策略均

24、衡（p,q），0 p, q 收益期望(p,q) ，即沒有q1是p的最佳應(yīng)對，從而與存在上述混合策略均衡矛盾 ? 于是可利用這無差異原則，試求p；類似地，求q。（注意，并不保證總能求出在（0,1）上的p和q） ? 若分別求得了（0,1）區(qū)間中的p和q，則說明 ? 對于甲的策略p，乙采用0,1上的任何策略都是一樣的，即都是最佳應(yīng)對，后來求出的q當(dāng)然也是。對于p也有對稱的認(rèn)識，亦即p和q互為最佳應(yīng)對想想混合策略組：(p,q+q)? q+q 依然是p的最佳應(yīng)對，但p卻不是q+q 的最佳應(yīng)對了！ ? q+q 的最佳應(yīng)對會是甲的某一個純策略！P 2(p,H)= p!P 2(H,H)+(1 p)!P 2(T,H)P 2(p,T)= p!P 2(H,T)+(1 p)!P 2(T,T)Set P 2(p,H)= P 2(p,T) to solve pP 2(q, p)= q!P 2(p,H)+(1q)!P 2(p,T)對任何q都無差異！乙在兩個純策略上的收益期望? P1(1,q)=q*90+(1-q)*86; P1(0,q)=q*92+(1-q)*88 ? 容易檢查，不存在q，使 P1(1,q) = P1(0,q