第5講：“開金礦”博弈：完全且完美信息動態(tài)博弈的求解

第五講：“開金礦”博弈——完全且完美信息動態(tài)博弈的求解1“靜態(tài)博弈”與“動態(tài)博弈”在靜態(tài)博弈中，所有參與人同時行動（或者，行動有先后，但沒有人在自己行動之前觀測到別人的行動）；在動態(tài)博弈中，參與人的行動有先后順序，后行動者在自己行動之前能觀測到先行動者的行動。2Dynamicgamesaretheoneswherethetimingofdecisionmakingplaysarole.3靜態(tài)博弈戰(zhàn)略式表述（StrategicFormRepresentation）動態(tài)博弈擴展式表述（ExtensiveFormRepresentation）4戰(zhàn)略式表述

（StrategicFormRepresentation）（1）參與人集合；（2）每個參與人的戰(zhàn)略集合；（3）由戰(zhàn)略組合決定的每個參與人的支付。5擴展式表述

（ExtensiveFormRepresentation）參與人集合；參與人的行動順序（theorderofmoves）；參與人的行動空間（actionset）；參與人的信息集（Informationset）；參與人的支付函數；外生事件（自然的選擇）的概率分布。6博弈矩陣兩人有限戰(zhàn)略博弈的戰(zhàn)略式表述。博弈樹n人有限戰(zhàn)略博弈的擴展式表述。7Contents1.“開金礦博弈”問題的描述2.有法律保障的“開金礦博弈”3.法律保障不足的開金礦博弈4.相機選擇與策略中的可信性問題5.逆推歸納法6.子博弈7.子博弈完美納什均衡81.“開金礦博弈”問題的描述9“開金礦博弈”問題甲在開采一價值4千萬元的金礦時缺1千萬元資金，而乙正好有1千萬元資金可以投資。假設甲想說服乙將這1千萬元資金借給自己用于開礦，并允諾在采到金子后與乙對半分成，乙是否該將錢借給甲呢？假設金礦的價值是經過權威部門探測認定的，沒必要懷疑，則乙最需要關心的就是甲采到金子后是否會履行諾言跟自己平分，因為萬一甲采到金子后不但不跟乙平分，而且還賴帳或卷款潛逃，乙會連自己的本錢都收不回來。10“開金礦博弈”問題的擴展式表述11乙甲借不借（1，0）（2，2）分不分（0，4）博弈樹給出了有限博弈的幾乎所有信息。博弈樹的基本建筑材料（basicbuildingblock）：結（node）枝（branch）信息集（Informationset）12乙甲借不借（1，0）（2，2）分不分（0，4）博弈樹的基本建筑材料

（basicbuildingblock）結（node）包括“決策結”和“終點結”“決策結（decisionnode）”：參與人采取行動的時點?！敖K點結（terminalnode）”：博弈行動路徑的終點。13乙甲借不借（1，0）（2，2）分不分（0，4）博弈樹的基本建筑材料

（basicbuildingblock）枝（branch）在博弈樹上，“枝”是從一個決策結到它的直接后續(xù)結的連線（有時用箭頭表述），每一個枝代表參與人的一個行動選擇。14乙甲借不借（1，0）（2，2）分不分（0，4）博弈樹的基本建筑材料

（basicbuildingblock）信息集（Informationset）博弈樹上的所有決策結分割成不同的信息集。每個信息集是決策結集合的一個子集，該子集包括所有滿足下列條件的決策結：（1）每一個決策結都是同一參與人的決策結；（2）該參與人知道博弈進入該集合的某個決策結，但不知道自己究竟處于哪一個決策結。15乙甲借不借（1，0）（2，2）分不分（0，4）博弈樹的基本建筑材料

（basicbuildingblock）信息集（Informationset）引入信息集的目的是描述下列情況：當一個參與人要做出決策時他可能并不知道“之前”發(fā)生的所有事情。16乙甲借不借（1，0）（2，2）分不分（0，4）完美信息博弈

