第9講博弈論重復(fù)博弈

1、蔡樹66162）科技樓14062 為什么現(xiàn)實(shí)生活中并不總是出現(xiàn)“囚徒困境”？3重復(fù)博弈4重復(fù)博弈引論為何研究重復(fù)博弈 經(jīng)濟(jì)中的長期關(guān)系 人們的預(yù)見性 未來利益對當(dāng)前行為的制約 長期合同、回頭客、長客和一次性買賣的區(qū)別 有無確定的結(jié)束時間5無限次重復(fù)博弈：一個基本博弈G一直重復(fù)博弈下去的博弈 G() 策略：博弈方在每個階段針對每種情況如何行為的計(jì)劃子博弈：從某個階段（不包括第一階段）開始，包括此后所有的重復(fù)博弈部分均衡路徑：由每個階段博弈方的行為組合串聯(lián)而成6重復(fù)博弈和無名氏定理 重復(fù)十次 （1）兩人同時選好十次策略 （2）兩人一次博弈接一次博弈，10次 （3）一人先選

2、一人后選，10次圖圖2-27 囚徒困境問題囚徒困境問題坦白抵賴坦白-8，-80，-10抵賴-10, 0-1,-1囚徒囚徒2囚徒囚徒17重復(fù)博弈和無名氏定理 重復(fù)博弈(repeated game)的定義 指同樣結(jié)構(gòu)的博弈重復(fù)多次，其中的每次博弈稱為“階段博弈(stage game)”。 如兩個多次犯罪的“囚徒問題”。 由于動態(tài)博弈是相機(jī)行動，反映到重復(fù)博弈中，就是可以使自己在某個階段的博弈選擇依賴于其他參與人過去的行動歷史。8重復(fù)博弈與策略空間的擴(kuò)展 如囚徒困境的重復(fù)博弈的一個策略可以是：“如果這次你選擇了坦白，我下次將選擇坦白；如果你這次選擇了抵賴，我下次將選擇抵賴” 。 因此，參與人在重復(fù)博

3、弈中的策略空間遠(yuǎn)遠(yuǎn)大于和復(fù)雜于在每個階段博弈中的策略空間。假定上屬博弈重復(fù)多次或無限次；那么，每個參與人有多個可以選擇的戰(zhàn)略：僅舉幾例：All-D: 不論過去什么發(fā)生，總是選擇不合作；All-C: 不論過去什么發(fā)生，總是選擇合作；合作-不合作交替進(jìn)行；tit-for-tat: 從合作開始，之后每次選擇對方前一階段的行動；trigger strategies: 從合作開始，一直到有一方不合作，然后永遠(yuǎn)選擇不合作。910 兩個均衡11均衡： （進(jìn)入，合謀）為什么實(shí)際上還是有很多會選擇（進(jìn)入，斗爭）？12重復(fù)博弈和無名氏定理 如此一直倒推回去，我們得到這個博弈的唯一子博弈精煉均衡是在位者在每一個市場

4、上都選擇默許，進(jìn)入者在每一個市場上選擇進(jìn)入。 這就是所謂的“連鎖店悖論”(chain-store paradox, Selten,1978) 因?yàn)閷?shí)際生活中，進(jìn)入者和在位者在每個市場都斗得你死我活13有限次重復(fù)博弈定理 令G是階段博弈，G(T)是G重復(fù)T次的重復(fù)博弈(T)。如果G有唯一的納什均衡，重復(fù)博弈G(T)的唯一子博弈精煉納什均衡結(jié)果是: 階段博弈G的納什均衡重復(fù)T次（即每個階段博弈出現(xiàn)的都是一次性博弈的均衡結(jié)果）。 只要博弈的重復(fù)次數(shù)是有限的，重復(fù)本身并不改變囚徒困境的均衡結(jié)果。 條件： “唯一性”：如果納什均衡不是唯一的，那會怎么樣？ 有限性：如果博弈重復(fù)無限次，那會怎么樣？ 時間性

5、：如果每次博弈的收益受到時間（貼現(xiàn)率、利率、風(fēng)險(xiǎn)、通貨膨脹）的影響 ，那會怎么樣？14多個均衡的重復(fù)博弈 (H,H)是“合作”，但不是NE NE為（M,M）(L,L) 純策略=動作 混合策略=? 條件策略(H|M,M|H, L|L) 其他策略15多個均衡的重復(fù)博弈 兩階段博弈 (HH,HH)仍然不是NE1617等價于一次博弈 HH是均衡，所以沒有人愿意偏離18 如果背叛，今天的收益加1，但是明天的收益減2（合作的收益為3，背叛的收益為1）19眼前利益與長遠(yuǎn)利益欺騙的短期收益信譽(yù)的長期收益時間20 當(dāng)博弈有多個納什均衡時，參與人可以使用不同的納什均衡懲罰前面階段的不合作行為或獎勵第一階段的合作行

