用博弈的思维看世界——记北京大学前沿计算研究中心讲席教授邓小铁

杜月娇

博弈论又称对策论，是使用严谨的数学模型研究现实世界中冲突对抗条件下最优决策问题的理论。两千多年前，孙膑利用博弈论原理帮助田忌赛马取胜，就是早期博弈论的萌芽。如今，博弈论不仅作为现代经济学的前沿领域成为主流的基本分析工具，而且它几乎覆盖了人类交互研究的方方面面，对政策科学与国际关系、人工智能、计算机与通信、生物演化等学科均有重大影响。在过去的近1个世纪中，博弈论深深地改变了人们的思维模式和对于世界的理解。

毅然投身博弈论研究领域，北京大学前沿计算研究中心讲席教授邓小铁从多个角度开创性地以计算复杂性方法论研究博弈论，长期从事算法博弈论、均衡计算和机制设计、互联网广告系统以及云计算定价及资源分配等问题研究，对学术、工作的炽热投入，已让他的科研硕果累累。随着互联网市场的兴起，博弈论问题快速计算的应用需求越发广泛，其对传统博弈理论的挑战促使邓小铁重新开始探讨基于大数据环境的互联网经济学理论。因为对科研的热爱，邓小铁始终在不遗余力地寻找向上的灵感。

植根心底的家国情怀

邓小铁

邓小铁有一份长长的履历，在清华大学、中国科学院完成本科和硕士学业后，他开启了近30年的海外漂泊生涯。他在美国斯坦福大学拿到了博士学位，在加拿大西门弗雷泽大学的加拿大自然科学与工程技术研究理事会做过国际博士后研究员，曾是加拿大约克大学计算机科学与工程系的副教授，中国香港城市大学计算机科学与工程系讲席教授，英国利物浦大学计算机科学与工程系的讲席教授，其间还在雅典、圣地亚哥、京都短暂访问工作过。丰富的人生经历，使他拥有了广阔的视角、包容的心态、卓越的思辨能力。这些特质常常伴随他的谈吐被自然流露，平和、不急不缓的语调中，传递出的是理性、智慧与坦然。

虽然在外的经历丰富而有趣，但回国的念头在邓小铁心里始终未动摇，因为出国并不是他人生排在第一位的规划，科研却是。由于对数学的热爱，当年他放弃了本科时从清华出国的机会，从力学专业转到运筹学专业，到中国科学院继续深造。正是在这段时间，他对博弈相关研究产生了浓厚兴趣，并将之作为自己未来的一个重要研究方向。至于此后因何出国，又为何辗转多地，因何回到上海交通大学计算机科学与工程系任教，在邓小铁看来，应是机缘使然。

邓小铁（左一）为获得前沿计算研究中心科研展示活动奖励的学生颁奖

而2017年入职北京大学前沿计算研究中心则是他的主动选择，究其原因还是因为数学。博弈论研究虽然不是纯数学的东西，但解决问题的思路却与数学有很大的关系，作为有重要国际影响的数学科学研究和人才培养基地，北京大学为他的研究提供了更广阔的空间。在那里与最优秀的数学人才开展深入而持续的合作，成为邓小铁非常期待的事情。

研究在不完美中前进

博弈论涉及的算法极为复杂，涉及全局优化，长期从事该领域研究的邓小铁深有感触。但凭借极其敏锐的感知，他却总能化繁为简，为问题找到解决方案。

20世纪50年代初，美国数学家、经济学家约翰·纳什提出后人称之为“纳什均衡”的概念，并利用角谷不动点定理证明了其存在性。这扭转了博弈论的发展历程，为现代博弈论引入经济学奠定了基础。

