2018年奈望林纳奖得主：一个揭示真理的计算机科学诗人

来源：Quanta Magazine

编译：Bot

编者按：近日，四年一度的国际数学家大会（ICM）在巴西召开，在这个被誉为数学“奥林匹克大赛”的盛会上，除了颁发给数学家的“菲尔兹奖”“高斯奖”和“陈省身奖”三个重磅奖项，还有理论计算机科学的最高荣誉之一——“奈望林纳奖”。而今年，斩获这个重量级奖项的人是MIT教授Constantinos Daskalakis。

在Constantinos Daskalakis的主页底部，有这样一首21行诗：Constantine Cavafy写的“The Satrapy”。

这首诗写于1910年，讲述的是一个“为伟大事业而生”的无名氏，但他的努力和成功总被人用天赋否定，心胸狭隘之人、冷漠无情之人也让他被迫放弃自己的梦想，去了波斯国王亚达薛西的宫廷。国王把他任命为总督，让他坐拥金钱、地位和荣誉，但他的灵魂却依然痛苦不已。亚达薛西没法给他真正想要的东西，最后无名氏发出喟叹：如果没有这些，你会过着什么样的生活……

对于Daskalakis来说，这首诗几乎是护身符一样的存在，它就像是个道德指南针，时刻提醒他“如果你有一个高尚的想法，那么无论作出任何决定，你都不该把它忘记”。

在这个指南针的指引下，现年37岁的Daskalakis在职业生涯中做出过不少决定，比如在大学毕业后放弃高薪工作，在自己研究的领域一直追求最困难的问题——为了揭露遥远的真相。“这一切都源于对深刻理解某物的渴望，”他表示，“除非真正搞懂，你就停不下来；除非真正理解，你的大脑就会持续思考。”

如今，Daskalakis凭借自己在博弈论、纳什均衡和机器学习领域的贡献获得“奈望林纳奖”，这是理论计算机科学的最高荣誉之一，而学界对此的评价是“实至名归”。拿康奈尔大学的计算机科学家ÉvaTardos的话来说：“我真的无法想象世间还存在这么一个人，能在那么多领域都影响重大。”

拒绝“总督的辖地”

Daskalakis的研究一直围绕数学和人类行为，这不是偶然，他是两位雅典高中教师的儿子——父亲教数学，母亲教希腊文学和历史——他的童年不仅沉浸在科学中，也沉浸在古希腊哲学家、剧作家的以人类为中心的思想中。

对于出生在雅典的人，他们从不说自己来自雅典，而是以祖父/祖母的籍贯为原籍，除非他们的家族已经在那儿生活了好几代。因此说起家乡，牵绊在Daskalakis心头的是克里特岛：“克里特人一直是‘麻烦制造者’，以前的奥斯曼帝国，后来的纳粹，他们都曾积极反抗。”

而无论是面对欺负弟弟的街头恶霸，还是事物的未知真理，Daskalakis都显示出了这种韧性。

在家里，Daskalakis两兄弟的最大乐趣就是深入研究父亲的课程教案，制作漫画书，或是试图推导开普勒行星运动定律，他虽然性能温和，但对了解周围世界却有着强烈渴望。

八年级时，Daskalakis的父亲带回了一台早期的Amstrad电脑，面对这个新“玩具”，他几乎每晚都熬夜，希望弄清楚它的工作原理。那时，年少的Daskalakis曾对父母说：“我知道我应该去睡觉了，但这非常重要！”

看着求知若渴的儿子，他的父母点下了头。

进入雅典国家技术大学后，Daskalakis选择的专业是电子和计算机工程。在本科同学对比下，他很快就发现自己是个“异常值”。整个大学期间，除了一门课，他在所有课程中都得了满分，这是大学建校200多年来都没人实现过的壮举。以至于这么多年过去了，学校老师都还记得他的名字。

大学毕业那年刚好是2004年，那时希腊正值经济蓬勃发展：前几年刚加入欧元区，当年又举办了奥运会。找到高薪工作对Daskalakis来说简直轻而易举，但他从没这么考虑过。“我一直在寻找充满创造性的机会。”他说。

“牵手”纳什均衡

一个机缘巧合，Daskalakis听了理论计算机科学家Christos Papadimitriou的一次演讲，这给他留下了非常深刻的印象。除了其他内容，演讲中重点提及的还有纳什均衡，这是博弈论和经济学的核心概念之一。只不过那时，Daskalakis并不知道这会是自己的博士生研究课题。

纳什均衡是数学家John Nash提出的概念，它表示在策略博弈中，玩家可以选择的最稳（有时也是最明智）行为。如果参与博弈的每个人都选择了最稳的行为，同时没人能通过选其他行为扩大自己的优势，那么他们就处于纳什均衡状态。1950年，Nash证明每场博弈都存在纳什均衡。

2013年，Daskalakis和John Nash的合影

这个发现让微观经济学家激动万分，因为它对构建市场机制十分有用。但就是这个在经济学中非常重要的纳什定理，John Nash却只能证明它存在，没法真正确定均衡的位置。在复杂博弈中，找到纳什均衡可能需要大量计算——但是如果这种计算方法不能被用于所有博弈类型，那研究人员花那么多精力、物力找到它还有意义吗？

