動態(tài)博弈學(xué)習(xí)

1、第8講 完美信息動態(tài)博弈第一節(jié)完美信息動態(tài)博弈的特點與解法1動態(tài)博弈的表示方法一一擴展型動態(tài)博弈涉及博弈的參與人多個階段的選擇和選擇的順序 問題，一般難以用策略型表示，而多用擴展型一一也稱博弈 樹一一表示（有限博弈）。以仿冒與反仿冒為例。一些名詞：參與人和行動順序：結(jié)點：決策結(jié)一一參與人決策的點；終點結(jié)支付向量：先行動的人的支付排第一，后行動的人的支付排第二信息集：在完美信息的情況下，處于莫一節(jié)點的參與人對這 個結(jié)點之前的信息都是了解的。所有的信息集都是 單結(jié)的C（根據(jù)參與人是否相互了解支付情況，有完全信息和不完全信息博弈之分，根據(jù)是否所有參與人都對自己選擇前的博弈 過程完全了解，由完美信息與

2、不完美信息博弈之分。）路徑：第一階段A仿冒，第二階段 B不制止，第三階段 A 仿冒，第四階段B制止。因為：承諾和威脅的可信性2可信性與納什均衡的問題納什均衡在動態(tài)博弈中不再適用 問題。例：開金礦博弈B有一價值4萬元的金礦缺一萬元資金。A有一萬元資金。B承諾如果A將資金借給他，金礦開采后收益對半分成。問 題：A是否應(yīng)該借給她？如果博弈進行到第二階段，B的合理行動是“不分”，承諾是不可信的?？紤]到這一點，A在第一階段選擇“不借”。如果在B不分時A選擇打官司。情況就是：如果打官司 非常勞民傷財，則打官司的 威脅就是不可信 的。 情況就是：所以，承諾或威脅是否可信對于博弈的結(jié)果有很大的影響。由于存在可

3、信性問題， 納什均衡不再是動態(tài)博弈的適合的均 衡解。看第三種情況。策略組合 A:第一階段選擇“借”，第三階段 “打” ；B :第二階段“分”是一個納什均衡。證明：給定A的策略，B “分”是最佳選擇；給定B “分”的策略，A第一階段借，第三階段打是最佳選 擇（第三階段打不需要實施，但是它是保證B分的關(guān)鍵，因而A的策略必須包括第三階段打的策略）這是因但是這個納什均衡不具有穩(wěn)定性不具有一致預(yù)測性 為，如果B在第二階段選擇了 “不分” ，A “打”的威脅是 不可信的。這樣B不會遵守承諾，A也不會愚蠢到依靠一個 不可信的威脅冒險將資金借給他。由于納什均衡不能排除參與人策略中不可信的威脅和承諾，因而是不穩(wěn)

4、定的，在分析動態(tài)博弈時不能給由一致性的預(yù)測。所以動態(tài)博弈中的需要尋找新的均衡概念(子博弈精煉 納時均衡)。3動態(tài)博弈的解法：逆向歸納法從上面的例子中可以看由動態(tài)博弈的適合的解法是逆向歸納法(backwards induction ):從博弈的最后一個階段參與人的行為開始分析，逐步倒退回前一階段相應(yīng)參與人的行為.一直到第一階段。逆向歸納法的邏輯基礎(chǔ)：動態(tài)博弈中先行動的參與人，在前面階段選擇行為時必然會考慮后行動的參與人在后面階段中的行為選擇，只有在最后一階段的參與人才能不受其他參與人的制約而直接做由選擇。而當后面階段的參與人的選擇確定后，前一階段的參與人的行為也就容易確定了。上例；寡頭逆向歸納法

5、排除了不可信的威脅或承諾。第二節(jié)子博弈精煉納什均衡1子博弈子博弈(subgame):由一個動態(tài)博弈第一階段以外的某階段 開始的后續(xù)博弈階段構(gòu)成的，有初始信息集 和進行博弈所需 要的全部信息，能夠 自成一個博弈 的原博弈的一部分，稱為 原博弈的一個子博弈。例：開金礦分割子博弈不能改變參與人的信息結(jié)構(gòu)子博弈必須有初始信息集。因此，非完美信息動態(tài)博弈可能 沒有子博弈。1子博弈不能分割任何信息集:12 子博弈精煉納什均衡 Subgame Perfect Nash Equilibrium 定義：完美信息動態(tài)博弈的策略組合s* （s*,.,s；,.,s；）是一個子博弈精煉納什均衡（ subgame per

