1、重復博弈重復博弈 主要內容：一、有限次重復博弈二、無限次重復博弈與無名氏定理三、重復博弈的社會學含義 例子1-越戰戰場上的潛規則 一名新兵剛上戰場，老兵按住他：別亂開槍！新兵問：為什么？老兵對其解釋：曾有一段時間，雙方打得不可開交，結果大家都躲著，屎尿都撒在貓耳洞里，由于貓耳洞很潮濕，人呆在里面很難受，導致有人耳朵都發了霉，最后是誰也打不著誰，自己卻活受罪。此后，便慢慢達成默契：我出來你不開槍，你出來我也不開槍。 例子2 一個男孩被視為傻瓜，因為每當別人拿一枚1塊硬幣和5分硬幣讓他選的時候，他總是選5分的，有一個人覺得奇怪，就問他：“為什么你不拿1塊錢的？”，男孩小聲回答：“假若我拿了1塊錢的

2、硬幣，下次他們就不會再拿錢讓我選了。” 威脅和承諾的重要性：以上兩個例子帶給我們什么啟發？ 問題1 在相互聯系緊密的人際關系中，人們普遍比較注意禮節、道德，因為合作和協調對大家都有好處；但是，我們又常常見到這樣的消息：在公共汽車上，兩個陌生人會為一個座位爭吵，為什么會發生這種事情？原因何在？ 問題2 在“囚徒困境”這一例子中，博弈的參與人為了追求自身利益的最大化，而陷入了個人理性與集體理性的沖突中，導致最優的結果未能出現，即合作沒有產生。如果我們假定博弈可以多次重復進行，結果是否會發生變化？是否會出現合作的局面？ 動態博弈中涉及的一個重要問題是，博弈過程中威脅和承諾如何影響博弈的進程。 重復博

3、弈所關心的議題也與之相似： （1）將來可信的威脅或承諾如何影響到當前的行動？ （2）在一次博弈中無法實現的均衡，在重復博弈中能否實現？一、有限次重復博弈考察下列博弈 該博弈存在唯一的唯一的Nash均衡均衡，即（U，L）。 同時注意到，該博弈還存在一個高效均衡（D，R），高效均衡對應著一種合作行為合作行為。 為什么高效的均衡不是納什均衡？如何保證這一高效均衡能夠實現？1,15,00,54,4UDLR12 兩次重復博弈的博弈樹兩次重復博弈的博弈樹121假設將上述博弈重復兩次，那么第二次博弈開始時，第一次博弈的結果可視為已知。1,15,00,54,4UDLR121,15,00,54,4UDLR121

4、+1,1+1 5+1,0+10+1,5+1 4+1,4+1UDLR12第二階段第二階段第一階段第一階段第一階段第一階段 運用逆推歸納法，可以發現上述重復博弈的子博弈精煉Nash均衡為：在每次博弈中，參與人1都選擇U，參與人2都選擇L。 這說明：在兩次重復博弈中，高效的均衡仍無法實現。 同樣可證明：在n階段重復博弈(即博弈重復n次且每次博弈開始時，前面博弈的結果都已知)中，高效的均衡同樣無法實現。有限重復博弈定義有限重復博弈定義 定義：定義： 對于給定的階段博弈G，令G(T)表示G重復進行T次的有限重復博弈，并且在下一次博弈開始前，所有之前博弈的進程均可被觀測到。有限重復博弈的戰略、子博弈與支付

5、有限重復博弈的戰略、子博弈與支付 戰略：重復博弈環境下，參與人的戰略非常復雜。一般地，我們定義參與人的一個戰略是在博弈的每個階段針對之前的博弈歷史而制定的行動計劃； 子博弈：子博弈要么仍然是重復博弈，要么是原博弈；有限重復博弈的戰略、子博弈與支付有限重復博弈的戰略、子博弈與支付 參與人的支付：是所有階段博弈支付的貼現值之和，或者加權平均值。 注意：注意：在重復博弈中，階段博弈可能是靜態博弈，也可能是動態博弈，因此，重復博弈可能是完美信息重復博弈和不完美信息重復博弈。此處我們僅討論完美信息重復博弈。 假定在位者在不同的市場上有20家連鎖店，進入者試圖進入這些市場。如果進入者進入了每一個市場，此時

