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

1、博弈論7 / 7（一）：基本知識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-cooperative game）。合作博

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

3、薩尼（1967-1968）d、不完全信息動態(tài)博弈，精煉貝葉斯納什均衡，澤爾騰（1975） Kreps, Wilson(1982) Fudenberg, Tirole(1991) 1.4課程主要內(nèi)容：完全信息靜態(tài)博弈 完全信息動態(tài)博弈 不完全信息靜態(tài)博弈 機(jī)制設(shè)計 合作博弈1.5博弈模型的兩種表示形式：策略式表述 (Strategic form), 擴(kuò)展式表述（Extensive form）1.6占優(yōu)均衡：a、占優(yōu)策略：在博弈中如果不管其他參與人選擇什么策略，一個參與人的某個策略給他帶來的支付值始終高于其他策略，或至少不劣于其他策略，則稱該策略為該參與人的嚴(yán)格占優(yōu)策略或占優(yōu)策略。 對于所有的s-

4、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和si是參與人i可選擇的兩個策略，若對其他參與人的任意策略組合s-i, 均成立ui(si, s-i) < ui(si, s-i), 則說策略si嚴(yán)劣于策略si。上面式子中，若將“<”改為“”，則說策略si弱劣于策略s

5、i。b、 定義：重復(fù)剔除嚴(yán)格策略就是各參與人在其各自策略集中，不斷剔除嚴(yán)劣策略如果最終各參與人僅剩下一個策略，則該策略組合就被稱為重復(fù)剔除嚴(yán)劣策略均衡。（二）：納什均衡（Nash Equilibrium）2.1納什均衡定義：對于一個策略式表述的博弈G= N,Si, ui, iN， 稱策略組合s*=(s1, si, , sn)是一個納什均衡，如果對于每一個i N, si*是給定其他參與人選擇s-i*=s1*, ,si-1*, si+1*, ,sn* 情況下參與人i的最優(yōu)策略（經(jīng)濟(jì)理性策略），即：ui(si*, s-i*) ui(si, s-i*), 對于任意的 siSi ,任意的 iN均成立。通

6、俗定義：納什均衡是一種策略組合，給定對手的策略，每個參與人選擇自己的最優(yōu)策略。納什均衡是一種穩(wěn)定的策略組合：當(dāng)所有參與人的選擇公開以后，每個人都滿意自己作出了正確的選擇；沒有人能得到更好的結(jié)果了。在博弈論中這種結(jié)果被稱為納什均衡（NE）。2.2定理：Nash在1950年證明：任何有限博弈，都至少存在一個NEExistence of Nash Equilibrium。即 在一個有n個參與人的策略式博弈G=S1,Sn; u1,un中，如果n是有限的，且Si是有限集（i=1,n），則該博弈至少存在一個納什均衡（在混合策略意義下）Wilson（1971）證明，幾乎所有有限博弈，都存在有限奇數(shù)個NE，包

7、括純策略NE和混合策略NE。Oddness Theorem2.3納什均衡、占優(yōu)均衡、重復(fù)剔除嚴(yán)劣策略均衡的關(guān)系定理a 每一個占優(yōu)均衡、重復(fù)剔除嚴(yán)劣策略均衡一定是納什均衡，但反過來不一定成立；定理b 納什均衡一定不能通過重復(fù)剔除嚴(yán)劣策略方法剔除。2.4劃線法先找出自己針對其他博弈方每種策略或策略組合（對多人博弈）的最佳對策，即自己的可選策略中與其他博弈方的策略或策略組合配合，給自己帶來最大得益的策略（這種相對最佳策略總是存在的，不過不一定唯一），然后在此基礎(chǔ)上，通過對其他博弈方策略選擇的判斷，包括對其他博弈方對自己策略判斷的判斷等，預(yù)測博弈的可能結(jié)果和確定自己的最優(yōu)策略。這就是劃線法。2.5箭頭

8、法箭頭法對于理解博弈關(guān)系很有好處,是尋找相對穩(wěn)定性策略組合的分析方法。對博弈中的每個策略組合進(jìn)行分析，考察在每個策略組合處各個參與方能否通過改變自己的策略而增加得益。如能，則從所分析的策略組合對應(yīng)的得益數(shù)組引一箭頭到改變策略后策略組合對應(yīng)的得益數(shù)組。最后綜合對每個策略組合的分析情況，形成對博弈結(jié)果的判斷。劃線法和箭頭法的結(jié)果是一致的，可以相互替代。（三）：混合策略（Mixed Strategies）納什均衡3.1定義：混合策略的定義：在博弈G=N, Si, ui, iN中，假設(shè)參與人i的純策略構(gòu)成的策略集合為Si=si1, sik，若參與人i以概率分布pi=(pi1, pik) 在其k個可選策

