王康寧大牛：IOI2013與博弈論

1、IOI2013 Day2 題目講解及一些有趣的博弈游戲1歡迎隨時(shí)指出課上內(nèi)容的錯(cuò)誤以及不清楚的地方?？陀^地說，本節(jié)課內(nèi)容比較簡單有趣、人民群眾喜聞樂見，面向非集訓(xùn)隊(duì)選手，旨在讓大家在被虐之后體驗(yàn)一下虐人的感覺。鼓勵(lì)積極回答問題，有小獎(jiǎng)品哦。由于大部分例子都比較經(jīng)典，如果你以前有所研究的話，可以把發(fā)言/做游戲的機(jī)會(huì)留給其他同學(xué)。設(shè)有投票環(huán)節(jié)，答對(duì)無獎(jiǎng)勵(lì)，不建議萬年棄權(quán)。為了保證博弈時(shí)雙方同時(shí)進(jìn)行決策，請(qǐng)希望參與游戲的同學(xué)準(zhǔn)備好紙筆。聲明2Part IIOI2013 Day2 題目講解3IOI2013 參賽感想4某系統(tǒng)由N 道連續(xù)的門和N 個(gè)開關(guān)組成。N 道門按前后順序依次排列，開關(guān)和門一一對(duì)應(yīng)。

2、門和開關(guān)均按 0, 1, , (N - 1) 的順序編號(hào)。0號(hào)門離你最近。所有開關(guān)都位于入口處。你并不知道哪個(gè)開關(guān)控制哪道門。每個(gè)開關(guān)都有“上”和“下”兩種狀態(tài)，其中有且只有一種狀態(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)下是正確的。Problem 1: 洞穴(cave)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)狀

3、態(tài)的不同組合。你的任務(wù)是確定每個(gè)開關(guān)的正確狀態(tài)是什么，以及門和開關(guān)之間的對(duì)應(yīng)關(guān)系。時(shí)間限制: 2秒 內(nèi)存限制: 32 MB1 N 5,000Problem 1: 洞穴(cave)6Problem 1: 洞穴(cave)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次詢問。Problem 1: 洞穴(cave)8事實(shí)上，我們無需依次嘗試每個(gè)開關(guān)。通過二分查找，每次可以減少一半的

4、可能選擇。這樣做需要約N*log2N次詢問，符合題中要求。Problem 1: 洞穴(cave)9一共有N個(gè)玩具,整數(shù)Wi表示這個(gè)玩具的重量，整數(shù)Si表示這個(gè)玩具的體積。機(jī)器人有兩種，分別是：弱機(jī)器人和小機(jī)器人 。有A個(gè)弱機(jī)器人。每個(gè)弱機(jī)器人有一個(gè)重量限制Xi，它只能拿起重量嚴(yán)格小于Xi的玩具，與玩具的體積大小沒關(guān)系。有B個(gè)小機(jī)器人。每個(gè)小機(jī)器人有一個(gè)體積限制Yi，它只能拿起體積嚴(yán)格小于Yi的玩具，與玩具的重量大小沒有關(guān)系。Problem 2: 機(jī)器人(robots)10Marita的每個(gè)機(jī)器人用1分鐘將一個(gè)玩具拿走放好。不同的機(jī)器人可以同時(shí)拿走并放好不同的玩具。你的任務(wù)是確定Marita的機(jī)

5、器人是否可以將所有的玩具都收拾好，如果是，那么最少用多少時(shí)間可以收拾好。時(shí)間限制: 3秒 內(nèi)存限制: 64 MB1 N 1,000,0000 A, B 50,000 且1 A + B1 Xi, Yi, Wi, Si 2,000,000,000Problem 2: 機(jī)器人(robots)11Problem 2: 機(jī)器人(robots)12考慮二分答案，這樣只需檢驗(yàn)m分鐘內(nèi)是否可以把所有玩具收拾好。將每個(gè)玩具i與坐標(biāo)(Wi:重量, Si:體積)對(duì)應(yīng)，這樣每個(gè)弱機(jī)器人可以收拾某一橫坐標(biāo)以左的玩具，每個(gè)小機(jī)器人可以收拾某一縱坐標(biāo)以下的玩具。從右至左添加這些玩具，一旦某一時(shí)刻某個(gè)弱機(jī)器人可以收拾當(dāng)前玩具