对所有人来说，世界在空间和时间维度上都是一个复杂的存在。理解这个存在并找出其中的规律，是人类求知的根本目的。时间维度上的规律就是动态变化中的高阶不变，只有把握住了这些高阶不变的东西，才能理解历史和现在并对未来做出可靠的预测，甚至改变未来。认识世界还有另一种途径，在一段时间内，从某个侧面和某种尺度意义上来说，世界也存在静止不发生变化的情况，那么理解这个不变的东西就显得尤为重要，因为这是把握一般规律的一个自然起点，这个不变的东西就是广泛意义上的均衡。

纳什均衡就是告诉大家，均衡一旦达到就不会发生变化从而进入一种稳定局面，除非外界环境或博弈规则发生改变。这个逻辑非常令人信服，对于分析多人决策且利益相互影响的问题非常有用，所以很快得到了普遍认可，以至成为目前社会科学尤其是经济学研究中最基本的研究工具和研究范式之一。

但纳什均衡不是完美的，它的非唯一性和难于计算性的缺点，使得它远没有零和博弈中极大极小解完美。20世纪七八十年代轰轰烈烈的纳什均衡精炼研究企图给出一个同样普适但是更加完美的概念，但最终不得不以失败告终。五花八门的各种精炼概念，除了子博弈完美均衡（SPE）和进化稳定策略（ESS）以外，最终能存活下来的屈指可数，都无法完全动摇纳什均衡的地位。模型和概念都是人们借以思维和理解世界的工具，都是一种近似，并没有对错之分，只有好用与不好用的区别，某种意义上理论和规律也是如此，并不存在终极的真理，科学研究在不完美中前进。华人在纳什均衡相关研究中有几个值得称道的理论成果，包括吴文俊和江嘉禾研究的本质均衡，周林改进的塔斯基不动点定理，以及邓小铁证明的二人博弈纳什均衡计算的PPAD困难性。

围绕“竞争市场中市场均衡定价与分配”“金融市场摩擦因子及套利方案”“优化管理框架中广度和深度对决策分析的计算难易程度的不同影响”等课题，致力于将计算复杂性作为方法论研究经济学、管理学基本问题，邓小铁展开了执着探索。

“功夫不负有心人”，2006年，邓小铁与合作者深入研究不动点模型计算复杂性工作。在不动点算法设计及分析的研究方向上，取得oracle模型及电路计算模型的精确复杂性结果。并以此为基础水到渠成地解决了二人博弈纳什计算问题。这一系列从建立离散不动点计算复杂性到二人博弈均衡计算属于PPAD完全类的工作，成为算法博弈论理论框架中的标志性成果。此后在此基础上，邓小铁又证明了莫比斯带上不动点计算是PPA完全的，把函数不动点的计算进行了完整刻画。

投身博弈论相关研究30余年，邓小铁在算法与博弈交互领域中的成就众多。1986年，他开创性地探讨合作博弈合理性的算法复杂性基础。此后，他将算法复杂性原理推广到管理结构扁平化、金融套利、市场均衡的应用中。2005年，他作为主要组织者创立了互联网经济学国际研讨会。历经16年，这一会议已成为国际互联网经济学的重要会议。因在算法与博弈论交互发展方面所作的贡献，他当选为计算机协会会士（ACM Fellow 2008）；因对部分信息和交互式近似计算作出的贡献，他获选电气和电子工程师协会会士（IEEE Fellow 2018）。2020年8月6日，欧洲科学院发布2020年度院士增选结果，邓小铁当选为外籍院士。

随着互联网在中国的普及及飞跃式发展，大量新的、现实社会中从来没有过的经济模式依靠互联网很快发展起来。让在互联网高速发展中产生的新经济模式健康、迅速地适应市场的发展，成为算法博弈论在互联网领域的价值体现。挑战传统博弈理论的系列成果，催促着邓小铁开启了基于大数据环境下研究互联网经济学理论的探索新旅程。

互联网带来的新局面

