2018奈望林纳奖得主:本科满分,读研解决纳什遗留难题

　　来源：科研圈

　　现年 37 岁的理论计算机科学家康斯坦丁诺斯。达斯卡拉基斯（Constantinos Daskalakis），由于对博弈论和机器学习的核心问题的研究贡献，获得了 2018 年奈望林纳奖（Rolf Nevanlinna Prize）。这位来自希腊的计算机科学家既是一位大学期间课程几乎全部满分的天才，也是一个拥有独特精神世界的“诗人”。

　　进入康斯坦丁诺斯?达斯卡拉基斯（Constantinos Daskalakis）的官方个人首页，你能看到的不仅是他的理论计算机科学研究论文，和他在麻省理工学院（MIT）指导的博士生名单。在页面的最底下，你还会看到希腊著名诗人康斯坦丁?卡瓦菲斯（Constantine Cavafy）的 21 行诗 《致总督》（<em>The Satrapy</em>）。



　　这首诗写于 1910 年，献给一位无名氏，此人生来本可有一番大作为，但是受到心胸狭窄之人的排挤，最终放弃了自己的梦想，转而效忠波斯王亚达薛西（Artaxerxes）。国王慷慨授予他行省总督（Satrapy）的头衔，但是他的灵魂 “却另有所属，暗自啜泣，为的是那些得之不易的无价成就：市民集会、古典剧院和桂冠诗人。”这一切都是波斯王亚达薛西无法给与的。因此，卡瓦菲斯发出喟叹：“你能在总督生涯中找到这些吗？没有这一切，你的生活又会如何？”

　　对达斯卡拉基斯而言，这首诗犹如护身符一般，守护他抵挡住来自人性最深处的欲望和诱惑。“这是我的道德指南针，”他说道，“我希望能够时常提醒自己，我内心抱有崇高的理想，当我做出决定的时候，不要忘记我的初心。”

　　37 岁的达斯卡拉基斯在其职业生涯中做出的各种决定，比如大学毕业后放弃一份报酬丰厚的工作、不断追求专业领域内最艰深的问题等等，都是为了最终发现遥远彼岸的真理。他自己也说：“这一切都源自我内心最深处想要了解真理的需求。它带给了我片刻不息的力量。”

　　如今，达斯卡拉基斯的贡献终于得到了认可。本月初，他获得了每四年颁发一次、代表理论计算机科学领域内最高荣誉的奈望林纳奖（Rolf Nevanlinna Prize）。获奖理由强调了他的“最强成就”：他成功解释了经济学的核心问题，即理性主体（可以是个人、商业机构、政府部门等）在博弈和市场中的行为，以及他在机器学习领域的最新研究。

　　他曾经的博士生、如今是普林斯顿大学教授的马修?温伯格（Matthew Weinberg）评价道：达斯卡拉基斯只对“最具影响力”的问题感兴趣。他的态度永远是：“这些所有未解决的问题都难疯了，然而一旦解决，必会影响深远，所以一定要有人去做这事，这些人就是我们。”

　　达斯卡拉基斯的研究跨越了数学领域和人类行为研究领域，这并非偶然。他出生于雅典，父母都是高中教师：父亲教授数学，母亲则是希腊文学和历史老师，他的童年不仅有科学，还有古希腊哲学家和剧作家笔下“以人为本”的深邃思想。

　　“我的身上有一种重要的文化传承，它们启发着我，又让我保持谦卑，这既是巨大的责任，也是一项挑战。”他讲道。


　　达斯卡拉基斯正在学习弹一种古老的古希腊乐器――巴格拉玛琴（baglamas）。图片来源：Cassandra Klos

　　拒绝成为“总督”

　　达斯卡拉基斯犹如希腊挺拔的山峰：1 米 85 的身高顶着一头冲天黑发，黝黑的双眼流露出温和的目光。他自己和他的弟弟尼古拉奥斯（Nikolaos）都认为他是个“冷静”的人。

