1、Lecture 6: Repeated Games（III）以“囚徒困境博弈”為例1嚴格競爭博弈的重復博弈嚴格競爭博弈的重復博弈零和博弈或其他嚴格競爭博弈的零和博弈或其他嚴格競爭博弈的有限次有限次和和無限次無限次重復博弈，都不可能產生比一重復博弈，都不可能產生比一次性博弈更理想的結果，博弈方的唯一次性博弈更理想的結果，博弈方的唯一選擇是選擇是始終采用原博弈的混合策略納什始終采用原博弈的混合策略納什均衡策略均衡策略，因為重復博弈不會改變博弈，因為重復博弈不會改變博弈方之間的利益對立關系。方之間的利益對立關系。以以“猜硬幣博弈猜硬幣博弈”為例為例2存在唯一純策略納什均衡存在唯一純策略納什均衡博弈的

2、重復博弈博弈的重復博弈3在有唯一純策略納什均衡的博弈中，博在有唯一純策略納什均衡的博弈中，博弈方之間的利益關系不再是始終對立的，弈方之間的利益關系不再是始終對立的，而是有很大一致性甚至完全一致。而是有很大一致性甚至完全一致。4乙甲存在唯一純策略納什均衡博弈的重復博弈存在唯一純策略納什均衡博弈的重復博弈？以以“存在唯一純策略納什均衡博存在唯一純策略納什均衡博弈弈”為原博弈的重復博弈中，博弈為原博弈的重復博弈中，博弈方的行為和博弈結果會不會發生方的行為和博弈結果會不會發生本質的變化呢？本質的變化呢？5乙甲存在唯一純策略納什均衡博弈的重復博弈存在唯一純策略納什均衡博弈的重復博弈存在唯一純策略納什均衡

3、博弈的重復博弈存在唯一純策略納什均衡博弈的重復博弈有限次重復博弈有限次重復博弈無限次重復博弈無限次重復博弈6囚徒困境博弈囚徒困境博弈7坦白坦白抵賴抵賴坦白坦白（-5，-5）（0，-8）抵賴抵賴（-8，0）（-1，-1）甲乙策略組合（坦白，坦白）是策略組合（坦白，坦白）是“囚徒困境囚徒困境”博弈的唯一純策略納什均衡。博弈的唯一純策略納什均衡。“囚徒困境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈“囚徒困境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈利用利用“逆推歸納法逆推歸納法”進行分析進行分析8坦白坦白抵賴抵賴坦白坦白（-5，-5）（0，-8）抵賴抵賴（-8，0）（-1，-1）乙甲“囚徒困

4、境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈首先，分析第二階段（即第二次重復時）兩博弈首先，分析第二階段（即第二次重復時）兩博弈方的選擇。方的選擇。第二階段仍然是兩囚徒之間的一個囚徒困境博弈，此時第二階段仍然是兩囚徒之間的一個囚徒困境博弈，此時前一階段的結果已成為既成事實，此后又不再有任何的前一階段的結果已成為既成事實，此后又不再有任何的后續階段，因此實現自身當前的最大利益是兩博弈方在后續階段，因此實現自身當前的最大利益是兩博弈方在該階段決策中的唯一原則。該階段決策中的唯一原則。因此不管前一次博弈的結果如何，第二階段的唯一結果因此不管前一次博弈的結果如何，第二階段的唯一結果就是原博弈唯一的

5、納什均衡（坦白，坦白），雙方得益就是原博弈唯一的納什均衡（坦白，坦白），雙方得益的現在值為（的現在值為（5 5 ，5 5 ）。）。9坦白坦白抵賴抵賴坦白坦白（-5，-5）（0，-8）抵賴抵賴（-8，0）（-1，-1）乙甲“囚徒困境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈然后，回到第一階段，即第一次博弈。然后，回到第一階段，即第一次博弈。理性的博弈方在第一階段就對后一階段（第二階段）理性的博弈方在第一階段就對后一階段（第二階段）的結局非常清楚。因此不管第一階段的博弈結果是的結局非常清楚。因此不管第一階段的博弈結果是什么，雙方在整個重復博弈中的最終得益，都將是什么，雙方在整個重復博弈中的最終