6、博弈就變成了20次重復博弈。當進入者進入第1個市場時，在位者應該如何反應呢？ 猜想：殺雞儆猴的效應猜想：殺雞儆猴的效應 連鎖店悖論連鎖店悖論 單階段博弈矩陣單階段博弈矩陣默許斗爭進入3，3-1，0不進入1，101，10進入者支付在位者納什均衡為：在位者在每一個市場選擇默許，進入者在位者在每一個市場選擇默許，進入者在每一個市場選擇進入。在每一個市場選擇進入。 單階段擴展式博弈單階段擴展式博弈階段博弈的子博弈精煉納什均衡為：在位者在每一個市在位者在每一個市場選擇默許，進入者在每一個市場選擇進入。場選擇默許，進入者在每一個市場選擇進入。重復博弈的子博弈精煉納什均衡：在位者在每一個市場在位者在每一個市

7、場選擇默許，進入者在每一個市場選擇進入。選擇默許，進入者在每一個市場選擇進入。FC-1,03,3k1,10IOA定理：定理： 如果階段博弈G有唯一的Nash均衡，則對任意有限的T，重復博弈G(T)有唯一的子博弈精煉解，即G的Nash均衡結果在每一個階段重復進行。問題：囚徒困境中的囚徒有可能實現高效的均衡嗎？考察下列博弈考察下列博弈1,15,00,00,54,40,00,00,03,3121L2L1M1R2M2R 存在多重納什均衡的情形存在多重納什均衡的情形 單階段單階段Nash均衡均衡： (L1 , L2)和(R1, R2)； 合作均衡合作均衡：（M1，M2）； 問題：問題：合作均衡能否出現？

8、 現在假設博弈重復兩次，可以根據以下原則構造均衡：由第一階段的結果，預測第二階段的均衡。 例如：若第一階段出現(M1,M2)(即出現合作)，則第二階段為(R1,R2)(即“好的納什均衡”)；若第一階段沒有出現(M1, M2), 則第二階段為(L1,L2)(即“差的納什均衡”)。1,15,00,00,54,40,00,00,03,3121L2L1M1R2M2R 冷酷戰略（冷酷戰略（grim strategies） 也稱觸發戰略； 以囚徒困境為例：開始選擇抵賴，而且一直選擇抵賴直到有一方選擇了坦白，然后永遠選擇坦白； 這意味著：一旦哪個參與人選擇了坦白，就觸發了懲罰的扳機。根據上述原則，可構造如下

9、戰略：根據上述原則，可構造如下戰略： S1：第一階段選擇M1；如果第一階段結果為(M1，M2)，則下一階段選R1；否則選擇L1。 S2：第一階段選擇M2；如果第一階段結果為(M1，M2) ，則下一階段選R2；否則選擇L2。根據上述戰略，博弈可表示為： 這意味著，合作可以在第一階段達到。這一結論說明，對將來行動所作的可信威脅或承諾可以影響到當前的行對將來行動所作的可信威脅或承諾可以影響到當前的行動動。 問題：問題：沒有考慮貼現率。1+1,1+1 5+1,0+1 0+1,0+10+1,5+1 4+3,4+3 0+1,0+10+1,0+1 0+1,0+1 3+1,3+1121L2L1M1R2M2R二

10、、二、無限次重復博弈與無名氏定理 定義：定義： 給定一階段博弈G，令 表示相應的無限次重復博弈，其中G將無限次的重復進行，且參與人的貼現率為 。對每個t，之前t-1次階段博弈的結果在t階段開始進行前都可以被觀測到，每個參與人在 中的收益都是該參與人在無限次的階段博弈中所得收益的貼現值。( , )G( , )G 在有限次重復博弈G(T)中，由第t+1階段開始的一個子博弈為G、進行T-t次的重復博弈，可表示為G(T-t)。 在無限次重復博弈 中，由 t+1 階段開始的每個子博弈都等同于初始博弈 。 和在有限情況下相似，博弈 到 t 階段為止有多少不同的可能進行過程，就有多少從 t+1 階段開始的子

11、博弈。( , )G( , )G( , )G考慮如下無限次重復博弈：考慮如下無限次重復博弈：1,15,00,54,4UDLR12 對于階段博弈為上述博弈的有限次重復博弈，合作不可能形成。 但對于無限次重復博弈，在一定的貼現率下，合作有可能形成。構造如下觸發策略： S1：第i階段選擇D；如果第i階段結果為(D，R)，則下一階段選D；否則以后一直選擇U。 S2：第i階段選擇R；如果第i階段結果為(D，R)，則下一階段選R；否則以后一直選擇L。 貼現率的求解：225+1+14+4+414所以 可以證明：在一定的貼現率下，上述觸發策略構成Nash均衡；1,15,00,54,4UDLR12 可行收益可行收