6、為。 從而迫使大家合作21人們?yōu)槭裁磿龊檬拢ê献鳎?？因?yàn)橛忻魈斓幕貓?bào)，或者避免明天的懲罰。人的理性就在于，為了將來更大的利益，可以犧牲眼前利益。大部分的小孩和動物，一般就做不到這一點(diǎn)。今天欺騙的收獲今天欺騙的收獲 合作后的收獲（承諾）合作后的收獲（承諾） 欺騙后的收獲（威脅）欺騙后的收獲（威脅）教訓(xùn)：在發(fā)展關(guān)系的時候，承諾合作后的收益以及威脅欺騙的懲罰，教訓(xùn)：在發(fā)展關(guān)系的時候，承諾合作后的收益以及威脅欺騙的懲罰， 有時能夠激勵今天良好行為的發(fā)生。有時能夠激勵今天良好行為的發(fā)生。 而這種行為，有助于創(chuàng)建一個好的未來！而這種行為，有助于創(chuàng)建一個好的未來！22先別急著吃棉花糖 有三只青蛙在河中的一

7、片葉子上順?biāo)?。其中一只想跳到河里。在葉子上還剩幾只青蛙？ 吃掉棉花糖等于吃掉未來! http:/ 美國的斯坦福大學(xué)曾進(jìn)行過一個著名的棉花糖實(shí)驗(yàn)。在這個實(shí)驗(yàn)里，把小孩子單獨(dú)留在房間里，并給他們一人一塊棉花糖，讓他們選擇是要馬上吃掉棉花糖，還是等待十五分鐘。如果愿意等，就可以再多得一塊棉花糖作為獎賞。研究結(jié)果發(fā)現(xiàn)，為了獲得獎賞，能夠抗拒眼前棉花糖的誘惑而等待十五分鐘的小孩，長大以后，普遍都比那些馬上吃掉棉花糖的小孩們更成功 23無限次重復(fù)博弈圖圖2-27 囚徒困境問題囚徒困境問題坦白抵賴坦白-8，-80，-10抵賴-10, 0-1,-1囚徒囚徒2囚徒囚徒124 首先，（一直坦白，一直坦白）可以

8、是一個均衡 有沒有其他的均衡？ 也即：有沒有其他的策略，當(dāng)雙方都采用該策略之后，就沒有人反悔去用其他策略？ 如果你知道對方會一直坦白，那么你的最佳應(yīng)對是一直坦白 T,T,T,T, T,T,T,T,25 考慮下列所謂的“冷酷策略”(grim strategies): 開始時選擇抵賴； 選擇抵賴直到有一方選擇了坦白，然后永遠(yuǎn)選擇坦白。重復(fù)博弈和無名氏定理圖圖2-27 囚徒困境問題囚徒困境問題坦白抵賴坦白-8，-80，-10抵賴-10, 0-1,-1囚徒囚徒2囚徒囚徒126 D,D,D,D,D,D, D,D,D,D,D,D, T,T,T,. T,D,T,D,T,. T,D,D,D,D, D,T,T,

9、T,T,.27重復(fù)博弈和無名氏定理 首先證明冷酷策略是一個納什均衡 回顧一下，所謂納什均衡，就是這樣的一個狀態(tài)，對于任意一個參與人，給定其他參與人選擇納什均衡策略，該參與人都無法偏離納什均衡策略。 因此，證明囚徒問題中冷酷策略是一個納什均衡的方法是：給定其中任意一個參與人堅(jiān)持“冷酷戰(zhàn)略”，另外一個參與人的最優(yōu)選擇也是堅(jiān)持冷酷戰(zhàn)略。28 如果i在博弈的某個階段首先選擇了坦白，在該階段得到0單位的支付，優(yōu)于選擇抵賴得到的-1。 但這個機(jī)會主義行為將觸發(fā)他的伙伴選擇“永遠(yuǎn)坦白”的懲罰，因此i隨后每個階段的支付都是-8。（-1是獎勵，-8是懲罰） 因此，如果下列條件滿足，給定對手沒有選擇坦白，i將不會