6、得益，都將是第一階段得益的基礎上各加第一階段得益的基礎上各加5 5 。因此從第一階段。因此從第一階段的選擇來看，這個重復博弈與如下得益矩陣表示的的選擇來看，這個重復博弈與如下得益矩陣表示的一次性博弈實際上是完全等價的。一次性博弈實際上是完全等價的。10坦白坦白抵賴抵賴坦白坦白（-55 ，-55 ）（05 ，-85 ）抵賴抵賴（-85 ，05 ）（-15 ，-15 ）乙甲“囚徒困境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈11坦白坦白抵賴抵賴坦白坦白（-5-5 ，-5-5 ）（0-5 ，-8-5 ）抵賴抵賴（-8-5 ，0-5 ）（-1-5 ，-1-5 ）乙乙甲甲該等價博弈有唯一的純策略納什

7、均衡（坦白，坦該等價博弈有唯一的純策略納什均衡（坦白，坦白），雙方的得益則為（白），雙方的得益則為（-5-5-5-5 ，-5-5-5-5 ）。）。“囚徒困境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈“囚徒困境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈存在唯一的子博弈完美納什均衡：存在唯一的子博弈完美納什均衡：（坦白，坦白），（坦白，坦白）；（坦白，坦白），（坦白，坦白）；博弈方的總得益組合為（博弈方的總得益組合為（-5-5-5-5 ，-5-5-5-5 ）。）。12“囚徒困境博弈囚徒困境博弈”的兩次重復博弈的兩次重復博弈囚徒困境博弈的兩次重復博弈相囚徒困境博弈的兩次重復博弈相當于一次性囚

8、徒困境博弈的簡單當于一次性囚徒困境博弈的簡單重復。重復。13“囚徒困境博弈囚徒困境博弈”的有限次重復博弈的有限次重復博弈（推廣）（推廣）“囚徒困境博弈囚徒困境博弈”的的 T T 次重復次重復博弈博弈存在唯一的子博弈完美納什均衡，即每次存在唯一的子博弈完美納什均衡，即每次重復都采用原博弈唯一的純策略納什均衡。重復都采用原博弈唯一的純策略納什均衡。14小結論小結論利用劃線法求解利用劃線法求解NashNash均衡解，都是在均衡解，都是在給定其他博弈方所取策略的條件下，比給定其他博弈方所取策略的條件下，比較同一博弈方采用不同策略時的得益大較同一博弈方采用不同策略時的得益大小。因此，在每個博弈方的各種可

9、能得小。因此，在每個博弈方的各種可能得益上加一個常數（不同博弈方的得益所益上加一個常數（不同博弈方的得益所加常數可以不同）之后，博弈的加常數可以不同）之后，博弈的NashNash均衡仍為均衡仍為“新新”博弈的均衡結果。博弈的均衡結果。15存在唯一純策略納什均衡博弈的有限次重復博弈存在唯一純策略納什均衡博弈的有限次重復博弈 定理定理： 設原博弈設原博弈G G有唯一的純策略納有唯一的純策略納什均衡，則對任意正整數什均衡，則對任意正整數T T ，重復博弈，重復博弈G G( (T T) ) 有唯一的子博弈完美納什均衡，有唯一的子博弈完美納什均衡，即各博弈方每個階段都采用即各博弈方每個階段都采用G G

10、的納什的納什均衡策略。均衡策略。1617存在唯一純策略納什均衡博弈的有限次重復博弈（存在唯一純策略納什均衡博弈的有限次重復博弈（續續） 利用逆推歸納法證明利用逆推歸納法證明 首先，分析重復博弈首先，分析重復博弈G(T)G(T)的最后一個階段，即第的最后一個階段，即第T T次重復次重復 由于第由于第T T次重復就是原博弈次重復就是原博弈G G，并且在該階段之后不再重復，因，并且在該階段之后不再重復，因此不管以前此不管以前T T-1 -1階段的博弈結果如何，在該階段中各博弈方必然階段的博弈結果如何，在該階段中各博弈方必然采用采用G G的唯一的納什均衡。的唯一的納什均衡。18存在唯一純策略納什均衡博

11、弈的有限次重復博弈（存在唯一純策略納什均衡博弈的有限次重復博弈（續續） 然后，再推回到前一階段，即第然后，再推回到前一階段，即第T T-1-1次重復次重復 由于此時各博弈方都知道下一階段由于此時各博弈方都知道下一階段( (即第即第T T階段階段) )的博弈結果，因此的博弈結果，因此對每個博弈方來說，從該階段開始的子博弈（即最后兩個階段）中對每個博弈方來說，從該階段開始的子博弈（即最后兩個階段）中各種策略組合的得益就是本階段的得益加上下一階段的均衡得益的各種策略組合的得益就是本階段的得益加上下一階段的均衡得益的貼現值。因此，各博弈方在該階段仍將采用貼現值。因此，各博弈方在該階段仍將采用G G的唯

