王康寧大牛IOI與博弈論

IOIDay2題目講解

及

一些有趣博弈游戲清華大學(xué)王康寧王康寧大牛IOI與博弈論第1頁歡迎隨時(shí)指出課上內(nèi)容錯(cuò)誤以及不清楚地方?？陀^地說，本節(jié)課內(nèi)容比較簡(jiǎn)單有趣、人民群眾喜聞樂見，面向非集訓(xùn)隊(duì)選手，意在讓大家在被虐之后體驗(yàn)一下虐人感覺。勉勵(lì)主動(dòng)回答下列問題，有小獎(jiǎng)品哦。因?yàn)榇蟛糠掷佣急容^經(jīng)典，假如你以前有所研究話，能夠把講話/做游戲機(jī)會(huì)留給其它同學(xué)。設(shè)有投票步驟，答對(duì)無獎(jiǎng)勵(lì)，不提議萬年棄權(quán)。為了確保博弈時(shí)雙方同時(shí)進(jìn)行決議，請(qǐng)希望參加游戲同學(xué)準(zhǔn)備好紙筆。申明王康寧大牛IOI與博弈論第2頁P(yáng)artI

IOIDay2題目講解王康寧大牛IOI與博弈論第3頁IOI參賽感想王康寧大牛IOI與博弈論第4頁某系統(tǒng)由N道連續(xù)門和N個(gè)開關(guān)組成。N道門按前后次序依次排列，開關(guān)和門一一對(duì)應(yīng)。門和開關(guān)均按0,1,…,(N-1)次序編號(hào)。0號(hào)門離你最近。全部開關(guān)都位于入口處。你并不知道哪個(gè)開關(guān)控制哪道門。每個(gè)開關(guān)都有“上”和“下”兩種狀態(tài)，其中有且只有一個(gè)狀態(tài)是正確。假如一個(gè)開關(guān)處于正確狀態(tài)，它所對(duì)應(yīng)門就會(huì)打開；假如它處于錯(cuò)誤狀態(tài)，與之對(duì)應(yīng)門就會(huì)關(guān)閉。不一樣開關(guān)有不一樣正確狀態(tài)，但你并不知道哪個(gè)開關(guān)在哪種狀態(tài)下是正確。Problem1:洞穴(cave)王康寧大牛IOI與博弈論第5頁你能夠這么做，將全部開關(guān)設(shè)置為某種狀態(tài)組合，然后走進(jìn)地下洞穴系統(tǒng)去查看哪道門是第一道被關(guān)閉門。因?yàn)殚T是不透明，所以你不會(huì)知道這道關(guān)閉門之后門是打開還是關(guān)閉。你有時(shí)間嘗試至多70,000次開關(guān)狀態(tài)不一樣組合。你任務(wù)是確定每個(gè)開關(guān)正確狀態(tài)是什么，以及門和開關(guān)之間對(duì)應(yīng)關(guān)系。時(shí)間限制:2秒內(nèi)存限制:32MB1≤N≤5,000Problem1:洞穴(cave)王康寧大牛IOI與博弈論第6頁P(yáng)roblem1:洞穴(cave)王康寧大牛IOI與博弈論第7頁考慮依次求出0號(hào)門對(duì)應(yīng)是哪個(gè)開關(guān)，1號(hào)門對(duì)應(yīng)是哪個(gè)開關(guān)，···，(N–1)號(hào)門對(duì)應(yīng)是哪個(gè)開關(guān)。每次固定之前門對(duì)應(yīng)開關(guān)為打開狀態(tài)，每次翻轉(zhuǎn)一個(gè)未知開關(guān)，直至當(dāng)前門改變狀態(tài)，便可推斷這一開關(guān)與當(dāng)前門對(duì)應(yīng)，同時(shí)還能求出打開狀態(tài)對(duì)應(yīng)“上”還是“下”。這么做需要約N2/4次問詢。Problem1:洞穴(cave)王康寧大牛IOI與博弈論第8頁實(shí)際上，我們無需依次嘗試每個(gè)開關(guān)。經(jīng)過二分查找，每次能夠降低二分之一可能選擇。這么做需要約N*log2N次問詢，符合題中要求。Problem1:洞穴(cave)王康寧大牛IOI與博弈論第9頁一共有N個(gè)玩具,整數(shù)W[i]表示這個(gè)玩具重量，整數(shù)S[i]表示這個(gè)玩具體積。機(jī)器人有兩種，分別是：弱機(jī)器人和小機(jī)器人。有A個(gè)弱機(jī)器人。每個(gè)弱機(jī)器人有一個(gè)重量限制X[i]，它只能拿起重量嚴(yán)格小于X[i]玩具，與玩具體積大小沒關(guān)系。有B個(gè)小機(jī)器人。每個(gè)小機(jī)器人有一個(gè)體積限制Y[i]，它只能拿起體積嚴(yán)格小于Y[i]玩具，與玩具重量大小沒相關(guān)系。Problem2:機(jī)器人(robots)王康寧大牛IOI與博弈論第10頁Marita每個(gè)機(jī)器人用1分鐘將一個(gè)玩具拿走放好。不一樣機(jī)器人能夠同時(shí)拿走并放好不一樣玩具。你任務(wù)是確定Marita機(jī)器人是否能夠?qū)⑷客婢叨际帐昂?，假如是，那么最少用多少時(shí)間能夠收拾好。時(shí)間限制:3秒內(nèi)存限制:64MB1≤N≤1,000,0000≤A,B≤50,000且1≤A+B1≤X[i],Y[i],W[i],S[i]≤2,000,000,000Problem2:機(jī)器人(robots)王康寧大牛IOI與博弈論第11頁P(yáng)roblem2:機(jī)器人(robots)王康寧大牛IOI與博弈論第12頁考慮二分答案，這么只需檢驗(yàn)m分鐘內(nèi)是否能夠把全部玩具收拾好。將每個(gè)玩具i與坐標(biāo)(W[i]:重量,S[i]:體積)對(duì)應(yīng)，這么每個(gè)弱機(jī)器人能夠收拾某一橫坐標(biāo)以左玩具，每個(gè)小機(jī)器人能夠收拾某一縱坐標(biāo)以下玩具。從右至左添加這些玩具，一旦某一時(shí)刻某個(gè)弱機(jī)器人能夠收拾當(dāng)前玩具，則它能夠收拾之后全部玩具。所以我們應(yīng)盡可能保留弱機(jī)器人，即優(yōu)先使用小機(jī)器人。Problem2:機(jī)器人(robots)王康寧大牛IOI與博弈論第13頁選擇小機(jī)器人時(shí)，當(dāng)然應(yīng)該優(yōu)先選擇能夠收拾當(dāng)前玩具小機(jī)器人中，Y[i]值最小一個(gè)。這么，我們便有了檢驗(yàn)可行性貪心策略。實(shí)現(xiàn)時(shí)能夠借助C++STL中set完成。時(shí)間復(fù)雜度為O(N*log2N)。Problem2:機(jī)器人(robots)王康寧大牛IOI與博弈論第14頁有一個(gè)R行C列網(wǎng)格。我們用(P,Q)表示位于P行Q列單元格。每個(gè)單元格包含一個(gè)非負(fù)整數(shù)，游戲開始時(shí)全部單元格內(nèi)整數(shù)均為零。有兩種操作：修改一個(gè)單元格(p,q)內(nèi)包含整數(shù)值；計(jì)算一個(gè)給定子矩陣中全部單元格內(nèi)數(shù)字最大條約數(shù)（GCD），子矩陣兩個(gè)對(duì)角分別為(p,q)和(u,v)。Problem3:游戲(game)王康寧大牛IOI與博弈論第15頁修改單元格內(nèi)數(shù)據(jù)共NU次，問詢GCD操作共NQ次。強(qiáng)制在線。時(shí)間限制:13秒內(nèi)存限制:230MB1≤R,C≤1,000,000,0000≤NU≤22,0000≤NQ≤250,000格子中數(shù)非負(fù)且小于1018Problem3:游戲(game)王康寧大牛IOI與博弈論第16頁使用經(jīng)典兩層trie樹嵌套，每次問詢時(shí)間復(fù)雜度為O(log2N)，空間復(fù)雜度為O(NU*log2N)。只要把內(nèi)層trie樹改為Splay樹即可把空間復(fù)雜度降至O(NU*logN)。Problem3:游戲(game)王康寧大牛IOI與博弈論第17頁P(yáng)artII