6、fect Nash equilibrium）, 如果：（1）它是原博弈的納什均衡；（2）它在每一個子博弈上 都構(gòu)成納什均衡。也就是說，一個策略組合是子博弈精煉納什均衡，當只當它 在每一個子博弈（包括原博弈）上都構(gòu)成一個納什均衡。子博弈納什均衡可以排除不可信的承諾或威脅。例：金礦博弈中策略組合A:第一階段選擇“借”，第三階段“打” ；B:第二階段“分”在整個博弈上是一個納什均衡，但是A在第三階段“打”的策略在第三階段單人博弈構(gòu)成的 子博弈中不是納什均衡。上例中的子博弈精煉納什均衡解是A:第一階段選擇“不借”，第三階段“不打” ；B:第二階段“不分”。上例中，第二階段和第三階段的行為實際上不會發(fā)生

7、，稱第 二階段A的選擇節(jié)點和第三階段B的選擇節(jié)點為“不在均衡路徑上”。一個子博弈精煉納什均衡必須對參與人在所有節(jié)點上的選 擇都作由規(guī)定，包括最終不在均衡路徑上的選擇。第三節(jié)幾個經(jīng)典動態(tài)博弈模型IStackelberg寡頭競爭模型設(shè)市場中有1、2兩家廠商生產(chǎn)同樣的商品。 廠商1是領(lǐng)先廠商， 先選擇策略一產(chǎn)量為 qi,廠商2是追隨廠商，根據(jù)廠商1的產(chǎn)量 選擇最大化的產(chǎn)量為 q2o市場的總產(chǎn)量為 Q=qi+q2.設(shè)市場出清 價格P是總產(chǎn)量的函數(shù)：P=8-Q o兩廠商都無固定成本，邊際成 本相等，ci=c2=2o 運用逆向歸納法求解。首先考慮后行動的廠商 2。在看到廠商1的產(chǎn)量為qi的情況下， 廠商2

8、的選擇產(chǎn)量q2最大化其支付： maxu2（q1，q2） q2（8 g q2） 2q?q2一階條件是：q； 3 2即廠商2的反應(yīng)函數(shù)。再考慮博弈的第一階段，廠商1選擇產(chǎn)量時肯定能夠預(yù)測到廠商2的最優(yōu)產(chǎn)量q2。因此其產(chǎn)量決策是：*q16q16q135maXu1（q1，q2）為（8 9 q?） 2為 *2qQ q1 q1（3 為 q； 2 q1 2求一階條件得：6qi*=3.因而4/=33/2=3/2.此時市場價格為 3.5,雙方的支付分別是 4.5 和 2.25。子博弈精煉納什均衡解釋廠商1在第一階段選擇3單位產(chǎn)量，廠商2在第二階段選擇1.5單位產(chǎn)量。請比較古諾模型的納什均衡解。古諾模型的納什均衡

9、解(2, 2)不是Stackelberg的子博弈精煉納什均衡解。如果廠商2威脅說它選擇產(chǎn)量2,這個威脅并不是可信的。如果廠商1不是選擇產(chǎn)量2,而是選擇比如說產(chǎn)量3,那么，廠商2的最優(yōu)選擇是1.5而不是威脅的2。2討價還價博弈一、三回合討價還價A、B兩人就如何分享10000元現(xiàn)金進行談判。談判規(guī)則如下：1、A提由分割比例(S1,10000-S1), B表示接受或不接受；2、如果B拒絕A的方案，則B提由分割比例(S2,10000-S2), A表示接受或不接受；3、如果A拒絕B的方案，則A提由 最后的分割方案(S, 10000-S), B只能接受。(每回合消耗系 數(shù)為)(S)解：逆向歸納法 第三回合

