王康宁大牛：IOI2013与博弈论

1、IOI2013 Day2 题目讲解及一些有趣的博弈游戏1欢迎随时指出课上内容的错误以及不清楚的地方。客观地说，本节课内容比较简单有趣、人民群众喜闻乐见，面向非集训队选手，旨在让大家在被虐之后体验一下虐人的感觉。鼓励积极回答问题，有小奖品哦。由于大部分例子都比较经典，如果你以前有所研究的话，可以把发言/做游戏的机会留给其他同学。设有投票环节，答对无奖励，不建议万年弃权。为了保证博弈时双方同时进行决策，请希望参与游戏的同学准备好纸笔。声明2Part IIOI2013 Day2 题目讲解3IOI2013 参赛感想4某系统由N 道连续的门和N 个开关组成。N 道门按前后顺序依次排列，开关和门一一对应。

2、门和开关均按 0, 1, , (N - 1) 的顺序编号。0号门离你最近。所有开关都位于入口处。你并不知道哪个开关控制哪道门。每个开关都有“上”和“下”两种状态，其中有且只有一种状态是正确的。如果一个开关处于正确的状态，它所对应的门就会打开；如果它处于错误的状态，与之对应的门就会关闭。不同的开关有不同的正确状态，但你并不知道哪个开关在哪种状态下是正确的。Problem 1: 洞穴(cave)5你可以这样做，将所有开关设置为某种状态组合，然后走进地下洞穴系统去查看哪道门是第一道被关闭的门。因为门是不透明的，所以你不会知道这道关闭的门之后的门是打开还是关闭的。你有时间尝试至多70,000 次开关状

3、态的不同组合。你的任务是确定每个开关的正确状态是什么，以及门和开关之间的对应关系。时间限制: 2秒 内存限制: 32 MB1 N 5,000Problem 1: 洞穴(cave)6Problem 1: 洞穴(cave)7考虑依次求出0号门对应的是哪个开关，1号门对应的是哪个开关，(N 1)号门对应的是哪个开关。每次固定之前的门对应的开关为打开状态，每次翻转一个未知的开关，直至当前门改变状态，便可推断这一开关与当前门对应，同时还能求出打开状态对应“上”还是“下”。这样做需要约N2/4次询问。Problem 1: 洞穴(cave)8事实上，我们无需依次尝试每个开关。通过二分查找，每次可以减少一半的

4、可能选择。这样做需要约N*log2N次询问，符合题中要求。Problem 1: 洞穴(cave)9一共有N个玩具,整数Wi表示这个玩具的重量，整数Si表示这个玩具的体积。机器人有两种，分别是：弱机器人和小机器人 。有A个弱机器人。每个弱机器人有一个重量限制Xi，它只能拿起重量严格小于Xi的玩具，与玩具的体积大小没关系。有B个小机器人。每个小机器人有一个体积限制Yi，它只能拿起体积严格小于Yi的玩具，与玩具的重量大小没有关系。Problem 2: 机器人(robots)10Marita的每个机器人用1分钟将一个玩具拿走放好。不同的机器人可以同时拿走并放好不同的玩具。你的任务是确定Marita的机

5、器人是否可以将所有的玩具都收拾好，如果是，那么最少用多少时间可以收拾好。时间限制: 3秒 内存限制: 64 MB1 N 1,000,0000 A, B 50,000 且1 A + B1 Xi, Yi, Wi, Si 2,000,000,000Problem 2: 机器人(robots)11Problem 2: 机器人(robots)12考虑二分答案，这样只需检验m分钟内是否可以把所有玩具收拾好。将每个玩具i与坐标(Wi:重量, Si:体积)对应，这样每个弱机器人可以收拾某一横坐标以左的玩具，每个小机器人可以收拾某一纵坐标以下的玩具。从右至左添加这些玩具，一旦某一时刻某个弱机器人可以收拾当前玩具