12、一的納什均衡。的唯一的納什均衡。19存在唯一純策略納什均衡博弈的有限次重復博弈（存在唯一純策略納什均衡博弈的有限次重復博弈（續續） 依此類推直至博弈的第一階段。依此類推直至博弈的第一階段。 最終，可得結論！最終，可得結論！20存在唯一純策略納什均衡博弈的有限次重復博弈（存在唯一純策略納什均衡博弈的有限次重復博弈（續續） 有唯一純策略納什均衡的有限次重復博弈不比一次性博弈的有唯一純策略納什均衡的有限次重復博弈不比一次性博弈的結果理想，因為唯一的子博弈完美納什均衡是各博弈方每次結果理想，因為唯一的子博弈完美納什均衡是各博弈方每次重復都采用原博弈的納什均衡。重復都采用原博弈的納什均衡。21存在唯一純

13、策略納什均衡博弈的無限次重復博弈存在唯一純策略納什均衡博弈的無限次重復博弈存在唯一純策略納什均衡博弈的存在唯一純策略納什均衡博弈的無限無限次次重復博弈重復博弈以囚徒困境式博弈的無限次重復為例以囚徒困境式博弈的無限次重復為例22囚徒困境式博弈的無限次重復博弈囚徒困境式博弈的無限次重復博弈囚徒困境式博弈的無限次重復囚徒困境式博弈的無限次重復下面的分析將表明，在囚徒困境式博弈的下面的分析將表明，在囚徒困境式博弈的無限次重復博弈中，對雙方有利的合作無限次重復博弈中，對雙方有利的合作（指雙方克制自己的行為，為對方的利益指雙方克制自己的行為，為對方的利益和共同的利益著想，并非真正的聯合、合和共同的利益著想

14、，并非真正的聯合、合作作）在子博弈完美納什均衡中有可能存在，）在子博弈完美納什均衡中有可能存在，博弈可能出現比較理想的結果。博弈可能出現比較理想的結果。以以削價競爭博弈削價競爭博弈的無限次重復為例。的無限次重復為例。23削價競爭博弈削價競爭博弈24博弈方博弈方2HL博弈方博弈方1H4，40，5L5，01，1H和和L分別表示高價（不削價）和低價（削價）策略分別表示高價（不削價）和低價（削價）策略 削價競爭博弈（削價競爭博弈（續續）該博弈的一次性博弈有唯一的純策略納什該博弈的一次性博弈有唯一的純策略納什均衡（均衡（L L，L L），得益組合為（），得益組合為（1 1，1 1）。）。25博弈方博弈方

15、2HL博弈方博弈方1H4，40，5L5，01，1削價競爭博弈（削價競爭博弈（續續）策略組合（策略組合（H，H）實現的得益組合（）實現的得益組合（4，4）比（比（1，1）高得多。但因為（）高得多。但因為（H，H）并不）并不是該博弈的納什均衡，因此在一次性博弈是該博弈的納什均衡，因此在一次性博弈中不會被采用，這是一個典型的中不會被采用，這是一個典型的囚徒困境囚徒困境式博弈式博弈。26博弈方博弈方2HL博弈方博弈方1H4，40，5L5，01，1削價競爭博弈（削價競爭博弈（續續）該博弈的該博弈的有限次重復博弈有限次重復博弈不能實現潛不能實現潛在的合作利益，兩博弈方在每次重復在的合作利益，兩博弈方在每次

16、重復中都不會采用效率較高的（中都不會采用效率較高的（H H，H H）。）。27博弈方博弈方2HL博弈方博弈方1H4，40，5L5，01，1觸發策略觸發策略（Trigger StrategyTrigger Strategy）重復博弈中博弈方首先試探合作，一旦發現重復博弈中博弈方首先試探合作，一旦發現對方不合作則用不合作報復的策略，稱為對方不合作則用不合作報復的策略，稱為“觸發策略觸發策略”。觸發策略是重復博弈中實現合作和提高均衡觸發策略是重復博弈中實現合作和提高均衡效率的關鍵機制，是重復博弈分析中構造子效率的關鍵機制，是重復博弈分析中構造子博弈完美納什均衡的基本博弈完美納什均衡的基本“構件構件”

17、之一。之一。28 “冷酷策略冷酷策略”（grim strategy）又稱為）又稱為“觸發策觸發策略略”（trigger strategy），因為任何參與人的），因為任何參與人的一次性不合作將觸發永遠的不合作。（張維一次性不合作將觸發永遠的不合作。（張維迎，迎，2012，第，第126頁）頁） 在冷酷戰略下，參與人沒有改正錯誤的機會。在冷酷戰略下，參與人沒有改正錯誤的機會。所以這個戰略確實是很冷酷的，但冷酷的結所以這個戰略確實是很冷酷的，但冷酷的結果是雙方都沒有背叛對方的積極性，因而是果是雙方都沒有背叛對方的積極性，因而是友善的。（張維迎，友善的。（張維迎，2012，第，第127頁）頁）2930削

