○ Constantinos Daskalakis獲得了2018年的奈望林納獎（Rolf Nevanlinna Prize）。| 圖片來源：Cassandra Klos/Quanta Magazine
在計算機上解決一個問題需要多長時間？
這個看似無關痛癢的問題，總的來說是無法回答的。然而，它卻處於計算複雜性理論的核心。這個領域的研究深深根植於數學和邏輯學，尋求理解可以用計算機有效解決與無法解決這兩種問題的邊界。
計算複雜性理論是計算機科學中最具活力和創造性的分支之一，而 Constantinos Daskalakis則是這個領域最閃亮的新星之一。他的工作改變了我們對於博弈論、市場、拍賣和其他經濟結構中的一系列基本問題的計算複雜性的理解。Daskalakis擁有的廣泛的好奇心、技術上的獨創性以及深刻的理論洞察力，使他能夠為這些問題提供全新的視角。
納什均衡與計算複雜性
他的第一個突出成就來源於他的博士論文，它介於博弈論與計算機科學的邊界。博弈論模擬理性主體（可以是個人、商業機構、政府部門等）在衝突、競爭或者合作等情況下的相互作用。
博弈論的一個基本概念是納什均衡。如果一場博弈中的每一個主體都採取最佳的可能策略，並且將其他主體的策略都考慮在內，以至於任何一個主體都不再有改變策略的動機，這時，這場博弈就達到了納什均衡。這個概念是以數學家約翰·納什（John F. Nash）的名字命名的。他在1950年證明了，所有的博弈都會達到納什均衡。這個結果對於經濟學有著深遠的影響，納什也因此獲得了1994年的諾貝爾經濟學獎。
○ 主體通過優化各自的策略最終達到納什均衡。| 圖片來源：ICM
博弈論的應用不僅限於經濟學領域，它在國際關係、生物學等領域都有著廣泛的應用。顯然，為了預測主體可能採取的策略，能夠有效地計算納什均衡是非常有用的。因此，在納什證明了他的定理之後不久，漫長的研究就開始了，研究者開發出計算納什均衡的算法。然而，沒有任何一個算法是高效的，有些甚至被證明是無效的，直到21世紀初。
人們開始懷疑，計算納什均衡或許是個難以解決的問題。如果這個問題難以解決，就沒有理由期待策略主體——也就是有著有限大腦的人類——總是能夠發現這種平衡。這樣的結論會削弱人們對於納什均衡能夠在多大程度上預測人類行為的期待。
計算可解性的問題在著名的“P與NP”範式的情境中經常出現。“P與NP”問題在上世紀七十年代迅速成為計算複雜性理論的核心主題。寬泛地說，P代表計算機（在多項式時間內）可以輕易解決的一類問題，意味著存在求解問題答案的有效算法。相反，NP類則包括計算機難以解決的問題，這意味著，如果給定一個答案，計算機可以有效地驗證答案是否正確，但是不存在有效的算法能夠直接給出答案。
NP類問題的困難之處在於，問題的解可能並不存在。而對於納什均衡的計算問題來說，納什的證明確定了解的存在。因此，納什均衡問題不適用於“P與NP”範式。在1994年，Christos Papadimitriou定義了一種被稱為PPAD的新的複雜性類。對PPAD這類問題來說，解總是存在的，只是沒有已知的有效算法來計算求解，因而適用於類似納什均衡這樣的問題。
○ Constantinos Daskalakis和納什拍攝於2013年。| 圖片來源：Vasilis Syrgkanis
PPAD代表“有向圖的多項式校驗參數”（Polynomial Parity Argument for Directed graphs），指的是用於證明組合數學存在解的一種確定的標準參數，這個參數是被稱為“握手引理”（handshaking lemma）的結果的有向版本。PPAD包括所有可用這個引理證明解的存在性的計算問題。
○ 有向圖指的是邊有指向的圖（左），無向圖的邊則沒有指向（右）。| 圖片來源：Wikipedia
○ 在圖論領域，握手引理說的是，對於每一個有限的無向圖，有著奇數邊的頂點數目為偶數。對於聚會上一群人彼此握手的情況，則是說，有偶數的人與奇數的人握過手。例如圖中，偶數的頂點（標記為2，4，5，6的頂點）有著奇數條邊。而且頂點所連接的邊數之和為2+3+2+3+1=14，等於邊的數目的兩倍。握手引理是數學家歐拉於1736年證明的。| 圖片來源：Wikipedia
PPAD中最重要的問題之一，是純數學中一個結果的計算版本，被稱為布勞威爾不動點定理（Brouwer fixed point theorem）。這個定理是布勞威爾於1911年證明的，它說的是，從一個球體到自身的連續映射不可能移動所有的點；至少有一個點在映射下保持不動。這一基本的結果是無數數學證明的基礎，其中包括納什均衡的存在性的證明。
布勞威爾的證明是非構造性的，這意味著雖然它確保不動點的存在，但是並不會指出如何才能找到這些不動點。布勞威爾不動點定理的計算版本試圖發展出尋找不動點的算法。Papadimitriou在他1994年的文章中表明，這個計算版本的問題是“PPAD-完全”類的，這意味著，這個問題屬於PPAD類，且PPAD類中的任何問題都可以被規約到PPAD-完全類，也就是說它與PPAD類問題一樣困難。
十年之後，Daskalakis成為了Papadimitriou的博士生，並開始研究納什均衡問題。他和Papadimitriou、Paul Goldberg一起取得了重大進展，他們證明了
從計算角度來看，納什均衡問題與找到布勞威爾不動點的問題是等價的，因而納什均衡問題也是PPAD-完全的。在證明納什均衡問題難以解決這方面，Daskalakis等人的工作打破了納什均衡的普適性：我們不能期待策略主體的相互作用總是會達到納什均衡，因為這些主體不能進行難以解決的計算。從實際層面來說，納什均衡並不總是存在。
○ 儘管納什均衡總是存在，但是實際計算角度來看，則可能達不到這種均衡。| 圖片來源：ICM
這項工作還揭示了為什麼納什均衡問題的有效算法是如此難以捉摸。如果我們深入研究人們已經開發出的計算納什均衡的算法的內部構造，就會看見潛藏在背景中的PPAD類的標誌結構。Daskalakis等人的工作表明，這種結構是不可避免的。除了提供新的概念和技術的洞察，他們的工作還強調，對於博弈的重要子類，高效的計算平衡的實用算法非常需要。在之後的工作中，Daskalakis在逼近納什均衡方面創造了顯著的成果，這反過來為其他研究者的深入發展提供了靈感。
拍賣的機制設計問題
Daskalakis做出突出貢獻的第二個主要領域與經濟學中一個叫作機制設計（mechanism design）的分支有關。這裡的“機制”是指提供一套激勵機制，來引導主體以某種確定的方式行動。在某種意義上，機制設計是博弈論的反面，因為博弈論試圖分析博弈中的主體會如何行動，而機制設計的目標是設計一場博弈，為主體提供正確的激勵，以達到理想的結果 。
機制的最基本模型是拍賣，而最簡單的例子，是隻出售一件物品的拍賣。要如何設計拍賣規則以實現利潤最大化呢？1981年，經濟學家Roger Myerson為單個物品拍賣的問題，以及每個投標人對於結果的偏好可以被總結為單一數字的其他拍賣設置提供了一個完整而優雅的答案。這樣的拍賣設置被稱為“單一維度的”。
Myerson的工作對經濟學產生了重大影響，並激發了大量後續研究。它的洞察被應用於許多企業，例如鑽探權拍賣、電信頻譜拍賣、在線拍賣。2007年諾貝爾經濟學獎授予了機制設計領域的三位科學家—— Myerson，Leonid Hurwicz和Eric Maskin。
還有其他類型的拍賣設置，其中提供出售的物品超過一件，而且物品可能被捆綁銷售，並且投標人對捆綁銷售物品的價值標定不能用單一數字表示。與我們對單一維度拍賣的透徹瞭解相反，對這樣的多維度拍賣，我們知之甚少。
○ 有人想購買一張畫，有人想購買另一張畫，捆綁銷售會引發不同買家的競爭，從而促進銷售，增加盈利。| 圖片來源：ICM
事實上，我們甚至連如何將兩件物品銷售給一個買家的最佳策略都不知道。隨著買家和物品的數量增加，可能的拍賣設計的數目迅速擴大為一個高度複雜的集合。最佳設計即使被找到，也往往表現出違反直覺的特點，而且對投標人偏好的細節也高度敏感。
從大約2011年左右，Daskalakis開始鑽研這個令人望而生畏的複雜問題。其中最大的挑戰之一就是發展出對所有可能的拍賣設計的集合的洞察力。Daskalakis與他當時的學生Yang Cai與Matt Weinberg一起，發展出了巧妙的方法——利用線性編程來揭示這個集合中的結構。
利用這個結構，他們發展了一種方法，將機制設計問題轉化為算法設計的問題。然後，他們就可以構建計算高效的算法來產生最佳機制。這項工作努力達到的在結構和計算兩個方面的平衡，被證明成果顯著。
這項工作中發展起來的新洞見促進了Daskalakis、Alan Deckelbaum和Christos Tzamos的更多進展。他們在數學中一個叫做最優輸運理論的領域獲得了新結果，並利用這些結果從數學上描述在單買家設置中，多物品機制的最優結構。
Daskalakis關於機制設計的工作中最有價值的方面，是破解了一個以前被視為難以解決的問題。由於它們的理論性很強，因此這些結果需要被簡化，然後才能夠被直接應用於具體問題之上。包括Daskalakis在內的一些研究人員已經開始探索調整他的結構和算法的結果，以犧牲一部分最優性來換取簡單性和穩健性。
除了在納什均衡問題和機制設計方面的工作，Daskalakis還在機器學習、統計學和概率論、以及計算生物學等領域做出了貢獻。在計算生物學領域，主要的一個任務是根據分子數據來重建系統發生樹（phylogenetic tree）。2011年，Daskalakis和Elchanan Mossel、Sebastien Roch一起，發表了在數學系統發生學中一個核心猜想的證明，這個猜想是關於演化樹能夠被重建的特定條件的。他最近的工作專注於高維統計學和機器學習的理論基礎。
○ 有時候，問對了問題，就走上了發現的道路。| 圖片來源：ICM
Constantinos Daskalakis的工作展現出了對處理困難、複雜和長期問題的無所畏懼。他深入研究問題的具體細節，並利用從中獲得的直覺來培養對於結構和技術的洞察，這成為了理論進步的關鍵。
他作為研究者的才華，與他活躍的好奇心以及富有感染力的熱情一起，讓他成為了這個領域天生的領導者。年僅37歲的Daskalakis，在未來的幾十年裡將必定會繼續扮演這一角色。
參考鏈接：
https://www.mathunion.org/imu-awards/rolf-nevanlinna-prize/rolf-nevanlinna-prize-2018
閱讀更多 原理 的文章