6、，則它可以收拾之后的所有玩具。因此我們應(yīng)盡量保留弱機(jī)器人，即優(yōu)先使用小機(jī)器人。Problem 2: 機(jī)器人(robots)13選擇小機(jī)器人時(shí)，當(dāng)然應(yīng)該優(yōu)先選擇可以收拾當(dāng)前玩具的小機(jī)器人中，Yi值最小的一個(gè)。這樣，我們便有了檢驗(yàn)可行性的貪心策略。實(shí)現(xiàn)時(shí)可以借助C+ STL中的set完成。時(shí)間復(fù)雜度為O(N*log2N)。Problem 2: 機(jī)器人(robots)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è)給定子矩陣中所有單元格

7、內(nèi)數(shù)字的最大公約數(shù)（GCD），子矩陣的兩個(gè)對(duì)角分別為(p, q) 和 (u, v) 。Problem 3: 游戲(game)15修改單元格內(nèi)數(shù)據(jù)共NU次，詢問GCD操作共NQ次。強(qiáng)制在線。時(shí)間限制: 13秒 內(nèi)存限制: 230 MB1 R, C 1,000,000,0000 NU 22,0000 NQ 250,000格子中的數(shù)非負(fù)且不大于1018Problem 3: 游戲(game)16使用經(jīng)典的兩層trie樹嵌套，每次詢問的時(shí)間復(fù)雜度為O(log2N)，空間復(fù)雜度為O(NU*log2N)。只要把內(nèi)層的trie樹改為Splay樹即可把空間復(fù)雜度降至O(NU*logN)。Problem 3: 游

8、戲(game)17Part II一些有趣的博弈游戲18警方逮捕A, B兩名嫌疑犯，但沒有足夠證據(jù)指控二人有罪。于是警方分開囚禁嫌疑犯，分別和二人見面，并向雙方提供以下相同的選擇：若一人認(rèn)罪并作證檢控對(duì)方，而對(duì)方保持沉默，此人將即時(shí)獲釋，沉默者將判監(jiān)10年。若二人都保持沉默，則二人同樣判監(jiān)2年。若二人互相檢舉，則二人同樣判監(jiān)8年。Example 1: 囚徒困境19 囚徒B 囚徒A招供不招供招供(-8, -8)(0, -10)不招供(-10, 0)(-2, -2)Example 1: 囚徒困境20投票我該招供。我不該招供。21我們稱策略B嚴(yán)格優(yōu)于(strictly dominate)策略A，如果無

9、論其他人選擇何種策略，選擇B均會(huì)比選擇A取得嚴(yán)格更好的結(jié)果。我們稱策略B弱優(yōu)于(weakly dominate)策略A，如果無論其他人選擇何種策略，選擇B均會(huì)比選擇A取得不更差的結(jié)果，且存在某種其他人的策略選擇，使得B比A取得嚴(yán)格更好的結(jié)果。以上兩種情況統(tǒng)稱策略B優(yōu)于(dominate)策略A。概念：優(yōu)勢(shì)策略與劣勢(shì)策略22稱策略B是嚴(yán)格優(yōu)勢(shì)策略(strictly dominant strategy)，如果策略B嚴(yán)格優(yōu)于任何其它策略。稱策略B是弱優(yōu)勢(shì)策略(weakly dominant strategy)，如果策略B優(yōu)于任何其它策略，并且存在某種策略A，使得策略B弱優(yōu)于策略A。稱策略B是嚴(yán)格劣勢(shì)

10、策略(strictly dominated strategy)，如果存在某策略嚴(yán)格優(yōu)于策略B。稱策略B是弱劣勢(shì)策略(weakly dominated strategy)，如果存在某策略弱優(yōu)于策略B。概念：優(yōu)勢(shì)策略與劣勢(shì)策略23 CCF 某OIer正常進(jìn)行分?jǐn)?shù)取相反數(shù)試圖取得高分(5, 0)(-5, -100)試圖取得低分(-5, 0)(100, -100)Example 2: 一次OI考試24純策略納什均衡(Pure Strategy Nash Equilibrium)是指這樣的純策略組合：對(duì)于任意一個(gè)玩家，如果其他玩家的策略不變，該玩家單方面改變自己的策略不會(huì)增加收益。上例中，CCF選擇正常