10、選擇坦白0( 8)( 8).1 ( 1)( 1). 這個不等式是否正確？有限和無限的不同，希爾伯特旅館的故事29另外一種計(jì)算方法0( 1)( 1 ( 8)( 1 ( 8).177. 這個策略為什么不適用于兩階段（有限）重復(fù)博弈？0( 1)( 1 ( 8)17 因?yàn)橛心嫦驓w納法：大家在第二階段肯定都坦白，也即，第二階段肯定是-8，不會有-10( 1)( 8( 8)10 30 所以，無限很重要 給你100萬，你愿意今天要這個錢還是明天（10年后）要這個錢？Why？ 今天的錢并不等于明天的錢：利率 明天的錢并不等于今天的錢：貼現(xiàn)率31貼現(xiàn)率將未來資產(chǎn)折算成現(xiàn)值(present value)的利率，一

11、般是用當(dāng)時零風(fēng)險(xiǎn)的利率來當(dāng)作貼現(xiàn)率，但并不是絕對。舉個例子：貼現(xiàn)率為10%，明年的100塊在今年就相當(dāng)于100/（1+10%）=90.909090.塊錢，到了去年就是100/（1+10%）*（1+10%），也就是說，今年用90.909090.塊可以買到的東西相當(dāng)于明年100塊可以買到的東西。 今天投資100萬元的項(xiàng)目，將來如能收回200萬，也不能證明此項(xiàng)投資一定有效。因?yàn)槿绻@回收的200萬要等50年之后，今天衡量的價值就遠(yuǎn)低于100萬。這是由于如果利率是3%，100萬元存銀行，50年內(nèi)得到的利息也將達(dá)338萬元（利率為2%的話，50年的利息為169萬元）。所以50年后回收200萬的投資與存銀

12、行得利息相比不值得去做。 貼現(xiàn)率：將來的錢現(xiàn)在花，把將來的錢借給現(xiàn)在利率：現(xiàn)在的錢存起來將來花，把現(xiàn)在的錢借給將來32考慮貼現(xiàn)因子的重復(fù)博弈 設(shè)a為貼現(xiàn)因子（假定兩人貼現(xiàn)因子相同）。貼現(xiàn)因子=1/（1+貼現(xiàn)率） 如果i在博弈的某個階段首先選擇了坦白，在該階段得到0單位的支付，優(yōu)于選擇抵賴得到的-1。 但這個機(jī)會主義行為將觸發(fā)他的伙伴選擇“永遠(yuǎn)坦白”的懲罰，因此i隨后每個階段的支付都是-8。 因此，如果下列條件滿足，給定對手沒有選擇坦白，i將不會選擇坦白.) 1() 1(1.) 8() 8(022aaaaaaa1118即33230( 1)( 1 ( 8)( 1 ( 8).1777.117 ()1

13、aaaaaaaa q a 1/8q a太小，則將來的錢根本不管用，將來不值得期待（有未來，但是更期待今天）q 因此，冷酷戰(zhàn)略是一個納什均衡。34重復(fù)博弈和無名氏定理 該策略是否是子博弈精煉均衡？ 因?yàn)椴┺闹貜?fù)無限次，從任何一個階段開始的子博弈與這個博弈的結(jié)構(gòu)完全相同。 在冷酷戰(zhàn)略均衡下，子博弈可以分為兩類：在類型a，沒有任何參與人曾經(jīng)坦白；在類型b，至少有一個參與人曾經(jīng)坦白。35重復(fù)博弈和無名氏定理 在類型a中，我們已經(jīng)證明，冷酷戰(zhàn)略在a類型子博弈中構(gòu)成納什均衡； 在b類子博弈中，根據(jù)冷酷戰(zhàn)略，參與人只是重復(fù)單階段博弈的納什均衡，因此也是子博弈的納什均衡。 因此，如果a 1/8，冷酷戰(zhàn)略是無限

14、次囚徒博弈的一個子博弈精煉納什均衡。36重復(fù)博弈和無名氏定理 該博弈還有許多其他子博弈精煉均衡。 各期都坦白，是另一個子博弈精煉納什均衡 子博弈精煉均衡的多重性是無限次重復(fù)博弈的普遍問題。37更多例子 無限次重復(fù)古諾模型 支持壟斷產(chǎn)量的條件：P194-195 低水平的合作：P195-197 加大懲罰力度和提高合作水平：P197-199 復(fù)雜的現(xiàn)實(shí)（OPEC）：P199-200 工資：P200-2053839Axelrod (1984)qTit-for-tat 是成功率最高的戰(zhàn)略4041懲罰與合作 Abreu(1986)：最大合作戰(zhàn)略是使用最嚴(yán)厲的可信懲罰（the strongest credi

15、ble punishment); 維護(hù)合作并不需要無限期的懲罰；只要懲罰期足夠長就可以了； 蘿卜加大棒（stick and carrot): 從合作開始，一直合作直到：如果有任何一方在t期不合作，在t+1期，前期合作者選擇“不合作”來實(shí)施懲罰，前期不合作者選擇合作；如果該合作的沒有合作或者該懲罰的沒有懲罰，在t+2期繼續(xù)按照上述t+1期的策略規(guī)定博弈；否則，合作恢復(fù)。42 仁：人不犯我，我不犯人仁：人不犯我，我不犯人 怒：以眼還眼，以手還手怒：以眼還眼，以手還手 即：（君子報(bào)仇，十年不晚）即：（君子報(bào)仇，十年不晚） 恕：寬恕對方，寬以待人?。簩捤Ψ?，寬以待人 信：說到做到信：說到做到43概率