（gameofperfectinformation）一個信息集可能包含多個決策結，也可能包含一個決策結。只包含一個決策結的信息集稱為“單結（singleton）信息集”。如果博弈樹的所有信息集都是單結的，該博弈稱為“完美信息博弈（gameofperfectinformation）”。完美信息博弈意味著博弈中沒有任何兩個參與人同時行動，并且所有后行動者能確切知道前行動者選擇了什么行動，所有參與人觀測到自然的行動。17乙甲借不借（1，0）（2，2）分不分（0，4）分析博弈問題時的一般假設博弈方都是以自身利益（得益）最大化為目的，即他們不考慮道德因素，除非能把道德因素折算成數量化的效用綜合進得益中。18乙甲借不借（1，0）（2，2）分不分（0，4）“開金礦博弈”問題的分析【結論】：甲在第二階段選擇“不分”；乙在第一階段選擇“不借”。19乙甲借不借（1，0）（2，2）分不分（0，4）對乙來說，本博弈中甲有一個“不可信”的允諾。

20乙甲借不借（1，0）（2，2）分不分（0，4）信任？“什么叫信心？當一個小孩子被父母拋向空中，他在空中咯咯地笑，這就是信心。什么叫信靠？當一個小孩子看到可怕的怪物，立即撲向父母的懷中，這就是信靠?！?1有限博弈如果一個擴展式表述博弈有有限個信息集，每個信息集上參與人有有限個行動選擇，我們說這個博弈是有限博弈。22乙甲借不借（1，0）（2，2）分不分（0，4）有限完美信息博弈定理（Zermelo，1913；Kuhn，1953）：一個有限完美信息博弈有一個純策略納什均衡。23乙甲借不借（1，0）（2，2）分不分（0，4）由于有不可信的允諾，使得甲、乙的合作最終成為不可能，這不是最佳結局。那么，有沒有辦法使甲的允諾變成可信的，從而使乙愿意選擇“借”，然后甲遵守諾言選擇“分”，最終增加雙方的利益呢？24乙甲借不借（1，0）（2，2）分不分（0，4）2.有法律保障的“開金礦博弈”25有法律保障的“開金礦博弈”

如果讓乙在甲違約時可以用法律武器，即“打官司”來保護自己的利益，則情況會有所不同。26（2，2）乙甲借不借（1，0）分不分（0，4）乙（1，0）打不打有法律保障的“開金礦博弈”分析表明，在乙的利益受到法律保障的情況下，甲的“分”錢允諾變成可信的會信守的允諾。27（2，2）乙甲借不借（1，0）分不分（0，4）乙（1，0）打不打有法律保障的“開金礦博弈”分析表明，在乙的利益受到法律保障的情況下，甲的“分”錢允諾變成可信的會信守的允諾。這樣，乙第一階段選擇“借”就成了合理的選擇。最終結果是乙在第一階段選擇“借”，甲在第二階段選擇“分”，從而博弈結束，雙方各得2千萬元。28（2，2）乙甲借不借（1，0）分不分（0，4）乙（1，0）打不打有法律保障的“開金礦博弈”分析表明，在乙的利益受到法律保障的情況下，甲的“分”錢允諾變成可信的會信守的允諾。這樣，乙第一階段選擇“借”就成了合理的選擇。最終結果是乙在第一階段選擇“借”，甲在第二階段選擇“分”，從而博弈結束，雙方各得2千萬元。此時，乙的完整策略是“第一階段選擇‘借’，若第二階段甲選擇‘不分’，第三階段選擇‘打’”，甲的完整策略是“第二階段選擇‘分’”。29有法律保障的“開金礦博弈”分析表明，在乙的利益受到法律保障的情況下，甲的“分”錢允諾變成可信的會信守的允諾。這樣，乙第一階段選擇“借”就成了合理的選擇。最終結果是乙在第一階段選擇“借”，甲在第二階段選擇“分”，從而博弈結束，雙方各得2千萬元。此時，乙的完整策略是“第一階段選擇‘借’，若第二階段甲選擇‘不分’，第三階段選擇‘打’”，甲的完整策略是“第二階段選擇‘分’”。這就是這個三階段動態(tài)博弈的解。3031（2，2）乙甲借不借（1，0）分不分（0，4）乙（1，0）打不打在一個由都有私心、都重視自身利益的成員所組成的社會中，完善公正的法律制度不但能夠保障社會的公平，而且還能提高社會經濟活動的效率，是實現最優(yōu)效率的社會分工合作的重要保障。32要充分保障社會公平和經濟效率，法律制度必須要滿足兩方面的要求：一是，對守法者有足夠的保護力度；二是，對違法者有足夠的震懾作用。333.法律保障不足的開金礦博弈34法律保障不足的開金礦博弈