12、益 一組收益 為階段博弈G的可行收益，如果它們是G的純戰略收益的凸組合，即純戰略收益的加權平均，權重非負且和為1。 前述階段博弈的可行收益集合如下圖所示。12( , , , )nx xx陰影部分為上述博弈的可行收益區間陰影部分為上述博弈的可行收益區間(0,5)(1,1)(0,0)(4,4)(5,0):(3,3):(1/3,1/3,1/3,0) (4,4),(5,0),(0,5),(1,1)收益權重 平均收益平均收益 給定貼現率 ，無限的收益序列 的平均收益為123，11(1)ttt211 ttt 111ttt所以故11(1)ttt 重復博弈總收益 階段博弈收益相等時的總收益無限次重復博弈的無名

13、氏定理：無限次重復博弈的無名氏定理： 令G為一個n人階段博弈，令 為G的 一個Nash均衡下的收益，且用 表 示G的其它任何可行收益， 表示可行收益的 集合。 若存在 則存在貼現率 ，使無限重復博弈 存在一個子博弈精煉Nash均衡，其平均收益可達到 。12( , , , )ne ee12( ,)nx xx, ,iiixei xX對12( ,)nx xx( , )GX 子博弈精煉子博弈精煉Nash均衡的可行收益區間均衡的可行收益區間(0,5)(1,1)(0,0)(4,4)(5,0) 無名氏定理的一個解釋無名氏定理的一個解釋 在無限次重復博弈中，如果參與人具有足夠的耐心（只要滿足一定的條件），那么

14、任何滿足個人理性的可行收益向量都可以通過一個特定的子博弈精煉Nash均衡得到。無名氏定理舉例1,15,00,54,4UDLR12 該博弈中唯一的納什均衡為（U，L），兩個局中人在此均衡下的收益都是1；所以，只要無限次重復博弈中參與人可行的平均單期收益不小于1，這樣的收益就是一個可能的均衡收益。 這說明，無限次重復博弈能夠導致帕累托改進。三、重復博弈的社會學含義三、重復博弈的社會學含義 羅伯特愛克斯羅德(政治科學家)對合作問題進行了實驗性研究，他組織了一場計算機競賽。這個競賽的思路非常簡單：任何想參加這個競賽的人都扮演“囚徒困境”案例中的一個囚犯，他們把自己的戰略編入計算機程序，然后他們的程序會

15、被成雙成對地融入不同的組合，分好組以后，參與者就開始玩“囚徒困境”的游戲。他們每個人都要在合作與背叛之間做出選擇，并且游戲重復多次。 競賽的第一個回合交上來的14個程序中包含了各種復雜的戰略。但使愛克斯羅德和其他人深為吃驚的是，競賽的桂冠屬于其中最簡單的戰略：一報還一報(Tit for Tat)。這是多倫多大學心理學家阿納托拉帕波特提交上來的戰略。 一報還一報戰略：一報還一報戰略：它總是以合作開局，但從此以后就采取以其人之道還治其人之身的戰略。也就是說，一報還一報的戰略實行了胡蘿卜加大棒的原則。 一報還一報戰略：永遠不先背叛對方，從這個意義上來說它是“善意的”。 一報還一報戰略：會在下一輪中對

16、對手的前一次合作給予回報（哪怕以前這個對手曾經背叛過它），從這個意義上來說它是寬容的。 一報還一報戰略：會采取背叛的行動來懲罰對手前一次的背叛，從這個意義上來說它又是“強硬的”。 一報還一報戰略：簡單明了，對手一看便知其用意何在。 一報還一報戰略的特征 為了驗證上述結果的合理性，愛克斯羅德又舉行了第二輪競賽，特別邀請了更多的人，看看能否從一報還一報戰略那兒將桂冠奪過來。這次有62個程序參加了競賽，結果是一報還一報又一次奪魁。 競賽的結論無可爭議地證明，具備以下特點的人，將總會是贏家：（1）本性善良；（2）品格寬厚；（3）不失強硬；（4）處事干練，原則簡單明了。 一報還一報戰略的勝利對人類和其他生物的合作行為的形成具有深刻地含義。 愛克斯羅德在合作進化一書中指出，一報還一報戰略能導致社會各個領域的合作，包括在最無指望的環境中的合作。 典型的例子就是越戰中自發產生的“自己活，也讓他人活”的原則：只要對方不開槍傷人，我也不開槍。一報還一報一報還一報自然界的例子自然界的例子 真菌從地下的石頭中汲取養分，為海藻提供了食物，而海藻反過來又為真菌提供了光合作用； 金蟻合歡樹為一種螞蟻提供了食物，而這種螞蟻反過來又保護了該樹； 無花果樹的花是黃蜂的食物，而黃蜂反過來又為無花果樹傳授花粉，將樹種撒向四處。 一報還一報的社會學含