用博弈的思維看世界
——記北京大學前沿計算研究中心講席教授鄧小鐵

杜月嬌

博弈論又稱對策論，是使用嚴謹?shù)臄?shù)學模型研究現(xiàn)實世界中沖突對抗條件下最優(yōu)決策問題的理論。兩千多年前，孫臏利用博弈論原理幫助田忌賽馬取勝，就是早期博弈論的萌芽。如今，博弈論不僅作為現(xiàn)代經(jīng)濟學的前沿領域成為主流的基本分析工具，而且它幾乎覆蓋了人類交互研究的方方面面，對政策科學與國際關(guān)系、人工智能、計算機與通信、生物演化等學科均有重大影響。在過去的近1個世紀中，博弈論深深地改變了人們的思維模式和對于世界的理解。

毅然投身博弈論研究領域，北京大學前沿計算研究中心講席教授鄧小鐵從多個角度開創(chuàng)性地以計算復雜性方法論研究博弈論，長期從事算法博弈論、均衡計算和機制設計、互聯(lián)網(wǎng)廣告系統(tǒng)以及云計算定價及資源分配等問題研究，對學術(shù)、工作的熾熱投入，已讓他的科研碩果累累。隨著互聯(lián)網(wǎng)市場的興起，博弈論問題快速計算的應用需求越發(fā)廣泛，其對傳統(tǒng)博弈理論的挑戰(zhàn)促使鄧小鐵重新開始探討基于大數(shù)據(jù)環(huán)境的互聯(lián)網(wǎng)經(jīng)濟學理論。因為對科研的熱愛，鄧小鐵始終在不遺余力地尋找向上的靈感。

植根心底的家國情懷

鄧小鐵

鄧小鐵有一份長長的履歷，在清華大學、中國科學院完成本科和碩士學業(yè)后，他開啟了近30年的海外漂泊生涯。他在美國斯坦福大學拿到了博士學位，在加拿大西門弗雷澤大學的加拿大自然科學與工程技術(shù)研究理事會做過國際博士后研究員，曾是加拿大約克大學計算機科學與工程系的副教授，中國香港城市大學計算機科學與工程系講席教授，英國利物浦大學計算機科學與工程系的講席教授，其間還在雅典、圣地亞哥、京都短暫訪問工作過。豐富的人生經(jīng)歷，使他擁有了廣闊的視角、包容的心態(tài)、卓越的思辨能力。這些特質(zhì)常常伴隨他的談吐被自然流露，平和、不急不緩的語調(diào)中，傳遞出的是理性、智慧與坦然。

雖然在外的經(jīng)歷豐富而有趣，但回國的念頭在鄧小鐵心里始終未動搖，因為出國并不是他人生排在第一位的規(guī)劃，科研卻是。由于對數(shù)學的熱愛，當年他放棄了本科時從清華出國的機會，從力學專業(yè)轉(zhuǎn)到運籌學專業(yè)，到中國科學院繼續(xù)深造。正是在這段時間，他對博弈相關(guān)研究產(chǎn)生了濃厚興趣，并將之作為自己未來的一個重要研究方向。至于此后因何出國，又為何輾轉(zhuǎn)多地，因何回到上海交通大學計算機科學與工程系任教，在鄧小鐵看來，應是機緣使然。

鄧小鐵（左一）為獲得前沿計算研究中心科研展示活動獎勵的學生頒獎

而2017年入職北京大學前沿計算研究中心則是他的主動選擇，究其原因還是因為數(shù)學。博弈論研究雖然不是純數(shù)學的東西，但解決問題的思路卻與數(shù)學有很大的關(guān)系，作為有重要國際影響的數(shù)學科學研究和人才培養(yǎng)基地，北京大學為他的研究提供了更廣闊的空間。在那里與最優(yōu)秀的數(shù)學人才開展深入而持續(xù)的合作，成為鄧小鐵非常期待的事情。

研究在不完美中前進

