博弈论入门

★引子

博弈论该理论专门研究多个独立个体之间的竞争行为（对抗行为）。在某些中文书籍里面，它又被称作“对策论 or 赛局理论”。
本篇只做入门，后面有精力，会考虑详细学习，
有时候 入门和无知，已经能感受到巨大的差距了，不是吗？

★策略 ＆ 策略集合

决策选项（move） VS 策略（strategy）

　某些资料（比如维基百科）把“move”直译为“移动”。这个译法比较怪。在本文中，俺称之为“决策选项”。
　　很多人混淆了“策略”与“决策选项”。
　　以象棋为例，完成一局需要经历很多个步骤。对每个步骤，你都有 N 个决策选项（要走哪个棋子，走到哪）。而“策略”指的是——从第一步到最后一步的所有决策选项的【总和】。你可以把“策略”通俗理解为某种【算法 or 指导思想】，它指导你从第一步走到最后一步。

★实例：（二战中）新几内亚的航路作战
话说太平洋战场上，美日双方对新几内亚岛展开争夺战。美方通过截获的情报得知日方有一支补给船队要开往该岛。日军补给船队有两条路线可走（北线 or 南线），两条路线都耗时3天。在南线，这3天都是晴天；在北线有2天是晴天，1天是阴雨（阴雨天会影响美军轰炸）。
　　美方空军将领手头只有一个飞行队，需要决策：把这个飞行队派到哪一边执行轰炸任务？如果押宝的方向错误，重新部署又会浪费掉1天时间。
　　对这个博弈过程，美方的收益矩阵参见下述表格。表格中的数字表示“可用来轰炸的天数”（对美军而言，这个数字越大越好）。

	日方
美方		北线	南线
	北线	2	2
	南线	1	3

　　从上述收益矩阵来看，美军应该选哪个策略，不那么明显。但如果【换位思考】，看日军的策略，就非常明显啦。

	日方
美方		北线	南线
	北线	2,-2	2,-2
	南线	1,-1	3,-3

　第2个表格补充了日方的收益（以逗号分隔）。由于日方是遭受轰炸，其收益以“负数”表示。 　　从日方的角度（表格的【纵向】角度）来看，走北线是其【支配策略】——不论美方如何选择，日方走北线的收益都不比南线差。对应到刚才介绍的概念，日方的这个“支配策略”属于“弱支配策略”。 　　知道日军必定走北线之后，美军就很容易选定自己的策略了。

★最小最大定理

这个玩意儿洋文叫做“Minimax”，比较绕口的陈述是：最小化最大损失。更通俗的表述是：在最坏情况下最小化损失。

分蛋糕博弈

★反向归纳法

　该方法洋文称之为“backward induction”。其精髓是【正向展望，反向推理】
　首先，你需要思考自己的每个决策，以及对方在应对你的决策时，会采用何种决策（这个思维过程类似于【决策树的展开】）
　　这个展开过程要一直推演到【最后一步】（也就是决策树的叶子节点）。此时你就可以看清双方在最后一步各自的最优选择；然后再反向回推到第一步。

海盗博弈（海盗分金问题）
博弈场景描述
　　5个海盗抢了100个金币，讨论如何分赃。
　　这5个海盗有等级高低（不妨假设 A＞B＞C＞D＞E）。先由等级最高的海盗提出分赃方案，然后投票。如果半数以上（含半数）同意，就按这个方案分，游戏结束；如果同意的不到半数，把提出方案的海盗扔进海里喂鲨鱼，然后由次一等级的海盗提出新的方案；以此类推。
　　每个海盗的特点是：足够理性（追求个人利益最大化）并且知道别人也足够理性；足够残忍（在个人利益等同的情况下，倾向于把更多同伴扔进海里）。

　　为了进行反向推理，假设最后只剩下2个海盗（D ＆ E）。此时的投票肯定过半（D 肯定投票赞同自己的方案）。在这种局面下，D 可以采用最极端的方案——自己全拿100个金币，E 则一个也拿不到。
　　现在回推一步。当只剩下3个海盗（C、D、E），由 C 提出方案。他只需要分1个金币给 E，E 就会投票支持（否则的话，等到由 D 来提方案，E 啥也拿不到）。所以在 C 的方案中，他自己拿99个金币，E 拿1个金币。
　　再往前一步。只剩下4个海盗（B、C、D、E），B 提方案，他当然也能想到刚才那些推理。他只需给 D 1个金币，D 就会支持他（如果等到 C 来提方案，D 啥也拿不到）。所以 B 提出的方案是 B：99，C：0，D：1，E：0，同样能得到半数支持。
　　基于上述分析，再看 A 的方案，就很显然了——A：98，B：0，C：1，D：0，E：1
有些同学可能会觉得：A 还可以提出另一个等价方案 A：98，B：0，C：0，D：1，E：1（把 C ＆ D 交换）
　　其实这个方案【不】等价。如果是后面这个方案，D 会投反对票，于是 A 去喂鲨鱼，由 B 来提方案，D 还是可以拿到1个金币。虽然两种方案，D 都是拿1个金币。但基于规则中提到的【残忍性】，D 会对 A 的方案投反对票。

★纳什均衡

　所谓的“纳什均衡”，通俗地说是指——在多人的“非合作博弈”中，如果每个博弈者都无法【单方面】改善自己的境地，此时的局面称作“纳什均衡”。
　　冯·诺伊曼已经在《博弈论与经济行为》一书中证明了：零和博弈必定存在这样的均衡点。
　　纳什的贡献在于——他从“零和博弈”推广到“非零和博弈”，并证明了：这样的均衡点依然存在。
实例：囚徒困境
囚犯困境

	囚犯B
囚犯A		坦白	抵赖
	坦白	-2,-2	0,-5
	抵赖	-5,0	1,-1

　　基于上述矩阵，“双方都坦白”的局面是“纳什均衡点”（表格中着色的格子）——在这个均衡局面下，任何一个囚犯【单方面】改变策略，只会让自己更不利。 　　作为对比，“双方都抵赖”虽然是双赢的局面，但这个局面是【不】稳定滴。因为在这个局面下，任何一个囚犯都有动机去改变策略，从而让自己的获益更多。