一些有趣博弈游戲王康寧大牛IOI與博弈論第18頁警方逮捕A,B兩名嫌疑犯，但沒有足夠證據(jù)指控二人有罪。于是警方分開囚禁嫌疑犯，分別和二人見面，并向雙方提供以下相同選擇：若一人認(rèn)罪并作證檢控對(duì)方，而對(duì)方保持緘默，此人將即時(shí)獲釋，緘默者將判監(jiān)。若二人都保持緘默，則二人一樣判監(jiān)2年。若二人相互檢舉，則二人一樣判監(jiān)8年。Example1:囚徒困境王康寧大牛IOI與博弈論第19頁囚徒B囚徒A招供不招供招供(-8,-8)(0,

-10)不招供(-10,0)(-2,-2)Example1:囚徒困境王康寧大牛IOI與博弈論第20頁投票我該招供。我不該招供。王康寧大牛IOI與博弈論第21頁我們稱策略B嚴(yán)格優(yōu)于(strictlydominate)策略A，假如不論其它人選擇何種策略，選擇B均會(huì)比選擇A取得嚴(yán)格更加好結(jié)果。我們稱策略B弱優(yōu)于(weaklydominate)策略A，假如不論其它人選擇何種策略，選擇B均會(huì)比選擇A取得不更差結(jié)果，且存在某種其它人策略選擇，使得B比A取得嚴(yán)格更加好結(jié)果。以上兩種情況統(tǒng)稱策略B優(yōu)于(dominate)策略A。概念：優(yōu)勢(shì)策略與劣勢(shì)策略王康寧大牛IOI與博弈論第22頁稱策略B是嚴(yán)格優(yōu)勢(shì)策略(strictlydominantstrategy)，假如策略B嚴(yán)格優(yōu)于任何其它策略。稱策略B是弱優(yōu)勢(shì)策略(weaklydominantstrategy)，假如策略B優(yōu)于任何其它策略，而且存在某種策略A，使得策略B弱優(yōu)于策略A。稱策略B是嚴(yán)格劣勢(shì)策略(strictlydominatedstrategy)，假如存在某策略嚴(yán)格優(yōu)于策略B。稱策略B是弱劣勢(shì)策略(weaklydominatedstrategy)，假如存在某策略弱優(yōu)于策略B。概念：優(yōu)勢(shì)策略與劣勢(shì)策略王康寧大牛IOI與博弈論第23頁

