重復(fù)博弈的詳細(xì)介紹課件

重復(fù)博弈

主要內(nèi)容：一、有限次重復(fù)博弈二、無(wú)限次重復(fù)博弈與無(wú)名氏定理三、重復(fù)博弈的社會(huì)學(xué)含義重復(fù)博弈主要內(nèi)容：例子1-越戰(zhàn)戰(zhàn)場(chǎng)上的潛規(guī)則一名新兵剛上戰(zhàn)場(chǎng)，老兵按住他：別亂開槍！新兵問(wèn)：為什么？老兵對(duì)其解釋：曾有一段時(shí)間，雙方打得不可開交，結(jié)果大家都躲著，屎尿都撒在貓耳洞里，由于貓耳洞很潮濕，人呆在里面很難受，導(dǎo)致有人耳朵都發(fā)了霉，最后是誰(shuí)也打不著誰(shuí)，自己卻活受罪。此后，便慢慢達(dá)成默契：我出來(lái)你不開槍，你出來(lái)我也不開槍。例子1-越戰(zhàn)戰(zhàn)場(chǎng)上的潛規(guī)則例子2

一個(gè)男孩被視為傻瓜，因?yàn)槊慨?dāng)別人拿一枚1塊硬幣和5分硬幣讓他選的時(shí)候，他總是選5分的，有一個(gè)人覺(jué)得奇怪，就問(wèn)他：“為什么你不拿1塊錢的？”，男孩小聲回答：“假若我拿了1塊錢的硬幣，下次他們就不會(huì)再拿錢讓我選了?！蓖{和承諾的重要性：以上兩個(gè)例子帶給我們什么啟發(fā)？例子2威脅和承諾的重要性：以上兩個(gè)例子帶給我們什么啟發(fā)？問(wèn)題1

在相互聯(lián)系緊密的人際關(guān)系中，人們普遍比較注意禮節(jié)、道德，因?yàn)楹献骱蛥f(xié)調(diào)對(duì)大家都有好處；但是，我們又常常見到這樣的消息：在公共汽車上，兩個(gè)陌生人會(huì)為一個(gè)座位爭(zhēng)吵，為什么會(huì)發(fā)生這種事情？原因何在？問(wèn)題1問(wèn)題2在“囚徒困境”這一例子中，博弈的參與人為了追求自身利益的最大化，而陷入了個(gè)人理性與集體理性的沖突中，導(dǎo)致最優(yōu)的結(jié)果未能出現(xiàn)，即合作沒(méi)有產(chǎn)生。如果我們假定博弈可以多次重復(fù)進(jìn)行，結(jié)果是否會(huì)發(fā)生變化？是否會(huì)出現(xiàn)合作的局面？問(wèn)題2動(dòng)態(tài)博弈中涉及的一個(gè)重要問(wèn)題是，博弈過(guò)程中威脅和承諾如何影響博弈的進(jìn)程。重復(fù)博弈所關(guān)心的議題也與之相似：（1）將來(lái)可信的威脅或承諾如何影響到當(dāng)前的行動(dòng)？（2）在一次博弈中無(wú)法實(shí)現(xiàn)的均衡，在重復(fù)博弈中能否實(shí)現(xiàn)？一、有限次重復(fù)博弈動(dòng)態(tài)博弈中涉及的一個(gè)重要問(wèn)題是，博弈過(guò)程中威脅和承諾如何影響考察下列博弈該博弈存在唯一的Nash均衡，即（U，L）。同時(shí)注意到，該博弈還存在一個(gè)高效均衡（D，R），高效均衡對(duì)應(yīng)著一種合作行為。為什么高效的均衡不是納什均衡？如何保證這一高效均衡能夠?qū)崿F(xiàn)？1,15,00,54,4UDLR12考察下列博弈該博弈存在唯一的Nash均衡，即（U，L）。1,