11、進(jìn)行比賽、選手試圖取得高分是唯一的純策略納什均衡。囚徒困境中，兩人都招供是唯一的純策略納什均衡。純策略納什均衡一定存在嗎？概念：純策略納什均衡25概念：純策略納什均衡26 玩家B 玩家A石頭剪刀布石頭(0, 0)(1, -1)(-1, 1)剪刀(-1, 1)(0, 0)(1, -1)布(1, -1)(-1, 1)(0, 0)概念：純策略納什均衡27 門將 射手向左向右向左(0.2, -0.2)(0.7, -0.7)向右(0.8, -0.8)(0.4, -0.4)Example 3: 點(diǎn)球大戰(zhàn)28混合策略納什均衡（Mixed Strategy Nash Equilibrium）是指這樣的混合策略

12、組合：對(duì)于任意一個(gè)玩家，如果其他玩家的策略不變，該玩家單方面改變自己的策略不會(huì)增加期望收益。當(dāng)玩家數(shù)有限且策略數(shù)有限時(shí)，混合策略納什均衡一定存在。概念：混合策略納什均衡29 學(xué)生 老師寫作業(yè)不寫作業(yè)檢查作業(yè)(-1, 0)(3, -10)不檢查作業(yè)(1, 0)(-3, 4)Example 4: 我該寫作業(yè)嗎？30Example 4: 我該寫作業(yè)嗎？在納什均衡中，只有3/4的學(xué)生寫作業(yè)。老師很生氣。老師希望增加寫作業(yè)的學(xué)生比例。于是 老師將不寫作業(yè)的懲罰提升至10倍。31 學(xué)生 老師寫作業(yè)不寫作業(yè)檢查作業(yè)(-1, 0)(3, -100)不檢查作業(yè)(1, 0)(-3, 4)Example 4: 我該

13、寫作業(yè)嗎？32投票老師總是說誰不寫作業(yè)就罰抄100遍，也沒見寫作業(yè)的人多啊。新的納什均衡里，寫作業(yè)的人數(shù)不變。這是好政策，新的納什均衡中，寫作業(yè)的學(xué)生數(shù)量一定有所增加。我就是有冒險(xiǎn)精神，懲罰越大越不寫作業(yè)！新的納什均衡里，寫作業(yè)的人數(shù)減少。33Example 5: B國的侵略B入侵A反抗B迎戰(zhàn)(0, 0)B撤退(2, 1)A投降(1, 2)34投票A國還是投降吧。士可殺不可辱！A國應(yīng)該奮起反抗。35Example 5: B國的侵略B國軍隊(duì)遠(yuǎn)渡重洋侵略A國，卻難免撤退的命運(yùn)。B軍統(tǒng)帥靈機(jī)一動(dòng) 燒船！36Example 5: B國的侵略B入侵A反抗B迎戰(zhàn)(0, 0)A投降(1, 2)37Examp

14、le 5: B國的侵略注意B國統(tǒng)帥的策略是燒船。而不是偷偷把船鑿出小孔。在對(duì)方不知情的情況下減少自己的可選策略是毫無意義的。38逆向歸納法(Backward Induction)指按時(shí)間順序的倒序，從游戲的結(jié)束開始，依次推理出每一步的最優(yōu)策略。概念：逆向歸納法39有N只獅子，由大到小依次標(biāo)號(hào)為1，2，N。有一天，他們發(fā)現(xiàn)了一只小羊。獅子的等級(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)獅子吃掉，以此類推。每只獅子都已保命為首要目的，

