博弈論知識點總結(jié)完整版

1、博弈論(一)：基本知識1.1 定義 :博弈論，又稱對策論，是使用 嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型研究沖突對抗條件下最優(yōu) 決策問題的理論， 是研究競爭的邏輯和規(guī)律 的數(shù)學(xué)分支。 即，博弈論是研究決策主體在 給定信息結(jié)構(gòu)下如何決策以最大化自己的 效用，以及不同決策主體之間的均衡。1.2 基本要素：參與人、各參與人的策 略集、各參與人的收益函數(shù)， 是博弈最重要 的基本要素。1.3 博弈的分類：博弈論根據(jù)其所采用 的假設(shè)不同而分為合作博弈理論和非合作 博弈理論。 兩者的區(qū)別在于參與人在博弈過 程中是否能夠達(dá)成一個具有約束力的協(xié)議 ( binding agreement )。倘若不能， 則稱非合 作博弈( Non-co

2、operative game )。合作博弈強調(diào)的是集體主義，團(tuán)體理 性，是效率、公平、公正；而非合作博弈則 主要研究人們在利益相互影響的局勢中如 何選擇策略使得自己的收益最大， 強調(diào)個人 理性、個人最優(yōu)決策，其結(jié)果有時有效率， 有時則不然。 目前經(jīng)濟(jì)學(xué)家談到博弈論主要 指的是非合作博弈， 也就是各方在給定的約 束條件下如何追求各自利益的最大化， 最后 達(dá)到力量均衡。博弈的劃分可以從參與人行動的次序 和參與人對其他參與人的特征、 戰(zhàn)略空間和 支付的知識、 信息，是否了解兩個角度進(jìn)行。 把兩個角度結(jié)合就得到了 4 種博弈：a、完全信息靜態(tài)博弈，納什均衡，Nash(1950)b、完全信息動態(tài)博弈，子

3、博弈精煉納 什均衡，澤爾騰( 1965)c、不完全信息靜態(tài)博弈，貝葉斯納什 均衡，海薩尼( 1967-1968 )d、不完全信息動態(tài)博弈，精煉貝葉斯 納什均 衡， 澤爾騰(1975) Kreps, Wilson(1982) Fudenberg, Tirole(1991)1.4 課程主要內(nèi)容：完全信息靜態(tài)博弈 完全信息動態(tài)博弈 不完全信息靜態(tài)博弈 機制設(shè)計 合作博弈1.5 博弈模型的兩種表示形式：策略式表 述 (Strategic form), 擴(kuò) 展 式 表 述 ( Extensive form )1.6 占優(yōu)均衡：a、占優(yōu)策略：在博弈中如果不管其他 參與人選擇什么策略， 一個參與人的某個策

4、略給他帶來的支付值始終高于其他策略， 或 至少不劣于其他策略， 則稱該策略為該參與 人的嚴(yán)格占優(yōu)策略或占優(yōu)策略。對于所有的 s-i， si* 稱為參與人i 的嚴(yán)格占優(yōu)戰(zhàn)略，如果滿足： ui(si*,s-i)ui(si,s-i) s-i, si si*b、占優(yōu)均衡：一個博弈的某個策略組合中， 如果對應(yīng)的所有策略都是各參與人的 占優(yōu)策略， 則稱該策略組合為該博弈的一個 占優(yōu)均衡。1.7 重復(fù)剔除嚴(yán)劣策略均衡：a、“嚴(yán)劣”和“弱劣”的含義：設(shè)Si和s是參與人i可選擇的兩個策 略，若對其他參與人的任意策略組合 s-i, 均 成立 ui(si, s-i) u i(si , s-i), 則說策略 si 嚴(yán)