16、問題有可能有限，有可能無限明天是否繼續(xù)是一個概率事件什么情況？人們也是傾向于合作如果沒有明天，今天就會為非作歹如果沒有明天，今天就會為非作歹如果有無限多明天，作惡不懲罰，今天就會為非作歹如果有無限多明天，作惡不懲罰，今天就會為非作歹如果有無限多明天，作惡會懲罰，今天就會合作如果有無限多明天，作惡會懲罰，今天就會合作如果明天有可能或者，也有可能掛掉，作惡會懲罰，則今天有可能合如果明天有可能或者，也有可能掛掉，作惡會懲罰，則今天有可能合作，合作的可能性看明天掛掉的概率和作惡懲罰的力度作，合作的可能性看明天掛掉的概率和作惡懲罰的力度44不可信的懲罰：壟斷廠家客戶商家不購買購買誠實(shí)欺騙（5，5）（1，

17、7）（0，0）45不確定性下的最優(yōu)處罰 在確定的情況下，懲罰越嚴(yán)厲，越有助于合作。因?yàn)榫馇闆r下，欺騙從來不會發(fā)生，所以懲罰實(shí)際上是沒有成本的。 但在不確定的情況下，即使每個人都選擇合作，“壞結(jié)果”也會出現(xiàn)。如果壞結(jié)果總是觸發(fā)懲罰，就會冤枉好人，過重的懲罰反到導(dǎo)致不合作；但如果總是原諒，合作也不會發(fā)生。46家族企業(yè)的困境；“殺熟” 如果懲罰對懲罰者本身的損害太大，懲罰就是不可信的。這與投鼠忌器是一個道理，你討厭老鼠，但是你沒有辦法，因?yàn)槟阈奶勰莻€盤子，那個器皿。投鼠忌器在我們企業(yè)內(nèi)部很多環(huán)節(jié)都會發(fā)生，導(dǎo)致懲罰不可信，所以對方就不會太注重信譽(yù)。家族成員有時候比非家族成員更不可信任，更不守規(guī)矩，就

18、是這個道理。 朋友專門騙朋友，是“殺熟”。問題也與懲罰的不可信有關(guān)。47長期參與人與不固定的短期參與人 最簡單的例子是廠家與消費(fèi)者之間的博弈：每個消費(fèi)者一般只購買一次，而廠家重復(fù)出售產(chǎn)品給眾多的消費(fèi)者。 此時，只要消費(fèi)者足夠多，并且每個消費(fèi)者能觀察到前一個消費(fèi)者購買的產(chǎn)品的質(zhì)量，合作仍然可以出現(xiàn)。48產(chǎn)品質(zhì)量博弈產(chǎn)品質(zhì)量博弈購買不購買高質(zhì)量低質(zhì)量1，1-1，20，00，049社會規(guī)范：集體抵制 Boycott: 每個人都應(yīng)該誠實(shí)；都有責(zé)任懲罰騙過人的人；不參與懲罰的人應(yīng)該受到懲罰；如：假定A在t期欺騙了B，C在t+1期就不應(yīng)該與B合作，否則，D在t+2期就不應(yīng)該與C合作；如果C在t+1期與B合

19、作，而D在t+2期又與C合作，F(xiàn)在t+3期就不應(yīng)該與D合作，如此等等； （美國對不參與伊拉克戰(zhàn)爭的國家的態(tài)度）；50敵友規(guī)則 開始把所有的人當(dāng)朋友；t期的朋友關(guān)系繼續(xù)保持到t+1期，當(dāng)只當(dāng)他在t期不曾騙過任何人并不曾與你的敵人合作； 朋友的朋友是朋友； 朋友的敵人是敵人； 敵人的朋友是敵人； 敵人的敵人未必是朋友。51傳統(tǒng)社會的個人信譽(yù)傳統(tǒng)社會的個人信譽(yù)q在傳統(tǒng)社會，人們常年生活在封閉的村莊，村民之間彼此非常熟悉，欺騙行為很容易識別，人們之間的口頭交流足以使任何欺騙行為廣為而知，每個人的歷史都存儲在別人的腦海里，對欺騙行為的懲罰即使不能施加于欺騙者本人，也可以通過家庭成員而實(shí)現(xiàn)，前面講的四個條件基本是可以得到滿足。因此，即使沒有法律，村民之間也可以建立起高度的信任，欺騙行為很少發(fā)生。計(jì)算機(jī)中的博弈（大作業(yè)） 調(diào)研博弈在計(jì)算機(jī)中的應(yīng)用情況，給出自己