6、，则它可以收拾之后的所有玩具。因此我们应尽量保留弱机器人，即优先使用小机器人。Problem 2: 机器人(robots)13选择小机器人时，当然应该优先选择可以收拾当前玩具的小机器人中，Yi值最小的一个。这样，我们便有了检验可行性的贪心策略。实现时可以借助C+ STL中的set完成。时间复杂度为O(N*log2N)。Problem 2: 机器人(robots)14有一个 R 行C 列的网格。我们用(P, Q) 表示位于 P 行Q 列的单元格。每个单元格包含一个非负整数，游戏开始时所有单元格内的整数均为零。有两种操作：修改一个单元格 (p, q) 内包含的整数值；计算一个给定子矩阵中所有单元格

7、内数字的最大公约数（GCD），子矩阵的两个对角分别为(p, q) 和 (u, v) 。Problem 3: 游戏(game)15修改单元格内数据共NU次，询问GCD操作共NQ次。强制在线。时间限制: 13秒 内存限制: 230 MB1 R, C 1,000,000,0000 NU 22,0000 NQ 250,000格子中的数非负且不大于1018Problem 3: 游戏(game)16使用经典的两层trie树嵌套，每次询问的时间复杂度为O(log2N)，空间复杂度为O(NU*log2N)。只要把内层的trie树改为Splay树即可把空间复杂度降至O(NU*logN)。Problem 3: 游

8、戏(game)17Part II一些有趣的博弈游戏18警方逮捕A, B两名嫌疑犯，但没有足够证据指控二人有罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：若一人认罪并作证检控对方，而对方保持沉默，此人将即时获释，沉默者将判监10年。若二人都保持沉默，则二人同样判监2年。若二人互相检举，则二人同样判监8年。Example 1: 囚徒困境19 囚徒B 囚徒A招供不招供招供(-8, -8)(0, -10)不招供(-10, 0)(-2, -2)Example 1: 囚徒困境20投票我该招供。我不该招供。21我们称策略B严格优于(strictly dominate)策略A，如果无

9、论其他人选择何种策略，选择B均会比选择A取得严格更好的结果。我们称策略B弱优于(weakly dominate)策略A，如果无论其他人选择何种策略，选择B均会比选择A取得不更差的结果，且存在某种其他人的策略选择，使得B比A取得严格更好的结果。以上两种情况统称策略B优于(dominate)策略A。概念：优势策略与劣势策略22称策略B是严格优势策略(strictly dominant strategy)，如果策略B严格优于任何其它策略。称策略B是弱优势策略(weakly dominant strategy)，如果策略B优于任何其它策略，并且存在某种策略A，使得策略B弱优于策略A。称策略B是严格劣势

10、策略(strictly dominated strategy)，如果存在某策略严格优于策略B。称策略B是弱劣势策略(weakly dominated strategy)，如果存在某策略弱优于策略B。概念：优势策略与劣势策略23 CCF 某OIer正常进行分数取相反数试图取得高分(5, 0)(-5, -100)试图取得低分(-5, 0)(100, -100)Example 2: 一次OI考试24纯策略纳什均衡(Pure Strategy Nash Equilibrium)是指这样的纯策略组合：对于任意一个玩家，如果其他玩家的策略不变，该玩家单方面改变自己的策略不会增加收益。上例中，CCF选择正常

11、进行比赛、选手试图取得高分是唯一的纯策略纳什均衡。囚徒困境中，两人都招供是唯一的纯策略纳什均衡。纯策略纳什均衡一定存在吗？概念：纯策略纳什均衡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: 点球大战28混合策略纳什均衡（Mixed Strategy Nash Equilibrium）是指这样的混合策略

12、组合：对于任意一个玩家，如果其他玩家的策略不变，该玩家单方面改变自己的策略不会增加期望收益。当玩家数有限且策略数有限时，混合策略纳什均衡一定存在。概念：混合策略纳什均衡29 学生 老师写作业不写作业检查作业(-1, 0)(3, -10)不检查作业(1, 0)(-3, 4)Example 4: 我该写作业吗？30Example 4: 我该写作业吗？在纳什均衡中，只有3/4的学生写作业。老师很生气。老师希望增加写作业的学生比例。于是 老师将不写作业的惩罚提升至10倍。31 学生 老师写作业不写作业检查作业(-1, 0)(3, -100)不检查作业(1, 0)(-3, 4)Example 4: 我该