兩次重復(fù)博弈的博弈樹假設(shè)將上述博弈重復(fù)兩次，那么第二次博弈開始時(shí)，第一次博弈的結(jié)果可視為已知。兩次重復(fù)博弈的博弈樹假設(shè)將上述博弈重復(fù)第二階段第一階段第一階段第二階段第一階段第一階段運(yùn)用逆推歸納法，可以發(fā)現(xiàn)上述重復(fù)博弈的子博弈精煉Nash均衡為：在每次博弈中，參與人1都選擇U，參與人2都選擇L。這說(shuō)明：在兩次重復(fù)博弈中，高效的均衡仍無(wú)法實(shí)現(xiàn)。同樣可證明：在n階段重復(fù)博弈(即博弈重復(fù)n次且每次博弈開始時(shí)，前面博弈的結(jié)果都已知)中，高效的均衡同樣無(wú)法實(shí)現(xiàn)。運(yùn)用逆推歸納法，可以發(fā)現(xiàn)上述重復(fù)博弈的子博弈精煉Nash均衡有限重復(fù)博弈定義定義：對(duì)于給定的階段博弈G，令G(T)表示G重復(fù)進(jìn)行T次的有限重復(fù)博弈，并且在下一次博弈開始前，所有之前博弈的進(jìn)程均可被觀測(cè)到。有限重復(fù)博弈定義定義：有限重復(fù)博弈的戰(zhàn)略、子博弈與支付戰(zhàn)略：重復(fù)博弈環(huán)境下，參與人的戰(zhàn)略非常復(fù)雜。一般地，我們定義參與人的一個(gè)戰(zhàn)略是在博弈的每個(gè)階段針對(duì)之前的博弈歷史而制定的行動(dòng)計(jì)劃；子博弈：子博弈要么仍然是重復(fù)博弈，要么是原博弈；有限重復(fù)博弈的戰(zhàn)略、子博弈與支付戰(zhàn)略：重復(fù)博弈環(huán)境下，參與人有限重復(fù)博弈的戰(zhàn)略、子博弈與支付參與人的支付：是所有階段博弈支付的貼現(xiàn)值之和，或者加權(quán)平均值。注意：在重復(fù)博弈中，階段博弈可能是靜態(tài)博弈，也可能是動(dòng)態(tài)博弈，因此，重復(fù)博弈可能是完美信息重復(fù)博弈和不完美信息重復(fù)博弈。此處我們僅討論完美信息重復(fù)博弈。有限重復(fù)博弈的戰(zhàn)略、子博弈與支付參與人的支付：是所有階段博弈假定在位者在不同的市場(chǎng)上有20家連鎖店，進(jìn)入者試圖進(jìn)入這些市場(chǎng)。如果進(jìn)入者進(jìn)入了每一個(gè)市場(chǎng)，此時(shí)博弈就變成了20次重復(fù)博弈。當(dāng)進(jìn)入者進(jìn)入第1個(gè)市場(chǎng)時(shí)，在位者應(yīng)該如何反應(yīng)呢？猜想：殺雞儆猴的效應(yīng)

連鎖店悖論假定在位者在不同的市場(chǎng)上有20家連鎖店，進(jìn)入者試圖進(jìn)入這些市

單階段博弈矩陣默許斗爭(zhēng)進(jìn)入3，3-1，0不進(jìn)入1，101，10進(jìn)入者支付在位者納什均衡為：在位者在每一個(gè)市場(chǎng)選擇默許，進(jìn)入者在每一個(gè)市場(chǎng)選擇進(jìn)入。單階段博弈矩陣默許斗爭(zhēng)進(jìn)入3，3-

單階段擴(kuò)展式博弈階段博弈的子博弈精煉納什均衡為：在位者在每一個(gè)市場(chǎng)選擇默許，進(jìn)入者在每一個(gè)市場(chǎng)選擇進(jìn)入。重復(fù)博弈的子博弈精煉納什均衡：在位者在每一個(gè)市場(chǎng)選擇默許，進(jìn)入者在每一個(gè)市場(chǎng)選擇進(jìn)入。單階段擴(kuò)展式博弈階段博弈的子博弈精定理：

如果階段博弈G有唯一的Nash均衡，則對(duì)任意有限的T，重復(fù)博弈G(T)有唯一的子博弈精煉解，即G的Nash均衡結(jié)果在每一個(gè)階段重復(fù)進(jìn)行。問(wèn)題：囚徒困境中的囚徒有可能實(shí)現(xiàn)高效的均衡嗎？定理：如果階段博弈G有唯一的Nash均考察下列博弈

存在多重納什均衡的情形單階段Nash均衡：

(L1,L2)和(R1,R2)；合作均衡：（M1，M2）；問(wèn)題：合作均衡能否出現(xiàn)？考察下列博弈存在多重納什均衡的情形單階段現(xiàn)在假設(shè)博弈重復(fù)兩次，可以根據(jù)以下原則構(gòu)造均衡：由第一階段的結(jié)果，預(yù)測(cè)第二階段的均衡。

例如：若第一階段出現(xiàn)(M1,M2)(即出現(xiàn)合作)，則第二階段為(R1,R2)(即“好的納什均衡”)；若第一階段沒(méi)有出現(xiàn)(M1,M2),則第二階段為(L1,L2)(即“差的納什均衡”)。現(xiàn)在假設(shè)博弈重復(fù)兩次，可以根據(jù)以下原則構(gòu)造均衡：由第一階段的

