计算机科学遇上经济学

2016年2月4日，MIT网站发布题为《ComputerScience meets economics》的新闻（由Larry Hardesty撰写），介绍MIT计算机科学与工程系的扎斯卡拉基斯（Constantinos Daskalakis）将理论计算机科学中的方法技巧用于博弈论。

http://news.mit.edu/2016/faculty-profile-constantinos-daskalakis-0204

扎斯卡拉基斯的工作领域是计算机科学。他研究将计算机科学技术应用到《博弈论》学科——试图的定量处理人类战略推理。在《博弈论》中，人的互动模型是作为有明确定义的博弈中的一系列动作，每一个动作代表一个特定的策略的一个实例，并可能引起其他局中人的不同反应，导致不同的奖励。即使是一个只有极少局中人的简单的博弈，也可以导致大的曲折。

《博弈论》可以广泛应用于是经济、外交、军事、生物和体育等问题研究。麻省理工学院任教约翰·纳什（《美丽心灵》男主角原型）因为在1950年发表了有关博弈论的开创性的论文，最终于1994年赢得了诺贝尔经济学奖（注1）。纳什提出并证明了所谓纳什均衡的存在性（任何一个有限的博弈至少存在一个纳什均衡）。纳什均衡描述了一个平衡的策略，没有局中人有单方面改变的动机（在一个博弈中，如果存在一个策略组合，单个局中人独自离开这个策略组合，其收益不会增加，就称为纳什均衡）。扎斯卡拉基斯在2004-2008年间研究算法博弈论，其博士论文获得ACM论文奖。他证明了三人博弈的纳什均衡计算，具有难治性（computationallyintractable）——这意味着对于任何最简单的博弈，即使用所有世界上的计算机，在宇宙毁灭前不可能完成纳什均衡的计算。因此，扎斯卡拉基斯认为，现实的市场博弈论建模并不可能融入纳什平衡。当计算机科学家碰到了一个棘手的问题，他们的第一个方法是了解它的近似解。他的博士论文重点从计算机科学引进近似的概念到经济学。他发表了一系列纳什均衡近似计算的文章。

然而，在博弈论中，也有的问题已被证明容易从计算的角度进行分析。扎斯卡拉基斯和他的学生解决了经济学中的一个重要问题，推广了芝加哥大学的罗杰·梅耶森（Roger Myerson，2007年诺贝尔经济学奖获得者）的工作。梅尔森运用博弈论的工具，展示了如何为一个项目设计拍卖，如果所有的投标人的采用他们最有利的投标策略，拍卖行也能实现最大的利润。梅尔森的工作立即提出一个相关的问题：如何对多个项目进行结构的拍卖？在组织一次拍卖中，投标人竞争的多个项目的最佳方式是什么？这个问题已经有30年了，麻省理工学院的计算机科学家们现在已经回答了这个如何对多个项目进行结构拍卖的问题——即使所有的投标人采取最大限度地提高自己的回报的策略，拍卖行仍然可以提取最大利润。扎斯卡拉基斯和他的学生杨彩和马修温伯格在最近的论文中，描述了发现的多物品拍卖的最优设计几乎完美的近似算法。

此后，扎斯卡拉基斯研究课题包括计算遗传学、概率理论和机器学习，并致力于将其结果推广到拍卖设计上。扎斯卡拉基斯说，计算机科学美学是“给了一个问题，我要寻找解决这个问题实例的一个算法”；经济学的美学是“给了一个问题，我要了解这个问题不同的情况下的解决方案的结构。我希望能够对这些解决方案的结构做一个通用的陈述”。扎斯卡拉基斯说，“在经济学和计算的交接面工作，你必须平衡两者的美学。现在我们试着将经济学的美学引入到我们的工作中去。”扎斯卡拉基斯补充说，我们不得不开发新的工具，在数学领域称为最优输运理论，以最有效的方式在多个起点和目的地间移动对象或数据。

---------

注1：根据马洪宽著《博弈论》（同济大学出版社2015年7月）一书，自从1994年以来，诺贝尔经济学奖多次授予博弈论专家:

1994年诺贝尔经济学奖授予纳什、塞尔顿和海梅尼。

1996年授予莫里斯和维克瑞。

2001年授予阿克罗夫、斯宾塞和斯蒂尔格列茨。

2007年授予赫尔维茨、马斯金和梅耶森。

2012年授予夏普利。

2014年授予让·梯若尔。

这些学者对博弈论理论和应用的发展做出了巨大贡献。

编译 2016-2-5