13、写作业吗？32投票老师总是说谁不写作业就罚抄100遍，也没见写作业的人多啊。新的纳什均衡里，写作业的人数不变。这是好政策，新的纳什均衡中，写作业的学生数量一定有所增加。我就是有冒险精神，惩罚越大越不写作业！新的纳什均衡里，写作业的人数减少。33Example 5: B国的侵略B入侵A反抗B迎战(0, 0)B撤退(2, 1)A投降(1, 2)34投票A国还是投降吧。士可杀不可辱！A国应该奋起反抗。35Example 5: B国的侵略B国军队远渡重洋侵略A国，却难免撤退的命运。B军统帅灵机一动 烧船！36Example 5: B国的侵略B入侵A反抗B迎战(0, 0)A投降(1, 2)37Examp

14、le 5: B国的侵略注意B国统帅的策略是烧船。而不是偷偷把船凿出小孔。在对方不知情的情况下减少自己的可选策略是毫无意义的。38逆向归纳法(Backward Induction)指按时间顺序的倒序，从游戏的结束开始，依次推理出每一步的最优策略。概念：逆向归纳法39有N只狮子，由大到小依次标号为1，2，N。有一天，他们发现了一只小羊。狮子的等级制度森严，这只羊只能由1号狮子来吃。如果1号狮子不吃，一切结束；如果他吃了小羊，那么他会暂时失去战斗力，可能(也只可能)被2号狮子吃掉。如果2号狮子吃掉1号狮子，那他也会暂时失去战斗力，可能(也只可能)被3号狮子吃掉，以此类推。每只狮子都已保命为首要目的，

15、当然，有食物吃就最好了。Example 6: 我可以吃你吗？40如果N=1如果N=2如果N=3如果N=4因此，当且仅当N为奇数时，1号狮子会吃掉小羊。Example 6: 我可以吃你吗？41给出一个N*M的石子阵。两个人轮流取每次取某个石子，和所有它上边、右边、右上的现存石子。取到最后一个石子的人输。问先手是否有必胜策略。Example 7: 一个取石子游戏42其实我不会玩。但我知道先手有必胜策略，除非N=M=1 。Example 7: 一个取石子游戏43假定N，M不全为1，这样先手只取最右上角的石子不会立刻结束游戏。用反证法，假设先手没有必胜策略。则无论他选择哪个石子，都无法改变失败的命运，

16、特别地，只取最右上角的石子也一样。Example 7: 一个取石子游戏44取掉最右上角的石子后，局面进入了当前先手必胜的状态，因此他可以选取某个石子，去掉它和它上边、右边、右上的现存石子，使局面进入当前先手必败的状态。然而这个状态，是最初的先手一步就可以达到的，也就是说，最初的先手可以选取某个石子，使局面进入当前先手(对手)必败的状态。因此先手必胜，与假设矛盾。因此假设不成立，即先手必胜。Example 7: 一个取石子游戏45Example 8: OIerOS vs. MacrohardMacrohard垄断市场开发OIerOS投入市场Macrohard降价打击(-1, 0)Macrohar

17、d不采取行动(1, 1)不开发OIerOS(0, 3)46假设Macrohard垄断了十个地区互不相干的市场。这十个地区的互不相干的OIer依次面临这一博弈。我们来模拟一下。如果使用逆向归纳法推理呢？为什么给出了不同的结论？Example 8: OIerOS vs. Macrohard47两个人各持一把枪，枪中只有一发子弹，面对面站着，相距足够远。两个人不断向前走，随时可以选择开枪。如果某人击中便是胜者。如果未击中，仍须继续向前走，对手可以等到距离很小时再开枪。也就是说，如果未击中便输掉了游戏。Example 9: 决斗游戏48对两个人命中率随距离变化的函数F(x)，G(x)作出以下假设：F(

18、0)=1, G(0)=1.F(x), G(x)在0,+)上连续且单调递减.F(x)0 (x+), G(x)0 (x+).为便于分析，我们认为两个人轮流行动，每次选择开枪或前行一步。这样，当步长越来越小时，就越来越接近原来的游戏了。Example 9: 决斗游戏49投票两个人会同时达到应当开枪的临界点。当然是命中率高的人先开枪了。笨鸟先飞，当然是命中率低的人先开枪了。50如果已知对方下一步不会开枪，我就没有必要在这时开枪。如果F(x)+G(x)1且已知对方下一步会开枪，我就应该在这时开枪。在两侧使用逆向归纳法，可以发现，正确的策略是:一旦F(x)+G(x)1，便开枪。Example 9: 决斗游