9、略中隨機(jī)選擇“策略”，稱這樣的選擇方式為混合策略。這里，0pij 1,對于j=1 , k都成立，且有, pi1+ pik=1。純策略可看成特殊的混合策略。上述定義是在有限博弈前提下進(jìn)行的。3.2混合策略意義下策略組合的表述x1X1, , xnXn，其中Xi , i =1, , n表示參與人i所有純策略生成的概率空間，xi為參與人i的一個具體混合策略猜硬幣博弈的一個混合策略就可記為（1/2, 1/2）,(1/2, 1/2)3.3VNM效用函數(shù)（Von Neumann and Morgenstern馮·諾依曼和摩根斯坦）如果某個隨機(jī)變量X以概率Pi取值xi，i=1,2,n，而某人在確定地

10、得到xi時的效用為u(xi)，那么，該隨機(jī)變量給他的效用便是： U(X) = P1u(x1) + P2u(x2) + . + Pnu(xn) 表示關(guān)于隨機(jī)變量X的期望效用。因此U(X)稱為期望效用函數(shù)，又叫做馮·諾依曼摩根斯坦效用函數(shù)（VNM函數(shù)）。3.4基于混合策略意義下的博弈策略式表述定義：基于(v-N-M效用的)策略式博弈由 a、參與人集合 b、每個參與人有一個（純）策略集合 c、對于每一個參與人來說，由所有參與人純策略組合構(gòu)成的風(fēng)險結(jié)果空間，存在一個v-N-M效用3.5混合策略意義下的納什均衡定義：對于博弈G= N, Si, ui, iN，基于v-N-M效用的混合策略組合*是

11、一個納什均衡，若對于每一個i, 以及i的任意一個混合策略i，*對應(yīng)的期望支付至少和(i，*-i )的期望支付一樣大換句話說，稱混合策略組合*是一個納什均衡，如果沒有一個參與人通過偏離策略*i 實(shí)現(xiàn)支付的增加3.6一個定理對于N-人靜態(tài)博弈問題，設(shè)混合策略納什均衡對應(yīng)的策略組合為(Xi , X i ) 。對于任意的i ,若最優(yōu)混合策略為Xi= x1,xl，00(不失一般性，假設(shè)前l(fā)個分量嚴(yán)格大于0)，記分量xk (k=1, l) 對應(yīng)的純策略sk, 則對于參與人i而言，sk與其他參與人的最優(yōu)混合策略組合X i 形成的局勢的收益值,等于納什均衡混合策略組合 (Xi, X i )的收益值。即ui (

12、sk, X i ) = ui (Xi, X i )成立 ， k=1, l3.7方法：a、求解混合策略均衡可以用期望收益等值法b、2×2雙矩陣博弈的圖解法:反應(yīng)函數(shù)的三個交點(diǎn)即是納什均衡（四）：多重納什均衡解及其分析4.1 帕雷托占優(yōu)均衡帕雷托占優(yōu)均衡的含義是：在多個納什均衡中，若存在一個納什均衡，其支付結(jié)果針對每個參與人而言都嚴(yán)格優(yōu)于其它納什均衡，則該納什均衡是帕雷托占優(yōu)納什均衡。4.2風(fēng)險占優(yōu)均衡(risk-dominant equilibrium)參與人對風(fēng)險占優(yōu)均衡的選擇傾向，有一種強(qiáng)化的機(jī)制。當(dāng)部分或所有參與人選擇風(fēng)險占優(yōu)均衡的可能性增強(qiáng)的時候，任一參與人選擇帕雷托占優(yōu)均衡策

13、略的期望支付會進(jìn)一步減小，而這又使得帕雷托占優(yōu)均衡策略的支付更小，從而形成一種選擇風(fēng)險占優(yōu)均衡策略的正反饋機(jī)制，并使其出現(xiàn)的概率越來越大。當(dāng)參與人數(shù)目增加時，選擇合作的風(fēng)險將會更大，可借助該點(diǎn)考慮招標(biāo)機(jī)制如何減少投標(biāo)方勾結(jié)問題。上述問題是我們知道建立誠信機(jī)制社會的重要意義。上述問題引出一個博弈相關(guān)分支為協(xié)調(diào)博弈(coordination game)4.3聚點(diǎn)均衡由實(shí)際問題抽象出來的博弈模型中，更多的一類問題是：多個納什均衡間不存在帕雷托占優(yōu)關(guān)系或明顯的風(fēng)險占優(yōu)關(guān)系，如夫妻愛好問題的兩個純策略均衡。這時如何預(yù)測哪一個納什均衡會出現(xiàn)是一個很有意義的問題以夫妻愛好博弈為例，在實(shí)際中往往二人很默契地知