18、價競爭博弈的無限次重復削價競爭博弈的無限次重復削價競爭博弈的無限次重復削價競爭博弈的無限次重復假設兩博弈方都采用假設兩博弈方都采用觸發策略觸發策略：第一階段采用：第一階段采用H H，在第，在第 t t 階段，如果前階段，如果前 t t-1 -1 階段的結果都是階段的結果都是(H(H，H)H)，則繼續采，則繼續采用用H H，否則采用，否則采用L L。雙方在無限次重復博弈中都是雙方在無限次重復博弈中都是先試圖合作，第一次無條件選先試圖合作，第一次無條件選H H，如果對方采用的也是合作，如果對方采用的也是合作態度，則堅持選態度，則堅持選H H；一旦發現；一旦發現對方不合作（選擇對方不合作（選擇L L

19、），則用），則用以后永遠選擇以后永遠選擇L L報復。報復。博弈方博弈方2HL博弈方博弈方1H4，40，5L5，01，1削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）證明：證明：當貼現系數當貼現系數 較大時，雙方采較大時，雙方采用上述觸發策略構成無限次重復博用上述觸發策略構成無限次重復博弈的一個子博弈完美納什均衡。弈的一個子博弈完美納什均衡。31博弈方博弈方2HL博弈方博弈方1H4，40，5L5，01，1觸發策略：觸發策略：第一階段采用第一階段采用H H，在第在第 t t 階段，如果前階段，如果前 t t-1 -1 階階段的結果都是段的結果都是(H(H，H)H)，則繼，則繼續采用續采

20、用H H，否則采用，否則采用L L。削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）證明：證明：首先，證明雙方采用上述觸發策略是一個首先，證明雙方采用上述觸發策略是一個納什均衡。納什均衡。然后，證明上述觸發策略組合構成整個無然后，證明上述觸發策略組合構成整個無限次重復博弈的子博弈完美納什均衡。限次重復博弈的子博弈完美納什均衡。 32觸發策略：觸發策略：第一階段采用第一階段采用H H，在第在第 t t 階段，如果前階段，如果前 t t-1 -1 階階段的結果都是段的結果都是(H(H，H)H)，則繼，則繼續采用續采用H H，否則采用，否則采用L L。削價競爭博弈的無限次重復（削價競爭博弈

21、的無限次重復（續續） 證明雙方采用上述觸發策略是一個納什均衡。證明雙方采用上述觸發策略是一個納什均衡。 假設博弈方假設博弈方1 1已經采用了觸發策略，證明在已經采用了觸發策略，證明在 達到一達到一定水平時，采用同樣的觸發策略是博弈方定水平時，采用同樣的觸發策略是博弈方2 2的最佳反的最佳反應策略。應策略。 因為博弈方因為博弈方1 1與博弈方與博弈方2 2是對稱的，因此只要這個結是對稱的，因此只要這個結論成立，就可以確定上述觸發策略是兩博弈方相互論成立，就可以確定上述觸發策略是兩博弈方相互對對方策略的最佳反應，因此構成納什均衡。對對方策略的最佳反應，因此構成納什均衡。33觸發策略：觸發策略：第一

22、階段采用第一階段采用H H，在第，在第 t t 階段，如果前階段，如果前 t t-1 -1 階段的結果都階段的結果都是是(H(H，H)H)，則繼續采用，則繼續采用H H，否則采，否則采用用L L。削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續） 假定博弈方假定博弈方1 1已經采用觸發策略，證明在已經采用觸發策略，證明在達到一達到一定水平時，采用同樣的觸發策略是博弈方定水平時，采用同樣的觸發策略是博弈方2 2的最佳的最佳反應策略。反應策略。博弈方博弈方2 2對博弈方對博弈方1 1觸發策略的最佳反應策略的后觸發策略的最佳反應策略的后半部分與觸發策略的后半部分是一樣的。半部分與觸發策略的后