19、戏51两个人分一元钱，规则如下：一个人提议分配规则。另一个人决定是否同意。如果同意，那就按此规则分配；如果不同意，这一元钱便会流失，两个人空手而归。修改一下规则：此游戏共进行K轮。在每一轮中如果双方达成协议，便依此分配收益，游戏结束；如果没有达成协议，那么总收益减少为之前的s倍(0s1)，下一轮中由另一人提议分配规则。这里我们假定一元钱的分配可以任意精细。Example A: 讨价还价52当K趋于正无穷时，即可以进行无限轮时，结果如何呢？又当s趋于1时，即每次折损很小时，结果如何呢？之前我们假定两个人有相同的折损系数，如果折损系数不同呢？若在t轮后成交将一元钱分配为a1, a2 (a1+a2=

20、1) ，那么两个人的收益分别为a1 * s1t ， a2 * s2t 。再令K趋于正无穷。令s1=1-p1，s2=1-p2，其中趋于零。那么这一元钱会如何分配呢？Example A: 讨价还价53这一博弈游戏可以看成分配买家对商品的期望价值与卖家的成本之间的差值，也就是讨价还价。通过上面的讨论，我们发现，在与卖方讨价还价中：要装作自己很有时间(折损系数小)。要伪装成对商品的期望价值较低的样子(直接获得部分可分配收益)。最好在卖方快要打烊时前去(对方折损系数大)。拆穿卖方对成本的过高虚报(增加可分配收益)。Example A: 讨价还价54有A，B两个团体对国会的即将发布的草案感兴趣。如果草案通

21、过，A获得收益3.如果草案未通过，B获得收益2.国会决定举行拍卖，规则是第二价格密封拍卖：两个人同时写下出价，出价较高者赢得拍卖，并支付次高出价，未赢得拍卖者无支出。在这里，如果A获胜，则草案通过；否则草案不通过。在这里，若两人出价相同，则认为A获胜。Example B: 第二价格密封拍卖55A，B分别应如何出价？在这里，报出对自己的实际价值是一个弱优势策略。下面，我们假定两人均不会使用弱劣势策略。Example B: 第二价格密封拍卖56现在，情况有了变化。如果国会否决了此议案，一切结束。如果国会通过此议案，议案要提交给总统，总统可以使用否决权。总统决定再进行一次同样的拍卖。无论A是否获胜，

22、她之前赢得拍卖的支出无法收回。如果A已经以2的代价赢得了第一次拍卖，她应如何应对这第二次拍卖？沉没成本(sunk cost)Example B: 第二价格密封拍卖57在开始时双方都知道会有两次拍卖，博弈会如何进行？现在假设若A输掉了第二次拍卖，她可以收回第一次的支出，只需支付作为手续费。游戏会如何进行？有一个人有着弱优势策略，是A还是B？Example B: 第二价格密封拍卖58如果我们重复K次囚徒困境游戏，结果会如何呢？Example C: 囚徒困境2 玩家B 玩家A合作背叛合作(2, 2)(-1, 3)背叛(3, -1)(0, 0)59投票在所有玩家都是理性的的前提下，重复多次囚徒困境会迫使玩家选择合作。在所有玩家都是理性的的前提下，重复多次囚徒困境玩家仍然会选择背叛。60如果K=1，就是普通的囚徒困境，玩家会选择背叛。如果K=2，玩家已知下一轮中双方一定会选择背叛，因此下一轮的收益不需要纳入本轮的考虑之中(沉没成本) ，因此会选择背叛。如果K=3，玩家已知后两轮中双方一定会选择背叛，因此后两轮的收益不需要纳入本轮的考虑之中，因此会选择背叛。对于任意的正整数K，进行K轮囚徒困境不会使理性的玩家选择合作。Example C: 囚徒困境261Example C: 囚徒困境2 玩家乙 玩家甲A(合作)B(背叛)C