博弈論涉及的算法極為復雜，涉及全局優(yōu)化，長期從事該領域研究的鄧小鐵深有感觸。但憑借極其敏銳的感知，他卻總能化繁為簡，為問題找到解決方案。

20世紀50年代初，美國數(shù)學家、經(jīng)濟學家約翰·納什提出后人稱之為“納什均衡”的概念，并利用角谷不動點定理證明了其存在性。這扭轉(zhuǎn)了博弈論的發(fā)展歷程，為現(xiàn)代博弈論引入經(jīng)濟學奠定了基礎。

對所有人來說，世界在空間和時間維度上都是一個復雜的存在。理解這個存在并找出其中的規(guī)律，是人類求知的根本目的。時間維度上的規(guī)律就是動態(tài)變化中的高階不變，只有把握住了這些高階不變的東西，才能理解歷史和現(xiàn)在并對未來做出可靠的預測，甚至改變未來。認識世界還有另一種途徑，在一段時間內(nèi)，從某個側(cè)面和某種尺度意義上來說，世界也存在靜止不發(fā)生變化的情況，那么理解這個不變的東西就顯得尤為重要，因為這是把握一般規(guī)律的一個自然起點，這個不變的東西就是廣泛意義上的均衡。

納什均衡就是告訴大家，均衡一旦達到就不會發(fā)生變化從而進入一種穩(wěn)定局面，除非外界環(huán)境或博弈規(guī)則發(fā)生改變。這個邏輯非常令人信服，對于分析多人決策且利益相互影響的問題非常有用，所以很快得到了普遍認可，以至成為目前社會科學尤其是經(jīng)濟學研究中最基本的研究工具和研究范式之一。

但納什均衡不是完美的，它的非唯一性和難于計算性的缺點，使得它遠沒有零和博弈中極大極小解完美。20世紀七八十年代轟轟烈烈的納什均衡精煉研究企圖給出一個同樣普適但是更加完美的概念，但最終不得不以失敗告終。五花八門的各種精煉概念，除了子博弈完美均衡（SPE）和進化穩(wěn)定策略（ESS）以外，最終能存活下來的屈指可數(shù)，都無法完全動搖納什均衡的地位。模型和概念都是人們借以思維和理解世界的工具，都是一種近似，并沒有對錯之分，只有好用與不好用的區(qū)別，某種意義上理論和規(guī)律也是如此，并不存在終極的真理，科學研究在不完美中前進。華人在納什均衡相關(guān)研究中有幾個值得稱道的理論成果，包括吳文俊和江嘉禾研究的本質(zhì)均衡，周林改進的塔斯基不動點定理，以及鄧小鐵證明的二人博弈納什均衡計算的PPAD困難性。

圍繞“競爭市場中市場均衡定價與分配”“金融市場摩擦因子及套利方案”“優(yōu)化管理框架中廣度和深度對決策分析的計算難易程度的不同影響”等課題，致力于將計算復雜性作為方法論研究經(jīng)濟學、管理學基本問題，鄧小鐵展開了執(zhí)著探索。

“功夫不負有心人”，2006年，鄧小鐵與合作者深入研究不動點模型計算復雜性工作。在不動點算法設計及分析的研究方向上，取得oracle模型及電路計算模型的精確復雜性結(jié)果。并以此為基礎水到渠成地解決了二人博弈納什計算問題。這一系列從建立離散不動點計算復雜性到二人博弈均衡計算屬于PPAD完全類的工作，成為算法博弈論理論框架中的標志性成果。此后在此基礎上，鄧小鐵又證明了莫比斯帶上不動點計算是PPA完全的，把函數(shù)不動點的計算進行了完整刻畫。