5、劣于策略 si 。上面式子中，若將“ ”改為“W”，則 說策略 si 弱劣于策略 si。b、定義： 重復(fù)剔除嚴(yán)格策略就是 各參與人在其各自策略集中， 不斷剔除嚴(yán)劣策略如果最終 各參與人僅剩下一個策略，則 該策略組合就被稱為重復(fù)剔除 嚴(yán)劣策略均衡。二 )： 納 什 均 衡 ( NashEquilibrium )2.1 納什均衡定義：對于一個策略式表 述的博弈 G= N,S, Ui, i N,稱策略組合 s*=(si,Sn )是一個納什均衡，如果對于 每一個i N, Si*是給定其他參與人選擇S-i*=S1*,Si-1*, Si+1*,Sn*情況下參與人 i 的最優(yōu)策略(經(jīng)濟(jì)理性策略)，即：Ui(

6、s*, S-i*) ui(si, S-i ),對于任意的 s S ,任意的i N 均成立。通俗定義：納什均衡是一種策略組合， 給定對手的策略，每個參與人選擇自己的最 優(yōu)策略。納什均衡是一種穩(wěn)定的策略組合： 當(dāng)所有參與人的選擇公開以后， 每個人都滿 意自己作出了正確的選擇； 沒有人能得到更 好的結(jié)果了。在博弈論中這種結(jié)果被稱為納 什均衡( NE)。2.2 定理：Nash在1950年證明：任何 有限博弈， 都至少存在一個 NE ExiStence of NaSh Equilibrium 。即在一個有 n 個參與人的策 略式博弈 G=S1,Sn; u1,un中，如果n 是有限的，且Si是有限集(i=

7、1,n),則該 博弈至少存在一個納什均衡 (在混合策略意 義下)Wils on (1971)證明，幾乎所有有限博 弈，都存在有限奇數(shù)個 NE,包括純策略NE 和混合策略 NE。 OddneSS Theorem2.3 納什均衡、占優(yōu)均衡、重復(fù)剔除嚴(yán) 劣策略均衡的關(guān)系定理 a 每一個占優(yōu)均衡、重復(fù)剔除嚴(yán)劣策 略均衡一定是納什均衡， 但反過來不一定成 立； 定理 b 納什均衡一定不能通過重復(fù)剔除嚴(yán) 劣策略方法剔除。2.4 劃線法 先找出自己針對其他博弈方每種策略或策 略組合(對多人博弈)的最佳對策，即自己 的可選策略中與其他博弈方的策略或策略 組合配合，給自己帶來最大得益的策略 (這 種相對最佳策略

8、總是存在的， 不過不一定唯 一)，然后在此基礎(chǔ)上，通過對其他博弈方 策略選擇的判斷，包括對其他博弈方對自己 策略判斷的判斷等，預(yù)測博弈的可能結(jié)果和 確定自己的最優(yōu)策略。這就是劃線法。2.5 箭頭法箭頭法對于理解博弈關(guān)系很有好處 ,是 尋找相對穩(wěn)定性策略組合的分析方法。 對博 弈中的每個策略組合進(jìn)行分析， 考察在每個 策略組合處各個參與方能否通過改變自己的策略而增加得益。如能，則從所分析的策 略組合對應(yīng)的得益數(shù)組引一箭頭到改變策 略后策略組合對應(yīng)的得益數(shù)組。 最后綜合對 每個策略組合的分析情況， 形成對博弈結(jié)果 的判斷。劃線法和箭頭法的結(jié)果是一致的， 可以相互替代。(三) ：混合策略( Mixe

9、dStrategies )納什均衡3.1 定義：混合策略的定義：在博弈G=N, Si, ui, i N中，假設(shè)參與人i的純策 略構(gòu)成的策略集合為Si=si1,sik，若參與人 i 以概率分布 pi=(pi1, , pik) 在其 k 個 可選策略中隨機選擇“策略” ，稱這樣的選 擇方式為混合策略。這里，0 pij 1,對于j=1，,k都成立，且有，pi1+ pik=1。 純策略可看成特殊的混合策略。 上述定義是 在有限博弈前提下進(jìn)行的。3.2混合策略意義下策略組合的表述x1 X1, , xnXn ，其中 Xi , i =1, , n 表示參與人 i 所有純策略生成的概 率空間， xi 為參與人

10、 i 的一個具體混合策略 猜硬幣博弈的一個混合策略就可記為 (1/2, 1/2),(1/2, 1/2)3.3VNM 效用函數(shù)( Von Neumann and Morgenstern馮諾依曼和摩根斯坦)如果某個隨機變量 X以概率Pi取值xi , i=1,2，,n,而某人在確定地得到xi時的效用為u(xi),那么，該隨機變量給他的效用便 是： U(X) = P 1u(x1) + P 2u(x2) + . + P nu(xn) 表示關(guān)于隨機變量 X 的期望效用。因此 U(X) 稱為期望效用函數(shù)，又叫做馮諾依曼一一 摩根斯坦效用函數(shù)( VNM 函數(shù))。3.4 基于混合策略意義下的博弈策略式 表述定義

11、：基于 (v-N-M 效用的 )策略式博弈 由a、參與人集合 b、每個參與人有一個 (純)策略集合c、對于每一個參與人來說，由所有參與人純策略組合構(gòu)成的風(fēng)險結(jié) 果空間，存在一個 v-N-M 效用3.5 混合策略意義下的納什均衡 定義：對于博弈 G= N, Si, ui, i N，基于v-N-M效用的混合策略組合a*是一個 納什均衡， 若對于每一個 i, 以及 i 的任意一 個混合策略a i, a *對應(yīng)的期望支付至少和 (a i, a *-i )的期望支付一樣大換句話說，稱混合策略組合a *是一個 納什均衡， 如果沒有一個參與人通過偏離策 略a *i實現(xiàn)支付的增加3.6 一個定理對于N-人靜態(tài)

