博弈論：基本知識(shí)1.1定義:博弈論，又稱對(duì)策論，是使用嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型研究沖突對(duì)抗條件下最優(yōu)決策問題的理論，是研究競爭的邏輯和規(guī)律的數(shù)學(xué)分支。即，博弈論是研究決策主體在給定信息結(jié)構(gòu)下如何決策以最大化自己的效用，以及不同決策主體之間的均衡。1.2基本要素：參與人、各參與人的策略集、各參與人的收益函數(shù)，是博弈最重要的基本要素。1.3博弈的分類：博弈論根據(jù)其所采用的假設(shè)不同而分為合作博弈理論和非合作博弈理論。兩者的區(qū)別在于參與人在博弈過程中是否能夠達(dá)成一個(gè)具有約束力的協(xié)議(bindingagreement)。倘若不能，則稱非合作博弈(Non-cooperativegame)。合作博弈強(qiáng)調(diào)的是集體主義，團(tuán)體理性，是效率、公平、公正；而非合作博弈則主要研究人們在利益相互影響的局勢中如何選擇策略使得自己的收益最大，強(qiáng)調(diào)個(gè)人理性、個(gè)人最優(yōu)決策，其結(jié)果有時(shí)有效率，有時(shí)則不然。目前經(jīng)濟(jì)學(xué)家談到博弈論主要指的是非合作博弈，也就是各方在給定的約束條件下如何追求各自利益的最大化，最后達(dá)到力量均衡。博弈的劃分可以從參與人行動(dòng)的次序和參與人對(duì)其他參與人的特征、戰(zhàn)略空間和支付的知識(shí)、信息，是否了解兩個(gè)角度進(jìn)行。把兩個(gè)角度結(jié)合就得到了4種博弈：a、完全信息靜態(tài)博弈，納什均衡，Nash(1950)b、完全信息動(dòng)態(tài)博弈，子博弈精煉納什均衡，澤爾騰(1965)c、不完全信息靜態(tài)博弈，貝葉斯納什均衡，海薩尼(1967-1968)d、不完全信息動(dòng)態(tài)博弈，精煉貝葉斯納什均衡，澤爾騰(1975)Kreps,Wilson(1982)Fudenberg,Tirole(1991)1.4課程主要內(nèi)容：完全信息靜態(tài)博弈完全信息動(dòng)態(tài)博弈不完全信息靜態(tài)博弈機(jī)制設(shè)計(jì)合作博弈1.5博弈模型的兩種表示形式：策略式表述(Strategicform),擴(kuò)展式表述(Extensiveform)1.6占優(yōu)均衡：a、占優(yōu)策略：在博弈中如果不管其他參與人選擇什么策略，一個(gè)參與人的某個(gè)策略給他帶來的支付值始終高于其他策略，或至少不劣于其他策略，則稱該策略為該參與人的嚴(yán)格占優(yōu)策略或占優(yōu)策略。對(duì)于所有的s-i，si*稱為參與人i的嚴(yán)格占優(yōu)戰(zhàn)略，如果滿足：ui(si*,s-i)>ui(si',s-i)"s-i,"si'1si*b、占優(yōu)均衡：一個(gè)博弈的某個(gè)策略組合中，如果對(duì)應(yīng)的所有策略都是各參與人的占優(yōu)策略，則稱該策略組合為該博弈的一個(gè)占優(yōu)均衡。1.7重復(fù)易IJ除嚴(yán)劣策略均衡：a、“嚴(yán)劣”和“弱劣”的含義：設(shè)耳和耳是參與人i可選擇的兩個(gè)策略，若對(duì)其他參與人的任意策略組合s-i,均成立ui(si',s-i)<ui(si-,s-i)，則說策略氣，嚴(yán)劣于策略氣，。上面式子中，若將“<”改為M,則說策略氣，弱劣于策略si-Ob、定義：重復(fù)剔除嚴(yán)格策略就是各參與人在其各自策略集中，不斷剔除嚴(yán)劣策略…如果最終各參與人僅剩下一個(gè)策略，則該策略組合就被稱為重復(fù)剔除嚴(yán)劣策略均衡。（二）：納什均衡（NashEquilibrium）2.1納什均衡定義：對(duì)于一個(gè)策略式表述的博弈G={N,§,upieN},稱策略組合s*=（s1）...氣，…，sn）是一個(gè)納什均衡，如果對(duì)于每一個(gè)igN,sr是給定其他參與人選擇s_i*={s1*,&_〔*,si+1*,...，sn*}情況下參與人i的最優(yōu)策略（經(jīng)濟(jì)理性策略），即：ui（si*,s-i*）>ui（si,號(hào)），對(duì)于任意的sieSi,任意的ieN均成立。通俗定義：納什均衡是一種策略組合，給定對(duì)手的策略，每個(gè)參與人選擇自己的最優(yōu)策略。納什均衡是一種穩(wěn)定的策略組合：當(dāng)所有參與人的選擇公開以后，每個(gè)人都滿意自己作出了正確的選擇；沒有人能得到更好的結(jié)果了。在博弈論中這種結(jié)果被稱為納什均衡（NE）。2.2定理：Nash在1950年證明：任何有限博弈,都至少存在一個(gè)NEExistenceofNashEquilibrium。即在一個(gè)有n個(gè)參與人的策略式博弈G={S1,...,Sn;u1,...,un}中，如果n是有限的，且Si是有限集（i=1,...,n），則該博弈至少存在一個(gè)納什均衡（在混合策略意義下）Wilson（1971）證明，幾乎所有有限博弈，都存在有限奇數(shù)個(gè)NE，包括純策略NE和混合策略NEOOddnessTheorem2.3納什均衡、占優(yōu)均衡、重復(fù)剔除嚴(yán)劣策略均衡的關(guān)系定理a每一個(gè)占優(yōu)均衡、重復(fù)剔除嚴(yán)劣策略均衡一定是納什均衡，但反過來不一定成立；定理b納什均衡一定不能通過重復(fù)剔除嚴(yán)劣策略方法剔除。2.4劃線法先找出自己針對(duì)其他博弈方每種策略或策略組合（對(duì)多人博弈）的最佳對(duì)策，即自己的可選策略中與其他博弈方的策略或策略組合配合，給自己帶來最大得益的策略（這種相對(duì)最佳策略總是存在的，不過不一定唯一），然后在此基礎(chǔ)上，通過對(duì)其他博弈方策略選擇的判斷，包括對(duì)其他博弈方對(duì)自己策略判斷的判斷等，預(yù)測博弈的可能結(jié)果和確定自己的最優(yōu)策略。這就是劃線法。2.5箭頭法箭頭法對(duì)于理解博弈關(guān)系很有好處，是尋找相對(duì)穩(wěn)定性策略組合的分析方法。對(duì)博弈中的每個(gè)策略組合進(jìn)行分析，考察在每個(gè)策略組合處各個(gè)參與方能否通過改變自己的策略而增加得益。如能，則從所分析的策略組合對(duì)應(yīng)的得益數(shù)組引一箭頭到改變策略后策略組合對(duì)應(yīng)的得益數(shù)組。最后綜合對(duì)每個(gè)策略組合的分析情況，形成對(duì)博弈結(jié)果的判斷。劃線法和箭頭法的結(jié)果是一致的，可以相互替代。（三）：混合策略（MixedStrategies）納什均衡3.1定義：混合策略的定義：在博弈G={N,Si,ui,ieN}中，假設(shè)參與人i的純策略構(gòu)成的策略集合為Si={si1,...,sik}，若參與人i以概率分布pi=（pi1,...,pik）在其k個(gè)可選策略中隨機(jī)選擇“策略”，稱這樣的選擇方式為混合策略。這里，0<pij<1,對(duì)于j=1,...,k都成立，且有,pi1+...+pik=1o純策略可看成特殊的混合策略。上述定義是在有限博弈前提下進(jìn)行的。3.2混合策略意義下策略組合的表述{x1eX1,…，xneXn}其中Xi,i=1,…，n表示參與人i所有純策略生成的概率空間，xi為參與人i的一個(gè)具體混合策略猜硬幣博弈的一個(gè)混合策略就可記為{(1/2,1/2),(1/2,1/2)}3.3VNM效用函數(shù)(VonNeumannandMorgenstern馮?諾依曼和摩根斯坦)如果某個(gè)隨機(jī)變量X以概率Pi取值xi,i=1,2,...,n，而某人在確定地得到xi時(shí)的效用為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、每個(gè)參與人有一個(gè)(純)策略集合c、對(duì)于每一個(gè)參與人來說，由所有參與人純策略組合構(gòu)成的風(fēng)險(xiǎn)結(jié)果空間，存在一個(gè)v-N-M效用3.5混合策略意義下的納什均衡定義：對(duì)于博弈G={N,Si,ui,ieN}，基于v-N-M效用的混合策略組合a*是一個(gè)納什均衡，若對(duì)于每一個(gè)i,以及i的任意一個(gè)混合策略ai，a*對(duì)應(yīng)的期望支付至少和(ai，a*-i)的期望支付一樣大換句話說，稱混合策略組合a*是一個(gè)納什均衡，如果沒有一個(gè)參與人通過偏離策略a*i實(shí)現(xiàn)支付的增加3.6一個(gè)定理對(duì)于N-人靜態(tài)博弈問題，設(shè)混合策略納什均衡對(duì)應(yīng)的策略組合為(Xi,X-i)。對(duì)于任意的i，若最優(yōu)混合策略為Xi={x1,...,xl，0...0}(不失一般性，假設(shè)前l(fā)個(gè)分量嚴(yán)格大于0)，記分量xk(k=1,...,l)對(duì)應(yīng)的純策略sk,則對(duì)于參與人i而言，sk與其他參與人的最優(yōu)混合策略組合X-i形成的局勢的收益值,等于納什均衡混合策略組合(Xi,X-i)的收益值。即ui(sk,X-i)=ui(Xi,X-i)成立，k=1,...,l3.7方法：a、求解混合策略均衡可以用期望收益等值法b、2x2雙矩陣博弈的圖解法:反應(yīng)函數(shù)的三個(gè)交點(diǎn)即是納什均衡:多重納什均衡解及其分析4.1帕雷托占優(yōu)均衡帕雷托占優(yōu)均衡的含義是：在多個(gè)納什均衡中，若存在一個(gè)納什均衡，其支付結(jié)果針對(duì)每個(gè)參與人而言都嚴(yán)格優(yōu)于其它納什均衡，則該納什均衡是帕雷托占優(yōu)納什均衡。4.2風(fēng)險(xiǎn)占優(yōu)均衡(risk-dominantequilibrium)參與人對(duì)風(fēng)險(xiǎn)占優(yōu)均衡的選擇傾向，有—種強(qiáng)化的機(jī)制。當(dāng)部分或所有參與人選擇風(fēng)險(xiǎn)占優(yōu)均衡的可能性增強(qiáng)的時(shí)候，任一參與人選擇帕雷托占優(yōu)均衡策略的期望支付會(huì)進(jìn)一步減小，而這又使得帕雷托占優(yōu)均衡策略的支付更小，從而形成一種選擇風(fēng)險(xiǎn)占優(yōu)均衡策略的正反饋機(jī)制，并使其出現(xiàn)的概率越來越大。當(dāng)參與人數(shù)目增加時(shí)，選擇合作的風(fēng)險(xiǎn)將會(huì)更大，可借助該點(diǎn)考慮招標(biāo)機(jī)制如何減少投標(biāo)方勾結(jié)問題。上述問題是我們知道建立誠信機(jī)制社會(huì)的重要意義。上述問題引出一個(gè)博弈相關(guān)分支為協(xié)調(diào)博弈(coordinationgame)4.3聚點(diǎn)均衡由實(shí)際問題抽象出來的博弈模型中，更多的一類問題是：多個(gè)納什均衡間不存在帕雷托占優(yōu)關(guān)系或明顯的風(fēng)險(xiǎn)占優(yōu)關(guān)系，如夫妻愛好問題的兩個(gè)純策略均衡。這時(shí)如何預(yù)測哪一個(gè)納什均衡會(huì)出現(xiàn)是一個(gè)很有意義的問題以夫妻愛好博弈為例，在實(shí)際中往往二人很默契地知道如何進(jìn)行博弈，雙方往往知道怎么進(jìn)行選擇策略，且能夠相互了解（這里面排除了互相協(xié)商后達(dá)成的一致）實(shí)際博弈中參與人往往會(huì)利用博弈模型以外的信息，實(shí)現(xiàn)對(duì)特定博弈均衡一致關(guān)注的“聚點(diǎn)”這些信息如：參與人共同的文化背景或規(guī)范，共同的知識(shí)，具有特定意義事物的特征，某些特殊的數(shù)量、位置關(guān)系等聚點(diǎn)均衡確實(shí)反映了人們在多重納什均衡選擇中的某些規(guī)律性，但因?yàn)樯婕耙蛩靥?，?duì)于一般博弈模型很難總結(jié)普遍規(guī)律，只能具體問題具體分析聚點(diǎn)：人們通常會(huì)協(xié)調(diào)彼此的行為。（你弱他就強(qiáng)）；先例產(chǎn)生的影響遠(yuǎn)大于邏輯或者法律效力；人們總是樂于安守現(xiàn)狀或接受自然形成的界線（三八線）相關(guān)均衡（correlatedequilibrium）實(shí)際上，在現(xiàn)實(shí)中遇到選擇困難時(shí)，特別是在長期中反復(fù)遇到相似選擇難題時(shí)，常會(huì)通過收集更多信息，形成特定的機(jī)制和規(guī)則，為某種形式的制度安排等主動(dòng)尋找思路。相關(guān)均衡就是這樣的一種均衡選擇機(jī)制。對(duì)于實(shí)際中比較復(fù)雜的博弈問題，參與人是否有能力設(shè)計(jì)這種機(jī)制，并且有足夠能力理解、信任這種機(jī)制，是有一定疑問的。相關(guān)均衡作為社會(huì)經(jīng)濟(jì)制度創(chuàng)新的一種解釋也許更有意義。防共謀均衡（coalition-proofequilibrium）定義：如果一個(gè)博弈的某個(gè)策略組合滿a、沒有任何單個(gè)參與人的“串通”會(huì)改變博弈的結(jié)果，即單獨(dú)改變策略無利可圖（該策略組合是納什均衡，b、給定選擇偏離的參與人有再次偏離的自由時(shí)，沒有任何兩個(gè)參與人通過“串通”改變博弈的結(jié)果。c、依此類推，直到所有參與人都參加的串通也不會(huì)改變博弈的結(jié)果。滿足上述要求的均衡策略組合稱為“防共謀均衡”在有多個(gè)參與人的博弈中，若部分參與人通過某種形式的默契或串通形成小團(tuán)體，可能得到比不串通個(gè)大的支付。這就是多人博弈的共謀問題。防共謀均衡是指這樣的一個(gè)納什均衡，在該均衡局勢下，少數(shù)參與人集合不能通過均衡策略的偏離，實(shí)現(xiàn)更好的局部利益。防共謀均衡是兩個(gè)以上參與人參加的博弈中，參與人在帕雷托占優(yōu)均衡中進(jìn)行合作思想的擴(kuò)展。（五）：動(dòng)態(tài)博弈5.1特點(diǎn)一類博弈行為通常需要參與人多步?jīng)Q策才能完成，具有明顯的階段性。博弈的結(jié)局、各參與人的收益由多階段決策結(jié)果確定。各參與人的決策有一定的順序。由于動(dòng)態(tài)博弈各參與人進(jìn)行決策具有明顯的階段性、行動(dòng)次序性，通常用擴(kuò)展式（extensiveform）表述法描述這些信息。5.2博弈的擴(kuò)展式表示口參與人集合：i=1,...,N。用N表示虛擬參與人“自然”；?:?自然的含義是某些外生的客觀概率分布事件口參與人的行動(dòng)順序（theorderofmoves）:描述各參與人在什么時(shí)候行動(dòng)；口參與人的行動(dòng)空間(actionset):在每次行動(dòng)時(shí)，參與人可選擇的行動(dòng)集合；口參與人的信息集(informationset):每次行動(dòng)時(shí)參與人知道什么；口參與人的收益函數(shù)：在行動(dòng)結(jié)束之后，每個(gè)參與人得到些什么?？谧匀贿x擇的概率分布(假定自然狀態(tài)是共同知識(shí)，口對(duì)于有限博弈，博弈樹是常用的表述方式。5.3博弈樹a若動(dòng)態(tài)博弈是有限博弈，則可用博弈樹表示該博弈。這里有限的含義是：各階段各參與人的行動(dòng)數(shù)目有限；博弈的階段數(shù)有限。b博弈樹的基本結(jié)構(gòu)為結(jié)點(diǎn)(nodes)。包括決策結(jié)及終點(diǎn)結(jié)。決策結(jié)是參與人采取行動(dòng)的時(shí)點(diǎn)；終點(diǎn)結(jié)是博弈行動(dòng)路徑的終點(diǎn)。枝(branches)。從一個(gè)決策結(jié)到它的直接后續(xù)結(jié)的連線，每一個(gè)枝代表參與人的一個(gè)行動(dòng)選擇。信息集。是決策結(jié)集合的一個(gè)子集。將博弈樹中某一決策者在某一行動(dòng)階段具有相同信息的所有決策結(jié)稱為一個(gè)信息集。注：每個(gè)決策結(jié)都是同一個(gè)參與人的決策結(jié)。該參與人知道博弈進(jìn)入該集合的某個(gè)決策結(jié)，但不知道自己究竟出于哪一個(gè)決策結(jié)(若該信息集有兩個(gè)或兩個(gè)以上元素)b5.4對(duì)于有限動(dòng)態(tài)博弈，若參與人對(duì)彼此在各決策結(jié)點(diǎn)的行動(dòng)集合，彼此的效用函數(shù)，歷史的行動(dòng)有著完全的了解，則稱這樣的博弈為完全信息動(dòng)態(tài)博弈。如果博弈樹的所有信息集都是單元素集，稱該博弈為完美信息博弈(gameofperfectinformation)。上述兩個(gè)定義的差別在于對(duì)自然行動(dòng)信息的描述。5.5動(dòng)態(tài)博弈的策略式表述a相機(jī)選擇(contingentplay)動(dòng)態(tài)博弈中參與人的策略是各自預(yù)先設(shè)定的，在博弈的各階段，針對(duì)各種情況做出相應(yīng)決策。即“等待”博弈到達(dá)自己的信息集(包含一個(gè)或多個(gè)決策結(jié))后再?zèng)Q定如何行動(dòng)。在策略式表述博弈中，參與人似乎是博弈開始之前就制定出了一個(gè)完全的相機(jī)選擇，即“如果......發(fā)生，我將選擇......”b從擴(kuò)展式表述構(gòu)造戰(zhàn)略式表述若把B的信息集從左到右排列，上述四個(gè)純策略可以簡單記為｛開發(fā)，開發(fā)｝｛開發(fā)，不開發(fā)｝｛不開發(fā)，開發(fā)｝｛不開發(fā)，不開發(fā)｝。上面四個(gè)純策略含義：當(dāng)A選擇開發(fā)時(shí)，B選擇大括號(hào)中前面的策略當(dāng)A選擇不開發(fā)時(shí)，B選擇大括號(hào)中后面的策略。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，0?:?在擴(kuò)展式表述博弈中，所有n個(gè)參與人的一個(gè)純戰(zhàn)略組合s=(s1,...,sn)決定了博弈樹上的一個(gè)路徑。?:?比如(開發(fā),{不開發(fā)，開發(fā)})決定了博弈的路徑為A9開發(fā)aBa不開發(fā)a(1,0)5.6完全信息動(dòng)態(tài)博弈納什均衡存在性定理口如果有限博弈是完美信息博弈，他還有一個(gè)純戰(zhàn)略納什均衡(Zermelo,1913)。5.7逆向歸納法：a逆向歸納法求解策略：從動(dòng)態(tài)博弈的最后一個(gè)階段出發(fā)，對(duì)該參與人采用經(jīng)濟(jì)理性原則進(jìn)行分析，逐步到推回前一個(gè)階段相應(yīng)參與人的行動(dòng)選擇，一直到第一階段的分析方法。b逆向歸納法是求解完美信息動(dòng)態(tài)博弈的經(jīng)典方法。逆推歸納法是完美信息動(dòng)態(tài)博弈分析中使用最普遍的方法。c與策略式分析比較：如果A選擇U,那么B的信息集不能達(dá)到，我們說B的信息集不在均衡路徑上(out-of-equilibriumpath)。此種情況下，B的選擇對(duì)A沒有什么影響。因此，納什均衡對(duì)一個(gè)參與人在非均衡信息集上的選擇沒有限制。但是，一個(gè)參與人在非均衡信息集上的戰(zhàn)略可以影響其他參與人在均衡信息集上的選擇。d逆向歸納法實(shí)質(zhì)上是重復(fù)剔除劣戰(zhàn)略法在擴(kuò)展式博弈中的應(yīng)用。逆向歸納法適不用于無限博弈和不完美信息博弈。逆向歸納法剔除了“非理性”的均衡策略5.8子博弈完美均衡(子博弈精煉納什均衡)子博弈概念：一個(gè)擴(kuò)展式博弈的子博弈G由一個(gè)決策結(jié)x和所有該決策結(jié)的后續(xù)結(jié)T(x)組成，它滿足下列條件：x是一個(gè)單結(jié)信息集，即h(x)={x};對(duì)于所有的T(x)中的x，如果x’與x’同屬于一個(gè)信息集，則x’也在T(x)中。需要說明的是，G本身是自己的一個(gè)子博弈。子博弈完美納什均衡(子博弈精煉納什均衡)擴(kuò)展式博弈的一個(gè)戰(zhàn)略組合s*=(s仍...膏，...，sn*)是一個(gè)子博弈完美納什均衡，如果它是原博弈的納什均衡。它在每一個(gè)子博弈上都是納什均衡納什均衡與子博弈精煉納什均衡的關(guān)系前面分析說明，一個(gè)特定的納什均衡決定了原博弈樹上唯一的一條路徑，這條路徑稱為“均衡路徑”(equilibriumpath)。相對(duì)該納什均衡，其他路徑稱為非均衡路徑(out-of-equilibriumpath)?？谠诿恳粋€(gè)子博弈上給出納什均衡意味著，構(gòu)成子博弈納什均衡的戰(zhàn)略不僅在均衡路徑的決策結(jié)上是最優(yōu)的，同時(shí)在非均衡路徑的決策結(jié)上也是最優(yōu)的?？趯?duì)于有限完美信息博弈，前面介紹的逆推歸納法得出的納什均衡即是子博弈精煉納什均衡。多階段靜態(tài)博弈6.1該類模型中至少在某個(gè)階段參與人同時(shí)選擇其決策?？谶@類模型實(shí)質(zhì)上就是完美信息動(dòng)態(tài)博弈，因此仍然可以采用逆推歸納法進(jìn)行分析?？谝?yàn)榇嬖谕瑫r(shí)選擇，因此每個(gè)階段不再是單人優(yōu)化問題，而是一個(gè)靜態(tài)博?:?定理：令G是階段博弈，6.2前向歸納法：前面已經(jīng)說明，完美信息