上周的文章里我们说到纳什从数学上证明了博弈必然存在均衡点，但并没有指出如何去找出均衡点。在纳什证明提出后的几十年里，无数研究人员都曾尝试找出一种能计算所有博弈纳什均衡的有效算法，但却一直没能获得成功。
（▲ 扎斯卡拉基斯（中）与帕帕季米特里乌（右），摄于2013年）
目前在麻省理工学院电子工程与计算机科学系任教的康斯坦丁·扎斯卡拉基斯（Constantinos Daskalakis）教授十多年前在加州大学伯克利分校读博士时与他的导师赫里斯托斯·帕帕季米特里乌（Christos Papadimitriou）在此问题上做出突破。他们从数学上证明了，对于博弈论问题的大多数情形，纳什均衡是很难有效计算的，以至于全世界所有计算机加在一起也无法在宇宙寿命之内找到均衡点。这意味着博弈论领域还需要纳什均衡以外的分析工具去描述现实世界。从另一个角度来说，一些难以有效计算的博弈论问题也可以从近似的角度去探索，能有效获得的近似解同样可以为我们理解现实世界带来启示。
（▲ 扎斯卡拉基斯与纳什的合影，摄于2013年）
扎斯卡拉基斯因其在博弈论问题计算方面的突出贡献在2018年国际数学家大会上获得了“奈望林纳奖”。国际数学家大会每四年举行一次，会上会颁发数学领域最高奖“菲尔兹奖”等几个重要奖项，菲尔兹奖授予40岁以下在纯数学领域做出卓越贡献的数学家，奈望林纳奖则是授予40岁以下在计算与信息科学相关的数学领域做出卓越贡献的科学家。纳什曾因在纯数学领域的非线性偏微分方程上的杰出成就（与博弈论并无关系）几乎获得了1958年的菲尔兹奖，但由于部分研究结果没有及时发表而未能如愿，这一打击在当时也进一步加重了他的病情。2015年，数学界的另一项大奖“阿贝尔奖”授予给纳什在偏微分方程方面所作出的卓越贡献，与1994年的诺贝尔经济学奖一样这对纳什来说是一份迟到的荣誉。在获得阿贝尔奖2个月后，纳什与夫人在一次乘出租车返家途中不幸遇车祸丧生，享年87岁。
除了研究博弈计算复杂性问题，算法博弈论的另一重要研究方向在于通过算法和策略设计博弈，比如车牌拍卖，各地根据不同的需求设计不同的规则，需求可能是控制数量、减少污染，或者保持公平性。博弈的规则会影响参与者的行为。
比如有些体育比赛因为规则设计的不合理会使得输掉某场球更有利于自己最后获得更好成绩。一个典型的案例是2012年伦敦奥运会的女双比赛。由于D组的中国组合田卿/赵芸蕾（那届奥运后来的女双冠军）在小组赛中意外输给了一对丹麦组合，只能以小组第二名出线。A组的中国组合于洋/王晓理（当时女双世界排名第一的头号种子）在小组赛最后一场与韩国组合郑景银/金荷娜的比赛前已经提前小组出线，如果这最后一场小组赛她们获胜的话会和田卿/赵芸蕾在淘汰赛阶段分在同一个半区，将在半决赛提前相遇。而也已经小组出线的韩国组合郑景银/金荷娜如果这最后一场小组赛获胜的话，她们下一轮淘汰赛将面对另一对韩国组合，而进入半决赛的话将会遇到强劲的中国组合田卿/赵芸蕾。所以那场比赛中中韩两对组合都是一心求败。从博弈论的角度来看，这场比赛“输球”是为最终取得最佳成绩的“优势策略”，也并没有违反规则。最后国际羽联以消极比赛为由取消中韩两对组合之后的后续比赛资格，同时还取消了另一场消极比赛的韩国和印尼两对组合的比赛资格。这一问题出现的实际原因是，制定游戏规则的人把规则制定好后，发现参与者并不符合自己设想的进程，对参与者进行处罚其实是转移了规则设计不合理的自身原因，“求输”只是在这一规则下导致的“纳什均衡”。每届足球世界杯小组赛最后一轮也经常会出现消极比赛，其实也是比赛规则导致的“纳什均衡”。规则的设计决定了博弈行为，所以设计一个合理的规则至关重要。
采购机制设计、拍卖、区块链及分布式商业等各种规则的设计都离不开算法博弈论。像比特币系统，需要从规则上就能防止“挖矿攻击”“贿赂攻击”等行为，这些都要从博弈论的角度去考虑。算法博弈论还有一个关注点是在拍卖理论，麻省理工学院电子工程与计算机科学系的两位世界计算机领域最高奖“图灵奖”得主西尔维奥·米卡利（Silvio Micali）和沙菲·戈德瓦塞尔（Shafi Goldwasser）正在利用他们赖以成名的交互式“零知识证明”的思路来设计新的拍卖机制与模型。零知识证明也可以用于确保金融机构之间交易的安全性。米卡利还设计创立了一个完全去中心化、安全性高、可扩展性高的全新区块链平台Algorand，今年6月19日已正式全球上线。
（▲左图为图灵奖得主米卡利和戈德瓦塞尔，右图为图灵奖得主姚期智院士）
“图灵奖”得主中唯一的华人获奖者姚期智院士也正在对拍卖和区块链进行研究。姚期智院士曾在美国麻省理工学院、斯坦福大学、加州大学伯克利分校和普林斯顿大学任教，目前是清华大学交叉信息研究院院长。
麻省理工学院电子工程与计算机科学系主任阿苏曼·厄兹达拉尔（Asuman Ozdaglar）则是网络博弈研究的领军人物，网络资源分配需要博弈论，激励网络合作的协议设计也需要博弈论，厄兹达拉尔还和她的丈夫、麻省理工学院著名经济学家达龙·阿西莫格鲁（Daron Acemoglu）一起合作从博弈论的角度分析信息如何在社交网络中传播。两人还为经济系和电子工程与计算机科学系的学生开了一门名为“网络”的联合课程，其中博弈论占了课程的很大一部分。
（▲ 厄兹达拉尔和阿西莫格鲁夫妇）
谷歌、Facebook这样的IT巨头，在大数据时代的驱动下拥有很多信息，但如何战略性地利用这些信息实现收益最大化，就涉及到公司与同行之间以及与客户（例如广告商）之间的博弈。比如，谷歌对每一个互联网用户的描述有上千个特征，向广告商提供其中的哪些特征能使收益最大化？这里可供选择的特征组合超过 21000 种，比人体的细胞还要多很多，我们需要设计算法从如此多的选择中找出最优的那一个。
经济学家长久以来一直在用博弈论理解世界，计算机科学家也正在用博弈论开展多方面的研究。博弈论其实是我们研究世界的一种工具。博弈论已经出现在很多学科的课程中，世界名校的经济系、计算机系、电子工程系、数学系、生物学系，还有心理学系、政治科学系和社会科学系的课程中都含有博弈论的内容。
【相关链接】
你了解多少博弈论？从社会经济到人工智能，博弈论无处不在！（上）
你了解多少博弈论？从社会经济到人工智能，博弈论无处不在！（中）
世界图书出版公司推出的“世界博弈论经典”分为“经济与社会科学系列”和“计算与信息科学系列”两个子系列，这些经典名著的作者中有诺贝尔经济学奖得主让·梯若尔（Jean Tirole）和罗杰·迈尔森（Roger Myerson），以及呼声很高的诺贝尔奖候选人、“博弈论四君子”中的阿里尔·鲁宾斯坦（Ariel Rubinstein）和肯·宾默尔（Ken Binmore）等。
几十本经典名著即将来袭，敬请期待！
其中的第一本，诺贝尔经济学奖得主让·梯若尔（Jean Tirole）和美国科学院院士朱·弗登伯格（Drew Fudenberg）合著的《博弈论》，已在世图淘宝官方旗舰店首发销售。
（▲感兴趣的读者欢迎打开淘宝app扫一扫上面的二维码购书~~）
公号ID：wpcbj1986世 图 好 书把世界介绍给中国
把中国介绍给世界
科技|人文|心理|外语|动漫