15、當(dāng)然，有食物吃就最好了。Example 6: 我可以吃你嗎？40如果N=1如果N=2如果N=3如果N=4因此，當(dāng)且僅當(dāng)N為奇數(shù)時(shí)，1號(hào)獅子會(huì)吃掉小羊。Example 6: 我可以吃你嗎？41給出一個(gè)N*M的石子陣。兩個(gè)人輪流取每次取某個(gè)石子，和所有它上邊、右邊、右上的現(xiàn)存石子。取到最后一個(gè)石子的人輸。問先手是否有必勝策略。Example 7: 一個(gè)取石子游戲42其實(shí)我不會(huì)玩。但我知道先手有必勝策略，除非N=M=1 。Example 7: 一個(gè)取石子游戲43假定N，M不全為1，這樣先手只取最右上角的石子不會(huì)立刻結(jié)束游戲。用反證法，假設(shè)先手沒有必勝策略。則無論他選擇哪個(gè)石子，都無法改變失敗的命運(yùn)，

16、特別地，只取最右上角的石子也一樣。Example 7: 一個(gè)取石子游戲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è)不成立，即先手必勝。Example 7: 一個(gè)取石子游戲45Example 8: OIerOS vs. MacrohardMacrohard壟斷市場開發(fā)OIerOS投入市場Macrohard降價(jià)打擊(-1, 0)Macrohar

17、d不采取行動(dòng)(1, 1)不開發(fā)OIerOS(0, 3)46假設(shè)Macrohard壟斷了十個(gè)地區(qū)互不相干的市場。這十個(gè)地區(qū)的互不相干的OIer依次面臨這一博弈。我們來模擬一下。如果使用逆向歸納法推理呢？為什么給出了不同的結(jié)論？Example 8: OIerOS vs. Macrohard47兩個(gè)人各持一把槍，槍中只有一發(fā)子彈，面對(duì)面站著，相距足夠遠(yuǎn)。兩個(gè)人不斷向前走，隨時(shí)可以選擇開槍。如果某人擊中便是勝者。如果未擊中，仍須繼續(xù)向前走，對(duì)手可以等到距離很小時(shí)再開槍。也就是說，如果未擊中便輸?shù)袅擞螒颉xample 9: 決斗游戲48對(duì)兩個(gè)人命中率隨距離變化的函數(shù)F(x)，G(x)作出以下假設(shè)：F(

18、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)步長越來越小時(shí)，就越來越接近原來的游戲了。Example 9: 決斗游戲49投票兩個(gè)人會(huì)同時(shí)達(dá)到應(yīng)當(dāng)開槍的臨界點(diǎn)。當(dāng)然是命中率高的人先開槍了。笨鳥先飛，當(dāng)然是命中率低的人先開槍了。50如果已知對(duì)方下一步不會(huì)開槍，我就沒有必要在這時(shí)開槍。如果F(x)+G(x)1且已知對(duì)方下一步會(huì)開槍，我就應(yīng)該在這時(shí)開槍。在兩側(cè)使用逆向歸納法，可以發(fā)現(xiàn)，正確的策略是:一旦F(x)+G(x)1，便開槍。Example 9: 決斗游

19、戲51兩個(gè)人分一元錢，規(guī)則如下：一個(gè)人提議分配規(guī)則。另一個(gè)人決定是否同意。如果同意，那就按此規(guī)則分配；如果不同意，這一元錢便會(huì)流失，兩個(gè)人空手而歸。修改一下規(guī)則：此游戲共進(jìn)行K輪。在每一輪中如果雙方達(dá)成協(xié)議，便依此分配收益，游戲結(jié)束；如果沒有達(dá)成協(xié)議，那么總收益減少為之前的s倍(0s1)，下一輪中由另一人提議分配規(guī)則。這里我們假定一元錢的分配可以任意精細(xì)。Example A: 討價(jià)還價(jià)52當(dāng)K趨于正無窮時(shí)，即可以進(jìn)行無限輪時(shí)，結(jié)果如何呢？又當(dāng)s趨于1時(shí)，即每次折損很小時(shí)，結(jié)果如何呢？之前我們假定兩個(gè)人有相同的折損系數(shù)，如果折損系數(shù)不同呢？若在t輪后成交將一元錢分配為a1, a2 (a1+a2=

20、1) ，那么兩個(gè)人的收益分別為a1 * s1t ， a2 * s2t 。再令K趨于正無窮。令s1=1-p1，s2=1-p2，其中趨于零。那么這一元錢會(huì)如何分配呢？Example A: 討價(jià)還價(jià)53這一博弈游戲可以看成分配買家對(duì)商品的期望價(jià)值與賣家的成本之間的差值，也就是討價(jià)還價(jià)。通過上面的討論，我們發(fā)現(xiàn)，在與賣方討價(jià)還價(jià)中：要裝作自己很有時(shí)間(折損系數(shù)小)。要偽裝成對(duì)商品的期望價(jià)值較低的樣子(直接獲得部分可分配收益)。最好在賣方快要打烊時(shí)前去(對(duì)方折損系數(shù)大)。拆穿賣方對(duì)成本的過高虛報(bào)(增加可分配收益)。Example A: 討價(jià)還價(jià)54有A，B兩個(gè)團(tuán)體對(duì)國會(huì)的即將發(fā)布的草案感興趣。如果草案通