　　在家里的时候，俩兄弟总是会不停地找各种事儿干：钻研他们父亲的数学课本，自己搞漫画创作，或者试图推算出开普勒的行星运行法则。在达斯卡拉基斯身上，温柔的性格与了解周围世界的强烈愿望并存。在他上八年级的时候，他的父亲带回家一台初代的 Amstrad 电脑，达斯卡拉基斯一整晚都没睡，就是为了搞清电脑的工作原理。“我跟我父母讲，我知道我该上床睡觉了，但是这事确实非常重要，所以他们才允许我熬夜。”他回忆道。

　　达斯卡拉基斯高中毕业后进入雅典国立科技大学（National Technical University of Athens），在电子和计算机工程专业学习，大家很快就明白他就是个“天才”。除了一门课程之外，他大学四年的成绩单上全是满分，这在该大学建校 200 多年的历史中还是第一次。达斯卡拉基斯的本科和研究生院同学、目前在德克萨斯大学任职的亚历山德罗斯?迪玛基斯（Alexandros Dimakis）说：“你要是去问大学里的每个老师，他们肯定都记得这个人，哪怕是 20 年后的今天。”

　　大学毕业以后，达斯卡拉基斯本可以轻而易举地找到一份薪酬优渥的工作。当时（2004 年）希腊的经济借着奥运会的东风蓬勃发展，但是他从没考虑过这条路，“我当时一直在寻找机会，做一些有创意的事情。”他说道。

　　他觉得自己的本科研究内容平平无奇，2003 年夏天由欧纳西斯基金会（Onassis Foundation）组织的一个项目给了他机会亲眼目睹一种非常不同的学习方法。该项目围绕计算机科学和经济学之间的关系展开研究，而基金会也成功吸引到一些业界“大牛”来办讲座。

　　其中一个讲座由理论计算机科学家赫里斯托斯?帕帕季米特里乌（Christos Papadimitriou）主持，这令他印象尤为深刻。在讲座上，他们主要讨论了计算纳什均衡（Nash equilibrium）的问题，这是博弈理论和经济学理论的核心概念之一。

　　“我当时真没想到这会成为我的博士论文。”达斯卡拉基斯回忆道。


达斯卡拉基斯与纳什，摄于2013年，图片来源：Vasilis Syrgkanis

　　一切起源于数学家乔治?纳什（John Nash），他的纳什均衡（Nash equilibrium）理论是现代经济学的基石之一。纳什均衡体现出了在策略性博弈中参与者能够表现出的最稳定（有时候是最敏感）的行为策略。如果玩家每人都选择一种策略，而且考虑到其他玩家的选择，他们都不会选择改用其他策略来扩大自己的优势，那么他们所有人都处于纳什平衡状态。1950 年纳什证明了每一个博弈都存在纳什均衡点。

　　然而，尽管纳什能证明均衡点始终存在，但是他的证明却无法找出均衡点的位置。对复杂博弈而言，找到纳什均衡点可能是一项巨大的计算挑战，如果纳什均衡无法用来计算所有的实际目的，那么让所有参与者找到并使用这种策略的意义又何在呢？

　　在纳什给出证明后的数十年里，研究人员费尽心力，但是始终没有找到一种有效的算法。帕帕季米特里乌钻研计算纳什均衡点将近二十年，但还是无法证明。“老实说，在内心深处，我觉得是无法解决了。”

　　“许多人将其视作算法博弈理论中最大的开放性问题。”斯坦福大学的计算机科学家蒂姆?洛夫贾登（Tim Roughgarden）评价道。

　　着迷于帕帕季米特里乌的讲座，达斯卡拉基斯最终决定申请这位教授所在的加利福尼亚大学的研究生。就在他将自己的申请邮件发送出去几小时之后，他就在雅典的街头意外碰到了他未来的导师。“这太不可思议了，究竟算是怎样的缘分呢！”

　　“我们仅仅是相互点头问候，但当时我就觉得就那是‘命中注定的一刻’，”帕帕季米特里乌回忆道，“我们望着对方，我想我们都清楚他肯定会被录取，还会是我的学生。”

　　“我是不相信什么预兆的，但那次偶遇确实是我人生中的重要一刻。”达斯卡拉基斯说到。


　　达斯卡拉基斯因研究博弈论、拍卖理论（auction theory）和机器学习而赢得了无数奖杯。图片来源：Cassandra Klos