投身博弈論相關(guān)研究30余年，鄧小鐵在算法與博弈交互領域中的成就眾多。1986年，他開創(chuàng)性地探討合作博弈合理性的算法復雜性基礎。此后，他將算法復雜性原理推廣到管理結(jié)構(gòu)扁平化、金融套利、市場均衡的應用中。2005年，他作為主要組織者創(chuàng)立了互聯(lián)網(wǎng)經(jīng)濟學國際研討會。歷經(jīng)16年，這一會議已成為國際互聯(lián)網(wǎng)經(jīng)濟學的重要會議。因在算法與博弈論交互發(fā)展方面所作的貢獻，他當選為計算機協(xié)會會士（ACM Fellow 2008）；因?qū)Σ糠中畔⒑徒换ナ浇朴嬎阕鞒龅呢暙I，他獲選電氣和電子工程師協(xié)會會士（IEEE Fellow 2018）。2020年8月6日，歐洲科學院發(fā)布2020年度院士增選結(jié)果，鄧小鐵當選為外籍院士。

隨著互聯(lián)網(wǎng)在中國的普及及飛躍式發(fā)展，大量新的、現(xiàn)實社會中從來沒有過的經(jīng)濟模式依靠互聯(lián)網(wǎng)很快發(fā)展起來。讓在互聯(lián)網(wǎng)高速發(fā)展中產(chǎn)生的新經(jīng)濟模式健康、迅速地適應市場的發(fā)展，成為算法博弈論在互聯(lián)網(wǎng)領域的價值體現(xiàn)。挑戰(zhàn)傳統(tǒng)博弈理論的系列成果，催促著鄧小鐵開啟了基于大數(shù)據(jù)環(huán)境下研究互聯(lián)網(wǎng)經(jīng)濟學理論的探索新旅程。

互聯(lián)網(wǎng)帶來的新局面

鄧小鐵介紹，近年來隨著互聯(lián)網(wǎng)技術(shù)和應用的持續(xù)爆炸式發(fā)展，大規(guī)模人群正在越來越頻繁地在互聯(lián)網(wǎng)上進行各種社會經(jīng)濟活動。這種變化帶來一個從未有過的新局面：大家可以直面超大規(guī)模的人類個體和群體的刻畫數(shù)據(jù)及其透過互聯(lián)網(wǎng)進行交互的數(shù)據(jù)。而互聯(lián)網(wǎng)帶來的這些全局數(shù)據(jù)及其交互數(shù)據(jù)卻給傳統(tǒng)學科帶來了有關(guān)大規(guī)模決策的新挑戰(zhàn)，其中主要的挑戰(zhàn)有：傳統(tǒng)博弈論中參與者參數(shù)的私有信息是已知的，而在互聯(lián)網(wǎng)環(huán)境下，私有信息未知或者可以造假，所以博弈是在非完全信息條件下進行的；另外，多人環(huán)境下博弈分析是個具有很高復雜性的難題。

挑戰(zhàn)存在的同時，相關(guān)研究的進展也為破解這些難題提供了新的思路。例如：在算法博弈論方面，激勵分析機制、算法復雜性分析研究、強化學習方法論在人機對抗的影響等研究的進展提供了將人工智能、算法博弈論和強化深度學習相結(jié)合找到高效解決方案的可能性。博弈決策理論迎來了關(guān)鍵的發(fā)展機遇。

針對經(jīng)濟活動和人機對抗的非完全信息條件下的博弈挑戰(zhàn)，建立博弈論認知的數(shù)據(jù)基礎模型、（未知）對手（群）的機器學習模型和均衡動力學分析方法論，實現(xiàn)個人對個人（p2p）合作預測、策略協(xié)調(diào)以及智能博弈決策均衡動力學特性的定量驗證，成為鄧小鐵參與的科技部科技創(chuàng)新2030重大項目“非完全信息下智能博弈的均衡與動力學”的攻關(guān)目標。

項目的研究思路從數(shù)據(jù)科學模型下對博弈論靜態(tài)共同知識假設的改變出發(fā)，探討認知差異的博弈智能體多方相互探索、個體優(yōu)化或共同優(yōu)化多重任務下博弈均衡和動力學理論。針對經(jīng)濟活動和人機對抗的場景，實現(xiàn)博弈環(huán)境建模、多方對手策略大數(shù)據(jù)建模、應用控制論分析和強化學習方法、對博弈均衡結(jié)構(gòu)和動力學過程進行可控實驗完成理論分析實用性考證。