21、過，A獲得收益3.如果草案未通過，B獲得收益2.國會(huì)決定舉行拍賣，規(guī)則是第二價(jià)格密封拍賣：兩個(gè)人同時(shí)寫下出價(jià)，出價(jià)較高者贏得拍賣，并支付次高出價(jià)，未贏得拍賣者無支出。在這里，如果A獲勝，則草案通過；否則草案不通過。在這里，若兩人出價(jià)相同，則認(rèn)為A獲勝。Example B: 第二價(jià)格密封拍賣55A，B分別應(yīng)如何出價(jià)？在這里，報(bào)出對(duì)自己的實(shí)際價(jià)值是一個(gè)弱優(yōu)勢(shì)策略。下面，我們假定兩人均不會(huì)使用弱劣勢(shì)策略。Example B: 第二價(jià)格密封拍賣56現(xiàn)在，情況有了變化。如果國會(huì)否決了此議案，一切結(jié)束。如果國會(huì)通過此議案，議案要提交給總統(tǒng)，總統(tǒng)可以使用否決權(quán)。總統(tǒng)決定再進(jìn)行一次同樣的拍賣。無論A是否獲勝，

22、她之前贏得拍賣的支出無法收回。如果A已經(jīng)以2的代價(jià)贏得了第一次拍賣，她應(yīng)如何應(yīng)對(duì)這第二次拍賣？沉沒成本(sunk cost)Example B: 第二價(jià)格密封拍賣57在開始時(shí)雙方都知道會(huì)有兩次拍賣，博弈會(huì)如何進(jìn)行？現(xiàn)在假設(shè)若A輸?shù)袅说诙闻馁u，她可以收回第一次的支出，只需支付作為手續(xù)費(fèi)。游戲會(huì)如何進(jìn)行？有一個(gè)人有著弱優(yōu)勢(shì)策略，是A還是B？Example B: 第二價(jià)格密封拍賣58如果我們重復(fù)K次囚徒困境游戲，結(jié)果會(huì)如何呢？Example C: 囚徒困境2 玩家B 玩家A合作背叛合作(2, 2)(-1, 3)背叛(3, -1)(0, 0)59投票在所有玩家都是理性的的前提下，重復(fù)多次囚徒困境會(huì)迫使玩家選擇合作。在所有玩家都是理性的的前提下，重復(fù)多次囚徒困境玩家仍然會(huì)選擇背叛。60如果K=1，就是普通的囚徒困境，玩家會(huì)選擇背叛。如果K=2，玩家已知下一輪中雙方一定會(huì)選擇背叛，因此下一輪的收益不需要納入本輪的考慮之中(沉沒成本) ，因此會(huì)選擇背叛。如果K=3，玩家已知后兩輪中雙方一定會(huì)選擇背叛，因此后兩輪的收益不需要納入本輪的考慮之中，因此會(huì)選擇背叛。對(duì)于任意的正整數(shù)K，進(jìn)行K輪囚徒困境不會(huì)使理性的玩家選擇合作。Example C: 囚徒困境261Example C: 囚徒困境2 玩家乙 玩家甲A(合作)B(背叛)C