　　不可估价的成就

　　2004 年秋天，达斯卡拉基斯搬入了伯克利校园。同样拥有橄榄树和地中海气候的旧金山湾区让他从希腊到美国城市生活的转变顺畅自然，随之而来的还有他梦寐以求的头脑风暴。“感觉到自己未来的可能生活，我欢欣雀跃、兴奋不已。”达斯卡拉基斯提到。

　　达斯卡拉基斯和他的旧友迪玛基斯搬入了一套一居室的公寓中，伯克利校区房价高昂，这也是他们俩所能负担得起的最经济的公寓了。他们使用一种公平的算法来决定谁住卧室，谁住客厅，各自分摊多少房租。达斯卡拉基斯虽然赢得了卧室，但是他常常睡客厅，因为他会整夜整夜的和迪玛基斯讨论问题，而他当时的女友则在卧室睡觉。

　　迪玛基斯回忆道：“达斯卡拉基斯拥有不知疲倦的思考能力。”有一次，他们俩去太浩湖（Lake Tahoe）滑雪，结束后迪玛基斯累得动不了了，但是达斯卡拉基斯已经开始思考问题，很快他就亟不可待地想和迪玛基斯讨论，尽管时间已经是半夜。“哥们儿，我的身体已经被掏空了。”迪玛基斯当时这么跟对方抱怨。

　　帕帕季米特里乌已经花了很多年时间和他几个最优秀的学生研究纳什均衡问题，但是始终毫无头绪。然而，达斯卡拉基斯却迫不及待地想要搞定它。“我一直在寻找有难度的挑战。”

　　很快，帕帕季米特里乌觉得这个多年来毫无进展的问题终于有了前进的征兆，“尽管目前看来还是不可能解决，但是我有一种感觉，这次我们撞上的是新的障碍，跟过去完全不一样。”

　　仅仅花了几周的时间思考这个问题，达斯卡拉基斯的头脑中就出现了一个关键思路。某天晚上，他觉得他已经找到解决整件事的方法了。他兴高采烈地和朋友们去了旧金山的酒吧，“在我意识到会有问题之前，我就想享受一下这种幸福的感觉。”然而第二天早上，他醒来后发现不仅自己的证明是错误的，而且他一直试图证明的方法都不对。但是这个错误反而让他向前跨出了重要一步，因为达斯卡拉基斯同时还意识到何种证明架构真正有用：那是一种类似于纳什用来证明自己定理的循环结构。

　　时间又过了几个月，达斯卡拉基斯和帕帕季米特里乌将上面这个思路和另一项研究结合起来，最终给出了完整的证明。在达斯卡拉基斯进入研究生院的第一个夏天，师徒两人已经解决了涉及四个或者更多参与者的所有博弈问题。他们的研究发现“即使在非常合理的复杂性假设的条件下，你仍然需要超乎寻常的大量计算来算出纳什均衡点。”洛夫贾登评价道。

　　他们希望能够将结论扩展到三人博弈中，达斯卡拉基斯以他一贯的热情开始着手解决这个问题。但是事实证明这是一场苦战，终于有一天，在彻底意识到问题的难度之后，达斯卡拉基斯觉得自己已经准备要放弃了。他打开自己的电脑查看邮件，但是电脑崩溃了。在等待硬盘扫描的漫长时间里，他又开始思考三人博弈问题，就在一刹那他意识到自己找到了解决之道。事后回想起来，他发现在自己脑海某一隐秘之处早就已经出现了答案，“它就在我的脑子里，但我却一直没有注意到。”

　　达斯卡拉基斯的许多思路似乎都产生在这种阈限时刻（liminal moment）：早晨刚睡醒时，等待电脑重启时，甚至是在洗澡或生病发烧时。“我常常在倒时差的时候特别容易出新想法。”他补充道。

　　达斯卡拉基斯对纳什均衡的解决让他迅速在理论计算机科学的圈子里声名鹊起。2008 年他被授予国际计算机协会博士论文奖（Association for Computing Machinery‘s Doctoral Dissertation Award），也因此进入希腊的公众视野。在报道他得奖的一篇博文传播开之后，希腊总统还邀请他回国见面，关于他的纪录片也在希腊的电视上播了又播。