CCF

某OIer正常進(jìn)行分?jǐn)?shù)取相反數(shù)試圖取得高分(5,0)(-5,

-100)試圖取得低分(-5,0)(100,-100)Example2:一次OI考試王康寧大牛IOI與博弈論第24頁純策略納什均衡(PureStrategyNashEquilibrium)是指這么純策略組合：對(duì)于任意一個(gè)玩家，假如其它玩家策略不變，該玩家單方面改變自己策略不會(huì)增加收益。上例中，CCF選擇正常進(jìn)行比賽、選手試圖取得高分是唯一純策略納什均衡。囚徒困境中，兩人都招供是唯一純策略納什均衡。純策略納什均衡一定存在嗎？概念：純策略納什均衡王康寧大牛IOI與博弈論第25頁

玩家B玩家A(0,0)(1,

-1)(-1,1)(-1,1)(0,0)(1,

-1)(1,

-1)(-1,1)(0,0)概念：純策略納什均衡王康寧大牛IOI與博弈論第26頁

玩家B玩家A石頭剪刀布石頭(0,0)(1,

-1)(-1,1)剪刀(-1,1)(0,0)(1,

-1)布(1,

-1)(-1,1)(0,0)概念：純策略納什均衡王康寧大牛IOI與博弈論第27頁門將射手向左向右向左(0.2,-0.2)(0.7,

-0.7)向右(0.8,-0.8)(0.4,-0.4)Example3:點(diǎn)球大戰(zhàn)王康寧大牛IOI與博弈論第28頁混合策略納什均衡（MixedStrategyNashEquilibrium）是指這么混合策略組合：對(duì)于任意一個(gè)玩家，假如其它玩家策略不變，該玩家單方面改變自己策略不會(huì)增加期望收益。當(dāng)玩家數(shù)有限且策略數(shù)有限時(shí)，混合策略納什均衡一定存在。概念：混合策略納什均衡王康寧大牛IOI與博弈論第29頁學(xué)生老師寫作業(yè)不寫作業(yè)檢驗(yàn)作業(yè)(-1,0)(3,

-10)不檢驗(yàn)作業(yè)(1,0)(-3,4)Example4:我該寫作業(yè)嗎？王康寧大牛IOI與博弈論第30頁Example4:我該寫作業(yè)嗎？在納什均衡中，只有3/4學(xué)生寫作業(yè)。老師很生氣。老師希望增加寫作業(yè)學(xué)生百分比。于是······老師將不寫作業(yè)處罰提升至10倍。王康寧大牛IOI與博弈論第31頁學(xué)生老師寫作業(yè)不寫作業(yè)檢驗(yàn)作業(yè)(-1,0)(3,

-100)不檢驗(yàn)作業(yè)(1,0)(-3,4)Example4:我該寫作業(yè)嗎？王康寧大牛IOI與博弈論第32頁投票老師總是說誰不寫作業(yè)就罰抄100遍，也沒見寫作業(yè)人多啊。新納什均衡里，寫作業(yè)人數(shù)不變。這是好政策，新納什均衡中，寫作業(yè)學(xué)生數(shù)量一定有所增加。我就是有冒險(xiǎn)精神，處罰越大越不寫作業(yè)！新納什均衡里，寫作業(yè)人數(shù)降低。王康寧大牛IOI與博弈論第33頁Example5:B國(guó)侵略B入侵A反抗B迎戰(zhàn)(0,0)B撤退(2,1)A投降(1,2)王康寧大牛IOI與博弈論第34頁投票A國(guó)還是投降吧。士可殺不可辱！A國(guó)應(yīng)該奮起反抗。王康寧大牛IOI與博弈論第35頁Example5:B國(guó)侵略B國(guó)軍隊(duì)遠(yuǎn)渡重洋侵略A國(guó)，卻難免撤退命運(yùn)。B軍統(tǒng)帥靈機(jī)一動(dòng)······燒船！王康寧大牛IOI與博弈論第36頁Example5:B國(guó)侵略B入侵A反抗B迎戰(zhàn)(0,0)A投降(1,2)王康寧大牛IOI與博弈論第37頁Example5:B國(guó)侵略注意B國(guó)統(tǒng)帥策略是燒船。而不是偷偷把船鑿出小孔。在對(duì)方不知情情況下降低自己可選策略是毫無意義。王康寧大牛IOI與博弈論第38頁逆向歸納法(BackwardInduction)指按時(shí)間次序倒序，從游戲結(jié)束開始，依次推理出每一步最優(yōu)策略。

