○ 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，在未来的几十年里将必定会继续扮演这一角色。

参考链接：