　　达斯卡拉基斯将自己在希腊的名望归因于他得奖时整个国家的状态。当时全球经济衰退给了希腊致命一击，希腊社会不得不与让整个国家陷入瘫痪的价值体系达成妥协。“我觉得他们在我获得成功之后，将我锁定为目标，来向世界宣扬，瞧瞧，希腊不只是一个即将崩塌的腐朽大厦。我们的希腊社会中还有这种非常健康、非常有天分的能量，他们能真正找到解决之路，拥有创造力，获得成功。”

　　再攀高峰

　　在研究生阶段取得成功之后，达斯卡拉基斯想着是否还有再次挑战这种高水平研究的机会。“你可能觉得，科学家一生只有一次巅峰，那纳什均衡就是我的巅峰吗？”达斯卡拉基斯扪心自问。但是他对追名逐利毫无兴趣。“还有很多有趣的问题等着我，有时候，你只需要不停地研究对你来说重要的问题就可以了。”

　　达斯卡拉基斯很快就成为了 MIT 的教授，开始指导自己的研究生。温伯格是他第一批学生之一，他回忆起走进达斯卡拉基斯的办公室，提议自己想要改善自己刚在一篇论文上读到的数值因素。“我记得他（达斯卡拉基斯）很有礼貌地回到：‘好的，这很好，但我觉得我们可以将眼光稍微放远点。’”

　　他那句话的意思是要去解决一个 30 多年来毫无实质性进展的问题。1981 年，芝加哥大学的经济学家罗杰?梅尔森（Roger Myerson）已经解决了如何设计单品拍卖从而让卖家利益最大化的问题，为此他还获得了诺贝尔经济学奖。

　　但是，许多交易涉及的是多件商品：比如餐馆菜单上的菜品选择，或者手机运营商的选择。比起单品问题，这里有更多潜在的拍卖结构，因为商品既可以分开单独销售，也可以以大量不同的可能形式捆绑销售。就理解其结构的难度而言，单件商品拍卖和多件商品拍卖之间存在巨大差距。洛夫贾登说“东西越多，情况越复杂。”十多年来，没有人能在更大范围内给出最佳的拍卖设计方案。

　　在2012年，达斯卡拉基斯与温伯格，还有另外一名学生蔡阳（音，Yang Cai），开发出一套算法，能够有效地找到最佳拍卖设计，而无需关注销售商品的数量。又过了几年，达斯卡拉基斯和另外两名研究生，阿兰?德凯尔鲍姆（Alan Deckelbaum）和克利斯托斯?查莫斯（Christos Tzamos），继续向前推进了他们的分析方法，以只有一位买家为前提（举例来讲，就是一个单独的买家在不同的手机供应商之间做选择）。在这种情况下，他们能够为任何销售机制找到最佳方案。

　　耶鲁大学的经济学家迪尔克?伯格曼（Dirk Bergemann）说：“许多经济学家一直在研究这个问题，达斯卡拉基斯的研究结果让他们大为震惊。”

　　最近，达斯卡拉基斯一直在使用高维统计来研究机器学习的理论基础。他尤其推崇一种名为生成对抗网络（generative adversarial networks）的机器学习方法，这种方法训练两个神经网络之间相互博弈来进行学习。然后，他“回到了原点”：和身为神经科学家的弟弟从头开展了一个研究项目。

　　随后，兄弟俩还开始使用数学模型来识别各种神经精神障碍症的致病基因。“我使用数学因为我想要解决问题，”弟弟尼古拉奥斯说，“他一直在思考数学能力的边界在哪里，这是非常理论化的概念。但是，如果我们发现了一个让我们俩同时感兴趣的问题，那它可能就非常重要了。”

　　如此激情四射的生活，达斯卡拉基斯不会拿去与任何东西做交易，就他本人所言：“生活就是要去做自己真正感兴趣的事情，而不是让人一想到就皱眉头的重担。”

　　个人主页上的《致总督》始终提醒着他最初开始追寻自己兴趣的崇高理由，“不要忘记你是从哪里开始的，也不要忘记是什么让你走到今天的。”