重復(fù)博弈囚徒困境

1、1.6 重復(fù)博弈一、有限重復(fù)博弈 定義： 對(duì)于完全信息博弈 ，其中 I(1,2,n)為參與者集合， 為所有參與者的策略空間， 為所有參與者的收益函數(shù)，如果G在時(shí)間上()不斷重復(fù)，并且在下一次博弈G開(kāi)始前，所有以前博弈的歷史都被觀察到，那么它構(gòu)成的動(dòng)態(tài)博弈就稱之為重復(fù)博弈，G就為重復(fù)博弈中的階段博弈。如果G重復(fù)進(jìn)行T次，那么G(T)就表示重復(fù)進(jìn)行T次的有限重復(fù)博弈。如果G重復(fù)進(jìn)行 次，那么G( )就表示無(wú)限重復(fù)博弈。 1二、序貫博弈與重復(fù)博弈 1、序貫博弈：參與人在前一個(gè)階段的行動(dòng)選擇決定隨后的子博弈結(jié)構(gòu)，從后一個(gè)決策節(jié)開(kāi)始的博弈不同于從前一個(gè)決策節(jié)開(kāi)始的博弈。 2、重復(fù)博弈：簡(jiǎn)單地說(shuō)，就是同樣

2、結(jié)構(gòu)的博弈重復(fù)多次，其中的每次博弈稱為“階段博弈”。階段博弈可以是靜態(tài)博弈，也可以是動(dòng)態(tài)博弈； 3、重復(fù)博弈的三項(xiàng)特征：（1）階段博弈之間沒(méi)有“物質(zhì)上”的聯(lián)系；序貫博弈涉及到物質(zhì)上的聯(lián)系。（2）所有參與人觀測(cè)到博弈過(guò)去的歷史；（3）參與人的總支付是所有階段博弈支付的貼現(xiàn)值之和或加權(quán)平均值。24、參與人在某一階段的博弈選擇依賴于其他參與人過(guò)去的行動(dòng)歷史，所以，參與人在重復(fù)博弈中的戰(zhàn)略空間遠(yuǎn)遠(yuǎn)大于和復(fù)雜于在每一個(gè)階段博弈中的戰(zhàn)略空間。這一點(diǎn)意味著，重復(fù)博弈可能帶來(lái)一些“額外的”均衡結(jié)果，這些均衡結(jié)果在一次性博弈中是從來(lái)不會(huì)出現(xiàn)的。5、影響重復(fù)博弈均衡結(jié)果的主要因素是博弈的重復(fù)次數(shù)。重復(fù)次數(shù)的重要性

3、來(lái)源于參與人在短期利益和長(zhǎng)遠(yuǎn)利益之間的權(quán)衡。 32.51 有限次重復(fù)博弈：連鎖店悖論例1：見(jiàn)下圖市場(chǎng)進(jìn)入博弈，假定同樣的市場(chǎng)有20個(gè)，其均衡會(huì)與單個(gè)市場(chǎng)不同嗎？ 均衡1：進(jìn)入者總是選擇進(jìn)入，在位者選擇默許； 均衡2：在位者選擇斗爭(zhēng)，進(jìn)入者總是選擇不進(jìn)入。40，50-10，00，3000，300 在位者 默許 斗爭(zhēng)進(jìn)入者 進(jìn)入不進(jìn)入圖1 市場(chǎng)進(jìn)入博弈4定理1、如果階段博弈G有惟一的納什均衡，則對(duì)任意有限的T，重復(fù)博弈G(T)有惟一的子博弈完美納什均衡，即G的納什均衡結(jié)果在每一個(gè)階段重復(fù)進(jìn)行。 注意：此定律的一個(gè)重要條件是：?jiǎn)坞A段博弈存在“唯一”的納什均衡。例2：重復(fù)博弈舉例 1、參與人：商人1，