12、博弈問題，設(shè)混合策略 納什均衡對應(yīng)的策略組合為 (Xi, X - i ) 。對于任意的 i ,若最優(yōu)混合策略為 Xi= x1,xl , 00(不失一般性，假設(shè)前I個 分量嚴(yán)格大于 0)，記分量xk (k=1,I)對 應(yīng)的純策略 sk,則對于參與人 i 而言， sk 與其他參與人 的最優(yōu)混合策略組合 X - i形成的局勢的 收益值 ,等于納什均衡混合策略組合 (Xi, X - i )的收益值。即 ui (sk, X - i ) = ui (Xi, X - i )成立,k=1,I3.7 方法：a、求解混合策略均衡可以用期望收益 等值法b、2X 2雙矩陣博弈的圖解法：反應(yīng)函數(shù) 的三個交點即是納什均衡

13、(四) ：多重納什均衡解及其分析4.1 帕雷托占優(yōu)均衡 帕雷托占優(yōu)均衡的含義是： 在多個納什均衡中， 若存在一個納什均衡，其支付結(jié)果 針對每個參與人而言都嚴(yán)格優(yōu)于其它納什 均衡，則該納什均衡是帕雷托占優(yōu)納什均 衡。4.2 風(fēng)險占優(yōu)均衡 (risk-dominant equiIibrium)參與人對風(fēng)險占優(yōu)均衡的選擇傾向， 有 一種強化的機制。 當(dāng)部分或所有參與人選擇 風(fēng)險占優(yōu)均衡的可能性增強的時候， 任一參 與人選擇帕雷托占優(yōu)均衡策略的期望支付 會進(jìn)一步減小， 而這又使得帕雷托占優(yōu)均衡 策略的支付更小， 從而形成一種選擇風(fēng)險占 優(yōu)均衡策略的正反饋機制， 并使其出現(xiàn)的概 率越來越大。當(dāng)參與人數(shù)目

14、增加時， 選擇合作的風(fēng)險 將會更大， 可借助該點考慮招標(biāo)機制如何減 少投標(biāo)方勾結(jié)問題。 上述問題是我們知道建 立誠信機制社會的重要意義。 上述問題引出 一個博弈相關(guān)分支為協(xié)調(diào)博弈 (coordination game)4.3 聚點均衡 由實際問題抽象出來的博弈模型中， 更多的一類問題是： 多個納什均衡間不存在帕 雷托占優(yōu)關(guān)系或明顯的風(fēng)險占優(yōu)關(guān)系， 如夫 妻愛好問題的兩個純策略均衡。 這時如何預(yù) 測哪一個納什均衡會出現(xiàn)是一個很有意義 的問題以夫妻愛好博弈為例， 在實際中往往二 人很默契地知道如何進(jìn)行博弈， 雙方往往知 道怎么進(jìn)行選擇策略， 且能夠相互了解 (這 里面排除了互相協(xié)商后達(dá)成的一致)實

15、際博弈中參與人往往會利用博弈模 型以外的信息， 實現(xiàn)對特定博弈均衡一致關(guān) 注的“聚點”這些信息如： 參與人共同的文化背景或 規(guī)范，共同的知識， 具有特定意義事物的特 征，某些特殊的數(shù)量、位置關(guān)系等聚點均衡確實反映了人們在多重納什 均衡選擇中的某些規(guī)律性， 但因為涉及因素 太多，對于一般博弈模型很難總結(jié)普遍規(guī) 律，只能具體問題具體分析聚點：人們通常會協(xié)調(diào)彼此的行為。 (你 弱他就強)；先例產(chǎn)生的影響遠(yuǎn)大于邏輯或 者法律效力； 人們總是樂于安守現(xiàn)狀或接受 自然形成的界線(三八線)4.4 相關(guān)均衡 (correIated equiIibrium) 實際上， 在現(xiàn)實中遇到選擇困難時，特別是在長期中反復(fù)