23、半部分是一樣的。由于在某個階段出現與（由于在某個階段出現與（H H，H H）不同的結果）不同的結果以后博弈方以后博弈方1 1將永遠采用將永遠采用L L，此時博弈方，此時博弈方2 2也只也只有一直選擇有一直選擇L L。34觸發策略：觸發策略：第一階段采用第一階段采用H H，在第，在第 t t 階段，如果前階段，如果前 t t-1 -1 階段的結果都階段的結果都是是(H(H，H)H)，則繼續采用，則繼續采用H H，否則采，否則采用用L L。削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）確定博弈方確定博弈方2 2在第一階段的最優選擇。在第一階段的最優選擇。如果博弈方如果博弈方2 2采用采

24、用L L，那么在第一階段能得到那么在第一階段能得到5 5，但以后引起博弈方但以后引起博弈方1 1一直采用一直采用L L的報復，自己的報復，自己也只能一直采用也只能一直采用L L，得益將永遠為，得益將永遠為1 1，總得益，總得益的貼現值為的貼現值為3525 11.51 觸發策略：觸發策略：第一階段采用第一階段采用H H，在第，在第 t t 階段，如果前階段，如果前 t t-1 -1 階段的結果都階段的結果都是是(H(H，H)H)，則繼續采用，則繼續采用H H，否則采，否則采用用L L。削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）如果博弈方如果博弈方2 2采用采用H H，則在第一階段

25、他將得則在第一階段他將得4 4，下一，下一階段又面臨同樣的選擇。若記階段又面臨同樣的選擇。若記V V為博弈方為博弈方2 2在該重復在該重復博弈中每階段采用最佳選擇的總得益現在值，那么博弈中每階段采用最佳選擇的總得益現在值，那么從第二階段開始的無限次重復博弈與從第一階段開從第二階段開始的無限次重復博弈與從第一階段開始的只差一階段，因而在無限次重復時可看作相同始的只差一階段，因而在無限次重復時可看作相同的，其總得益的現在值折算成第一階段的得益為的，其總得益的現在值折算成第一階段的得益為V V ，因此當第一階段的最佳選擇是，因此當第一階段的最佳選擇是H H時，整個時，整個無限次重復博弈總得益的現在值

26、為：無限次重復博弈總得益的現在值為：364VV觸發策略：觸發策略：第一階段采用第一階段采用H H，在第，在第 t t 階段，如果前階段，如果前 t t-1 -1 階段的結果都階段的結果都是是(H(H，H)H)，則繼續采用，則繼續采用H H，否則采，否則采用用L L。削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）37441VVV削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）因此，當因此，當384511即即1/41/4時，博弈方時，博弈方2 2會采用會采用H H策略，否則會采用策略，否則會采用L L策略。即策略。即當當1/41/4時，時，博弈方博弈方2 2對博弈方對博弈方1

27、 1觸發策略的最佳反應是第觸發策略的最佳反應是第一階段采用一階段采用H H。 觸發策略：觸發策略：第一階段采用第一階段采用H H，在第，在第 t t 階段，如果前階段，如果前 t t-1 -1 階段的結果都階段的結果都是是(H(H，H)H)，則繼續采用，則繼續采用H H，否則采，否則采用用L L。削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）由于從第二階段開始的無限次重復博弈，由于從第二階段開始的無限次重復博弈，與從第一階段開始的無限次重復博弈是完與從第一階段開始的無限次重復博弈是完全相同的，因此博弈方第二階段的選擇必全相同的，因此博弈方第二階段的選擇必然也是然也是H H，第三階段

28、也同樣。，第三階段也同樣。39觸發策略：觸發策略：第一階段采用第一階段采用H H，在第，在第 t t 階段，如果前階段，如果前 t t-1 -1 階段的結果都階段的結果都是是(H(H，H)H)，則繼續采用，則繼續采用H H，否則采，否則采用用L L。削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）依此類推，只要博弈方依此類推，只要博弈方1 1采用前述觸發策略，采用前述觸發策略，那么博弈方那么博弈方2 2的最優選擇始終是的最優選擇始終是H H。當然，。當然，如果博弈方如果博弈方1 1偏離偏離H H，博弈方，博弈方2 2也必須用也必須用L L來來報復。報復。40削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）因此，博弈方因此，博弈方2 2對博弈方對博弈方1 1觸發策略的完整觸發策略的完整反應策略是同樣的觸發策略。反應策略是同樣的觸發策略。這就證明了這就證明了雙方采用上述觸發策略是一個納什均衡雙方采用上述觸發策略是一個納什均衡。41削價競爭博弈的無限次重復（削價競爭博弈的無限次重復（續續）證明上述觸發策略組合構成整個無限證明上述觸發策略組合構成整個無限次重復博弈的子博弈完美納什均衡。次重復博弈的子博弈完美納什均衡。因為重復博弈的子博