4、 商人2； 2、行動(dòng)空間：都是誠(chéng)信、欺騙； 3、博弈次數(shù)：兩次； 4、支付函數(shù)： 見(jiàn)圖2所示。4，40，55，01，1 商人1 誠(chéng)信 欺騙商人2誠(chéng)信欺騙圖2 信用困境（1）5 逆推到第一階段，將第二階段的納什均衡收益代入，則如圖3所示。 有限重復(fù)博弈納什 均衡是（欺騙，欺騙） 此題解釋了現(xiàn)實(shí)中 存在的一類(lèi)現(xiàn)象 普遍的欺詐行為；沒(méi)有解釋另一類(lèi)現(xiàn)象廣泛的合作。 為了在理論上容納合作解，博弈論主要從三個(gè)方面來(lái)加以發(fā)展： 一是引入多重均衡； 二是引入無(wú)限重復(fù)博弈； 三是引入信息不完全。 5，51，66，12，2 商人1 誠(chéng)信 欺騙商人2誠(chéng)信欺騙圖3 信用困境（2）62.52 無(wú)限重復(fù)博弈 1、合作解要

5、在有限重復(fù)博弈申出現(xiàn)要求階段博弈G必須存在多重納什均衡，但在無(wú)限重復(fù)博弈中這一條件并不是必需的：即使階段博弈G只存在惟一納什均衡，無(wú)限重復(fù)博弈中也可以存在子博弈完美納什均衡解，其中沒(méi)有任何一個(gè)階段結(jié)果是G的納什均衡。顯然這和定理1 相對(duì)立，根本的原因就在于博弈可以進(jìn)行無(wú)限期。如果博弈是無(wú)限的，那么長(zhǎng)遠(yuǎn)利益就要好于短期利益。 2、解開(kāi)連鎖店難題的辦法之一是引入信息的不完全性，或者博弈重復(fù)無(wú)限次，或者重復(fù)未知的次數(shù)。7（一）數(shù)學(xué)分析假設(shè)利率r，則貼現(xiàn)率為：1/（1+r），貼現(xiàn)因子 ，一般的有1/（1+r）= ； 有了貼現(xiàn)因子，我們就能比較無(wú)限博弈中的不同收益值。 收益值計(jì)算法如下：如果未來(lái)的收益系

6、列為： 其收益流現(xiàn)值為：如果每一期的收益都是R，則貼現(xiàn)值為：8例4：仍考察信用困境博弈1、單階段博弈是：（欺騙，欺騙）2、無(wú)限重復(fù)博弈中子博弈精練納什均衡有可能為：每一階段都是合作：（誠(chéng)信，誠(chéng)信）；3、此博弈的可能完美均衡： 觸發(fā)策略，又叫冷酷戰(zhàn)略；4，40，55，01，1 商人1 誠(chéng)信 欺騙商人2誠(chéng)信欺騙圖6 信用困境（1）9（二）證明冷酷戰(zhàn)略戰(zhàn)略表述：在第一階段選擇誠(chéng)信，且如果所有前面t一1階段的結(jié)果都是(誠(chéng)信，誠(chéng)信)，則在第t階段，選擇誠(chéng)信，否則選擇欺騙，并永久欺騙下去。 1、先證明此戰(zhàn)略是納什均衡：即如果給定參與者j的策略為觸發(fā)策略，那么參與者i的最優(yōu)反應(yīng)也是觸發(fā)策略，即觸發(fā)策略是彼此

7、策略的最優(yōu)反應(yīng)。假設(shè) 與1足夠接近的條件下，我們用計(jì)算來(lái)證明；10 參與者j在某階段選擇欺騙將會(huì)使當(dāng)期得到5的收益，但卻會(huì)觸發(fā)參與者i的永遠(yuǎn)不合作策略，于是未來(lái)每一階段的收益都將成為1。 收益現(xiàn)值為： 如果采取合作，設(shè)V為j在無(wú)限博弈中的最優(yōu)反映的收益現(xiàn)值，則有： a、 故： b、 當(dāng)且僅當(dāng)下式成立，選擇誠(chéng)信才是最優(yōu)的。4，40，55，01，1 商人1 誠(chéng)信 欺騙商人2誠(chéng)信欺騙圖6 信用困境（1）（1）（2）112、再證明此戰(zhàn)略是子博弈精練納什均衡 無(wú)限重復(fù)博弈的每一子博弈都等同于原博弈，而觸發(fā)策略是無(wú)限重復(fù)信用博弈的納什均衡，因而它同樣是任意一個(gè)子博弈的納什均衡，根據(jù)完美均衡的定義可知觸發(fā)策