邓小铁介绍，近年来随着互联网技术和应用的持续爆炸式发展，大规模人群正在越来越频繁地在互联网上进行各种社会经济活动。这种变化带来一个从未有过的新局面：大家可以直面超大规模的人类个体和群体的刻画数据及其透过互联网进行交互的数据。而互联网带来的这些全局数据及其交互数据却给传统学科带来了有关大规模决策的新挑战，其中主要的挑战有：传统博弈论中参与者参数的私有信息是已知的，而在互联网环境下，私有信息未知或者可以造假，所以博弈是在非完全信息条件下进行的；另外，多人环境下博弈分析是个具有很高复杂性的难题。

挑战存在的同时，相关研究的进展也为破解这些难题提供了新的思路。例如：在算法博弈论方面，激励分析机制、算法复杂性分析研究、强化学习方法论在人机对抗的影响等研究的进展提供了将人工智能、算法博弈论和强化深度学习相结合找到高效解决方案的可能性。博弈决策理论迎来了关键的发展机遇。

针对经济活动和人机对抗的非完全信息条件下的博弈挑战，建立博弈论认知的数据基础模型、（未知）对手（群）的机器学习模型和均衡动力学分析方法论，实现个人对个人（p2p）合作预测、策略协调以及智能博弈决策均衡动力学特性的定量验证，成为邓小铁参与的科技部科技创新2030重大项目“非完全信息下智能博弈的均衡与动力学”的攻关目标。

项目的研究思路从数据科学模型下对博弈论静态共同知识假设的改变出发，探讨认知差异的博弈智能体多方相互探索、个体优化或共同优化多重任务下博弈均衡和动力学理论。针对经济活动和人机对抗的场景，实现博弈环境建模、多方对手策略大数据建模、应用控制论分析和强化学习方法、对博弈均衡结构和动力学过程进行可控实验完成理论分析实用性考证。

在具体攻关中，邓小铁将赞助搜索拍卖问题重新建模成一个重复性拍卖问题，将其视为一个拍卖者对抗买家的私有数据分布的学习和开发任务。“我们定义了一个私有数据操纵模型（P D M模型），它是一个卖家和买家在私有数据操纵上的博弈问题：拍卖者先声明一个基于买家递交的竞拍价值分布的分配和付款规则。卖家的期望收益取决于机制的设计以及买家在他们递交的竞拍价值（可能并非他们的真实估价）上的选择。在这个操控私有信息（PDM）博弈下，我们重新评估了赞助搜索拍卖问题的理论和方法，并发现了一种新的均衡理论。这一理论也能很好地解释为什么谷歌最近在高度重复的搜索引擎广告（SSA）拍卖中从二价拍卖转回到一价拍卖。”邓小铁介绍。他所做的这一工作是非完全信息非对称博弈理论框架和动力学模型的重要基础性工作。

互联网科技在进步的同时，也带动了经济学、社会学、管理科学、计算机科学的深层次互动和学科交叉研究，而且也在引领着新电子化经济的演变和革命。源于经济学研究关于竞争与合作的方法论，也在电子化市场和网络资源分配的计算任务中扮演着日益重要的角色。

运用算法博弈论框架下取得的最新研究成果，邓小铁深入探讨着这种经济学过程的理性基础。在承担的国家自然科学基金国际（地区）合作与交流项目“市场和网络中的竞争力和公平性的分析研究”中，着眼于经济效率和社会公平两个可能相冲突的目标，他带领团队有针对性地研究了电子化下公共资源的分配、电子化市场下的多平台竞争、共享经济下的网络资源的交换和共享，以及群体合作的可能性。力图在资源分配、市场竞争和网络资源共享环境中，从公平与竞争两方面探讨电子化经济学的理论框架，针对相关问题发展算法博弈的计算方法论，实现对典型应用机制的深入分析和完整刻画，为电子化经济发展提供解决公平与竞争对立的算法博弈论基础理论和大数据方法。