16、遇到相似選擇難題時， 常 會通過收集更多信息， 形成特定的機制和規(guī) 則，為某種形式的制度安排等主動尋找思 路。相關(guān)均衡就是這樣的一種均衡選擇機 制。對于實際中比較復(fù)雜的博弈問題， 參與 人是否有能力設(shè)計這種機制， 并且有足夠能 力理解、信任這種機制，是有一定疑問的。相關(guān)均衡作為社會經(jīng)濟(jì)制度創(chuàng)新的一 種解釋也許更有意義。4.5 防共謀均衡 (coaIition-proof equiIibrium)定義：如果一個博弈的某個策略組合滿 足a沒有任何單個參與人的“串通”會改變博弈的結(jié)果， 即單獨改變策略無利可圖 （該策略組合是納什均衡） 。b、給定選擇偏離的參與人有再次偏離 的自由時， 沒有任何兩個參

17、與人通過 “串通” 改變博弈的結(jié)果。c、依此類推，直到所有參與人都參加 的串通也不會改變博弈的結(jié)果。滿足上述要求的均衡策略組合稱為 “防 共謀均衡”在有多個參與人的博弈中， 若部分參與人通過某種形式的默契或串通形成小團(tuán)體， 可能得到比不串通個大的支付。 這就是多人 博弈的共謀問題。防共謀均衡是指這樣的一個納什均衡， 在該均衡局勢下， 少數(shù)參與人集合不能通過 均衡策略的偏離，實現(xiàn)更好的局部利益。防共謀均衡是兩個以上參與人參加的 博弈中， 參與人在帕雷托占優(yōu)均衡中進(jìn)行合 作思想的擴(kuò)展。（五）：動態(tài)博弈5.1 特點 一類博弈行為通常需要參與人多步 決策才能完成，具有明顯的階段性。博弈的 結(jié)局、各參與

18、人的收益由多階段決策結(jié)果確 定。各參與人的決策有一定的順序。由于動態(tài)博弈各參與人進(jìn)行決策具 有明顯的階段性、 行動次序性，通常用擴(kuò)展 式 （extensive form） 表述法描述這些信息。5.2 博弈的擴(kuò)展式表示參與人集合：i=1,N。用N表示 虛擬參與人“自然” ；? 自然的含義是某些外生的 客觀概率分布事件 參與人的行動順序 （the order of moves）:描述各參與人在什么時候行 動；參與人的行動空間 （action set）:在每次行動時，參與人可選擇的行動集 合；參與人的信息集 （information set） ：每次行動時參與人知道什么；參與人的收益函數(shù)：在行動結(jié)束

19、之 后，每個參與人得到些什么。自然選擇的概率分布（假定自然狀 態(tài)是共同知識） 。對于有限博弈，博弈樹是常用的表述方式。5.3 博弈樹a若動態(tài)博弈是有限博弈，則可用博 弈樹表示該博弈。這里有限的含義是： 各階段各參與人的行動數(shù)目有限；博弈 的階段數(shù)有限。b 博弈樹的基本結(jié)構(gòu)為結(jié)點（nodes）。包括決策結(jié)及終點結(jié)。 決策結(jié)是參與人采取行動的時點；終點 結(jié)是博弈行動路徑的終點。枝（branches）。從一個決策結(jié)到它的 直接后續(xù)結(jié)的連線，每一個枝代表參與 人的一個行動選擇。信息集。是決策結(jié)集合的一個子集。 將博弈樹中某一決策者在某一行動階段 具有相同信息的所有決策結(jié)稱為一個信 息集。注：每個決策結(jié)

20、都是同一個參與人的決 策結(jié)。該參與人知道博弈進(jìn)入該集合的 某個決策結(jié)，但不知道自己究竟出于哪 一個決策結(jié)（若該信息集有兩個或兩個 以上元素） 。5.4 對于有限動態(tài)博弈，若參與人對彼 此在各決策結(jié)點的行動集合， 彼此的效用函 數(shù)， 歷史的行動有著完全的了解， 則稱這樣 的博弈為完全信息動態(tài)博弈。如果博弈樹的所有信息集都是單元 素集，稱該博弈為完美信息博弈 （game of perfect information） 。上述兩個定義的差別在于對自然行 動信息的描述。5.5 動態(tài)博弈的策略式表述a 相機選擇 （contingent play）動態(tài)博弈中參與人的策略是各自預(yù) 先設(shè)定的，在博弈的各階段，

21、針對各種 情況做出相應(yīng)決策。即“等待”博弈到 達(dá)自己的信息集（包含一個或多個決策結(jié))后再決定如何行動。在策略式表述博弈中，參與人似乎 是博弈開始之前就制定出了一個完全的 相機選擇，即“如果發(fā)生，我將選 擇”。b從擴(kuò)展式表述構(gòu)造戰(zhàn)略式表述若把B的信息集從左到右排列，上述四 個純策略可以簡單記為開發(fā)，開發(fā)開發(fā)， 不開發(fā)不開發(fā)，開發(fā)不開發(fā)，不開發(fā)。 上面四個純策略含義：當(dāng) A選擇開發(fā)時，B 選擇大括號中前面的策略；當(dāng)A選擇不開發(fā) 時，B選擇大括號中后面的策略。B的純策略為：開發(fā)，開發(fā)開發(fā)， 不開發(fā)不開發(fā)，開發(fā)不開發(fā)，不開發(fā)A的純策略為：Sa=(開發(fā)，不開發(fā))于是可以寫成策略式表述形式，為開發(fā)，開發(fā)開