8、略是一個(gè)子博弈精練納什均衡。在無(wú)限重復(fù)信用困境的觸發(fā)策略納什均衡中，當(dāng)博弈進(jìn)行到t階段時(shí)，存在兩個(gè)可能的歷史過(guò)程：(1)所有以前階段的結(jié)果都是(誠(chéng)信，誠(chéng)信)的子博弈；(2)至少有一個(gè)前面階段的結(jié)果不是(誠(chéng)信，誠(chéng)信)的子博弈。如果參與者在整個(gè)博弈中采取觸發(fā)策略，則：(1)參與者在第一類(lèi)子博弈中的最優(yōu)策略同樣是觸發(fā)策略，我們已證明它是整個(gè)博弈的一個(gè)納什均衡；(2)參與者在第二類(lèi)子博弈中的最優(yōu)策略是永遠(yuǎn)單純重復(fù)階段博弈的均衡(欺騙，躍騙)，它本身就是階段博弈G的納什均衡。這就證明了無(wú)限重復(fù)信用困境中的冷酷戰(zhàn)略納什均衡是子博弈精練的。 12（三）以牙還牙戰(zhàn)略也是此博弈的子博弈精練納什均衡，可類(lèi)似以上進(jìn)

9、行證明。 1、先后悔比后后悔好； （1）0階段欺騙，1階段后悔的收益現(xiàn)值 (3) （2）0階段欺騙，t階段后悔的收益現(xiàn)值 (4)132、后悔要比永遠(yuǎn)欺騙好； （3）式大于（1）式：當(dāng)貼現(xiàn)因子為 1/4時(shí)，參與者j選擇后悔，以求得重新合作要優(yōu)于永遠(yuǎn)欺騙。 3、證明永遠(yuǎn)誠(chéng)信比欺騙之后再后悔要優(yōu) ，等于證明（2）式大于（3）式；4、結(jié)論：當(dāng)貼現(xiàn)因子 接近1(1/4)，以牙還牙策略組合是重復(fù)無(wú)限信用博弈的納什均衡。 14（四）無(wú)名氏定理 當(dāng)貼現(xiàn)因子充分接近1，無(wú)限重復(fù)信用博弈存在合作解，那么是否所有的無(wú)服重復(fù)博弈G( )都存在合作解?這就引出了無(wú)名氏定理。無(wú)名氏定理：令G為一個(gè)n人階段博弈， 為以G為

10、階段博弈的無(wú)限次重復(fù)博弈， 是G的一個(gè)納什均衡（純戰(zhàn)略或混合戰(zhàn)略）， 是 決定的支付向量， 是一個(gè)任意可行的支付向量，V是可行支付向量集合。那么，對(duì)于任何滿足 的 ，存在一個(gè)貼現(xiàn)因子 使得對(duì)于所有的 ， 是一個(gè)特定的子博弈精練納什均衡結(jié)果。 子博弈精練納什均衡的多重性是無(wú)限次重復(fù)博弈的普遍問(wèn)題。15（五）對(duì)無(wú)名氏定理的三點(diǎn)說(shuō)明：1、懲罰點(diǎn)（納什威脅點(diǎn)）：在上述定理中，階段博弈的納什均衡 可能是混合戰(zhàn)略均衡也可能是純戰(zhàn)略均衡；由 決定的支付向量 是達(dá)到任何精練均衡的結(jié)果v的懲罰點(diǎn)。2、可行支付： 稱為一個(gè)可行支付向量，如果它是階段博弈G的純戰(zhàn)略支付的凸組合；所有可行支付向量構(gòu)成可行支付集合V。

