Interesting Game Theory (Continuously updating)
博弈论是非常有趣的一门学科，学好博弈论，人人千层饼。
这篇blog用来记录一些有趣的博弈论小问题吧。
1. 病狗问题
一个村子里, 有50户人家,每家都养了一条狗.
现在, 发现村子里面出现了n只病狗, 村里规定, 谁要是发现了自己的狗是病狗, 就要将自己的狗枪毙.
但问题是, 村子里面的人只能看出别人家的狗是不是病狗, 而不能看出自己的狗是不是病的, 如果看出别人家的狗是病狗, 也不能告诉别人.
于是大家开始观察, 第一天晚上, 没有枪声； 第二天晚上, 没有枪声；第三天晚上, 枪声响起（具体几枪不清楚)。
假设村民都是博弈论大师，且足够理性，问村子里有几只病狗?
Answer
枪响了3声，共三只病狗。
已知：一直村里一定存在病狗，但数量不确定。
村民只能看到别人家狗子的健康状况，且互相不能交流。
如果只有一只病狗，狗主人势必发现村子里其他人的狗子都健康。
好比已知屋子里3个人中至少有一个SB, 结果你发现其他俩人都不是... 答案就很明显了
所以如果只有一只bingo，第一天狗主人就会开枪。
然而第一天晚上无事发生，表明，病狗的主人还看到了其他至少一只bingo，当天晚上bingo的主人们都在等别人开枪。
第一天没有人开枪，说明至少村里有两只bingo。好比已知屋子里3个人中至少有俩是SB, 你发现面前俩人中有一个SB，那剩下的是谁不言而喻。
但是，第二天也没人开枪。 表明，bingo的主人至少看到了两只bingo, 所以他觉得第一天没人开枪正常，第二天bingo主人看到的其他两个bingo主人应该会开枪。
假定村里有3只bingo, 所以当第二天依旧没人开枪，第三天bingo主人们都意识到了一件事，自己的狗子也是bingo。
好比屋子里已知有3个SB, 你只看到了俩...
于是，第三天，枪声响起。
2. 海盗分金币
在一座座荒岛上，有5个强盗掘出了100块非常珍贵的金币。
他们商定了一个分配金币的规则：
首先抽签决定每个人的次序，排列成强盗一至五。
然后由强盗一先提出分配方案，经5人表决，如多数人同意，方案就被通过，否则强盗一将被扔入大海喂鲨鱼。
如果强盗一被扔入大海，就由强盗二接着提出分配方案，如多数人同意方案就被通过，否则强盗二也要被扔入大海。
以下依次类推。
假定每个强盗都足够聪明, 足够贪婪，且都能做出理性的选择，那么，强盗一提出什么样的分配方案，能够使自己得到最大的收益？
Answer
[97,0,1,0,2] or [97,0,1,2,0]
有没有觉得答案有些离谱？，我们慢慢分析：
已知有5个海盗，各个心狠手辣，有精又贪，人均千层饼。
先从海盗五开始分析，海盗五当然希望一二三四全投死，这样钱就都是自己的
所以，当海盗四提出方案时（这表明海盗一二三已经全部out），海盗五必反对。
因此，海盗四预判了海盗五的操作后，不会让自己成为方案的提出者
这意味着，海盗四不能让海盗三死。
所以，轮到海盗三提出方案时（这意味着海盗一二已经out)，预判海盗四必然同意，海盗五必然反对
海盗三必然提出方案: [100, 0, 0]， 方案必然也会通过，毕竟海盗四不想死
然而海盗二早已预判了海盗三的预判
所以当海盗一out后，海盗二提出方案： [98, 0, 1, 1]
因为海盗四五也预判了海盗三的预判，所以会同意更有利(分到一个金币)的方案
但是海盗一早已预判了海盗二的预判，只需要还海盗二的方案基础上拉拢到海盗三四五中两个人就好
于是，海盗一的方案： [97, 0, 1, 2, 0] or [97, 0, 1, 0, 2]
这个方案中只需要放弃海盗二，拉拢海盗三，再对海盗四五捧一踩一即可.
3. 囚徒困境
一件严重的纵火案发生后，警察在现场抓到甲、乙两个犯罪嫌疑人。事实上，正是他们一起放火烧了这座仓库。
但是，警方没有掌握足够的证据，只得把他们分开囚禁起来，要求他们坦白交代。 在分开囚禁后，警察对其分别告知：
- 如果你坦白，而对方不坦白，则将你释放，判对方8年。
- 如果你不坦白，而对方坦白，则将对方释放，而判你8年。
- 如果你两都坦白了，则判你两各自4年。
Answer
| \ | 甲·坦白 | 甲·不坦白 |
| 乙·坦白 |
甲: 4年 乙: 4年 |
甲: 8年 乙: 0年 |
| 乙·不坦白 |
甲: 0年 乙: 8年 |
甲: 0年 乙: 0年 |
先提一个概念：纳什均衡
在博弈论中，如果每个参与者都选择了自己的策略，并且没有玩家可以透过 其他参与者保持不变、自己改变策略而获益，那么当前的策略选择的集合及其相应的结果构成了纳什均衡。
因为人性的问题，甲乙二人都会选择让自己利益最大化的方案。
抛开乙的选择，甲在坦白与不坦白之前对比，根据上表的内容，明显坦白收益大于不坦白。
对于乙来讲，抛开甲的选择不谈，同样坦白收益大于不坦白。
因此二人最终都会选择坦白。这个结果构成了他们的纳什均衡，即甲、乙二人都无法通过改变策略而获益更多
4. 旅行者困境
航空公司丢失了两位互相不认识乘客的旅行包。
两个旅行包正好都是一样的，并且里面有相同价值的古董，两位乘客都向航空公司索赔1000美元。
为了评估出古董的真实价值，公司经理将两位乘客分开以避免两人合谋，分别让他们写下古董的价值，其金额必须是整数，而且要不低于300美元，并且不高于1000美元。
同时还告诉两人：如果两个数字是一样的，那么会被认为是其真实价值，他们能获得相应金额的赔偿。
如果数字不一样，较小的会被认为是真实价值，而两人在获得这个金额的同时有相应的奖赏/惩罚：写下较小金额的会获得10美元额外的奖励，较大的会有10美元的惩罚。
现在问题在于：两位旅行者应该用什么策略来决定他们应该写下的金额？
Answer
旅行者困境是一种非零和博弈，博弈双方都为了让自己收益最大化，而不考虑对方收益这个例子和囚徒困境有一点点像，比如把两位旅行者随意写金额，
改为选择两个金额 500 | 600，那么这就是个囚徒困境。
这道题可以算做囚徒困境的延伸，不难看出，
当两位旅行者都选择300的时候，这个策略组合达到了纳什均衡，
因为写下较小的金额会多10刀奖励，净赚9刀，双方势必互相压价，直到无价可压。
有趣的是，现实中非理性的人群往往因为不够理性而赚的更多。
这就是内卷吗？
5. 蜈蚣博弈
假设蜈蚣博弈有两位参与者爱丽丝与鲍伯，爱丽丝先行动。
开始时，爱丽丝面前有两堆硬币，一堆有四枚，另一堆则有一枚。
每位参与者行动时要二选一：
- 拿走较多的那堆硬币并把较少的那堆留给对手
- 把两堆硬币放到对手面前让对手继续行动
如果选择后者，两堆硬币的数量就会翻倍（此处变多的硬币来源于外部）。
例如第一回合中爱丽丝选择让对手继续行动，则两堆硬币的数量分别变为八枚和两枚。
蜈蚣博弈有一个两人事先都知道的最大期数，一旦超过这个期数，则当前行动者必须选择拿走较多那堆的硬币，结束博弈。 假如爱丽丝与鲍伯都足够理性，爱丽丝先手，应该如何选择？
Answer
爱丽丝当场拿走4枚金币为最优解。无论谁先手都会拿走较多的那堆金币巧妙地点在于 初始状态下 一堆有4枚金币，另一堆只有1枚金币，无论如何翻倍，多的那一堆永远要多于少的一堆。
假设博弈进行到了最后一期，不妨设当前行动者是鲍伯，他选择背叛带来的收益大于合作带来的收益，因此他会选择背叛。
爱丽丝也知道这一点，因为鲍伯选择背叛给爱丽丝带来的收益小于爱丽丝在前一期就背叛带来的收益，所以在前一期爱丽丝就会选择背叛。
以此类推，每一期的行动者都会选择背叛
6. 枪手博弈
彼此痛恨的甲乙丙三个枪手准备决斗。甲枪法最好，十发八中。乙枪法次之，十发六中。丙枪法最差，十发四中。假设他们了解彼此实力，也能做出理性判断。
- 如果三人同时开枪，并且每人只发一枪。第一轮枪战后，谁活下来的机会大？
- 如果三人轮流开枪，并且由枪法最差的丙先开枪，他该怎么做？
Answer
问题1：丙活下来的几率最大
原因如下:
三人同时开枪，则不需要考虑顺序对结果的影响，那么按照各自枪法的好坏，第一轮开枪的选择：
- 甲会向对自己威胁最大的乙开枪。
- 乙会向对自己威胁最大的甲开枪。
- 丙也会对对自己威胁最大的甲开枪。
- 甲：40% * 60% = 24%;
- 乙：20%;
- 丙：100%;
所以只有甲乙都存活或者甲乙都死亡时，丙才会安全。否则丙在平衡打破后死亡几率激增。
问题2：开空枪，既不攻击甲，也不攻击乙。
本次规则为轮流开枪，同样根据枪法好坏，甲乙一定优先攻击对方。
丙先开枪的情况下，万一击中，假设击中甲(乙)，另一方乙（甲）接着开枪，目标一定为丙。
由于丙枪法最差，且在第一枪开出后，相对后手开枪，所以局势非常不利。
所以丙的做法一定是，谁也不攻击，放空枪，等待甲/乙分出胜负。之后便可先手攻击甲乙两者中的获胜者。
Comments