分析表明：乙在第三階段選擇“打”官司的威脅不是可信的，而是一種“不可信的（incredible）”“空頭威脅（emptythreat）”。所以乙在第一階段選擇“不借”。35（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打4.相機選擇與策略中的可信性問題36通過開金礦博弈的幾個不同版本，我們清楚了在動態(tài)博弈中，各個博弈方的選擇和博弈的結果，與各個博弈方在各個階段選擇各種行為的可信程度有很大關系。37可信性問題是動態(tài)博弈分析中的一個中心問題有時候，雖然有些博弈方很想或聲稱要采取某種行動，但是如果這些行動缺乏以經濟利益為基礎的可信性，那么這些想法或聲明最終就不會有真正的效力，就只能落空。38通過開金礦博弈的幾個不同版本，說明了動態(tài)博弈中的相機選擇引出的可信性問題，以及可信性在動態(tài)博弈分析中的關鍵意義。39動態(tài)博弈中的策略動態(tài)博弈中博弈方的策略是他們自己預先設定的，在各個博弈階段，針對各種情況的相應行為選擇的計劃。40動態(tài)博弈中的“相機選擇”問題動態(tài)博弈中博弈方的策略實際上并沒有強制力，而且實施起來有一個過程，因此只要符合博弈方自己的利益，他們完全可以在博弈過程中改變計劃。我們稱這種問題為動態(tài)博弈中的“相機選擇”（contingentplay）問題。41策略中的“可信性”問題相機選擇的存在使得博弈方的策略中，所設定的各個階段、各種情況下會采取行為的“可信性”（credibility）有了疑問。也就是說，各個博弈方是否會真正、始終按照自己的策略所設定的方案行為，還是可能臨時改變自己的行動方案呢？不同版本的開金礦博弈給出了實際案例。42相機選擇與策略中的可信性問題由于動態(tài)博弈中博弈方的策略是多階段的行動計劃，實施起來有一個過程，而且又沒有強制力，因此博弈方完全可以在博弈過程中改變計劃，我們稱這種問題為“相機選擇”問題。相機選擇的存在使得動態(tài)博弈中各博弈方策略設定的行為選擇的“可信性”有了疑問。43“破釜沉舟”——完全承諾（Totalcommitment）445.逆推歸納法45逆推歸納法我們前面引入“可信性”問題時，對不同版本的“開金礦博弈”問題的分析結論都是正確的，對博弈方的選擇和博弈結果都做出了正確的判斷，都排除了博弈方不可信的行為選擇。之所以能做到這一點，根本原因是采用了一種分析動態(tài)博弈的有效方法――“逆推歸納法”（BackwardsInduction）。這種方法的表現形式為：從動態(tài)博弈的最后一個階段博弈方的行為開始分析，逐步倒推回前一個階段相應博弈方的行為選擇，一直到第一個階段。46法律保障不足的開金礦博弈第一步：分析第三階段乙是否打官司的選擇，由于“打”官司比“不打”官司損失更大，他必然會選擇“不打”官司。47（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打法律保障不足的開金礦博弈第一步：分析第三階段乙是否打官司的選擇，由于“打”官司比“不打”官司損失更大，他必然會選擇“不打”官司。因此一旦博弈進行到這個階段，結果必然是乙選擇“不打”官司，雙方得益為（0，4）。48（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打法律保障不足的開金礦博弈第一步：分析第三階段乙是否打官司的選擇，由于“打”官司比“不打”官司損失更大，他必然會選擇“不打”官司。因此一旦博弈進行到這個階段，結果必然是乙選擇“不打”官司，雙方得益為（0，4）。所以在分析前兩個階段的博弈時，原來的三階段博弈與下頁的兩階段博弈是完全等價的。49（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打法律保障不足的開金礦博弈第二步：繼續(xù)對該兩階段博弈運用逆推歸納法，可知甲在第二階段選擇“不分”，因此博弈可進一步化為下頁的等價博弈。50（2，2）乙甲借不借（1，0）分不分（0，4）法律保障不足的開金礦博弈第三步：這個等價博弈已經是一個單人博弈了，可知乙將選擇“不借”。51乙借不借（1，0）（0，4）逆推歸納法逆推歸納法事實上就是把多階段動態(tài)博弈轉化為一系列的單人博弈，通過對一系列單人博弈的分析，確定各博弈方在各自階段的選擇，最終對動態(tài)博弈結果（包括，博弈的路徑、各博弈方的得益）做出綜合判斷，歸納出各博弈方各階段的選擇，從而得出各博弈方在整個動態(tài)博弈中的策略。52逆推歸納法逆推歸納法確定的各個博弈方在各階段的選擇，都是建立在后續(xù)階段各個博弈方理性選擇基礎上的，因此自然排除了包含不可信的威脅或允諾的可能性，因此它得出的結論是比較可靠的，確定的各個博弈方的策略組合是有穩(wěn)定性的。53逆推歸納法逆推歸納法是在動態(tài)博弈分析中使用得最普遍的方法，在分析完全且完美信息動態(tài)博弈中非常有用。54逆推歸納法的邏輯基礎動態(tài)博弈中先行為的理性的博弈方，在前面階段選擇行為時必須會先考慮后行為博弈方在后面階段中將會怎樣選擇行為，只有在博弈的最后一個階段選擇的，不再有后繼階段牽制的博弈方，才能直接做出明確選擇。而當后面階段博弈方的選擇確定以后，前一階段博弈方的行為也就容易確定了。55逆推歸納法的一般方法從動態(tài)博弈的最后一個階段開始分析，每一次確定出所分析階段博弈方的選擇和路徑，然后再確定前一個階段的博弈方選擇和路徑。逆推歸納到某個階段，那么這個階段及以后的博弈結果就可以肯定下來，該階段的選擇節(jié)點等于一個結束終端。我們可以用不包含該階段與其后所有階段博弈的等價博弈來代替原來的博弈。566.子博弈（Subgame）子博弈是動態(tài)博弈分析中一個非常關鍵的概念，它是動態(tài)博弈中滿足一定條件的局部所構成的次級博弈。57子博弈（Subgame）的定義由一個動態(tài)博弈第一階段以外的某階段開始的后續(xù)博弈階段構成的，有初始信息集和進行博弈所需要的全部信息，能夠自成一個博弈的原博弈的一部分，稱為原動態(tài)博弈的一個“子博弈”。58定義：一個擴展式表述博弈的子博弈G由一個決策結x和所有該決策結的后續(xù)結T(x)(包括終點結)組成，它滿足下列條件：（1）x是一個單結信息集，即包含決策結x的信息集h(x)={x}；（2）對于所有的x’∈T(x)，如果x”∈h(x’)，那么x”∈T(x)。59法律保障不足的開金礦博弈如果乙在第一階段選擇了“借”，意味著這個動態(tài)博弈進行到了甲作選擇的第二階段。此時甲面臨的是一個在乙已經借錢給他的前提下，自己選擇是否分成，然后再由乙選擇是否打官司的兩階段動態(tài)博弈問題。60（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打法律保障不足的開金礦博弈按照子博弈的定義，在前頁介紹的子博弈中，當甲選擇“不分”，輪到乙選擇“打”還是“不打”的第三階段，是前頁介紹的子博弈的子博弈，我們稱后面這個子博弈為原博弈的“二級子博弈”。61（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打子博弈（續(xù)）一般地，當動態(tài)博弈的階段數更多時，還可能存在更多層次的子博弈。62（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打子博弈（續(xù)）子博弈在動態(tài)博弈中是很普遍的，完美信息多階段動態(tài)博弈基本上都有一級或多級子博弈。63（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打子博弈（續(xù)）并不是動態(tài)博弈的任何部分都能構成子博弈。子博弈不能包括原博弈的第一階段。并不是所有多階段動態(tài)博弈都有子博弈。在不完美信息動態(tài)博弈中可能不存在子博弈。647.子博弈完美納什均衡（SubgamePerfectNashequilibrium）65在動態(tài)博弈分析中，納什均衡不能排除不可信的行為選擇，不是真正具有穩(wěn)定性的均衡概念，因此需要發(fā)展出一個新的均衡概念，它能排除不可信的行為選擇。66子博弈完美納什均衡的定義如果在一個完美信息的動態(tài)博弈中，各博弈方的策略構成的一個策略組合滿足，在整個動態(tài)博弈及它的所有子博弈中都構成納什均衡，那么這個策略組合稱為該動態(tài)博弈的一個“子博弈完美納什均衡”（SubgamePerfectNashEquilibrium）。67子博弈完美納什均衡（續(xù)）提出“子博弈完美納什均衡”這個概念的價值在于它能夠排除納什均衡策略中不可信的威脅或承諾，因此它是真正穩(wěn)定的。68子博弈完美納什均衡（續(xù)）“子博弈完美納什均衡”為什么能夠排除策略組合中的不可信行為呢？雖然包含不可信行為選擇的策略組合可以構成整個博弈的納什均衡，但其中的不可信行為選擇至少在博弈的某些子博弈中不符合博弈方的自身利益，因而不構成這些子博弈的納什均衡，因此要求在所有子博弈中都是納什均衡的子博弈完美納什均衡就排除了其中存在不可信行為選擇的策略組合，從而在動態(tài)博弈分析中具有真正的穩(wěn)定性。69子博弈完美納什均衡（續(xù)）雙方的策略組合“乙第一階段選擇‘借’，第三階段選擇‘打’；甲第二階段選擇‘分’”是整個博弈的一個納什均衡。但是，這個策略組合中乙的策略要求乙在第三階段單人博弈構成的子博弈中選擇“打”，不是該子博弈的一個納什均衡，因此根據子博弈完美納什均衡的定義判斷，這個策略組合確實不是一個子博弈完美納什均衡。這也正是上述納什均衡策略組合不穩(wěn)定的根源。70（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打子博弈完美納什均衡（續(xù)）策略組合“乙在第一階段選擇‘不借’，如果有第三階段選擇則選‘不打’；甲如果有第二階段則選‘不分’”是子博弈完美納什均衡。因為該策略組合的雙方策略不僅在整個博弈中構成納什均衡，而且在兩級子博弈中也都構成納什均衡，從而不存在任何不可信的威脅或承諾，根據子博弈完美納什均衡的定義，該策略組合構成這個動態(tài)博弈的一個子博弈完美納什均衡。71（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打子博弈完美納什均衡（續(xù)）當兩博弈方按照子博弈完美納什均衡策略組合“乙在第一階段選擇‘不借’，如果有第三階段選擇則選‘不打’；甲如果有第二階段則選‘不分’”行為時，實際上不會進行到博弈的第二、第三階段，兩個博弈方在第二、第三階段的行為實際上不會發(fā)生。72（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打子博弈完美納什均衡（續(xù)）我們稱此時第二階段甲的選擇節(jié)點和第三階段乙的選擇節(jié)點為“不在均衡路徑上”（out-of-equilibriumpath；off-equilibriumpath）的，兩博弈方的策略中在這兩個節(jié)點的選擇稱為“不在均衡路徑上的選擇”。73（2，2）乙甲借不借（1，0）分不分（0，4）乙（－1，0）打不打子博弈完美納什均衡（續(xù)）一個子博弈完美納什均衡必須對博弈方在所有選擇節(jié)點處的選擇做出規(guī)定，包括最終不在均衡路徑上的節(jié)點，而且不管是在均衡路徑上的選擇還是不在均衡路徑上的選擇，都必須在相應子博弈中構成納什均衡，不能包含任何不可信的威脅或承諾，否則就不能保證一個策略組合是子博弈完美納什均衡。74“在每一個子博弈上給出納什均衡”構成子博弈精煉納什均衡的戰(zhàn)略不僅在均衡路徑的決策結上最優(yōu)，而且在非均衡路徑的決策結上也是最優(yōu)的。這是納什均衡與子博弈精煉納什均衡的實質區(qū)別所在。這里的要義是，戰(zhàn)略是參與人行動規(guī)則的完備描述，它要告訴參與人在每一種可預見的情況下（每一個決策結上）選擇什么行動，即使這種情況實際上并沒有發(fā)生（甚至參與人并不預測它會發(fā)生），因此，只有當一個戰(zhàn)略規(guī)定的行動規(guī)則在所有可能的情況下都是最優(yōu)的時，它才是一個合理的、可置信的戰(zhàn)略。（張維迎，2012，第99頁）75“序貫理性”