在纳什证明提出后的几十年里，无数研究人员都曾尝试着找出一种能计算所有博弈纳什均衡的有效算法，但他们无一成功。而就在Daskalakis听的那场讲座里，主讲人Papadimitriou的想法是世上还没有出现有效的算法。

听完讲座，Daskalakis当机立断向加州大学伯克利分校投递了申请，选择的导师就是Papadimitriou。

之后发生的事是戏剧性的。二十多年来，Papadimitriou一直在研究纳什均衡问题，但他其实对解决问题早已失去了希望。为了找到接班人，他曾劝说几个最有才华的学生接触这方面的内容，但一切都无济于事。入学伯克利后，Daskalakis热切地从导师手中接过任务：“我一直在寻找具有挑战性的的东西。”

史无前例的进展

Daskalakis搬到伯克利时是2004年的秋天，虽然美国和希腊相距甚远，但两地都是地中海气候，这对一个渴望做出突破的青年来说是幸运的，他可以顺利完成生理上的过渡。

但伯克利附近疯涨的房价还是带来了一些困扰，Daskalakis和他的老朋友Dimakis搬进了一间一居室的公寓，这是他们负担得起的极限。通过使用一种“公平”的划分算法，最后Daskalakis赢得了卧室，但由于他经常在客厅忘我研究，他的朋友总是被迫搬进卧室休息。

Daskalakis因在博弈论、机器学习上的贡献获奖无数

只是经过短短几周，Daskalakis就在纳什均衡中嗅到了一个关键点，当晚他很开心地邀请朋友去酒吧庆祝。然而，第二天早上，他突然醒悟到之前的想法有问题，于是更加努力的工作，最终这个错误演变成了一个重大进展，因为他开始意识到如果要证明自己的定理是正确的，他就必须要使用一个具有纳什循环结构的证明架构。

目睹了学生的进展后，导师Papadimitriou也感受到了前所未有的动力：“放在以前，我还觉得这不可能，但现在我觉得我们在撞一堵‘新墙’，而不是‘旧墙’。”

经过合作研究，到第二年夏天，也就是Daskalakis进入伯克利研究生院满一年，他们已经解决4人及以上多人博弈的纳什均衡计算。他们的工作表明，“在非常合理的复杂性假设下，如果要计算纳什均衡，你会需要巨大的计算量”。

之后他们又把目标转向三人博弈，Daskalakis凭借自己的刻苦和热情同样解决了这个问题，但事实证明，这个过程是场鏖战。在研究三人博弈纳什均衡的过程中，Daskalakis有过多次放弃的想法，但他总是不轻言放弃，这股子韧性最终为他赢得了命运女神的眷顾，研究到忘我时，他总会在一些极限时刻突然获得灵感，比如睡醒时分、开机发呆时、洗澡时、生病时……

他用铅笔和纸记录下了一步步计算过程……

希腊的“摇滚明星”

凭借提出纳什均衡解决方案，Daskalakis在理论计算机科学界立即声名鹊起。2008年，当他被授予ACM最佳博士论文奖时，他的成就迅速渗透进希腊民间，国家总统邀请他前去访问，关于他的纪录片一遍又一遍在希腊电视上播出。一次，他前往波士顿的一家希腊餐厅用餐，当时正在餐厅内演出的音乐家不禁失声：“天呐，那就是Costis Daskalakis！”

诚然，Daskalakis的成名离不开希腊经济的低迷，当时债务危机给希腊带去了近乎毁灭性的影响，整个社会都笼罩在腐败的阴云里。这时，身为希腊人的Daskalakis取得了中大成就，这无疑给国民打了一剂强心针：“希腊不仅是个即将崩溃的腐朽建筑，它也培养了这样一个健康而才华横溢的年轻人。”

在研究生阶段取得胜利后，Daskalakis还是坚持沉下心研究，很快，他被聘为麻省理工学院的教授，开始为自己的学生出谋划策。而近期，他的研究方向是使用高维统计来研究机器学习的理论基础，他尤其关注生成对抗网络（GAN），希望能把这个源于博弈的神经网络用于解决博弈问题。

科研竞争很激烈，但Daskalakis会坚守本心，他认为：“研究最终会归结为对某个东西感兴趣，如果真的感兴趣，就不会觉得思考是负担。”那首21行诗——“The Satrapy”总是在那里提醒他：你为什么要追求这个目标？你一定不能忘记自己始于何处，也不能忘记为何能到此处。

The Satrapy

What a misfortune, although you are made

for fine and great works

this unjust fate of yours always

denies you encouragement and success;

that base customs should block you;

and pettiness and indifference.

And how terrible the day when you yield

(the day when you give up and yield),

and you leave on foot for Susa,

and you go to the monarch Artaxerxes

who favorably places you in his court,

and offers you satrapies and the like.

And you accept them with despair

these things that you do not want.

Your soul seeks other things, weeps for other things;

the praise of the public and the Sophists,

the hard-won and inestimable Well Done;

the Agora, the Theater, and the Laurels.

How can Artaxerxes give you these,

where will you find these in a satrapy;

and what life can you live without these.

Constantine P. Cavafy (1910).

原文地址：www.quantamagazine.org/computer-scientist-constantinos-daskalakis-wins-nevanlinna-prize-20180801/