Daskalakis憑借自己在博弈論、納什均衡和機器學習領域的貢獻獲得“奈望林納獎”

編者按：近日，四年一度的國際數學家大會（ICM）在巴西召開，在這個被譽為數學“奧林匹克大賽”的盛會上，除了頒發(fā)給數學家的“菲爾茲獎”“高斯獎”和“陳省身獎”三個重磅獎項，還有理論計算機科學的最高榮譽之一——“奈望林納獎”。而今年，斬獲這個重量級獎項的人是MIT教授Constantinos Daskalakis。

在Constantinos Daskalakis的主頁底部，有這樣一首21行詩：Constantine Cavafy寫的“The Satrapy”。

這首詩寫于1910年，講述的是一個“為偉大事業(yè)而生”的無名氏，但他的努力和成功總被人用天賦否定，心胸狹隘之人、冷漠無情之人也讓他被迫放棄自己的夢想，去了波斯國王亞達薛西的宮廷。國王把他任命為總督，讓他坐擁金錢、地位和榮譽，但他的靈魂卻依然痛苦不已。亞達薛西沒法給他真正想要的東西，最后無名氏發(fā)出喟嘆：如果沒有這些，你會過著什么樣的生活……

對于Daskalakis來說，這首詩幾乎是護身符一樣的存在，它就像是個道德指南針，時刻提醒他“如果你有一個高尚的想法，那么無論作出任何決定，你都不該把它忘記”。

在這個指南針的指引下，現年37歲的Daskalakis在職業(yè)生涯中做出過不少決定，比如在大學畢業(yè)后放棄高薪工作，在自己研究的領域一直追求最困難的問題——為了揭露遙遠的真相?！斑@一切都源于對深刻理解某物的渴望，”他表示，“除非真正搞懂，你就停不下來；除非真正理解，你的大腦就會持續(xù)思考?！?/p>

如今，Daskalakis憑借自己在博弈論、納什均衡和機器學習領域的貢獻獲得“奈望林納獎”，這是理論計算機科學的最高榮譽之一，而學界對此的評價是“實至名歸”。拿康奈爾大學的計算機科學家évaTardos的話來說：“我真的無法想象世間還存在這么一個人，能在那么多領域都影響重大?！?/p>

拒絕“總督的轄地”

Daskalakis的研究一直圍繞數學和人類行為，這不是偶然，他是兩位雅典高中教師的兒子——父親教數學，母親教希臘文學和歷史——他的童年不僅沉浸在科學中，也沉浸在古希臘哲學家、劇作家的以人類為中心的思想中。

對于出生在雅典的人，他們從不說自己來自雅典，而是以祖父/祖母的籍貫為原籍，除非他們的家族已經在城里生活了好幾代。因此說起家鄉(xiāng)，牽絆在Daskalakis心頭的是克里特島：“克里特人一直是‘麻煩制造者’，以前的奧斯曼帝國，后來的納粹，他們都曾積極反抗。”

而無論是面對欺負弟弟的街頭惡霸，還是事物的未知真理，Daskalakis都顯示出了這種韌性。

在家里，Daskalakis兩兄弟的最大樂趣就是深入研究父親的課程教案，制作漫畫書，或是試圖推導開普勒行星運動定律，他雖然性能溫和，但對了解周圍世界卻有著強烈渴望。

八年級時，Daskalakis的父親帶回了一臺早期的Amstrad電腦，面對這個新“玩具”，他幾乎每晚都熬夜，希望弄清楚它的工作原理。那時，年少的Daskalakis曾對父母說：“我知道我應該去睡覺了，但這非常重要！”

看著求知若渴的兒子，他的父母點下了頭。

進入雅典國家技術大學后，Daskalakis選擇的專業(yè)是電子和計算機工程。在本科同學對比下，他很快就發(fā)現自己是個“異常值”。整個大學期間，除了一門課，他在所有課程中都得了滿分，這是大學建校200多年來都沒人實現過的壯舉。以至于這么多年過去了，學校老師都還記得他的名字。

大學畢業(yè)那年剛好是2004年，那時希臘正值經濟蓬勃發(fā)展：前幾年剛加入歐元區(qū)，當年又舉辦了奧運會。找到高薪工作對Daskalakis來說簡直輕而易舉，但他從沒這么考慮過?！拔乙恢痹趯ふ页錆M創(chuàng)造性的機會?！彼f。

“牽手”納什均衡

一個機緣巧合，Daskalakis聽了理論計算機科學家Christos Papadimitriou的一次演講，這給他留下了非常深刻的印象。除了其他內容，演講中重點提及的還有納什均衡，這是博弈論和經濟學的核心概念之一。只不過那時，Daskalakis并不知道這會是自己的博士生研究課題。

納什均衡是數學家John Nash提出的概念，它表示在策略博弈中，玩家可以選擇的最穩(wěn)（有時也是最明智）行為。如果參與博弈的每個人都選擇了最穩(wěn)的行為，同時沒人能通過選其他行為擴大自己的優(yōu)勢，那么他們就處于納什均衡狀態(tài)。1950年，Nash證明每場博弈都存在納什均衡。