冷酷戰(zhàn)略（grimstrategies）也稱觸發(fā)戰(zhàn)略；以囚徒困境為例：開始選擇抵賴，而且一直選擇抵賴直到有一方選擇了坦白，然后永遠(yuǎn)選擇坦白；這意味著：一旦哪個(gè)參與人選擇了坦白，就觸發(fā)了懲罰的扳機(jī)。冷酷戰(zhàn)略（grimstrategies根據(jù)上述原則，可構(gòu)造如下戰(zhàn)略：S1：第一階段選擇M1；如果第一階段結(jié)果為(M1，M2)，則下一階段選R1；否則選擇L1。S2：第一階段選擇M2；如果第一階段結(jié)果為(M1，M2)，則下一階段選R2；否則選擇L2。根據(jù)上述原則，可構(gòu)造如下戰(zhàn)略：S1：第一階段選擇M1；如果第根據(jù)上述戰(zhàn)略，博弈可表示為：這意味著，合作可以在第一階段達(dá)到。這一結(jié)論說(shuō)明，對(duì)將來(lái)行動(dòng)所作的可信威脅或承諾可以影響到當(dāng)前的行動(dòng)。問(wèn)題：沒(méi)有考慮貼現(xiàn)率。根據(jù)上述戰(zhàn)略，博弈可表示為：這意味著，合作可以在第一階段達(dá)到二、無(wú)限次重復(fù)博弈與無(wú)名氏定理定義：給定一階段博弈G，令表示相應(yīng)的無(wú)限次重復(fù)博弈，其中G將無(wú)限次的重復(fù)進(jìn)行，且參與人的貼現(xiàn)率為。對(duì)每個(gè)t，之前t-1次階段博弈的結(jié)果在t階段開始進(jìn)行前都可以被觀測(cè)到，每個(gè)參與人在中的收益都是該參與人在無(wú)限次的階段博弈中所得收益的貼現(xiàn)值。二、無(wú)限次重復(fù)博弈與無(wú)名氏定理定義：在有限次重復(fù)博弈G(T)中，由第t+1階段開始的一個(gè)子博弈為G、進(jìn)行T-t次的重復(fù)博弈，可表示為G(T-t)。在無(wú)限次重復(fù)博弈中，由t+1階段開始的每個(gè)子博弈都等同于初始博弈。和在有限情況下相似，博弈到t階段為止有多少不同的可能進(jìn)行過(guò)程，就有多少?gòu)膖+1階段開始的子博弈。在有限次重復(fù)博弈G(T)中，由第t+1階段開始的一個(gè)子博弈為考慮如下無(wú)限次重復(fù)博弈：對(duì)于階段博弈為上述博弈的有限次重復(fù)博弈，合作不可能形成。但對(duì)于無(wú)限次重復(fù)博弈，在一定的貼現(xiàn)率下，合作有可能形成?？紤]如下無(wú)限次重復(fù)博弈：對(duì)于階段博弈為上述博弈的有限次重復(fù)博構(gòu)造如下觸發(fā)策略：S1：第i階段選擇D；如果第i階段結(jié)果為(D，R)，則下一階段選D；否則以后一直選擇U。S2：第i階段選擇R；如果第i階段結(jié)果為(D，R)，則下一階段選R；否則以后一直選擇L。構(gòu)造如下觸發(fā)策略：S1：第i階段選擇D；如果第i階段結(jié)果為(貼現(xiàn)率的求解：所以可以證明：在一定的貼現(xiàn)率下，上述觸發(fā)策略構(gòu)成Nash均衡；貼現(xiàn)率的求解：所以可以證明：在一定的貼現(xiàn)率下，上述觸發(fā)策略構(gòu)

可行收益一組收益為階段博弈G的可行收益，如果它們是G的純戰(zhàn)略收益的凸組合，即純戰(zhàn)略收益的加權(quán)平均，權(quán)重非負(fù)且和為1。前述階段博弈的可行收益集合如下圖所示?？尚惺找嬉唤M收益為階陰影部分為上述博弈的可行收益區(qū)間(0,5)(1,1)(0,0)(4,4)(5,0)陰影部分為上述博弈的可行收益區(qū)間(0,5)(1,1)(0,0

平均收益

給定貼現(xiàn)率，無(wú)限的收益序列的平均收益為所以故

重復(fù)博弈總收益

階段博弈收益相等時(shí)的總收益平均收益給定貼現(xiàn)率，無(wú)限的收益無(wú)限次重復(fù)博弈的無(wú)名氏定理：令G為一個(gè)n人階段博弈，令為G的一個(gè)Nash均衡下的收益，且用表示G的其它任何可行收益，表示可行收益的集合。若存在則存在貼現(xiàn)率，使無(wú)限重復(fù)博弈存在一個(gè)子博弈精煉Nash均衡，其平均收益可達(dá)到。無(wú)限次重復(fù)博弈的無(wú)名氏定理：令G為一個(gè)n人階段博弈，令

子博弈精煉Nash均衡的可行收益區(qū)間(0,5)(1,1)(0,0)(4,4)(5,0)子博弈精煉Nash均衡的可行收益區(qū)間(0,5)(1,1)

無(wú)名氏定理的一個(gè)解釋

在無(wú)限次重復(fù)博弈中，如果參與人具有足夠的耐心（只要滿足一定的條件），那么任何滿足個(gè)人理性的可行收益向量都可以通過(guò)一個(gè)特定的子博弈精煉Nash均衡得到。無(wú)名氏定理的一個(gè)解釋在無(wú)限次無(wú)名氏定理舉例該博弈中唯一的納什均衡為（U，L），兩個(gè)局中人在此均衡下的收益都是1；所以，只要無(wú)限次重復(fù)博弈中參與人可行的平均單期收益不小于1，這樣的收益就是一個(gè)可能的均衡收益。這說(shuō)明，無(wú)限次重復(fù)博弈能夠?qū)е屡晾弁懈倪M(jìn)。無(wú)名氏定理舉例該博弈中唯一的納什均衡為（U，L），兩個(gè)局中人三、重復(fù)博弈的社會(huì)學(xué)含義

羅伯特·愛克斯羅德(政治科學(xué)家)對(duì)合作問(wèn)題進(jìn)行了實(shí)驗(yàn)性研究，他組織了一場(chǎng)計(jì)算機(jī)競(jìng)賽。這個(gè)競(jìng)賽的思路非常簡(jiǎn)單：任何想?yún)⒓舆@個(gè)競(jìng)賽的人都扮演“囚徒困境”案例中的一個(gè)囚犯，他們把自己的戰(zhàn)略編入計(jì)算機(jī)程序，然后他們的程序會(huì)被成雙成對(duì)地融入不同的組合，分好組以后，參與者就開始玩“囚徒困境”的游戲。他們每個(gè)人都要在合作與背叛之間做出選擇，并且游戲重復(fù)多次。三、重復(fù)博弈的社會(huì)學(xué)含義羅伯特·愛克