项目预期达成的目标包括：实现公共资源拍卖机制设计中对公平性的确定性保障；完成不同拍卖机制下各种竞争方案的优化和最佳调节作用的市场法规的设计；完成对等网络资源共享的激励相容及均衡态计算，及网络拓扑结构和分享协议对最优团队形成的机制设计。在推动科技进步的同时，项目还将建立以色列和中国两个优秀的算法博弈论研究团队之间的强强合作，让成果产生更广泛的国际影响力。

邓小铁介绍，参与项目攻关的，除自己的团队外还有来自中国香港和以色列的团队。其中香港的祁琦教授与邓小铁已有十余年的合作基础，他们同为市场和博弈计算方面的专家，最近却开始在公平与效率的背景下研究拍卖。而来自以色列的拉维（Lavi）教授则是拍卖领域的专家，最近开始研究市场竞争。在与拍卖模式相关的市场研究上，他们彼此间的互补性体现在中国团队在公平性研究方向的特点和以色列团队对竞争性研究的独特见解。在网络资源共享方面，中国团队着重于最终到达的均衡态，及其计算方法的研究，而以色列团队的研究则对团队的形成过程的竞争有更为精准的分析及计算。因此，双方团队的这些不同优势的结合将对关键问题的解决有一个整体把握，有助于项目的成功。

“中国和以色列两国都是全球化经济发展的重要参与国。公共资源如何更好分配，互联网商家如何合理竞争以及共享经济中的资源如何实现共享，是两国甚至全世界都要面对的关键问题，双方在这些问题上展开深入对话，并选择算法博弈论的角度展开有关公平和竞争力的研究，对两国形成共识及产生更大的国际影响力无疑都是一种助力。”邓小铁说。

让博弈论走进现实

在邓小铁看来，应用才是算法的最终目的，再好的博弈理论，也要通过实践的检验。为了达到目的，他一直在努力。在进行博弈论理论研究的同时，他研究了体育竞赛策略机制设计、C P U时间均衡定价、群体决策最优摊余成本代价等应用性课题，在互联网经济学中确认了参与者的前瞻最优策略、跨平台套利均衡、市场均衡博弈收敛解，获得了互联网经济模式设计的多项专利。

北京大学前沿计算研究中心队员秋游

正因为邓小铁在算法博弈论应用方面开展的深度研究，百度曾聘请他担任公司的战略顾问。谈到算法博弈论运用于百度公司相关产品的情况时，邓小铁介绍：“竞价排名是互联网经济中新生的重要经济市场。竞价排名的拍卖方式可以在非人为制定规矩的情况下，以最快的时间将互联网上的点击以合理的方式定价，卖给广告商。算法博弈论在这一市场里，可以用来分析广告商的竞价行为，估算市场盈利，让社会效益达到最优。”

除百度，邓小铁与华为公司、阿里巴巴公司也开展了合作。近期团队为蚂蚁金服研发的产品测试后收到了很好的效果，已准备正式上线，这让邓小铁备受鼓舞。

“国家发展每个人都有好运气。”他说，“其实我走了一条很窄的路，研究的东西并不热门，但却得到了很多的机会。”从纯粹只有定义的算法博弈论做起，到互联网经济下博弈论有了用武之地，再到机器学习与人工智能结合推动博弈论发展的新时代，邓小铁经历了博弈论从黑暗向黄金时期发展的完整历程，路也越走越远。“未来的博弈不仅仅是人与人之间的博弈，更有人与机器的博弈，机器与机器的博弈。”邓小铁说。

在向前迈进的同时，邓小铁也对博弈论原始模型进行着回溯，对那些不合理的地方做着纠正。将之前的假设拆掉，还原理论本来的面貌，是他追求的目标。

邓小铁记得，刚回国时，朋友问过他回国的原因。他回答，因为国内有很好的实验基础。回国这些年各项工作的开展让他的想法得到了验证，邓小铁切身感受到国家强劲的发展势头。

在人人都为心中的那个“中国梦”拼搏的美好时代，遵从内心，跟随热爱，对未来要走的路，邓小铁格外笃定。