概念：逆向歸納法王康寧大牛IOI與博弈論第39頁有N只獅子，由大到小依次標(biāo)號(hào)為1，2，···，N。有一天，他們發(fā)覺了一只小羊。獅子等級(jí)制度森嚴(yán)，這只羊只能由1號(hào)獅子來吃。假如1號(hào)獅子不吃，一切結(jié)束；假如他吃了小羊，那么他會(huì)暫時(shí)失去戰(zhàn)斗力，可能(也只可能)被2號(hào)獅子吃掉。假如2號(hào)獅子吃掉1號(hào)獅子，那他也會(huì)暫時(shí)失去戰(zhàn)斗力，可能(也只可能)被3號(hào)獅子吃掉，以這類推。每只獅子都已保命為首要目標(biāo)，當(dāng)然，有食物吃就最好了。Example6:我能夠吃你嗎？王康寧大牛IOI與博弈論第40頁假如N=1假如N=2假如N=3假如N=4…所以，當(dāng)且僅當(dāng)N為奇數(shù)時(shí)，1號(hào)獅子會(huì)吃掉小羊。Example6:我能夠吃你嗎？王康寧大牛IOI與博弈論第41頁給出一個(gè)N*M石子陣。兩個(gè)人輪番取每次取某個(gè)石子，和全部它上邊、右邊、右上現(xiàn)存石子。取到最終一個(gè)石子人輸。問先手是否有必勝策略。Example7:一個(gè)取石子游戲王康寧大牛IOI與博弈論第42頁其實(shí)我不會(huì)玩。但我知道先手有必勝策略，除非N=M=1。Example7:一個(gè)取石子游戲王康寧大牛IOI與博弈論第43頁假定N，M不全為1，這么先手只取最右上角石子不會(huì)立刻結(jié)束游戲。用反證法，假設(shè)先手沒有必勝策略。則不論他選擇哪個(gè)石子，都無法改變失敗命運(yùn)，尤其地，只取最右上角石子也一樣。Example7:一個(gè)取石子游戲王康寧大牛IOI與博弈論第44頁取掉最右上角石子后，局面進(jìn)入了當(dāng)前先手必勝狀態(tài)，所以他能夠選取某個(gè)石子，去掉它和它上邊、右邊、右上現(xiàn)存石子，使局面進(jìn)入當(dāng)前先手必?cái)顟B(tài)。然而這個(gè)狀態(tài)，是最初先手一步就能夠到達(dá)，也就是說，最初先手能夠選取某個(gè)石子，使局面進(jìn)入當(dāng)前先手(對(duì)手)必?cái)顟B(tài)。所以先手必勝，與假設(shè)矛盾。所以假設(shè)不成立，即先手必勝。Example7:一個(gè)取石子游戲王康寧大牛IOI與博弈論第45頁Example8:OIerOSvs.MacrohardMacrohard壟斷市場(chǎng)開發(fā)OIerOS投入市場(chǎng)Macrohard降價(jià)打擊(-1,0)Macrohard不采取行動(dòng)(1,1)不開發(fā)OIerOS(0,3)王康寧大牛IOI與博弈論第46頁假設(shè)Macrohard壟斷了十個(gè)地域互不相干市場(chǎng)。這十個(gè)地域互不相干OIer依次面臨這一博弈。我們來模擬一下。假如使用逆向歸納法推理呢？為何給出了不一樣結(jié)論？Example8:OIerOSvs.Macrohard王康寧大牛IOI與博弈論第47頁兩個(gè)人各持一把槍，槍中只有一發(fā)子彈，面對(duì)面站著，相距足夠遠(yuǎn)。兩個(gè)人不停向前走，隨時(shí)能夠選擇開槍。假如某人擊中便是勝者。假如未擊中，仍須繼續(xù)向前走，對(duì)手能夠等到距離很小時(shí)再開槍。也就是說，假如未擊中便輸?shù)袅擞螒?。Example9:決斗游戲王康寧大牛IOI與博弈論第48頁對(duì)兩個(gè)人命中率隨距離改變函數(shù)F(x)，G(x)作出以下假設(shè)：F(0)=1,G(0)=1.F(x),G(x)在[0,+∞)上連續(xù)且單調(diào)遞減.F(x)→0(x→+∞),G(x)→0(x→+∞).為便于分析，我們認(rèn)為兩個(gè)人輪番行動(dòng)，每次選擇開槍或前行一步。這么，當(dāng)步長(zhǎng)越來越小時(shí)，就越來越靠近原來游戲了。Example9:決斗游戲王康寧大牛IOI與博弈論第49頁投票兩個(gè)人會(huì)同時(shí)到達(dá)應(yīng)該開槍臨界點(diǎn)。當(dāng)然是命中率高人先開槍了。笨鳥先飛，當(dāng)然是命中率低人先開槍了。王康寧大牛IOI與博弈論第50頁假如已知對(duì)方下一步不會(huì)開槍，我就沒有必要在這時(shí)開槍。假如F(x)+G(x)<1，我就沒有必要在這時(shí)開槍。假如F(x)+G(x)>1且已知對(duì)方下一步會(huì)開槍，我就應(yīng)該在這時(shí)開槍。在兩側(cè)使用逆向歸納法，能夠發(fā)覺，正確策略是:一旦F(x)+G(x)≥1，便開槍。Example9:決斗游戲王康寧大牛IOI與博弈論第51頁兩個(gè)人分一元錢，規(guī)則以下：一個(gè)人提議分配規(guī)則。另一個(gè)人決定是否同意。假如同意，那就按此規(guī)則分配；假如不一樣意，這一元錢便會(huì)流失，兩個(gè)人空手而歸。修改一下規(guī)則：此游戲共進(jìn)行K輪。在每一輪中假如雙方達(dá)成協(xié)議，便依此分配收益，游戲結(jié)束；假如沒有達(dá)成協(xié)議，那么總收益降低為之前s倍(0<s<1)，下一輪中由另一人提議分配規(guī)則。這里我們假定一元錢分配能夠任意精細(xì)。ExampleA:討價(jià)還價(jià)王康寧大牛IOI與博弈論第52頁當(dāng)K趨于正無窮時(shí)，即能夠進(jìn)行無限輪時(shí)，結(jié)果怎樣呢？又當(dāng)s趨于1時(shí)，即每次折損很小時(shí)，結(jié)果怎樣呢？之前我們假定兩個(gè)人有相同折損系數(shù)，假如折損系數(shù)不一樣呢？若在t輪后成交將一元錢分配為a1,a2