10、：A提由最后的分割方案(S,10000-S),雙方支付 是(2S, 2(10000 S)第二回合：B只需使A得到的份額 S22S,即：S2S,因此支付(S2, (10000 S2) = 2S, (10000 S)o 第一回合：A 只需使 B 得到的份額2S2S ,10000 S1(10000 S),即：S1 10000 10000所以，均衡解是第一回合 A提由& 10000 10000B 接受。雙方支付為(10000 100002S,100002S )討論：由于A處于強勢地位，在第三回合，A肯定會提出S=10000,因而最后雙方的支付是10000 ( 12), 10000 (2 ),雙方最終的

11、支付取決于消耗系數(shù) 。(2)越大，A所得越小，B越大。當 =0.5時，2有最大值0.25。這表明雖然在博弈中 A處于強勢地位，但B可以跟A “耗時間”， 這樣A不得不“花錢買太平”，讓B也取得一定份額。只有當 A 完全不怕拖時間(=1)或者B的爭奪是毀滅性的(=0)時， A才不需花錢買太平?，F(xiàn)實中的一些經(jīng)濟糾紛就是這樣。第三節(jié)重復(fù)博弈問題：在旅游地很容易由現(xiàn)假貨，而在居民小區(qū)的便利店則很少由現(xiàn)假貨，為什么？重復(fù)博弈 是指由同樣結(jié)構(gòu)的基本博弈重復(fù)多次進行構(gòu)成的 博弈過程，其中的每次博弈稱為階段博弈。給定一個基本博弈 G(可是靜態(tài)或動態(tài)博弈，重復(fù)進行T次 G,并且在每次重復(fù) G之前各參與人都能觀察

12、到以前博弈的 結(jié)果，這樣的博弈過程稱為“G的T次重復(fù)博弈”，記為G(T) o 而G則稱為G(T)基本博弈，G(T)中的每次重復(fù)稱為 G(T) 的一個“階段”重復(fù)博弈具有三個特征：1、階段博弈之間沒有 “物質(zhì)上”的聯(lián)系(no physical links ),即前一階段的博弈不改變后一階段博弈的結(jié)構(gòu)。（每階段博弈的結(jié)構(gòu)相同）2、所有參與人都能觀察到博弈過去的歷史（完美信息）。3、參與人的總支付是所有階段博弈支付的貼現(xiàn)值或加權(quán)平 均值。參與人是從 總支付最大化 的角度進行決策的。在長期 內(nèi)，參與人之間的行為可能相互影響，合作或者報復(fù)不合作 者（便利店老板就比較害怕報復(fù)），這樣，在博弈的一個階段支付

13、大并不意味著在長期內(nèi)的支付也大，所以，在重復(fù)博 弈中參與人必須考慮到長期利益?，F(xiàn)實中的例子：寡頭門在市場上的長期競爭，如價格戰(zhàn)，市場份額戰(zhàn)等； 兩個企業(yè)履行長期協(xié)議；商業(yè)中的回頭客等有限次重復(fù)博弈假設(shè)重復(fù)次數(shù)較少的有限次重復(fù)博弈可以不考慮貼現(xiàn)問題。存在唯一純策略納什均衡博弈的有限次重復(fù)博弈參與人的行為不會因為博弈的有限次重復(fù)而發(fā)生改變，10例一：連鎖店在位者進入者40, 50-10, 00, 3000, 300默許斗爭進入不進入在此博弈中，如果進入者先 行動，唯一的子博弈精煉納什均衡結(jié)果是進入者進入，在 位者默許（注意，這是一個兩階段動態(tài)博弈）A現(xiàn)在假設(shè)有同樣的20個市場，因此這個基本博弈需要

14、重復(fù)進行20次。討論：在位者是否會為了阻止進入者進入其它市場而在開始就進行斗爭?結(jié)論是不會。逆向歸納法證明。思考：為什么會由現(xiàn)這種似乎與經(jīng)驗相違背的現(xiàn)象？1、在現(xiàn)實中，很多情況下并不能明確只有20個市場需要保護，因而就不是“有限次” 了ii2、在多階段博弈中，對參與人的理性要求非常高，誰也不能保證參與人不會發(fā)生顫抖”。3、在現(xiàn)實中，信息可能是不完全的。例2:有限次囚徒困境重復(fù)博弈囚徒2坦白 不坦白-5, -50, -8-8, 0-1 , -1囚徒1 坦白不坦白假設(shè)兩人計劃犯兩次同樣的罪，即博弈重復(fù)進行兩次逆向歸納法：在知道第二階段結(jié)果是(坦白，坦白)后，兩階段的總收益是：囚徒1-10, -10

15、下，-13-13, -5-6, -6囚徒2坦白不坦白坦白 不坦白一般結(jié)論：G(T)是階段博弈G重復(fù)T次得到的重復(fù)博弈。如果 G有唯12 一的純策略納什均衡，重復(fù)博弈 G（T）的唯一子博弈精煉納 什均衡結(jié)果是階段博弈 G的納什均衡重復(fù) T次（即每個階 段博弈由現(xiàn)的都是一次性博弈的均衡結(jié)果） 。多個純策略納什均衡博弈的有限次重復(fù)博弈例1:三價博弈 故事：兩生產(chǎn)同質(zhì)商品的寡頭。在兩寡頭都是高價時市場總禾I潤為10,都是中價時市場總利潤為 6,都是低價時市場總 利潤為2。兩寡頭同時決策，價格相同時分享利潤，否則低 價者獨占。5,50,60,26,03,30,22,02,01,1ML寡頭1 H寡頭2H

16、M L存在兩個純策略納什均衡（M,M ）和（L,L）（還有混合策略）。但顯然（H,H ）帕雷托 效率最高。是否重復(fù)（兩次）進行能夠?qū)崿F(xiàn)使效率改善？假設(shè)寡頭采取觸發(fā)策略（trigger strategy ）,即開始選擇 合作，如果對方也合作，就一直合作；但在博弈中一旦發(fā)現(xiàn) 對方不合作，就永遠選擇報復(fù)，不合作。寡頭1,第一次選H.如果第一次結(jié)果為（H,H）,則第二次選13M;否則選L.寡頭2:同上。子博弈精煉納什均衡結(jié)果是：第一階段（ H, H）,第二階段（M , M ）。證明： 第二階段（M,M ）是原博弈的納什均衡，參與人的行為不會 發(fā)生偏離。第一階段（H,H ）雖然不是原博弈的納什均衡，單獨

17、偏離為M能增加1單位支付，但這樣做第二階段要損失2,因而不會偏離（H,H）.如果將第二階段（M,M ）的支付（3, 3）加到原博弈的（H,H ）策略組合上，將（L,L ）的支付（1,1）加到原博弈的其他 策略組合上，則兩階段的總支付是：很清楚，納什均衡結(jié)果8,81,71,37,14,41,33,13,12,2寡頭2H M L是（8, 8）寡頭1HML討論：觸發(fā)策略中報復(fù)的可信性問題。在某階段由現(xiàn)不合作時，其后所有階段都實行報復(fù)，但報復(fù)14時自己也只能得到較差的結(jié)果，如上例中第二階段報復(fù)的支付是（1, 1）。在這種情況下，是否真的實施報復(fù)？例2,兩市場重復(fù)博弈故事：廠商1、2同時面臨a、b兩個市

18、場機會。每個廠商由 于能力有限只能選擇一個市場a或b進行開發(fā).廠商2A B廠商1 A卜,3 11,3B |幺1卜，0 |A市場較大但開發(fā)程度低，一家廠商不足以很好的開發(fā)，因 而單獨一家開發(fā)只能得到1,兩家共同開發(fā)能夠得到 （3,3）。B市場是一個較小但開發(fā)程度高的市場，只有一家廠商進入 時得到4,共同進入是只能得到（0, 0）。階段博弈的納什均衡是 （A,B ）、（B,A）以及混合策略以0.5的 概率在A、B之間隨機選擇，期望支付是 0.25* （3+4+1+0） 二2。最理想的結(jié)果（3, 3）不能實現(xiàn)。兩次重復(fù)博弈。均衡結(jié)果不唯一，有許多均衡路徑。151、（A,B） （A,B）;平均支付（1

19、,4）2、（B,A） （B,A）;平均支付（4, 1） 堅持同一純策略3、（0.5,0.5）（0.5,0.5）;期望平均支付（2, 2）兩階段都選擇混合策略4、（A,B）（B,A）;平均支付（2.5, 2.5）5、（B,A）（A,B）;平均支付（2.5, 2.5）輪換策略6、第一次純策略，第二次混合策略；平均支付（1.5, 3）或（3, 1.5）。7、第一次混合策略，第二次純策略；平均支付（1.5, 3）或（3, 1.5）。輪換策略是效率較高，也比較公平的策略。也就是說， 當博弈重復(fù)兩次后，雖然博弈的結(jié)果不維一，但是輪換策略 這種效率較高又比較公平的策略就可能由現(xiàn)，如果雙方能夠協(xié)商（請注意，因

20、為輪換策略本身是子博弈精煉納什均衡， 因而協(xié)商是有可能的；而（A,A）不是子博弈精煉納什均衡，因而不可能協(xié)商一致），這種結(jié)果就會由現(xiàn)，雙方的處境就會 得到改善。不過，即使輪換策略被選擇，最后的結(jié)果仍不是最理想的結(jié) 果兩階段都選擇（A,A）,平均支付（3, 3）。16博弈重復(fù)三次均衡策略更多，幾乎不能列舉。但下面這個觸發(fā)策略構(gòu)成子 博弈精煉納什均衡：廠商1:第一階段選擇 A;如果第一階段結(jié)果是（A,A ）,則 第二階段選擇 A,如果是（A,B）,則選擇B;第三階段選擇 B. 廠商2:第一階段選擇 A;第二階段選擇 B;如果第一階段 結(jié)果是（A,A ）,則第三階段選擇A,如果是（B,A）,則第三階

21、段選擇B.均衡路徑是（A,A） - （A,B） - （B,A）,平均支付為8/3=2.67. 第二、三階段本身是納什均衡，不會偏離。第一階段不是階段博弈的納什均衡，但是如果偏離，則會引 起對方報復(fù)，因而也不會偏離。例如，如果廠商1第一階段選擇B,則均衡路徑是（B,A）-（A,B） （A,B）,平均支付為6/3。 所以上述觸發(fā)策略構(gòu)成子博弈精煉納什均衡。這個觸發(fā)策略的平均支付是（2.67, 2.67）。可以證明， 它大于其他所有可能的子博弈精煉納什均衡。也就是說，博 弈重復(fù)三階段使得雙方有可能選擇觸發(fā)策略，使雙方進一步改善。如果博弈重復(fù)次數(shù)進一步增加，例如重復(fù)T次，則可以米取觸發(fā)策略：廠商1：前

22、T-2次選擇A,但從第二次開始，如果發(fā)現(xiàn) 結(jié)果不是（A,A）則改為B只到T-2次；T-1次，如果第T-217 階段結(jié)果是（A,A）,則第-1階段選擇A,如果是（A,B）,則選 擇B;第T階段選擇B.廠商2:前T-2次選擇A,但從第二次開始，如果發(fā)現(xiàn)結(jié)果 不是（A,A）則改為B只到T-2次；T-1次選擇B;T次，如 果第T-2階段結(jié)果是（A,A ），則第T階段選擇A,如果是（B,A）, 則第T階段選擇B.那么可以證明這個策略也是子博弈精煉納什均衡，均衡結(jié)果平均支付趨向于最理想的（3, 3）。有限次重復(fù)博弈的無名氏定理前面例子表明，當原博弈有多個純策略納什均衡時，有限次重復(fù)博弈有許多效率差別很大的

23、子博弈精煉納什均衡，并且通過設(shè)計特定的策略，主要是觸發(fā)策略，可以實現(xiàn)效率較高 的均衡。這就是無名氏定理的主要內(nèi)容：有限次重復(fù)博弈的無名氏定理：設(shè)原博弈的一次性博弈有均衡支付向量優(yōu)于w,那么在該博弈的多次重復(fù)中，所有不小于 個體理性支付的可實現(xiàn)支付，都至少有一個子博弈精煉納什 均衡的極限的平均支付來實現(xiàn)。Wi為一次性博弈中i最差的均衡支付，w= （Wi,W2.Wn）,在兩 市場博弈為（1 , 1 ）。個體理性支付（individual rationality ）是指不管其它參與人18 的行為如何，某參與人在博弈中只要自己采取某種特定策略，最低限度能獲得的支付。上例中，只要雙方都選擇a,則兩個參與

24、人都至少能夠得到 1以上的支付，因此個體理性支付就是1。在上例中，可實現(xiàn)支付就是由(0, 0), (1, 4) , (4, 1)和 (3, 3)四點連接形成的四邊形。因此，所有不小于個體理性支付的可實現(xiàn)支付就是由 (1, 1), (1, 4), (4, 1)和(3,無限次重復(fù)博弈無限次重復(fù)博弈與有限次重復(fù)博弈的異同:191、沒有最后一階段博弈；2、不可忽略貼現(xiàn)問題3、都可能通過懲罰來實現(xiàn)理想的均衡。唯一純策略納什均衡博弈的無限次重復(fù)博弈寡頭2一、無限次重復(fù)的囚徒困境 以寡頭削價競爭為例寡頭1 HL基本博弈的結(jié)果是（L,L ）o前面已經(jīng)證明，有限次重復(fù)不會改變結(jié)果。如果是無限次，則在貼現(xiàn)因子較大

25、的情況下（比較重視長期利益）可能實現(xiàn)合作。觸發(fā)策略：第一階段采取 H ,在t階段，如果前t-1階段的 結(jié)果都是（H,H ）,則繼續(xù)采用H ; 一旦發(fā)現(xiàn)對方不合作（L）, 則以后永遠選擇L報復(fù)。假設(shè)參與人1已經(jīng)采用了觸發(fā)策略。如果寡頭2也選擇觸發(fā)策略，則總支付的現(xiàn)值是：244* 42*4 .1如果寡頭2不采取觸發(fā)策略，在第一階段采用L,因為第二20階段起被報復(fù)只能采用L,因而支付為（5,1,1,.）。總支付的現(xiàn)值是：25*12*1 . 5 1因此，只要 12,即 1/4 ,采用觸發(fā)策略對寡頭 2就是明智的。由于寡頭1、2是對稱的，因而同樣可以證明觸發(fā)策略對寡頭1也是明智的。這樣，我們就證明了觸發(fā)

26、策略是原博弈的一個納什均衡。由于博弈進行無限次， 從任何一個階段開始的子博弈都與這 個博弈結(jié)構(gòu)相同，因而觸發(fā)策略在任何一個子博弈上都是納 什均衡。所以，觸發(fā)策略構(gòu)成該無限次重復(fù)博弈的子博弈精煉納什均 衡。啟發(fā)：在博弈重復(fù)無限次，且參與人都有耐心的情況下， 任何短期的機會主義行為的所得都是微不足道的，參與人有積極性為自己建立一個樂意合作的聲譽，同時也有積極性懲罰對方的機會主義行為。當然，該博弈也存在其他子博弈精煉納什均衡，比如每 一階段都選擇不合作（L,L ）就是一個。無限次重復(fù)博弈的子博弈精煉納什均衡的多重性問題。（個人認為，多重均衡正好反映了現(xiàn)實，即在現(xiàn)實中，有的 寡頭選擇合作，有的寡頭選擇不合作）。213.2.2、無限次重復(fù)博弈的無名氏定理設(shè)G是一個完全信息的靜態(tài)博弈。用(ei,e2,.en)表示G的 納什均衡支付。用(xi,.xn)表示G的任意可實現(xiàn)的支付， 如果xiei對任意參與人i都成立，那么總存在一個1 ,使得無限次重復(fù)博弈 G(,)中一定存在一個子博弈精煉納 什均衡，使得各參與人的平均支付就是(Xl,X2.Xn)o無名氏定理表明，在無限次重復(fù)博伊中，如果參與人有 足夠耐心，那么任何滿足個人理性的可行的支付都可以通過 一個特定的子博