算法博弈论（一）

在小罗同学的技术支持下，本公众号开设一个博弈论专栏，不定期更新，无限期拖稿。欢迎大家一起来学习有趣的博弈论。

博弈论（Game Theory），又称对策论，于1928年由约翰·冯·诺依曼（没错，就是你看到过很多次的那个天才冯·诺伊曼）提出，而后不断发展，直至今日，已经成为一门完善的理论。

博弈论最初应用于经济学，是经济学的标准分析工具之一，随着其理论的不断完善与发展，现在博弈论已经被应用到生物学、计算机科学、政治学等诸多方面。

当然，既然你是在这里看到这篇文章的，那我们所讲的博弈论自然是偏重于计算机科学方面的，再细说，应当称其为算法博弈论（Algorithmic Game Theory）。（注：学习算法博弈论最经典的入门教材应当就是《Algorithmic Game Theory》这本书了，附上亚马逊链接：https://www.amazon.cn/dp/0521872820，不过我估计没人会买，当然，我们的公众号也提供相应的PDF版本哦，公众号回复【AGT】获取资源）

讲到博弈论，就不得不提及一个烂到家的经典问题了：囚徒困境（Prisoners’ dilemma）。

囚徒困境和IG那个囚徒没啥关系啊，他应该不至于牵扯到这种困境中（一本正经脸）。如下图所示，有两个犯人合作犯案（分别称之为P1和P2）被警察逮捕了，某种审讯条例规定，如果两个人都保持沉默（Silent），拒不承认罪行，则由于没有足够证据，只能判他们每人两年刑期；若一个犯人招供（Confess），另一个犯人仍然嘴硬，则招供的犯人只判一年，而嘴硬的犯人需要受到惩罚而被判五年；若两个犯人都选择招供，则两头棒打，谁让你们犯案的，两个人都被判四年。

OK，看到这里，相信很多读者说：这不是很简单嘛，两个人事先串通，都不招供就是了，这样才是最好的。看上去这个方法好像没什么毛病，也很贴合情景，合则两利，分则两伤。

但设身处地地试想一下，若诸君是其中一人呢，你真的会这样做吗？由上图可得，如果另一个人选择嘴硬，那你选择招供反而更好，这样你只判一年，而他要四年；如果另一个人选择招供，那你也只好选择招供，因为你要是嘴硬就得判五年，太亏了。如果两个人都这样想，这样就会出现一个很有意思的结果：两个人都选择招供，结果就是各打四十大板，每人四年走起。

当然，你可以反驳这种做法，比如这样违反兄弟必杀守则啦之类的，这里就要引入博弈论研究的假设了：

（1）决策主体是理性的，即博弈论认为任何人都不会损己利人，但如果可以的话一定会损人利己；

（2）完全理性是共同知识，即大家都知道没人是傻子，都是只想着给自己赚钱的自私鬼；

（3）每个参与者对所处环境以及其他参与者的行为形成正确信念与预期，这句话挺绕口，但其实很简单，就是说每个参与者的价值观是正确的，反社会反人类的事情他不干，他也知道其他人都这样想，大家都是正常人，没有疯子会来搅局。这三个假设我用自己的话进行了描述，虽然可能不太准确，但这样应该足够入门了。

在博弈论的三个假设中，最为麻烦的就是第一条了：每个人都理性。在下面这个例子中，你将进一步看到这个条件带来的反人类之处。

这个例子叫做污染博弈（Pollution game）。污染博弈和现在的环保主题还是很贴近的，同时它也可以看作多人版本的一个囚徒困境。污染博弈的背景是这样的：世界上有n个国家，每个国家必须选择放任环境污染不管和积极治理环境污染这两种策略之一进行执行，若有一个国家选择放任污染，则全球每个国家的成本都+1（成本指治理污染花的钱或者处理因为环境污染带来的问题等花的钱）；若某个国家选择积极治理环境，则其他国家的成本不变，但它自己国家的成本需要+3。

问题看上去很简单，一个显而易见的方法是大家一起治理，这样每个国家的成本都是3，这不挺好的么！但是，越是感觉简单越要想一想第一条假设：在这种解法中大家真的都是理性的吗？其中有没有人可以选择其他方案来损人利己呢？OK，这样想了以后发现事情不是那么单纯了，如果就一个国家选择不管，那其他国家的成本都是4，它自己的成本只有1.，这样好像对它自己挺好的。又完了，所有国家都这样想，大家都选择撂挑子，结果居然是最差的情况，每个国家的成本都是n。

篇幅所限，本文就讲到这里，后续内容会慢慢进行更新。博弈论在网络路由和拍卖定价等方面有着重要的作用，同时也与多个前沿研究方向有所交集，值得大家看一看，触类旁通。