(a1+a2=1)，那么兩個(gè)人收益分別為a1*s1t

，a2*s2t

。再令K趨于正無窮。令s1=1-p1Δ，s2=1-p2Δ，其中Δ趨于零。那么這一元錢會(huì)怎樣分配呢？ExampleA:討價(jià)還價(jià)王康寧大牛IOI與博弈論第53頁這一博弈游戲能夠看成份配買家對(duì)商品期望價(jià)值與賣家成本之間差值，也就是討價(jià)還價(jià)。經(jīng)過上面討論，我們發(fā)覺，在與賣方討價(jià)還價(jià)中：要裝作自己很有時(shí)間(折損系數(shù)小)。要偽裝成對(duì)商品期望價(jià)值較低樣子(直接取得部分可分配收益)。最好在賣方快要打烊時(shí)前往(對(duì)方折損系數(shù)大)。拆穿賣方對(duì)成本過高虛報(bào)(增加可分配收益)。ExampleA:討價(jià)還價(jià)王康寧大牛IOI與博弈論第54頁有A，B兩個(gè)團(tuán)體對(duì)國(guó)會(huì)即將公布草案感興趣。假如草案經(jīng)過，A取得收益3.假如草案未經(jīng)過，B取得收益2.國(guó)會(huì)決定舉行拍賣，規(guī)則是第二價(jià)格密封拍賣：兩個(gè)人同時(shí)寫下出價(jià)，出價(jià)較高者贏得拍賣，并支付次高出價(jià)，未贏得拍賣者無支出。在這里，假如A獲勝，則草案經(jīng)過；不然草案不經(jīng)過。在這里，若兩人出價(jià)相同，則認(rèn)為A獲勝。ExampleB:第二價(jià)格密封拍賣王康寧大牛IOI與博弈論第55頁A，B分別應(yīng)怎樣出價(jià)？在這里，報(bào)出對(duì)自己實(shí)際價(jià)值是一個(gè)弱優(yōu)勢(shì)策略。下面，我們假定兩人均不會(huì)使用弱劣勢(shì)策略。ExampleB:第二價(jià)格密封拍賣王康寧大牛IOI與博弈論第56頁現(xiàn)在，情況有了改變。假如國(guó)會(huì)否決了此議案，一切結(jié)束。假如國(guó)會(huì)經(jīng)過此議案，議案要提交給總統(tǒng)，總統(tǒng)能夠使用否決權(quán)?？偨y(tǒng)決定再進(jìn)行一次一樣拍賣。不論A是否獲勝，她之前贏得拍賣支出無法收回。假如A已經(jīng)以2代價(jià)贏得了第一次拍賣，她應(yīng)怎樣應(yīng)對(duì)這第二次拍賣？淹沒成本(sunkcost)ExampleB:第二價(jià)格密封拍賣王康寧大牛IOI與博弈論第57頁在開始時(shí)雙方都知道會(huì)有兩次拍賣，博弈會(huì)怎樣進(jìn)行？現(xiàn)在假設(shè)若A輸?shù)袅说诙闻馁u，她能夠收回第一次支出，只需支付ε作為手續(xù)費(fèi)。游戲會(huì)怎樣進(jìn)行？有一個(gè)人有著弱優(yōu)勢(shì)策略，是A還是B？ExampleB:第二價(jià)格密封拍賣王康寧大牛IOI與博弈論第58頁假如我們重復(fù)K次囚徒困境游戲，結(jié)果會(huì)怎樣呢？ExampleC:囚徒困境2玩家B玩家A合作背叛合作(2,2)(-1,3)背叛(3,-1)(0,0)王康寧大牛IOI與博弈論第59頁投票在全部玩家都是理性前提下，重復(fù)屢次囚徒困境會(huì)迫使玩家選擇合作。在全部玩家都是理性前提下，重復(fù)屢次囚徒困境玩家依然會(huì)選擇背叛。王康寧大牛IOI與博弈論第60頁假如K=1，就是普通囚徒困境，玩家會(huì)選擇背叛。假如K=2，玩家已知下一輪中雙方一定會(huì)選擇背叛，所以下一輪收益不需要納入本輪考慮之中(淹沒成本)，所以會(huì)選擇背叛。假如K=3，玩家已知后兩輪中雙方一定會(huì)選擇背叛，因今后兩輪收益不需要納入本輪考慮之中，所以會(huì)選擇背叛?！瓕?duì)于任意正整數(shù)K，進(jìn)行K輪囚徒困境不會(huì)使理性玩家選擇合作。ExampleC:囚徒困境2王康寧大牛IOI與博弈論第61頁ExampleC:囚徒困境2

玩家乙玩家甲A(合作)B(背叛)CA(合作)(4,4