競(jìng)賽的第一個(gè)回合交上來(lái)的14個(gè)程序中包含了各種復(fù)雜的戰(zhàn)略。但使愛克斯羅德和其他人深為吃驚的是，競(jìng)賽的桂冠屬于其中最簡(jiǎn)單的戰(zhàn)略：一報(bào)還一報(bào)(TitforTat)。這是多倫多大學(xué)心理學(xué)家阿納托·拉帕波特提交上來(lái)的戰(zhàn)略。

一報(bào)還一報(bào)戰(zhàn)略：它總是以合作開局，但從此以后就采取以其人之道還治其人之身的戰(zhàn)略。也就是說(shuō)，一報(bào)還一報(bào)的戰(zhàn)略實(shí)行了胡蘿卜加大棒的原則。

競(jìng)賽的第一個(gè)回合交上來(lái)的14個(gè)程序中包一報(bào)還一報(bào)戰(zhàn)略：永遠(yuǎn)不先背叛對(duì)方，從這個(gè)意義上來(lái)說(shuō)它是“善意的”。一報(bào)還一報(bào)戰(zhàn)略：會(huì)在下一輪中對(duì)對(duì)手的前一次合作給予回報(bào)（哪怕以前這個(gè)對(duì)手曾經(jīng)背叛過(guò)它），從這個(gè)意義上來(lái)說(shuō)它是"寬容的"。一報(bào)還一報(bào)戰(zhàn)略：會(huì)采取背叛的行動(dòng)來(lái)懲罰對(duì)手前一次的背叛，從這個(gè)意義上來(lái)說(shuō)它又是“強(qiáng)硬的”。一報(bào)還一報(bào)戰(zhàn)略：簡(jiǎn)單明了，對(duì)手一看便知其用意何在。

一報(bào)還一報(bào)戰(zhàn)略的特征一報(bào)還一報(bào)戰(zhàn)略：永遠(yuǎn)不先背叛對(duì)方，從這個(gè)意義上來(lái)說(shuō)它是“善意

為了驗(yàn)證上述結(jié)果的合理性，愛克斯羅德又舉行了第二輪競(jìng)賽，特別邀請(qǐng)了更多的人，看看能否從一報(bào)還一報(bào)戰(zhàn)略那兒將桂冠奪過(guò)來(lái)。這次有62個(gè)程序參加了競(jìng)賽，結(jié)果是一報(bào)還一報(bào)又一次奪魁。

競(jìng)賽的結(jié)論無(wú)可爭(zhēng)議地證明，具備以下特點(diǎn)的人，將總會(huì)是贏家：（1）本性善良；（2）品格寬厚；（3）不失強(qiáng)硬；（4）處事干練，原則簡(jiǎn)單明了。為了驗(yàn)證上述結(jié)果的合理性，愛克斯羅德又舉行了第一報(bào)還一報(bào)戰(zhàn)