11、凸組合：假設(shè) 為參與者選擇純策略組合下所有可能收益組合的集合（r為向量），向量 中的任意一個(gè)元素 ，且 那么， 就稱之為凸組合。 16 例如“信用困境”的所有純戰(zhàn)略收益的凸組合如圖7的陰影部分 其納什威脅點(diǎn)是e=(1,1)。無(wú)名氏定理告訴我們，如果 足夠接近于1，由過(guò)點(diǎn)（1,1）的兩條垂直線圍成的可行集合上的任意點(diǎn)都可以是一個(gè)子博弈精練納什均衡的結(jié)果。3、平均支付：假設(shè)貼現(xiàn)因子為 ，無(wú)窮收益系列為： ，其貼現(xiàn)值之和為： ； 另假設(shè)有無(wú)窮收益系列： ，其貼現(xiàn)值之和為： ；要求 成為無(wú)窮序列 的平均支付，要求： 因此有：即：平均支付是貼現(xiàn)值之和的標(biāo)準(zhǔn)化（標(biāo)準(zhǔn)化因子是 ）可行收益集合(1,1)(5,

12、0)(4,4)(0,5)企業(yè)1收益企業(yè)2收益o17例：無(wú)限重復(fù)庫(kù)諾特雙頭壟斷下的共謀1、在納什均衡下，庫(kù)諾特均衡產(chǎn)量： 庫(kù)諾特均衡利潤(rùn)：2、在壟斷情況下：壟斷產(chǎn)量： 壟斷利潤(rùn)：3、無(wú)窮次重復(fù)博弈，考慮冷酷戰(zhàn)略： 首先選擇生產(chǎn) ，繼續(xù)選擇生產(chǎn) ； 直到有一個(gè)企業(yè)選擇生產(chǎn)： ，然后生產(chǎn)： （1）給定企業(yè) j 堅(jiān)持冷酷戰(zhàn)略，證明其為納什均衡： 企業(yè) i 堅(jiān)持合作，每期利潤(rùn)為： 如果企業(yè) i 選擇短期最優(yōu)產(chǎn)量： 當(dāng)期利潤(rùn)為： 但隨后的利潤(rùn)流量為：18如果下列條件滿足，企業(yè) i 會(huì)選擇合作均衡： 解得：（2）證明其為子博弈精練納什均衡； （略）（3）討論 a、此博弈也有多個(gè)精練納什均衡，“總選擇庫(kù)諾特均

13、衡產(chǎn)量”就是一個(gè)精練納什均衡；若產(chǎn)量選擇： 都是冷酷戰(zhàn)略精練均衡的一個(gè)特定結(jié)果。 b、其可行支付集與子博弈 精練均衡可達(dá)到的支付集 如圖7所示19c、保留支付（最小最大支付）： 是當(dāng)其他參與人試圖給參與人 i 最大懲罰時(shí)參與人 i 能保證自己得到的最大支付；d、個(gè)人理性支付：指大于保留支付的支付；202.53 參與人不固定時(shí)的重復(fù)博弈 消費(fèi)者市場(chǎng)交易就是一個(gè)典型的例子。廠商是長(zhǎng)期的固定參與人，重復(fù)提供產(chǎn)品；而消費(fèi)者是不固定的，假設(shè)一次博弈只有一個(gè)廠商，一個(gè)消費(fèi)者，且只買(mǎi)一件產(chǎn)品，支付矩陣如圖8。 （1）在一次性博弈中，均衡結(jié)果為（不購(gòu)買(mǎi)，低質(zhì)量） （2）在重復(fù)博弈中均衡結(jié)果為（購(gòu)買(mǎi)，高質(zhì)量）；條件是 （3）此例說(shuō)明消費(fèi)者偏好大商場(chǎng)買(mǎi)東西而不信賴走街竄巷的小商販的原因