（sequentialrationality）子博弈精煉納什均衡就是剔除那些只有在特定情況下是合理的而在其他情況下并不合理的行動規(guī)則。博弈論專家常常使用“序貫理性”（sequentialrationality）指不論過去發(fā)生了什么，參與人在博弈的每一個時點上最優(yōu)化自己的決策。子博弈精煉納什均衡要求的正是參與人應該是序貫理性的。（張維迎，2012，第99頁）76子博弈完美納什均衡（續(xù)）子博弈完美納什均衡本身也是納什均衡，是比納什均衡更強的均衡概念。澤爾騰（Selten，1965）引入“子博弈精煉納什均衡（SubgamePerfectNashEquilibrium）”概念的目的是將那些包含不可置信威脅戰(zhàn)略的納什均衡從均衡中剔除，從而給動態(tài)博弈結果一個合理預測。簡單地說，子博弈精煉納什均衡要求均衡戰(zhàn)略的行為規(guī)則在每一個信息集上都是最優(yōu)的。（張維迎，2012，第96頁）77子博弈完美納什均衡（續(xù)）子博弈完美納什均衡在動態(tài)博弈分析中的地位與納什均衡在靜態(tài)博弈分析中一樣，是最核心的分析概念和基本著眼點。要對動態(tài)博弈做出有效的分析，首先必須找出它們的子博弈完美納什均衡，必須判斷一個策略組合是不是子博弈完美納什均衡。78子博弈完美納什均衡（續(xù)）求完美信息動態(tài)博弈的“子博弈完美納什均衡”最基本的方法就是逆推歸納法：引進子博弈和子博弈完美納什均衡之后，逆推歸納法事實上可以理解為：從動態(tài)博弈的最后一級子博弈開始，逐步找出博弈方在各級子博弈中的最優(yōu)選擇，最終找出動態(tài)博弈的子博弈完美納什均衡。79子博弈完美納什均衡（續(xù)）逆推歸納法與子博弈完美納什均衡之間在本質上是完全一致的，找出的策略組合一定是子博弈完美納什均衡。80對于有限完美信息博弈，逆推歸納法是求解子博弈精煉納什均衡的最簡便方法。因為有限完美信息博弈的每一個決策結都是一個單獨的信息集，每一個決策結都開始一個子博弈。為了求解子博弈精煉納什均衡，我們從最后一個子博弈開