2013年，Daskalakis和John Nash的合影

這個發(fā)現讓微觀經濟學家激動萬分，因為它對構建市場機制十分有用。但就是這個在經濟學中非常重要的納什定理，John Nash卻只能證明它存在，沒法真正確定均衡的位置。在復雜博弈中，找到納什均衡可能需要大量計算——但是如果這種計算方法不能被用于所有博弈類型，那研究人員花那么多精力、物力找到它還有意義嗎？

在納什證明提出后的幾十年里，無數研究人員都曾嘗試著找出一種能計算所有博弈納什均衡的有效算法，但他們無一成功。而就在Daskalakis聽的那場講座里，主講人Papadimitriou的想法是世上還沒有出現有效的算法。

聽完講座，Daskalakis當機立斷向加州大學伯克利分校投遞了申請，選擇的導師就是Papadimitriou。

之后發(fā)生的事是戲劇性的。二十多年來，Papadimitriou一直在研究納什均衡問題，但他其實對解決問題早已失去了希望。為了找到接班人，他曾勸說幾個最有才華的學生接觸這方面的內容，但一切都無濟于事。入學伯克利后，Daskalakis熱切地從導師手中接過任務：“我一直在尋找具有挑戰(zhàn)性的的東西。”

史無前例的進展

Daskalakis搬到伯克利時是2004年的秋天，雖然美國和希臘相距甚遠，但兩地都是地中海氣候，這對一個渴望做出突破的青年來說是幸運的，他可以順利完成生理上的過渡。

但伯克利附近瘋漲的房價還是帶來了一些困擾，Daskalakis和他的老朋友Dimakis搬進了一間一居室的公寓，這是他們負擔得起的極限。通過使用一種“公平”的劃分算法，最后Daskalakis贏得了臥室，但由于他經常在客廳忘我研究，他的朋友總是被迫搬進臥室休息。

Daskalakis因在博弈論、機器學習上的貢獻獲獎無數

只是經過短短幾周，Daskalakis就在納什均衡中嗅到了一個關鍵點，當晚他很開心地邀請朋友去酒吧慶祝。然而，第二天早上，他突然醒悟到之前的想法有問題，于是更加努力的工作，最終這個錯誤演變成了一個重大進展，因為他開始意識到如果要證明自己的定理是正確的，他就必須要使用一個具有納什循環(huán)結構的證明架構。

目睹了學生的進展后，導師Papadimitriou也感受到了前所未有的動力：“放在以前，我還覺得這不可能，但現在我覺得我們在撞一堵‘新墻’，而不是‘舊墻’?！?/p>

經過合作研究，到第二年夏天，也就是Daskalakis進入伯克利研究生院滿一年，他們已經解決4人及以上多人博弈的納什均衡計算。他們的工作表明，“在非常合理的復雜性假設下，如果要計算納什均衡，你會需要巨大的計算量”。

之后他們又把目標轉向三人博弈，Daskalakis憑借自己的刻苦和熱情同樣解決了這個問題，但事實證明，這個過程是場鏖戰(zhàn)。在研究三人博弈納什均衡的過程中，Daskalakis有過多次放棄的想法，但他總是不輕言放棄，這股子韌性最終為他贏得了命運女神的眷顧，研究到忘我時，他總會在一些極限時刻突然獲得靈感，比如睡醒時分、開機發(fā)呆時、洗澡時、生病時……

他用鉛筆和紙記錄下了一步步計算過程……

希臘的“搖滾明星”

憑借提出納什均衡解決方案，Daskalakis在理論計算機科學界立即聲名鵲起。2008年，當他被授予ACM最佳博士論文獎時，他的成就迅速滲透進希臘民間，國家總統(tǒng)邀請他前去訪問，關于他的紀錄片一遍又一遍在希臘電視上播出。一次，他前往波士頓的一家希臘餐廳用餐，當時正在餐廳內演出的音樂家不禁失聲：“天吶，那就是Costis Daskalakis！”

誠然，Daskalakis的成名離不開希臘經濟的低迷，當時債務危機給希臘帶去了近乎毀滅性的影響，整個社會都籠罩在腐敗的陰云里。這時，身為希臘人的Daskalakis取得了重大成就，這無疑給國民打了一劑強心針：“希臘雖然是個即將崩潰的腐朽建筑，它也培養(yǎng)了這樣一個健康而才華橫溢的年輕人?！?/p>

在研究生階段取得勝利后，Daskalakis還是堅持沉下心研究，很快，他被聘為麻省理工學院的教授，開始為自己的學生出謀劃策。而近期，他的研究方向是使用高維統(tǒng)計來研究機器學習的理論基礎，他尤其關注生成對抗網絡（GAN），希望能把這個源于博弈的神經網絡用于解決博弈問題。

科研競爭很激烈，但Daskalakis會堅守本心，他認為：“研究最終會歸結為對某個東西感興趣，如果真的感興趣，就不會覺得思考是負擔?！蹦鞘?1行詩——“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).