22、發(fā)，不開發(fā)不開發(fā)，開發(fā)不開 發(fā)，不開發(fā)開發(fā)-3, -3-3, -31, 01, 0不開發(fā)0, 10, 00, 10, 0? 在擴(kuò)展式表述博弈中，所有 n個參與人的一個純戰(zhàn)略組 合S=(Si,s)決定了博弈樹 上的一個路徑。? 比如(開發(fā)，不開發(fā)，開 發(fā))決定了博弈的路徑為 A開發(fā) B不開發(fā)(1,0)5.6完全信息動態(tài)博弈納什均衡存在性 定理如果有限博弈是完美信息博弈，他 還有一個純戰(zhàn)略納什均衡(Zermelo,1913)。5.7逆向歸納法：a逆向歸納法求解策略：從動態(tài)博弈 的最后一個階段出發(fā)， 對該參與人采用經(jīng)濟(jì) 理性原則進(jìn)行分析，逐步到推回前一個階段 相應(yīng)參與人的行動選擇，一直到第一階段的

23、分析方法。b逆向歸納法是求解完美信息動態(tài) 博弈的經(jīng)典方法。逆推歸納法是完 美信息動態(tài)博弈分析中使用最普遍 的方法。c與策略式分析比較：如果A選擇U,那么B的信息集不能達(dá)到，我們說 B的 信息集不在均衡路徑上(out-of-equilibriumpath)。此種情況下，B的選擇對A沒有什 么影響。因此，納什均衡對一個參與人在非 均衡信息集上的選擇沒有限制。但是，一個 參與人在非均衡信息集上的戰(zhàn)略可以影響 其他參與人在均衡信息集上的選擇。d逆向歸納法實質(zhì)上是重復(fù)剔除劣 戰(zhàn)略法在擴(kuò)展式博弈中的應(yīng)用。逆 向歸納法適不用于無限博弈和不完 美信息博弈。逆向歸納法剔除了非理性”的均衡策略5.8子博弈完美均衡

24、(子博弈精煉納什 均衡) 子博弈概念：一個擴(kuò)展式博弈的子博 弈G由一個決策結(jié)x和所有該決策結(jié)的后續(xù) 結(jié)T(x)組成，它滿足下列條件：x是一個單結(jié)信息集，即h(x)=x;對于所有的T(x)中的x如果x與 x同屬于一個信息集， 則x 也在T(x)中。需要說明的是，G本身是自己的一個子 博弈。 子博弈完美納什均衡(子博弈精煉納 什均衡)擴(kuò)展式博弈的一個戰(zhàn)略組合 s*=(S1*,s*, ,*)是一個子博弈完美納什 均衡，如果它是原博弈的納什均衡。它在每一個子博弈上都是納什均衡 納什均衡與子博弈精煉納什均衡的 關(guān)系前面分析說明，一個特定的納什均衡決 定了原博弈樹上唯一的一條路徑，這條路徑稱為“均衡路徑”

25、(equilibrium path)。相對該納什均衡，其他路徑稱為非均衡 路徑(out-of-equilibrium path) 。在每一個子博弈上給出 納什均衡意味著，構(gòu)成子博弈納什 均衡的戰(zhàn)略不僅在均衡路徑的決策 結(jié)上是最優(yōu)的，同時在非均衡路徑 的決策結(jié)上也是最優(yōu)的。對于有限完美信息博弈， 前面介紹的逆推歸納法得出的納什 均衡即是子博弈精煉納什均衡。六) 多階段靜態(tài)博弈6.1 該類模型中至少在某個階 段參與人同時選擇其決策。這類模型實質(zhì)上就 是完美信息動態(tài)博弈，因此 仍然可以采用逆推歸納法 進(jìn)行分析。因為存在同時選擇， 因此每個階段不再是單人 優(yōu)化問題，而是一個靜態(tài)博 弈。6.2 前向歸納法：前面已經(jīng)說 明，完美信息動態(tài)博弈的經(jīng)典 求解方法為逆序歸納法。還有一種分析方式， 就是 前向歸納法 (forward induction) 。前向歸納法由科爾博格和莫頓斯