14、道如何進(jìn)行博弈，雙方往往知道怎么進(jìn)行選擇策略，且能夠相互了解（這里面排除了互相協(xié)商后達(dá)成的一致）實(shí)際博弈中參與人往往會利用博弈模型以外的信息，實(shí)現(xiàn)對特定博弈均衡一致關(guān)注的“聚點(diǎn)”這些信息如：參與人共同的文化背景或規(guī)范，共同的知識，具有特定意義事物的特征，某些特殊的數(shù)量、位置關(guān)系等聚點(diǎn)均衡確實(shí)反映了人們在多重納什均衡選擇中的某些規(guī)律性，但因為涉及因素太多，對于一般博弈模型很難總結(jié)普遍規(guī)律，只能具體問題具體分析聚點(diǎn)：人們通常會協(xié)調(diào)彼此的行為。（你弱他就強(qiáng)）；先例產(chǎn)生的影響遠(yuǎn)大于邏輯或者法律效力；人們總是樂于安守現(xiàn)狀或接受自然形成的界線（三八線）4.4相關(guān)均衡(correlated equilibr

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

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

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

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

19、該集合的某個決策結(jié)，但不知道自己究竟出于哪一個決策結(jié)（若該信息集有兩個或兩個以上元素）。5.4對于有限動態(tài)博弈，若參與人對彼此在各決策結(jié)點(diǎn)的行動集合，彼此的效用函數(shù)，歷史的行動有著完全的了解，則稱這樣的博弈為完全信息動態(tài)博弈。如果博弈樹的所有信息集都是單元素集，稱該博弈為完美信息博弈(game of perfect information)。上述兩個定義的差別在于對自然行動信息的描述。5.5動態(tài)博弈的策略式表述a相機(jī)選擇(contingent play)動態(tài)博弈中參與人的策略是各自預(yù)先設(shè)定的，在博弈的各階段，針對各種情況做出相應(yīng)決策。即“等待”博弈到達(dá)自己的信息集（包含一個或多個決策結(jié)）后再決

20、定如何行動。在策略式表述博弈中，參與人似乎是博弈開始之前就制定出了一個完全的相機(jī)選擇，即“如果發(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ā)開發(fā)，不開發(fā)不開發(fā)，開發(fā)不開發(fā)，不開發(fā)開發(fā)-3，-3-3，-31，01，0不開發(fā)0，10，00，10，0v 在擴(kuò)

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

22、遍的方法。c與策略式分析比較：如果A選擇U,那么B的信息集不能達(dá)到，我們說B的信息集不在均衡路徑上(out-of-equilibrium path)。 此種情況下，B的選擇對A沒有什么影響。因此，納什均衡對一個參與人在非均衡信息集上的選擇沒有限制。但是，一個參與人在非均衡信息集上的戰(zhàn)略可以影響其他參與人在均衡信息集上的選擇。d逆向歸納法實(shí)質(zhì)上是重復(fù)剔除劣戰(zhàn)略法在擴(kuò)展式博弈中的應(yīng)用。逆向歸納法適不用于無限博弈和不完美信息博弈。逆向歸納法剔除了“非理性”的均衡策略5.8子博弈完美均衡（子博弈精煉納什均衡）子博弈概念：一個擴(kuò)展式博弈的子博弈G由一個決策結(jié)x和所有該決策結(jié)的后續(xù)結(jié)T(x)組成，它滿足下

23、列條件：x是一個單結(jié)信息集,即h(x)=x;對于所有的T(x)中的x，如果x與x同屬于一個信息集，則x也在T(x)中。需要說明的是，G本身是自己的一個子博弈。子博弈完美納什均衡（子博弈精煉納什均衡）擴(kuò)展式博弈的一個戰(zhàn)略組合s*=(s1*,si*,sn*)是一個子博弈完美納什均衡，如果它是原博弈的納什均衡。它在每一個子博弈上都是納什均衡納什均衡與子博弈精煉納什均衡的關(guān)系前面分析說明，一個特定的納什均衡決定了原博弈樹上唯一的一條路徑，這條路徑稱為“均衡路徑”(equilibrium path)。相對該納什均衡，其他路徑稱為非均衡路徑(out-of-equilibrium path)。q 在每一個子博弈上給出納什均衡意味著，構(gòu)成子博弈納什均衡的戰(zhàn)略不僅在均衡路徑的決策結(jié)上是最優(yōu)的，同時在非均衡路徑的決策結(jié)上也是最優(yōu)的。q 對于有限完美信息博弈，前面介紹的逆推歸納法得出的納什均衡即是子博弈精煉納什均衡。（六）多階段靜態(tài)博弈6.1該類模型中至少在某個階段參與人同時選擇其決策。q 這類模型實(shí)質(zhì)上就是完美信息動態(tài)博弈，因此仍然可以采用逆推歸納法進(jìn)行分析。q 因為存在同時選擇，因此每個階段不再是單人優(yōu)化問題，而是一個靜態(tài)博弈。6.2前向歸納法：前面已經(jīng)說明，完美信息動態(tài)博弈的經(jīng)典求解方法為逆序歸納法。q 還有一種分析