在具體攻關(guān)中，鄧小鐵將贊助搜索拍賣問題重新建模成一個重復性拍賣問題，將其視為一個拍賣者對抗買家的私有數(shù)據(jù)分布的學習和開發(fā)任務。“我們定義了一個私有數(shù)據(jù)操縱模型（P D M模型），它是一個賣家和買家在私有數(shù)據(jù)操縱上的博弈問題：拍賣者先聲明一個基于買家遞交的競拍價值分布的分配和付款規(guī)則。賣家的期望收益取決于機制的設計以及買家在他們遞交的競拍價值（可能并非他們的真實估價）上的選擇。在這個操控私有信息（PDM）博弈下，我們重新評估了贊助搜索拍賣問題的理論和方法，并發(fā)現(xiàn)了一種新的均衡理論。這一理論也能很好地解釋為什么谷歌最近在高度重復的搜索引擎廣告（SSA）拍賣中從二價拍賣轉(zhuǎn)回到一價拍賣。”鄧小鐵介紹。他所做的這一工作是非完全信息非對稱博弈理論框架和動力學模型的重要基礎性工作。

互聯(lián)網(wǎng)科技在進步的同時，也帶動了經(jīng)濟學、社會學、管理科學、計算機科學的深層次互動和學科交叉研究，而且也在引領著新電子化經(jīng)濟的演變和革命。源于經(jīng)濟學研究關(guān)于競爭與合作的方法論，也在電子化市場和網(wǎng)絡資源分配的計算任務中扮演著日益重要的角色。

運用算法博弈論框架下取得的最新研究成果，鄧小鐵深入探討著這種經(jīng)濟學過程的理性基礎。在承擔的國家自然科學基金國際（地區(qū)）合作與交流項目“市場和網(wǎng)絡中的競爭力和公平性的分析研究”中，著眼于經(jīng)濟效率和社會公平兩個可能相沖突的目標，他帶領團隊有針對性地研究了電子化下公共資源的分配、電子化市場下的多平臺競爭、共享經(jīng)濟下的網(wǎng)絡資源的交換和共享，以及群體合作的可能性。力圖在資源分配、市場競爭和網(wǎng)絡資源共享環(huán)境中，從公平與競爭兩方面探討電子化經(jīng)濟學的理論框架，針對相關(guān)問題發(fā)展算法博弈的計算方法論，實現(xiàn)對典型應用機制的深入分析和完整刻畫，為電子化經(jīng)濟發(fā)展提供解決公平與競爭對立的算法博弈論基礎理論和大數(shù)據(jù)方法。

項目預期達成的目標包括：實現(xiàn)公共資源拍賣機制設計中對公平性的確定性保障；完成不同拍賣機制下各種競爭方案的優(yōu)化和最佳調(diào)節(jié)作用的市場法規(guī)的設計；完成對等網(wǎng)絡資源共享的激勵相容及均衡態(tài)計算，及網(wǎng)絡拓撲結(jié)構(gòu)和分享協(xié)議對最優(yōu)團隊形成的機制設計。在推動科技進步的同時，項目還將建立以色列和中國兩個優(yōu)秀的算法博弈論研究團隊之間的強強合作，讓成果產(chǎn)生更廣泛的國際影響力。

