程序员面试逻辑题解析——第一章：竞赛——不可能都是赢家

第一部分智力游戏 如果能解出这些谜题，那么让你做管理工作显然是大材小用了。 注意　尖叫的表情表示这是一道特别难解的谜题。 第1章 竞赛——不可能都是赢家 1.1　甜食爱好者 3 1.2　拜占庭赌徒　 5 1.3　“碰碰”运气 7 1.4　信息增益　 9 1.5　直冲云霄！ 11 1.6　政治分肥 13 1.7　社会博弈 14 1.8　猫鼠游戏 17 1.9　流感中的数学 19 1.1　甜食爱好者 杰里米（Jeremy）和玛丽（Marie）是两个喜欢蛋糕也喜欢数学的小孩，可能你也认识这样的小孩。于是，当大厨玛蒂娜（Martine）给他们准备了两块一模一样的长方形蛋糕后，杰里米便说服玛丽来玩一个游戏。 游戏的规则是这样的：杰里米先把一块蛋糕切成两份，这两份大小可能一样，也可能不一样。切完以后，玛丽决定是否要先选蛋糕。如果玛丽先选，她会选那份大的；如果让杰里米先选，玛丽可以预料到杰里米会选走那份大的。 随后，杰里米把另外一块蛋糕也切成两份（请注意，他可以把其中一份切得非常小）。如果之前是玛丽先选的，那么这次杰里米就可以拿走大的那份。如果之前是杰里米先选的，那么这次玛丽就可以拿走大的那份。 热身问题 假设每个小孩的目标是分得尽可能多的蛋糕，那么对于杰里米来说最好的策略是什么呢？ 提示 在查看答案之前，用f 和1f 来表示第一块蛋糕被切分后两部分的大小，其中f ≥1/2。假设下面两种情况：第一种，玛丽先选，拿走了f 那块；第二种，玛丽后选，拿走了1f 那块。依次分析这两种情况下的结果。 热身问题解答 根据提示，玛丽会这样推理：如果她拿了大小为f 的那块，那么杰里米就几乎可以得到第二块蛋糕的全部（杰里米会切点儿蛋糕屑给玛丽，自己拿走几乎整块蛋糕）。这样，玛丽得到的份额是f，而杰里米得到的是(1f )+1。如果她拿了小的那块（用1f 表示），那么对于杰里米来说最好是把第二块平分了，如此一来，玛丽得到的是(1f )+1/2。根据这个推理，杰里米意识到对他来说最好的分法是使f = (1f )+1/2，也就是2 f =3/2，即f =3/4。这样，如果第一块蛋糕是玛丽先选，那么杰里米会得到第一块蛋糕的1/4和整个第二块蛋糕。如果第一块蛋糕是玛丽后选，那么杰里米会得到第一块蛋糕的3/4和第二块蛋糕的1/2。在这两种情况下，玛丽都能得到3/4的蛋糕，而杰里米能得到5/4。注意，如果杰里米在分第一块蛋糕时，大的那块小于3/4，那么玛丽只要后选，就能得到多于1/4的蛋糕，并且能得到第二块蛋糕的1/2，这样她能得到的蛋糕总量将多于3/4。对比之下，如果分第一块蛋糕时，大的那块大于3/4，那么玛丽只要先选，也能得到多于3/4的蛋糕。 我详细地分析了热身问题，因为一个星期后，会有一个更难的挑战。这次大厨玛蒂娜做了3块一模一样的长方形蛋糕，杰里米和玛丽都对它们垂涎欲滴。 他们制订了新规则。杰里米还是负责切蛋糕，但是玛丽有两次先选蛋糕的机会，而杰里米只有一次。也就是杰里米先切第一块蛋糕，玛丽决定她是否要先选。然后杰里米切第二块蛋糕，这次还是由玛丽决定是否先选。第三块蛋糕还是如此。唯一需要注意的是，玛丽至少要留给杰里米一次先选蛋糕的机会。 (1) 在新规则下，杰里米怎样做得到的蛋糕才能最多？他最多能得到多少？ (2) 假设有7块蛋糕，玛丽有6次先选蛋糕的机会，谁有优势？有多大优势？ (3) 假设总是让杰里米来切蛋糕，有没有办法可以确保两个小孩能得到一样多的蛋糕？ 1.2　拜占庭赌徒　 在人们的印象中，拜占庭帝国是以无休止的宫廷阴谋和诡计而闻名的，但它实在不该得此恶名。现代历史研究表明，按照公元一千年的标准拜占庭帝国是相当稳定与和谐的。然而成见难消，这道谜题所讨论的游戏就是受假想的拜占庭阴谋启发的。我们称之为“拜占庭赌徒”。 赌局的规则如下。你将和一群“顾问”一起参与赌局。其中一个顾问会在一张纸上写下0或者1，展示给其他顾问看，但不会让你看到，然后把那张纸扣着放在你面前。随后，每个顾问都会告诉你纸上写的是什么数字。他们都演技精湛，所以你无法通过任何明显的记号或面部表情分辨出他们是否在说谎。每一局，你都可以选择不下注，也可以押上你部分甚至全部资产。 热身问题 假设一共有4位顾问，其中两个人会一直说实话，但是你不知道是哪两位。你可以玩三局，每一局都采用等额投注[ 你若押对了数字，便额外获得等同于你所押的赌注的钱；你若押错，便损失了赌注。——译者注]。赌局开始时，你有100美元，你能确保赢多少钱呢？ 热身问题解答 如果4位顾问中，有3个或4个人给你的建议相同，那就在他们说的那个数字上押最大的注。因为这群人中，至少有一个人是诚实的。如果每两个人给的建议是相同的，那这局先不要下注。这一局结束后，你就能知道哪两个顾问是说实话的，这样以后每局你都可以押最大的注。也就是说，从第二局开始，你就可以押上所有的钱而且能稳赢。三局结束后，你将会有400美元。 (1) 假设现在只有3位顾问，而且只有一个人会一直说实话。你还是可以玩3局，每一局都采用等额投注。赌局开始时，你有100美元，你能确保赢多少钱呢？ 这个赌局将变得更长也更难以应付。你可以玩4局，但是不再有人一直说实话了，只会有一位“不总说实话”的顾问，他不一定每局都说实话，但是4局里至少有3局要说实话。更糟的是，顾问们在你下完注后甚至可以改写纸上的数字。但是如果改写数字会导致那个“不总说实话”的顾问无法存在，他们便不能更改。 (2) 4轮赌局，4位顾问，其中3位可以随意说谎，另一位4次中必须至少有3次说实话，在这种情况下，你能保证赢多少？ (3) 如果你可以参加5局，“不总说实话”的顾问5次中必须有4次说实话，另外3位顾问可以随意说谎，在这种情况下，你能保证最后至少还有150美元吗？ 1.3 “碰碰”运气　 在电影《赌命法则》[ 电影名为Intacto，中文译为《赌命法则》，也叫《完整无缺》，是西班牙一部带有寓言意味的惊悚电影。 ——译者注]的世界里，运气或多或少被设定为一个人永久性的特质。幸运的人不论在赌桌上还是在十字路口都好运连连。但是有那么一群人，他们懂得如何通过触碰来窃取别人的运气，所以好运的人得提防和这群人发生身体接触。影片中主角的任务之一就是要找到这些好运的人。有一次，他想要试一下他招募的那些人的运气，于是，他让他们蒙着眼在树林里奔跑。运气最好的就是第一个到达目的地的人，而很多不那么走运的都撞到了树上。 我们来玩一个温和点的游戏，一般形式是一共有N个人参加，有B次机会下注。每个玩家都知道N和B的值，且每个人都有一笔起始资金（不一定相等），以点数计。 每一轮都是等额投注，抛硬币，赌哪一面朝上。如果你押x点并且赢了，你的财富就会增加x点，否则，输了就会损失这x点。 在每一次抛硬币之前，每个人自行选择将赌注（可以不下注，也可以押部分甚至全部点数）押在正面或反面。 当B轮赌局结束后，剩余点数最多的那个玩家将获胜。如果有两个人的剩余点数一样，就没有赢家。这些点数在游戏结束后是没有任何价值的，所以只有成为最后的胜利者才可以获得奖赏。 热身问题1 现在鲍勃（Bob）和爱丽丝（Alice）拥有相同的点数，而且鲍勃要先于爱丽丝下注。假设还有一轮，爱丽丝有多少获胜的机会？ 热身问题1解答 如果鲍勃押x点赌正面，那么爱丽丝就押x+1点也赌正面。如果确实是正面，那么爱丽丝获胜，否则，鲍勃将获胜。同样，爱丽丝也可以选择什么都不押，这样，如果是反面，爱丽丝便获胜。无论哪种情况，爱丽丝获胜的概率都是1/2。 热身问题2 还是爱丽丝和鲍勃两个玩家，这次爱丽丝比鲍勃拥有更多的点数，还可以玩5轮。如果鲍勃要比爱丽丝先下注，爱丽丝怎样才能使她获胜的概率最大？ 热身问题2解答 爱丽丝每次都可以稳赢。每一轮，爱丽丝都追随鲍勃下同样的注。假设鲍勃押b点赌硬币是正面，那么爱丽丝也押b点赌正面。无论硬币最后是正面朝上还是反面朝上，爱丽丝的剩余点数总是比鲍勃多。 现在让我们来思考几个更有挑战性的问题。 (1) 鲍勃、卡罗尔（Carol）和爱丽丝3个人玩。爱丽丝有51点，鲍勃和卡罗尔都只有50点。按照鲍勃、卡罗尔、爱丽丝这个顺序依次下注。鲍勃和卡罗尔结成联盟，他们俩无论谁赢了都会和另一个分享奖赏。如果只剩下一轮，鲍勃和卡罗尔要如何下注才能使他们当中至少一个人获胜的概率最大？ (2) 如果爱丽丝必须第一个下注，还能得出上题的结论吗？ (3) 鲍勃和爱丽丝两个人玩，鲍勃有51点，爱丽丝有50点，还有两轮。倒数第二轮鲍勃先下注，最后一轮爱丽丝先下注。两轮之后，鲍勃获胜的概率大于1/2吗？如果大于1/2，具体大多少？ (4) 鲍勃有51点，爱丽丝有50点，还有两轮。但这一次，倒数第二轮爱丽丝先下注，最后一轮鲍勃先下注。两轮之后，鲍勃获胜的概率大于1/2吗？如果大于1/2，具体大多少？ (5) 鲍勃有51点，爱丽丝有50点，还有两轮。倒数第二轮爱丽丝先下注，最后一轮鲍勃先下注。这一次，鲍勃事先声明倒数第二轮他的赌注将是20点，但是他会等到爱丽丝下完注后再决定押在哪一面。爱丽丝获胜的概率能大于1/2吗？ 就好像挤进芭蕾舞团、争夺奥运会金牌或攀缘权力的金字塔，往往名额越少，竞争越激烈，承担的风险也就越大。看看你是否认同这一点。 (6) 鲍勃、爱丽丝、里诺（Rino）和朱莉安娜（Juliana）4个人玩，他们每人都有100点，还有两轮。每个人都竭尽全力想赢，因此不再有任何形式的联盟。倒数第二轮，鲍勃和爱丽丝押100点赌正面，里诺押100点赌反面。现在轮到朱莉安娜下注，她知道下一轮她将是第一个下注的人。那么，如果她这一轮押90点（不管是押正面还是反面），她赢的概率是多少？她应该押正面还是反面呢？ 1.4　信息增益 乔丹（Jordan）和他的5个朋友阿里安娜（Ariana）、鲍勃、卡罗琳（Caroline）、大卫（David）及埃伦（Ellen）是智多星俱乐部的领军人物，他们都是杰出的解谜者。因此，永远穿着考究的著名游戏竞赛节目主持人杰夫·尼古拉斯（Jeff Nicholas），向乔丹和他的朋友们发出了比赛邀请。 “我们的比赛是现场直播的。我会蒙上你那5个朋友的眼睛，给他们各戴上一顶帽子，帽子上写有1到10中的某一个数字（可能有些人的数字是一样的），然后将他们领到电视直播间。在直播间里，我会组织他们按我指定的顺序围成一个圈，然后取下蒙眼布，给他们换上不反光的深色太阳眼镜，以防止他们互相使眼色。 “他们到达直播间后，你和观众便可以通过电视监控器看到他们，也可以看到他们头上的数字，但是他们看不到你。我手上有一张蓝票和一张红票。你可以让我把其中的一张票交给他们5人中的任意一个。你只能做这些。敲打直播间的窗户之类是不允许的，否则你们将被取消比赛资格。 “你的朋友们也不可以互相交谈或者传递任何信号，否则都会被取消比赛资格。（显而易见，除了递交那张票，我不会帮你们任何忙。） 但是，他们能看到那张票被交给了谁及票的颜色，也能看到其他人帽子上的数字，不过无法看到自己帽子上的数字。 “我下令后，每个人都伸出手指代表自己头上的数字。猜对的人将获得千倍于自己头上数字的美元作奖金。如果所有的人都猜对了，那么乔丹，你将获得5000美元的奖金。但是如果有人猜错了，你得给我买套新的阿玛尼西装。” “就这样？”乔丹问道，“他们从外界收到的唯一信息就是谁拿到了票以及票的颜色？” “是的，”尼古拉斯说，“但是要记住，他们每个人都能看到别人帽子上的数字。我估计你赢不了这个比赛。我真的很想要一套西装。” (1) 乔丹有没有可能设计出一套协议，使得他的5个朋友都能猜对他们帽子上的数字？如果可以，请解释一下。如果不行，乔丹获胜的概率高吗？ 热身问题 我们先来考虑一个相对简单的情况，这样对乔丹要设计的协议可以有个大致的了解。假设5顶帽子上的数字必须是连续的（例如4，5，6，7，8），乔丹应该怎么做？ 热身问题解答 乔丹和他的朋友可以遵循以下协议。阿里安娜代表1，鲍勃代表2，卡罗琳代表3，大卫代表4，埃伦代表5和6。如果乔丹把票交给阿里安娜，说明这串连续的数字是从1开始的。如果交给鲍勃，说明是从2开始的，交给卡罗琳就是从3开始，交给大卫就是从4开始。如果交给埃伦蓝票，就说明从5开始，而如果交给埃伦的是红票，则代表从6开始。 因此，只要乔丹一发出票，他的5个朋友就都知道了起始数字。他们只要看看其他人帽子上的数字，就能用排除法推算出自己的数字了。 但是在杰夫的挑战中，这些数字并不一定是连续的，甚至有可能存在相同的数字。你认为乔丹能挑战成功吗？ 1.5　直冲云霄！　 “直冲云霄”这个智力游戏是基于空心乐透球的。以下是游戏规则。 你的对手有100张完全一样的纸。他被安排在一个你看不到的房间，在每张纸上不重复地写下1到1 000 000之间任何一个数字，然后将这些纸分别塞到不透明的小信封里。接着，这些信封将被交到一个独立的第三方“填充者”手里。填充者一直是当着你和对手的面工作的。他给你看100个空心的乐透球，然后把信封的顺序打乱，将它们分别塞进100个乐透球中并将球封口。这些球都是经过跌落、弹跳和弹性测试的，可以保证它们的物理性质完全相同。 填充者接下来把这些球都放到乐透机中。乐透机将彻底地搅乱这些球，直到摇出来一个球，把它编为1号球。这个球打开后，你将获知纸上的数字（我们将其简称为“值”）。你可以选择“捕获”或者放弃这个值。如果选择捕获，那么这个值将进入你的“捕获堆”，并记为已使用一次“捕获”；如果放弃，那么这个值就永久地进入了“弃值堆”，但是，你可以记住这个值以备后用。重复上述操作，直到100个球都从机器里出来。你总共有3次“捕获”机会。你的目标是捕获对手所写的最大值。如果成功了，你将赢得100 000美元；如果失败了，你将输掉100 000美元。你应该参与这个游戏吗？若参与的话，获胜的概率有多大？ 这道题其实是“苏丹的女儿”谜题的变体。年轻的求婚者要从苏丹的100个女儿中选择他的新娘。这100个姑娘以随机的顺序介绍给他，他只能根据她们的外貌和仪态来作出决定，没有其他可供评判的依据。如果他拒绝了其中的一个，那么他和她就彻底无缘了。一旦他作出了选择，就只能娶那一个。 热身问题 假设这100个姑娘介绍给他的顺序与她们的外貌无关，比如是基于她们的出生时间，你能为这个求婚者设计一个策略，使得他至少有1/4的概率娶到最美的那个姑娘吗？ 热身问题解答 策略如下。求婚者首先逐个结识前50个女儿，但是拒绝她们。随后，在剩下的50个中，他选择其中第一个比之前见过的50个都美丽的女儿。当然，这不能保证他能娶到最美的那个（甚至不能保证他能选到一个姑娘），但是，这个策略的优点是，只需简单的分析便能大致得出娶到最美的女儿的概率。分析如下。最美的女儿在后50人中的概率是1/2，第二美的女儿在前50人中的概率是1/2，这两个条件同时满足的概率是1/4——假设这100个姑娘被介绍给求婚者的顺序与外貌无关（比如就像题目中假设的，是基于她们的出生时间）。当这两个条件同时满足时，求婚者可以按照上述策略选到最美的姑娘。而实际上，此策略也适用于其他情况。例如，第三美的女儿在前50人中，最美的和第二美的都在后50人中，但最美的比第二美的先出现。如果更深入地分析，会发现更好的策略是拒绝前37个女儿，然后选择之后出现的第一个比这37位都美貌的女儿。 (1) 这个奖金为100万美元的“直冲云霄”游戏有三次“捕获”机会，有没有好的策略呢？如果有的话，你的获胜概率是多少呢？ 提示 编程可能会派上用场。 (2) 如果有1000个乐透球，答案会如何变化？ 1.6　政治分肥　 一笔多达1亿美元的款项将被拨给一个州，这个州由5个区组成。州议会中的议员席位是按照各区人口占州人口的比例分配的。A区有35位州议员，B区有25位，C区有16位，D区有14位，E区有10位。 如果由51位以上议员组成了联盟，那么他们就能使这笔款项拨给自己所代表的区，拨款将按照议员人数的比例分配给各个区。例如，如果A区的35位议员和B区的25位议员结成联盟，他们就能使得这1亿美元拨给A区和B区，A区将得到35/60亿美元，B区将得到25/60亿美元。每个区都只关心他们自己的利益。 热身问题 对B区来说，怎样结盟是最好的？ 热身问题解答 对B区来说，B、C和E这3个区结盟是最好的，因为这样B区能得到总款项的25/55；而如果跟A区结盟，B区只能得到总款项的25/60。 (1) 可能会形成哪些联盟？ B区的议员历来都有一项特权，当分配拨款的时候他们可以操控规则。也就是说，他们不仅可以要求形成联盟的议员必须达到半数以上（就像我们之前假设的51位），还可以规定更高的比例。例如，他们可以要求联盟的议员达到总人数的67%或者75%，才可以获得拨款。 (2) 为了得到尽可能多的钱，B区应该怎么规定这个百分比（51%、67%还是75%）？ 1.7　社会博弈 亚当·斯密（Adam Smith）提出，在自由市场中，有一只“看不见的手”会引导自利的生产商将商品以低价出售给消费者。自此之后，政府和政治就不再被混为一谈了。但是，直到两个多世纪以后，摩根斯特恩（Morgenstern）和冯·诺依曼（Von Neumann）创立的博弈论以及约翰·纳什（John Nash）的研究成果才就这种自利行为的前因后果给出了合理的数学分析。（电影《美丽心灵》的数学家就是以纳什为原型的。） 这道谜题就是博弈论在社会商品中的应用，让我们从“看不见的手”开始。 鲍勃和爱丽丝是两个有竞争关系的生产商。如果他们给商品定个高价，便可以共享市场，每个人都能获得3份利润。如果爱丽丝决定降价，而鲍勃仍维持原价，那么爱丽丝就可以获得4份利润，而鲍勃则分文无收，因为不会有人向他购买商品。这时，鲍勃会降价以获得至少1份利润。类似地，如果转换角色，则获得4份利润的就是鲍勃，而爱丽丝不再获利。因此，出于利己的目的，他们俩都会降价，获利都将降至1份。 下表描述了上述的4种情况，其中，鲍勃和爱丽丝的利润用二元组的方式表示，左边的数字代表鲍勃的利润，右边代表爱丽丝的利润。例如，右上角的单元格代表鲍勃高价（0份利润），爱丽丝低价（4份利润）的情况。 爱丽丝 高 爱丽丝 低 鲍勃 高 3， 3 0， 4 鲍勃 低 4， 0 1， 1 约翰·纳什定义了均衡状态（equilibrium state）的概念，后来被称为纳什均衡。在此状态下，任何一方背离均衡状态，都不可能获得好处。这个例子中唯一的纳什均衡状态位于右下角单元格，即鲍勃和爱丽丝都不单方面提价。如果鲍勃提高价格（对应右上角单元格），他的利润将降为0；同样，如果爱丽丝提高价格（对应左下角单元格），她也将没有利润。 这就是那只“看不见的手”在起作用。对于消费者来说，鲍勃和爱丽丝的竞争会导致商品售价降低，对社会是有利的。事实上，现代经济已经充分证明了这一点。 不过利己思维不一定能给社会带来好处。假设我们用这张表描述的不是相互竞争的生产商对商品价格的选择，而是他们在诚信经商或社会责任上的表现。于是，“鲍勃 高”这一行代表鲍勃诚信经营，而“鲍勃 低”这一行代表他信誉不良（比如欺诈、污染或者贿赂议立法者）。右上角的单元格描述了鲍勃诚信经营但是爱丽丝不守信用的情形，你可以看到，爱丽丝反而能受益。如果他们俩都进行不正当交易，他们的利润都将下降。在这个情形中，利己思维给社会造成了损失。那些腐败的国家、犯罪高发的地区以及争吵不休的家庭，都是活生生的例子。 博弈论是中性的。同样的博弈矩阵，同样的纳什均衡，结果却可好可坏。利己思维对社会可以是福，也可以是祸。 现在，让我们假定你的工作是设计公共政策。面对这个表示欺诈经营带来的个人利益的矩阵，你想要在一定程度上改变它。于是，你建立了警察和刑事司法体系。如果违法经营，有10%的概率被抓到，且将损失5份的利润（比如，关进监狱无法营业）。 于是，在右上角单元格的情况下，爱丽丝的利润有90%的几率是4份，有10%的几率是5份，因此预期收益是(4×0.9)+((5)×0.1)=3.1。根据我们的预期，重新计算矩阵如下： 爱丽丝 诚信 爱丽丝 欺诈 鲍勃 诚信 3， 3 0， 3.1 鲍勃 欺诈 3.1， 0 0.4， 0.4 现在，如果双方都诚信经营，那么欺诈行为所带来的利益会明显减少。如果进一步加重惩罚或者提高被抓住的概率，双方都诚信经营将有可能实现纳什均衡。 热身问题 假设你可以加大惩罚的力度（例如使利润损失更大），但不能提高被抓住的概率，你可以也使左上角和右下角单元格都实现纳什均衡吗？ 热身问题解答 如果将惩罚带来的利润损失设定为8份，那么爱丽丝在右上角单元格状态下的获利是(4×0.9)+ ((8)×0.1)=2.8，在右下角单元格状态下的获利是(1×0.9)+((8)×0.1)=0.1。重新计算矩阵为： 爱丽丝 诚信 爱丽丝 欺诈 鲍勃 诚信 3， 3 0， 2.8 鲍勃 欺诈 2.8， 0 0.1， 0.1 因此，双方都诚信经营将实现纳什均衡，因为鲍勃和爱丽丝都没有理由欺诈经营来离开这个状态。另一方面，右下角的单元格描述的也是纳什均衡。如果鲍勃和爱丽丝都进行欺诈经营，他们还是可以获得微薄的预期收益，但如果任意一人想要诚信经商，那就会连这点儿微薄的利润都保不住。 下面给出几个更具挑战性的谜题。 (1) 如果想使双方都欺诈经营不再是纳什均衡，应该怎么更改惩罚机制？ 随着社会文明的进步，人们惩罚的观念发生了改变，提出了“罪罚相适应”原则。该原则限制了量刑过重。 (2) 假设你负责制定公共政策，想将对欺诈经营的惩罚限制在5份利润之内，那么如果只想维持左上角单元格为纳什均衡，你应该将抓住犯罪行为的几率提高到多少？ 在现代社会中，不平等现象还是存在的。即使大家都诚信守法，不同生产商的受益也存在着差别。比如，鲍勃和爱丽丝都诚信经营，鲍勃的利润是5份，而爱丽丝只有2份。且暂时让我们假设欺诈经营是不会被抓到的，则博弈矩阵如下： 爱丽丝 诚信 爱丽丝 欺诈 鲍勃 诚信 5， 2 0， 4 鲍勃 欺诈 4， 0 1， 1 大家都诚信经营时，社会收益有所增加，但未能实现平等。另一方面，欺诈经营的诱因也随之发生变化。 (3) 假设欺诈经营被抓到的几率是10%，能不能找到合适的惩罚值使得右上角单元格（爱丽丝违法经营，鲍勃诚信经营）成为唯一的纳什均衡点？ (4) 仍然假设欺诈经营被抓到的几率是10%，要想使爱丽丝一直诚信守法，要怎么设计惩罚机制？ 最后，让我们回到最开始时的设定。主角还是有竞争关系的生产商鲍勃和爱丽丝，不存在任何的惩罚机制，博弈矩阵如下。 爱丽丝 高 爱丽丝 低 鲍勃 高 3， 3 0， 4 鲍勃 低 4， 0 1， 1 那只“看不见的手”引导他们降价，但他们并不愿意这么做。他们意识到，如果建立合作关系，那么其总收益将是3+3=6，而不是竞争关系下的1+1=2。因此他们考虑合并企业，以获得6份（而不是2份）的利润。这样，对于鲍勃来说，由于合并带来了额外的收益，他会认为爱丽丝的企业实际上具有5份利润的价值，而不是现在竞争关系下所挣得的那1份利润。当然，这些增加的收益都是消费者贡献的，因为其商品价格大致相同。 下次当你听到有人探讨不平等、犯罪、开明的自利[ 英文为enlightened self-interest，意为人们各种看起来是“利他”的行为，根本上都是一种出于“自利”动机，追求自身利益的行为。亚当·斯密在《国富论》中有如下描述：“不是屠夫、酿酒师和面包师的善心才让我们有了心仪的晚餐，他们考虑的都是他们自身的利益。”——译者注]和反垄断法时，你就可以拿出博弈矩阵来，其中所蕴含的智慧远远胜过夸夸其谈。 1.8　猫鼠游戏　 一个小偷刚刚抢劫了市中心的一家银行。他自以为自己干得悄无声息，一定没有被警方追踪。但实际上，警方早就接到了警报，并且掌握了小偷的确切位置。他们希望放长线钓大鱼，将小偷及其同伙一网打尽。 这个城市的布局可以用一个19×19的道路网格表示。小偷（用T表示）的起始位置正好在城市中心，距离城市任一边界都是9格。图1只展示了整个城市网格的右上角部分。小偷一开始向北驶向城北的第一个十字路口。在每一个十字路口，车辆都可以向右转，向左转，或者直行，但不能后退。如果能到达城市的南边界或北边界，小偷就能逃之夭夭了。 图1　标记T处即是小偷的初始位置。他和北边界、东边界、南边界和西边界的距离都是9个格子，此图只展示了北边界和东边界 警察想先看看小偷要开车去哪里，但他们要确保小偷不能开出城市网格。 在每个十字路口，只要没有警察，小偷便可以自由行驶。但如果有警察，他们便可以逼迫小偷向左、向右或者直走。然而，警方想尽可能留给小偷一定的自由。这样警察就必须决定如何部署警力以实现下述目标。 (1) 警方只想在5个十字路口控制小偷的行驶方向，他们也知道小偷是迫不及待地想要逃脱。那么小偷最多过多久（以网格计）便可以到达北边界或南边界？ (2) 假设警方不想让小偷到达北边界或南边界，因此他们的计划是，每n个十字路口中选m个（m <n）控制小偷的前进方向。如果他们既要防止小偷逃脱，又想对小偷的行驶路线施加最少的干预（m/n最小），m和n的值应该是多少？ (3) 如果小偷只要到达任何一个边界（包括东边界和西边界），就可以逃脱，那么m和n的值又应该是多少？ 1.9　流感中的数学　 假设政府卫生部门告诉你，如果接种流感疫苗，你有5%的概率会死于疫苗的不良反应，如果不接种疫苗，在疫情爆发时你有10%的概率被传染并死于流感。假设疫苗能够提供完美的保护，你愿意接种疫苗吗？ 很多人都会选择不接种。 这一明显的不理性行为通常被归因于“不作为偏见”，即作为与不作为相比，人们往往更倾向于不作为。但是我认为还有其他原因。一方面，卫生部门为了证明自己存在的意义，更希望人们采取行动。如果是这样，他们可能会夸大流感的后果，或者轻描淡写接种疫苗的风险。 但是，即便卫生部门给出的概率是可信的，并且“不作为偏见”也被纠正，人们还是注意到如果大多数人接种了疫苗，那自己即使不接种，染上流感的风险也会降低。 假设，你不接种疫苗死于流感的概率可以用以下公式计算：如果f 表示接种疫苗的人口比例（不包括你），那么你死于流感的概率就是(1f )×10%。比如说，65%的人接种了疫苗，还有35%的人（包括你）没有接种，那么你染上流感的概率是0.35×10%=3.5%。 热身问题 假设疫情爆发时，卫生部门可以要求60%的人必须接种疫苗，那么对于全部人口来说，死于流感的平均风险有多大？ 热身问题解答 根据题中描述，如果卫生部门禁止所有人接种疫苗，那么死于流感的人口比例是10%。而如果其强制要求每个人都接种，死于疫苗不良反应的人口比例就是5%。如果60%的人接种了疫苗，那么他们有5%的概率死于疫苗的不良反应，但是没有接种疫苗的人有40%×10%的可能死于流感，所以他们的死亡比例为4%。因此，所有死亡人口的比例是(0.6×5%)+(0.4×4%)=4.6%。 (1) 如果卫生部门强制要求一定比例的人口接种疫苗，那么为了使流感爆发时的平均死亡率最低，应该如何规定这个比例？ 另一方面，假设政府部门觉得强制人们接种疫苗的做法有失妥当，因此，卫生局轮流给每个人都提供一次接种疫苗的机会，如果拒绝了就没有第二次机会了。每个人都知道在他之前有多少人接种了疫苗，并且认为其他人也和自己一样认可卫生部门提供的风险统计数字（接种疫苗有5%的概率死于不良反应，不接种疫苗有(1f )×10%的概率死于流感）。当且仅当疫苗对自身有益时，大家才会接种疫苗，而不会出于更为崇高的目的。 (2) 在上述前提条件下（没有强迫接种，信任卫生部门的风险统计数据，利己思维），百分之多少的人口会接种疫苗？ (3) 假设有25%的人是无论如何都不会接种疫苗的，但是接种之前谁也不知道具体是哪些人。那么在和上题同样的前提条件下，百分之多少的人口会接种疫苗？ 卫生部门看了推测结果后，意识到善意的谎言还是必要的。因此，卫生部门决定将感染流感后的死亡率从10%夸大为R，那么根据之前的公式（其中的10%已经用R 来替换），不接种疫苗的感染流感死亡概率将变成(1f )×R 。这个夸大感染病毒后死亡概率的策略是一个精心守护的秘密，因此所有人都还是完全信任政府并且认为其他人亦是如此。 (4) 同样，卫生部门不会强迫任何人接种疫苗，那么为了使自愿接种疫苗的人口百分比同第1题，卫生部门应该将流感的致死率夸大为多少？ 免责声明 感染流感和接种流感疫苗的实际致死率要远远低于此题中给出的数字。此外，“善意的谎言”方案是纯属虚构的。 第一部分智力游戏 如果能解出这些谜题，那么让你做管理工作显然是大材小用了。 注意　尖叫的表情表示这是一道特别难解的谜题。 第1章 竞赛——不可能都是赢家 1.1　甜食爱好者 3 1.2　拜占庭赌徒　 5 1.3　“碰碰”运气 7 1.4　信息增益　 9 1.5　直冲云霄！ 11 1.6　政治分肥 13 1.7　社会博弈 14 1.8　猫鼠游戏 17 1.9　流感中的数学 19 1.1　甜食爱好者 杰里米（Jeremy）和玛丽（Marie）是两个喜欢蛋糕也喜欢数学的小孩，可能你也认识这样的小孩。于是，当大厨玛蒂娜（Martine）给他们准备了两块一模一样的长方形蛋糕后，杰里米便说服玛丽来玩一个游戏。 游戏的规则是这样的：杰里米先把一块蛋糕切成两份，这两份大小可能一样，也可能不一样。切完以后，玛丽决定是否要先选蛋糕。如果玛丽先选，她会选那份大的；如果让杰里米先选，玛丽可以预料到杰里米会选走那份大的。 随后，杰里米把另外一块蛋糕也切成两份（请注意，他可以把其中一份切得非常小）。如果之前是玛丽先选的，那么这次杰里米就可以拿走大的那份。如果之前是杰里米先选的，那么这次玛丽就可以拿走大的那份。 热身问题 假设每个小孩的目标是分得尽可能多的蛋糕，那么对于杰里米来说最好的策略是什么呢？ 提示 在查看答案之前，用f 和1f 来表示第一块蛋糕被切分后两部分的大小，其中f ≥1/2。假设下面两种情况：第一种，玛丽先选，拿走了f 那块；第二种，玛丽后选，拿走了1f 那块。依次分析这两种情况下的结果。 热身问题解答 根据提示，玛丽会这样推理：如果她拿了大小为f 的那块，那么杰里米就几乎可以得到第二块蛋糕的全部（杰里米会切点儿蛋糕屑给玛丽，自己拿走几乎整块蛋糕）。这样，玛丽得到的份额是f，而杰里米得到的是(1f )+1。如果她拿了小的那块（用1f 表示），那么对于杰里米来说最好是把第二块平分了，如此一来，玛丽得到的是(1f )+1/2。根据这个推理，杰里米意识到对他来说最好的分法是使f = (1f )+1/2，也就是2 f =3/2，即f =3/4。这样，如果第一块蛋糕是玛丽先选，那么杰里米会得到第一块蛋糕的1/4和整个第二块蛋糕。如果第一块蛋糕是玛丽后选，那么杰里米会得到第一块蛋糕的3/4和第二块蛋糕的1/2。在这两种情况下，玛丽都能得到3/4的蛋糕，而杰里米能得到5/4。注意，如果杰里米在分第一块蛋糕时，大的那块小于3/4，那么玛丽只要后选，就能得到多于1/4的蛋糕，并且能得到第二块蛋糕的1/2，这样她能得到的蛋糕总量将多于3/4。对比之下，如果分第一块蛋糕时，大的那块大于3/4，那么玛丽只要先选，也能得到多于3/4的蛋糕。 我详细地分析了热身问题，因为一个星期后，会有一个更难的挑战。这次大厨玛蒂娜做了3块一模一样的长方形蛋糕，杰里米和玛丽都对它们垂涎欲滴。 他们制订了新规则。杰里米还是负责切蛋糕，但是玛丽有两次先选蛋糕的机会，而杰里米只有一次。也就是杰里米先切第一块蛋糕，玛丽决定她是否要先选。然后杰里米切第二块蛋糕，这次还是由玛丽决定是否先选。第三块蛋糕还是如此。唯一需要注意的是，玛丽至少要留给杰里米一次先选蛋糕的机会。 (1) 在新规则下，杰里米怎样做得到的蛋糕才能最多？他最多能得到多少？ (2) 假设有7块蛋糕，玛丽有6次先选蛋糕的机会，谁有优势？有多大优势？ (3) 假设总是让杰里米来切蛋糕，有没有办法可以确保两个小孩能得到一样多的蛋糕？ 1.2　拜占庭赌徒　 在人们的印象中，拜占庭帝国是以无休止的宫廷阴谋和诡计而闻名的，但它实在不该得此恶名。现代历史研究表明，按照公元一千年的标准拜占庭帝国是相当稳定与和谐的。然而成见难消，这道谜题所讨论的游戏就是受假想的拜占庭阴谋启发的。我们称之为“拜占庭赌徒”。 赌局的规则如下。你将和一群“顾问”一起参与赌局。其中一个顾问会在一张纸上写下0或者1，展示给其他顾问看，但不会让你看到，然后把那张纸扣着放在你面前。随后，每个顾问都会告诉你纸上写的是什么数字。他们都演技精湛，所以你无法通过任何明显的记号或面部表情分辨出他们是否在说谎。每一局，你都可以选择不下注，也可以押上你部分甚至全部资产。 热身问题 假设一共有4位顾问，其中两个人会一直说实话，但是你不知道是哪两位。你可以玩三局，每一局都采用等额投注[ 你若押对了数字，便额外获得等同于你所押的赌注的钱；你若押错，便损失了赌注。——译者注]。赌局开始时，你有100美元，你能确保赢多少钱呢？ 热身问题解答 如果4位顾问中，有3个或4个人给你的建议相同，那就在他们说的那个数字上押最大的注。因为这群人中，至少有一个人是诚实的。如果每两个人给的建议是相同的，那这局先不要下注。这一局结束后，你就能知道哪两个顾问是说实话的，这样以后每局你都可以押最大的注。也就是说，从第二局开始，你就可以押上所有的钱而且能稳赢。三局结束后，你将会有400美元。 (1) 假设现在只有3位顾问，而且只有一个人会一直说实话。你还是可以玩3局，每一局都采用等额投注。赌局开始时，你有100美元，你能确保赢多少钱呢？ 这个赌局将变得更长也更难以应付。你可以玩4局，但是不再有人一直说实话了，只会有一位“不总说实话”的顾问，他不一定每局都说实话，但是4局里至少有3局要说实话。更糟的是，顾问们在你下完注后甚至可以改写纸上的数字。但是如果改写数字会导致那个“不总说实话”的顾问无法存在，他们便不能更改。 (2) 4轮赌局，4位顾问，其中3位可以随意说谎，另一位4次中必须至少有3次说实话，在这种情况下，你能保证赢多少？ (3) 如果你可以参加5局，“不总说实话”的顾问5次中必须有4次说实话，另外3位顾问可以随意说谎，在这种情况下，你能保证最后至少还有150美元吗？ 1.3 “碰碰”运气　 在电影《赌命法则》[ 电影名为Intacto，中文译为《赌命法则》，也叫《完整无缺》，是西班牙一部带有寓言意味的惊悚电影。 ——译者注]的世界里，运气或多或少被设定为一个人永久性的特质。幸运的人不论在赌桌上还是在十字路口都好运连连。但是有那么一群人，他们懂得如何通过触碰来窃取别人的运气，所以好运的人得提防和这群人发生身体接触。影片中主角的任务之一就是要找到这些好运的人。有一次，他想要试一下他招募的那些人的运气，于是，他让他们蒙着眼在树林里奔跑。运气最好的就是第一个到达目的地的人，而很多不那么走运的都撞到了树上。 我们来玩一个温和点的游戏，一般形式是一共有N个人参加，有B次机会下注。每个玩家都知道N和B的值，且每个人都有一笔起始资金（不一定相等），以点数计。 每一轮都是等额投注，抛硬币，赌哪一面朝上。如果你押x点并且赢了，你的财富就会增加x点，否则，输了就会损失这x点。 在每一次抛硬币之前，每个人自行选择将赌注（可以不下注，也可以押部分甚至全部点数）押在正面或反面。 当B轮赌局结束后，剩余点数最多的那个玩家将获胜。如果有两个人的剩余点数一样，就没有赢家。这些点数在游戏结束后是没有任何价值的，所以只有成为最后的胜利者才可以获得奖赏。 热身问题1 现在鲍勃（Bob）和爱丽丝（Alice）拥有相同的点数，而且鲍勃要先于爱丽丝下注。假设还有一轮，爱丽丝有多少获胜的机会？ 热身问题1解答 如果鲍勃押x点赌正面，那么爱丽丝就押x+1点也赌正面。如果确实是正面，那么爱丽丝获胜，否则，鲍勃将获胜。同样，爱丽丝也可以选择什么都不押，这样，如果是反面，爱丽丝便获胜。无论哪种情况，爱丽丝获胜的概率都是1/2。 热身问题2 还是爱丽丝和鲍勃两个玩家，这次爱丽丝比鲍勃拥有更多的点数，还可以玩5轮。如果鲍勃要比爱丽丝先下注，爱丽丝怎样才能使她获胜的概率最大？ 热身问题2解答 爱丽丝每次都可以稳赢。每一轮，爱丽丝都追随鲍勃下同样的注。假设鲍勃押b点赌硬币是正面，那么爱丽丝也押b点赌正面。无论硬币最后是正面朝上还是反面朝上，爱丽丝的剩余点数总是比鲍勃多。 现在让我们来思考几个更有挑战性的问题。 (1) 鲍勃、卡罗尔（Carol）和爱丽丝3个人玩。爱丽丝有51点，鲍勃和卡罗尔都只有50点。按照鲍勃、卡罗尔、爱丽丝这个顺序依次下注。鲍勃和卡罗尔结成联盟，他们俩无论谁赢了都会和另一个分享奖赏。如果只剩下一轮，鲍勃和卡罗尔要如何下注才能使他们当中至少一个人获胜的概率最大？ (2) 如果爱丽丝必须第一个下注，还能得出上题的结论吗？ (3) 鲍勃和爱丽丝两个人玩，鲍勃有51点，爱丽丝有50点，还有两轮。倒数第二轮鲍勃先下注，最后一轮爱丽丝先下注。两轮之后，鲍勃获胜的概率大于1/2吗？如果大于1/2，具体大多少？ (4) 鲍勃有51点，爱丽丝有50点，还有两轮。但这一次，倒数第二轮爱丽丝先下注，最后一轮鲍勃先下注。两轮之后，鲍勃获胜的概率大于1/2吗？如果大于1/2，具体大多少？ (5) 鲍勃有51点，爱丽丝有50点，还有两轮。倒数第二轮爱丽丝先下注，最后一轮鲍勃先下注。这一次，鲍勃事先声明倒数第二轮他的赌注将是20点，但是他会等到爱丽丝下完注后再决定押在哪一面。爱丽丝获胜的概率能大于1/2吗？ 就好像挤进芭蕾舞团、争夺奥运会金牌或攀缘权力的金字塔，往往名额越少，竞争越激烈，承担的风险也就越大。看看你是否认同这一点。 (6) 鲍勃、爱丽丝、里诺（Rino）和朱莉安娜（Juliana）4个人玩，他们每人都有100点，还有两轮。每个人都竭尽全力想赢，因此不再有任何形式的联盟。倒数第二轮，鲍勃和爱丽丝押100点赌正面，里诺押100点赌反面。现在轮到朱莉安娜下注，她知道下一轮她将是第一个下注的人。那么，如果她这一轮押90点（不管是押正面还是反面），她赢的概率是多少？她应该押正面还是反面呢？ 1.4　信息增益 乔丹（Jordan）和他的5个朋友阿里安娜（Ariana）、鲍勃、卡罗琳（Caroline）、大卫（David）及埃伦（Ellen）是智多星俱乐部的领军人物，他们都是杰出的解谜者。因此，永远穿着考究的著名游戏竞赛节目主持人杰夫·尼古拉斯（Jeff Nicholas），向乔丹和他的朋友们发出了比赛邀请。 “我们的比赛是现场直播的。我会蒙上你那5个朋友的眼睛，给他们各戴上一顶帽子，帽子上写有1到10中的某一个数字（可能有些人的数字是一样的），然后将他们领到电视直播间。在直播间里，我会组织他们按我指定的顺序围成一个圈，然后取下蒙眼布，给他们换上不反光的深色太阳眼镜，以防止他们互相使眼色。 “他们到达直播间后，你和观众便可以通过电视监控器看到他们，也可以看到他们头上的数字，但是他们看不到你。我手上有一张蓝票和一张红票。你可以让我把其中的一张票交给他们5人中的任意一个。你只能做这些。敲打直播间的窗户之类是不允许的，否则你们将被取消比赛资格。 “你的朋友们也不可以互相交谈或者传递任何信号，否则都会被取消比赛资格。（显而易见，除了递交那张票，我不会帮你们任何忙。） 但是，他们能看到那张票被交给了谁及票的颜色，也能看到其他人帽子上的数字，不过无法看到自己帽子上的数字。 “我下令后，每个人都伸出手指代表自己头上的数字。猜对的人将获得千倍于自己头上数字的美元作奖金。如果所有的人都猜对了，那么乔丹，你将获得5000美元的奖金。但是如果有人猜错了，你得给我买套新的阿玛尼西装。” “就这样？”乔丹问道，“他们从外界收到的唯一信息就是谁拿到了票以及票的颜色？” “是的，”尼古拉斯说，“但是要记住，他们每个人都能看到别人帽子上的数字。我估计你赢不了这个比赛。我真的很想要一套西装。” (1) 乔丹有没有可能设计出一套协议，使得他的5个朋友都能猜对他们帽子上的数字？如果可以，请解释一下。如果不行，乔丹获胜的概率高吗？ 热身问题 我们先来考虑一个相对简单的情况，这样对乔丹要设计的协议可以有个大致的了解。假设5顶帽子上的数字必须是连续的（例如4，5，6，7，8），乔丹应该怎么做？ 热身问题解答 乔丹和他的朋友可以遵循以下协议。阿里安娜代表1，鲍勃代表2，卡罗琳代表3，大卫代表4，埃伦代表5和6。如果乔丹把票交给阿里安娜，说明这串连续的数字是从1开始的。如果交给鲍勃，说明是从2开始的，交给卡罗琳就是从3开始，交给大卫就是从4开始。如果交给埃伦蓝票，就说明从5开始，而如果交给埃伦的是红票，则代表从6开始。 因此，只要乔丹一发出票，他的5个朋友就都知道了起始数字。他们只要看看其他人帽子上的数字，就能用排除法推算出自己的数字了。 但是在杰夫的挑战中，这些数字并不一定是连续的，甚至有可能存在相同的数字。你认为乔丹能挑战成功吗？ 1.5　直冲云霄！　 “直冲云霄”这个智力游戏是基于空心乐透球的。以下是游戏规则。 你的对手有100张完全一样的纸。他被安排在一个你看不到的房间，在每张纸上不重复地写下1到1 000 000之间任何一个数字，然后将这些纸分别塞到不透明的小信封里。接着，这些信封将被交到一个独立的第三方“填充者”手里。填充者一直是当着你和对手的面工作的。他给你看100个空心的乐透球，然后把信封的顺序打乱，将它们分别塞进100个乐透球中并将球封口。这些球都是经过跌落、弹跳和弹性测试的，可以保证它们的物理性质完全相同。 填充者接下来把这些球都放到乐透机中。乐透机将彻底地搅乱这些球，直到摇出来一个球，把它编为1号球。这个球打开后，你将获知纸上的数字（我们将其简称为“值”）。你可以选择“捕获”或者放弃这个值。如果选择捕获，那么这个值将进入你的“捕获堆”，并记为已使用一次“捕获”；如果放弃，那么这个值就永久地进入了“弃值堆”，但是，你可以记住这个值以备后用。重复上述操作，直到100个球都从机器里出来。你总共有3次“捕获”机会。你的目标是捕获对手所写的最大值。如果成功了，你将赢得100 000美元；如果失败了，你将输掉100 000美元。你应该参与这个游戏吗？若参与的话，获胜的概率有多大？ 这道题其实是“苏丹的女儿”谜题的变体。年轻的求婚者要从苏丹的100个女儿中选择他的新娘。这100个姑娘以随机的顺序介绍给他，他只能根据她们的外貌和仪态来作出决定，没有其他可供评判的依据。如果他拒绝了其中的一个，那么他和她就彻底无缘了。一旦他作出了选择，就只能娶那一个。 热身问题 假设这100个姑娘介绍给他的顺序与她们的外貌无关，比如是基于她们的出生时间，你能为这个求婚者设计一个策略，使得他至少有1/4的概率娶到最美的那个姑娘吗？ 热身问题解答 策略如下。求婚者首先逐个结识前50个女儿，但是拒绝她们。随后，在剩下的50个中，他选择其中第一个比之前见过的50个都美丽的女儿。当然，这不能保证他能娶到最美的那个（甚至不能保证他能选到一个姑娘），但是，这个策略的优点是，只需简单的分析便能大致得出娶到最美的女儿的概率。分析如下。最美的女儿在后50人中的概率是1/2，第二美的女儿在前50人中的概率是1/2，这两个条件同时满足的概率是1/4——假设这100个姑娘被介绍给求婚者的顺序与外貌无关（比如就像题目中假设的，是基于她们的出生时间）。当这两个条件同时满足时，求婚者可以按照上述策略选到最美的姑娘。而实际上，此策略也适用于其他情况。例如，第三美的女儿在前50人中，最美的和第二美的都在后50人中，但最美的比第二美的先出现。如果更深入地分析，会发现更好的策略是拒绝前37个女儿，然后选择之后出现的第一个比这37位都美貌的女儿。 (1) 这个奖金为100万美元的“直冲云霄”游戏有三次“捕获”机会，有没有好的策略呢？如果有的话，你的获胜概率是多少呢？ 提示 编程可能会派上用场。 (2) 如果有1000个乐透球，答案会如何变化？ 1.6　政治分肥　 一笔多达1亿美元的款项将被拨给一个州，这个州由5个区组成。州议会中的议员席位是按照各区人口占州人口的比例分配的。A区有35位州议员，B区有25位，C区有16位，D区有14位，E区有10位。 如果由51位以上议员组成了联盟，那么他们就能使这笔款项拨给自己所代表的区，拨款将按照议员人数的比例分配给各个区。例如，如果A区的35位议员和B区的25位议员结成联盟，他们就能使得这1亿美元拨给A区和B区，A区将得到35/60亿美元，B区将得到25/60亿美元。每个区都只关心他们自己的利益。 热身问题 对B区来说，怎样结盟是最好的？ 热身问题解答 对B区来说，B、C和E这3个区结盟是最好的，因为这样B区能得到总款项的25/55；而如果跟A区结盟，B区只能得到总款项的25/60。 (1) 可能会形成哪些联盟？ B区的议员历来都有一项特权，当分配拨款的时候他们可以操控规则。也就是说，他们不仅可以要求形成联盟的议员必须达到半数以上（就像我们之前假设的51位），还可以规定更高的比例。例如，他们可以要求联盟的议员达到总人数的67%或者75%，才可以获得拨款。 (2) 为了得到尽可能多的钱，B区应该怎么规定这个百分比（51%、67%还是75%）？ 1.7　社会博弈 亚当·斯密（Adam Smith）提出，在自由市场中，有一只“看不见的手”会引导自利的生产商将商品以低价出售给消费者。自此之后，政府和政治就不再被混为一谈了。但是，直到两个多世纪以后，摩根斯特恩（Morgenstern）和冯·诺依曼（Von Neumann）创立的博弈论以及约翰·纳什（John Nash）的研究成果才就这种自利行为的前因后果给出了合理的数学分析。（电影《美丽心灵》的数学家就是以纳什为原型的。） 这道谜题就是博弈论在社会商品中的应用，让我们从“看不见的手”开始。 鲍勃和爱丽丝是两个有竞争关系的生产商。如果他们给商品定个高价，便可以共享市场，每个人都能获得3份利润。如果爱丽丝决定降价，而鲍勃仍维持原价，那么爱丽丝就可以获得4份利润，而鲍勃则分文无收，因为不会有人向他购买商品。这时，鲍勃会降价以获得至少1份利润。类似地，如果转换角色，则获得4份利润的就是鲍勃，而爱丽丝不再获利。因此，出于利己的目的，他们俩都会降价，获利都将降至1份。 下表描述了上述的4种情况，其中，鲍勃和爱丽丝的利润用二元组的方式表示，左边的数字代表鲍勃的利润，右边代表爱丽丝的利润。例如，右上角的单元格代表鲍勃高价（0份利润），爱丽丝低价（4份利润）的情况。 爱丽丝 高 爱丽丝 低 鲍勃 高 3， 3 0， 4 鲍勃 低 4， 0 1， 1 约翰·纳什定义了均衡状态（equilibrium state）的概念，后来被称为纳什均衡。在此状态下，任何一方背离均衡状态，都不可能获得好处。这个例子中唯一的纳什均衡状态位于右下角单元格，即鲍勃和爱丽丝都不单方面提价。如果鲍勃提高价格（对应右上角单元格），他的利润将降为0；同样，如果爱丽丝提高价格（对应左下角单元格），她也将没有利润。 这就是那只“看不见的手”在起作用。对于消费者来说，鲍勃和爱丽丝的竞争会导致商品售价降低，对社会是有利的。事实上，现代经济已经充分证明了这一点。 不过利己思维不一定能给社会带来好处。假设我们用这张表描述的不是相互竞争的生产商对商品价格的选择，而是他们在诚信经商或社会责任上的表现。于是，“鲍勃 高”这一行代表鲍勃诚信经营，而“鲍勃 低”这一行代表他信誉不良（比如欺诈、污染或者贿赂议立法者）。右上角的单元格描述了鲍勃诚信经营但是爱丽丝不守信用的情形，你可以看到，爱丽丝反而能受益。如果他们俩都进行不正当交易，他们的利润都将下降。在这个情形中，利己思维给社会造成了损失。那些腐败的国家、犯罪高发的地区以及争吵不休的家庭，都是活生生的例子。 博弈论是中性的。同样的博弈矩阵，同样的纳什均衡，结果却可好可坏。利己思维对社会可以是福，也可以是祸。 现在，让我们假定你的工作是设计公共政策。面对这个表示欺诈经营带来的个人利益的矩阵，你想要在一定程度上改变它。于是，你建立了警察和刑事司法体系。如果违法经营，有10%的概率被抓到，且将损失5份的利润（比如，关进监狱无法营业）。 于是，在右上角单元格的情况下，爱丽丝的利润有90%的几率是4份，有10%的几率是5份，因此预期收益是(4×0.9)+((5)×0.1)=3.1。根据我们的预期，重新计算矩阵如下： 爱丽丝 诚信 爱丽丝 欺诈 鲍勃 诚信 3， 3 0， 3.1 鲍勃 欺诈 3.1， 0 0.4， 0.4 现在，如果双方都诚信经营，那么欺诈行为所带来的利益会明显减少。如果进一步加重惩罚或者提高被抓住的概率，双方都诚信经营将有可能实现纳什均衡。 热身问题 假设你可以加大惩罚的力度（例如使利润损失更大），但不能提高被抓住的概率，你可以也使左上角和右下角单元格都实现纳什均衡吗？ 热身问题解答 如果将惩罚带来的利润损失设定为8份，那么爱丽丝在右上角单元格状态下的获利是(4×0.9)+ ((8)×0.1)=2.8，在右下角单元格状态下的获利是(1×0.9)+((8)×0.1)=0.1。重新计算矩阵为： 爱丽丝 诚信 爱丽丝 欺诈 鲍勃 诚信 3， 3 0， 2.8 鲍勃 欺诈 2.8， 0 0.1， 0.1 因此，双方都诚信经营将实现纳什均衡，因为鲍勃和爱丽丝都没有理由欺诈经营来离开这个状态。另一方面，右下角的单元格描述的也是纳什均衡。如果鲍勃和爱丽丝都进行欺诈经营，他们还是可以获得微薄的预期收益，但如果任意一人想要诚信经商，那就会连这点儿微薄的利润都保不住。 下面给出几个更具挑战性的谜题。 (1) 如果想使双方都欺诈经营不再是纳什均衡，应该怎么更改惩罚机制？ 随着社会文明的进步，人们惩罚的观念发生了改变，提出了“罪罚相适应”原则。该原则限制了量刑过重。 (2) 假设你负责制定公共政策，想将对欺诈经营的惩罚限制在5份利润之内，那么如果只想维持左上角单元格为纳什均衡，你应该将抓住犯罪行为的几率提高到多少？ 在现代社会中，不平等现象还是存在的。即使大家都诚信守法，不同生产商的受益也存在着差别。比如，鲍勃和爱丽丝都诚信经营，鲍勃的利润是5份，而爱丽丝只有2份。且暂时让我们假设欺诈经营是不会被抓到的，则博弈矩阵如下： 爱丽丝 诚信 爱丽丝 欺诈 鲍勃 诚信 5， 2 0， 4 鲍勃 欺诈 4， 0 1， 1 大家都诚信经营时，社会收益有所增加，但未能实现平等。另一方面，欺诈经营的诱因也随之发生变化。 (3) 假设欺诈经营被抓到的几率是10%，能不能找到合适的惩罚值使得右上角单元格（爱丽丝违法经营，鲍勃诚信经营）成为唯一的纳什均衡点？ (4) 仍然假设欺诈经营被抓到的几率是10%，要想使爱丽丝一直诚信守法，要怎么设计惩罚机制？ 最后，让我们回到最开始时的设定。主角还是有竞争关系的生产商鲍勃和爱丽丝，不存在任何的惩罚机制，博弈矩阵如下。 爱丽丝 高 爱丽丝 低 鲍勃 高 3， 3 0， 4 鲍勃 低 4， 0 1， 1 那只“看不见的手”引导他们降价，但他们并不愿意这么做。他们意识到，如果建立合作关系，那么其总收益将是3+3=6，而不是竞争关系下的1+1=2。因此他们考虑合并企业，以获得6份（而不是2份）的利润。这样，对于鲍勃来说，由于合并带来了额外的收益，他会认为爱丽丝的企业实际上具有5份利润的价值，而不是现在竞争关系下所挣得的那1份利润。当然，这些增加的收益都是消费者贡献的，因为其商品价格大致相同。 下次当你听到有人探讨不平等、犯罪、开明的自利[ 英文为enlightened self-interest，意为人们各种看起来是“利他”的行为，根本上都是一种出于“自利”动机，追求自身利益的行为。亚当·斯密在《国富论》中有如下描述：“不是屠夫、酿酒师和面包师的善心才让我们有了心仪的晚餐，他们考虑的都是他们自身的利益。”——译者注]和反垄断法时，你就可以拿出博弈矩阵来，其中所蕴含的智慧远远胜过夸夸其谈。 1.8　猫鼠游戏　 一个小偷刚刚抢劫了市中心的一家银行。他自以为自己干得悄无声息，一定没有被警方追踪。但实际上，警方早就接到了警报，并且掌握了小偷的确切位置。他们希望放长线钓大鱼，将小偷及其同伙一网打尽。 这个城市的布局可以用一个19×19的道路网格表示。小偷（用T表示）的起始位置正好在城市中心，距离城市任一边界都是9格。图1只展示了整个城市网格的右上角部分。小偷一开始向北驶向城北的第一个十字路口。在每一个十字路口，车辆都可以向右转，向左转，或者直行，但不能后退。如果能到达城市的南边界或北边界，小偷就能逃之夭夭了。 图1　标记T处即是小偷的初始位置。他和北边界、东边界、南边界和西边界的距离都是9个格子，此图只展示了北边界和东边界 警察想先看看小偷要开车去哪里，但他们要确保小偷不能开出城市网格。 在每个十字路口，只要没有警察，小偷便可以自由行驶。但如果有警察，他们便可以逼迫小偷向左、向右或者直走。然而，警方想尽可能留给小偷一定的自由。这样警察就必须决定如何部署警力以实现下述目标。 (1) 警方只想在5个十字路口控制小偷的行驶方向，他们也知道小偷是迫不及待地想要逃脱。那么小偷最多过多久（以网格计）便可以到达北边界或南边界？ (2) 假设警方不想让小偷到达北边界或南边界，因此他们的计划是，每n个十字路口中选m个（m <n）控制小偷的前进方向。如果他们既要防止小偷逃脱，又想对小偷的行驶路线施加最少的干预（m/n最小），m和n的值应该是多少？ (3) 如果小偷只要到达任何一个边界（包括东边界和西边界），就可以逃脱，那么m和n的值又应该是多少？ 1.9　流感中的数学　 假设政府卫生部门告诉你，如果接种流感疫苗，你有5%的概率会死于疫苗的不良反应，如果不接种疫苗，在疫情爆发时你有10%的概率被传染并死于流感。假设疫苗能够提供完美的保护，你愿意接种疫苗吗？ 很多人都会选择不接种。 这一明显的不理性行为通常被归因于“不作为偏见”，即作为与不作为相比，人们往往更倾向于不作为。但是我认为还有其他原因。一方面，卫生部门为了证明自己存在的意义，更希望人们采取行动。如果是这样，他们可能会夸大流感的后果，或者轻描淡写接种疫苗的风险。 但是，即便卫生部门给出的概率是可信的，并且“不作为偏见”也被纠正，人们还是注意到如果大多数人接种了疫苗，那自己即使不接种，染上流感的风险也会降低。 假设，你不接种疫苗死于流感的概率可以用以下公式计算：如果f 表示接种疫苗的人口比例（不包括你），那么你死于流感的概率就是(1f )×10%。比如说，65%的人接种了疫苗，还有35%的人（包括你）没有接种，那么你染上流感的概率是0.35×10%=3.5%。 热身问题 假设疫情爆发时，卫生部门可以要求60%的人必须接种疫苗，那么对于全部人口来说，死于流感的平均风险有多大？ 热身问题解答 根据题中描述，如果卫生部门禁止所有人接种疫苗，那么死于流感的人口比例是10%。而如果其强制要求每个人都接种，死于疫苗不良反应的人口比例就是5%。如果60%的人接种了疫苗，那么他们有5%的概率死于疫苗的不良反应，但是没有接种疫苗的人有40%×10%的可能死于流感，所以他们的死亡比例为4%。因此，所有死亡人口的比例是(0.6×5%)+(0.4×4%)=4.6%。 (1) 如果卫生部门强制要求一定比例的人口接种疫苗，那么为了使流感爆发时的平均死亡率最低，应该如何规定这个比例？ 另一方面，假设政府部门觉得强制人们接种疫苗的做法有失妥当，因此，卫生局轮流给每个人都提供一次接种疫苗的机会，如果拒绝了就没有第二次机会了。每个人都知道在他之前有多少人接种了疫苗，并且认为其他人也和自己一样认可卫生部门提供的风险统计数字（接种疫苗有5%的概率死于不良反应，不接种疫苗有(1f )×10%的概率死于流感）。当且仅当疫苗对自身有益时，大家才会接种疫苗，而不会出于更为崇高的目的。 (2) 在上述前提条件下（没有强迫接种，信任卫生部门的风险统计数据，利己思维），百分之多少的人口会接种疫苗？ (3) 假设有25%的人是无论如何都不会接种疫苗的，但是接种之前谁也不知道具体是哪些人。那么在和上题同样的前提条件下，百分之多少的人口会接种疫苗？ 卫生部门看了推测结果后，意识到善意的谎言还是必要的。因此，卫生部门决定将感染流感后的死亡率从10%夸大为R，那么根据之前的公式（其中的10%已经用R 来替换），不接种疫苗的感染流感死亡概率将变成(1f )×R 。这个夸大感染病毒后死亡概率的策略是一个精心守护的秘密，因此所有人都还是完全信任政府并且认为其他人亦是如此。 (4) 同样，卫生部门不会强迫任何人接种疫苗，那么为了使自愿接种疫苗的人口百分比同第1题，卫生部门应该将流感的致死率夸大为多少？ 免责声明 感染流感和接种流感疫苗的实际致死率要远远低于此题中给出的数字。此外，“善意的谎言”方案是纯属虚构的。