鄧小鐵介紹，參與項目攻關(guān)的，除自己的團隊外還有來自中國香港和以色列的團隊。其中香港的祁琦教授與鄧小鐵已有十余年的合作基礎，他們同為市場和博弈計算方面的專家，最近卻開始在公平與效率的背景下研究拍賣。而來自以色列的拉維（Lavi）教授則是拍賣領域的專家，最近開始研究市場競爭。在與拍賣模式相關(guān)的市場研究上，他們彼此間的互補性體現(xiàn)在中國團隊在公平性研究方向的特點和以色列團隊對競爭性研究的獨特見解。在網(wǎng)絡資源共享方面，中國團隊著重于最終到達的均衡態(tài)，及其計算方法的研究，而以色列團隊的研究則對團隊的形成過程的競爭有更為精準的分析及計算。因此，雙方團隊的這些不同優(yōu)勢的結(jié)合將對關(guān)鍵問題的解決有一個整體把握，有助于項目的成功。

“中國和以色列兩國都是全球化經(jīng)濟發(fā)展的重要參與國。公共資源如何更好分配，互聯(lián)網(wǎng)商家如何合理競爭以及共享經(jīng)濟中的資源如何實現(xiàn)共享，是兩國甚至全世界都要面對的關(guān)鍵問題，雙方在這些問題上展開深入對話，并選擇算法博弈論的角度展開有關(guān)公平和競爭力的研究，對兩國形成共識及產(chǎn)生更大的國際影響力無疑都是一種助力。”鄧小鐵說。

讓博弈論走進現(xiàn)實

在鄧小鐵看來，應用才是算法的最終目的，再好的博弈理論，也要通過實踐的檢驗。為了達到目的，他一直在努力。在進行博弈論理論研究的同時，他研究了體育競賽策略機制設計、C P U時間均衡定價、群體決策最優(yōu)攤余成本代價等應用性課題，在互聯(lián)網(wǎng)經(jīng)濟學中確認了參與者的前瞻最優(yōu)策略、跨平臺套利均衡、市場均衡博弈收斂解，獲得了互聯(lián)網(wǎng)經(jīng)濟模式設計的多項專利。

北京大學前沿計算研究中心隊員秋游

正因為鄧小鐵在算法博弈論應用方面開展的深度研究，百度曾聘請他擔任公司的戰(zhàn)略顧問。談到算法博弈論運用于百度公司相關(guān)產(chǎn)品的情況時，鄧小鐵介紹：“競價排名是互聯(lián)網(wǎng)經(jīng)濟中新生的重要經(jīng)濟市場。競價排名的拍賣方式可以在非人為制定規(guī)矩的情況下，以最快的時間將互聯(lián)網(wǎng)上的點擊以合理的方式定價，賣給廣告商。算法博弈論在這一市場里，可以用來分析廣告商的競價行為，估算市場盈利，讓社會效益達到最優(yōu)。”

除百度，鄧小鐵與華為公司、阿里巴巴公司也開展了合作。近期團隊為螞蟻金服研發(fā)的產(chǎn)品測試后收到了很好的效果，已準備正式上線，這讓鄧小鐵備受鼓舞。

“國家發(fā)展每個人都有好運氣。”他說，“其實我走了一條很窄的路，研究的東西并不熱門，但卻得到了很多的機會。”從純粹只有定義的算法博弈論做起，到互聯(lián)網(wǎng)經(jīng)濟下博弈論有了用武之地，再到機器學習與人工智能結(jié)合推動博弈論發(fā)展的新時代，鄧小鐵經(jīng)歷了博弈論從黑暗向黃金時期發(fā)展的完整歷程，路也越走越遠。“未來的博弈不僅僅是人與人之間的博弈，更有人與機器的博弈，機器與機器的博弈。”鄧小鐵說。

在向前邁進的同時，鄧小鐵也對博弈論原始模型進行著回溯，對那些不合理的地方做著糾正。將之前的假設拆掉，還原理論本來的面貌，是他追求的目標。

鄧小鐵記得，剛回國時，朋友問過他回國的原因。他回答，因為國內(nèi)有很好的實驗基礎。回國這些年各項工作的開展讓他的想法得到了驗證，鄧小鐵切身感受到國家強勁的發(fā)展勢頭。

在人人都為心中的那個“中國夢”拼搏的美好時代，遵從內(nèi)心，跟隨熱愛，對未來要走的路，鄧小鐵格外篤定。