現(xiàn)代計算復(fù)雜性理論對經(jīng)濟學(xué)的啟示

作者：曹志剛（北京交通大學(xué)經(jīng)濟管理學(xué)院教授）

經(jīng)濟學(xué)經(jīng)常被批判為“經(jīng)濟學(xué)帝國主義”。憑借其在方法論方面的優(yōu)勢，經(jīng)濟學(xué)已滲透到很多人文社會科學(xué)學(xué)科，包括政治學(xué)、心理學(xué)、社會學(xué)和歷史學(xué)等，研究疆域不斷擴充。計算機科學(xué)更是一個“帝國主義”，擴展至我們所能想到的幾乎所有學(xué)科，包括數(shù)學(xué)和物理學(xué)這些基礎(chǔ)科學(xué)。無疑，這兩個“帝國主義”的相遇將激蕩出一系列新的思想火花。

目前已有很多文章就人工智能特別是機器學(xué)習對經(jīng)濟學(xué)實證研究的影響做出很多普及性論述。這些論述主要圍繞計算機科學(xué)作為與統(tǒng)計學(xué)類似的工具，對經(jīng)濟學(xué)實證研究的價值，特別是對計量經(jīng)濟學(xué)的補充乃至替代。筆者則主要介紹一個以往很少涉及的話題，即理論計算機特別是其計算復(fù)雜性理論對經(jīng)濟理論的啟示。北京大學(xué)的鄧小鐵教授表示，計算機和市場都是人為創(chuàng)造的，這使得計算機科學(xué)和經(jīng)濟學(xué)都不是自然科學(xué)。安德魯·麥克倫南也表示，互聯(lián)網(wǎng)出現(xiàn)以后，計算機科學(xué)更是變?yōu)橐婚T社會科學(xué)。我們可以把市場理解成一個分布式計算機，其智能程度和資源配置效率來源于其數(shù)據(jù)、算法和算力。數(shù)據(jù)即買家和賣家相關(guān)的信息，算法就是交易和分配等一系列市場規(guī)則，算力則取決于決策主體的理性程度。經(jīng)濟學(xué)者聚焦于“看不見的手”和“看得見的手”如何影響資源配置效率和公平，而計算機學(xué)者研究如何從硬件和軟件兩方面提高計算機的計算性能。這些天然的聯(lián)系使得兩個學(xué)科底層思想的碰撞交流有著堅實的邏輯基礎(chǔ)。

理論計算機知識體系主要分為兩大塊即算法和復(fù)雜性，分別研究計算機能做什么和不能做什么。經(jīng)濟學(xué)者傳統(tǒng)上對算法關(guān)注并不多。近些年，伴隨著數(shù)字經(jīng)濟的蓬勃發(fā)展，我們生產(chǎn)生活的很多方面被算法接管，越來越多的經(jīng)濟學(xué)者也對算法這種特殊的技術(shù)越來越感興趣，從算法對人的替代、算法合謀、算法公平性等角度展開研究。特別是新一輪人工智能興起以來，由于數(shù)據(jù)、算法和算力成為眾所周知的人工智能三大要素，經(jīng)濟學(xué)者對算法及其影響的興趣日趨增加。算法不僅對經(jīng)濟發(fā)展本身產(chǎn)生了巨大影響，還成為經(jīng)濟學(xué)者進行理論研究的工具。微積分和優(yōu)化等數(shù)學(xué)理論早已成為經(jīng)濟學(xué)研究的日常工具，但多數(shù)經(jīng)濟學(xué)者對算法這種新的研究工具并不熟悉。這背后的原因很多，比如經(jīng)濟學(xué)者一般不關(guān)注離散問題，而理論計算機涉及的多為離散問題、有限問題，其數(shù)學(xué)技巧通常也跟微積分關(guān)系不大。

上述情況正在發(fā)生緩慢變化。2012年諾貝爾經(jīng)濟學(xué)獎授予了羅伊德·沙普利與埃爾文·羅斯，以肯定他們在市場設(shè)計特別是穩(wěn)定匹配方面的奠基性貢獻。市場設(shè)計和穩(wěn)定匹配主要涉及離散數(shù)學(xué)，其中的DA算法和TTC算法都是相關(guān)理論的核心內(nèi)容。除經(jīng)濟學(xué)者外，該方向的發(fā)展進程也由理論計算機學(xué)者和運籌學(xué)研究者共同推動，使得經(jīng)濟學(xué)與理論計算機的交叉融合日趨緊密。另外，算法和機制也有天然的聯(lián)系：任何復(fù)雜機制的運行都需要算法的支撐，而算法涉及人的激勵后也可以看成一種機制。由于上述原因，過去的10多年越來越多的微觀理論經(jīng)濟學(xué)者和理論計算機學(xué)者從機制設(shè)計的視角研究算法，這是算法機制設(shè)計和計算經(jīng)濟學(xué)的重要內(nèi)容。

計算機和市場的創(chuàng)造過程有著明顯的不同，即計算機是數(shù)學(xué)研究者有意識、有計劃的創(chuàng)造，其每一次硬件的更新迭代、重要算法的發(fā)明都有明確的來源和歷史；而市場是集體協(xié)同行為的無意識結(jié)果，是一種社會演化的產(chǎn)物，其各種交易規(guī)則通常沒有明確的發(fā)明人，背后集結(jié)的是群體智慧。盡管起源方式不同，市場和計算機兩種對象都極具復(fù)雜性。市場讓最先領(lǐng)略到其精妙運行的經(jīng)濟學(xué)者對其充滿敬意，正如領(lǐng)略到生物演化之美的生物學(xué)者對生命的敬意。不論是自然演化的市場還是中心設(shè)計的計算機，其自身局限和能力邊界都特別值得關(guān)注。那么，計算機學(xué)者關(guān)于計算復(fù)雜性的研究對經(jīng)濟學(xué)者研究市場有著哪些啟發(fā)呢？

迄今為止，專注于研究計算機不能做什么的計算復(fù)雜性理論很少被經(jīng)濟學(xué)者關(guān)注。計算復(fù)雜性和算法是現(xiàn)代計算機科學(xué)一枚“硬幣”的兩面?，F(xiàn)代計算復(fù)雜性理論對經(jīng)濟學(xué)理論的啟發(fā)同樣不應(yīng)被忽視。計算復(fù)雜性理論同時對市場和政府的能力設(shè)置了邊界，可以從不同于經(jīng)濟學(xué)的視角為市場與政府的關(guān)系提供新的理解。正如“囚徒困境”揭示了個體理性與集體理性間的基本矛盾，“阿羅不可能定理”揭示了社會選擇中的基本矛盾，蒙代爾“三元悖論”揭示了開放國家在制定經(jīng)濟政策時必須面對的一種基本矛盾，而均衡計算方面的計算復(fù)雜性結(jié)論可以從以下新穎的視角對理解市場運行提供有益啟發(fā)。

第一，計算性摩擦。我們知道市場并非在真空中運行，理想中的完全競爭市場在現(xiàn)實中并不存在。市場失靈除市場勢力和外部性等原因外，交易成本和信息摩擦等因素也是經(jīng)濟學(xué)者經(jīng)?？紤]的現(xiàn)實制約。還有一種經(jīng)濟學(xué)者很少能嚴格建模研究的有限理性，即決策主體計算能力的局限，可稱為“計算性摩擦”。市場的有效運行依賴于買賣雙方的精打細算，依賴于假設(shè)中理想的無窮計算能力。人們在詬病這種完全理性假設(shè)時經(jīng)常表示，不能把市場中的決策主體想象成數(shù)學(xué)家。針對這種詬病有一種自然的回應(yīng)，那就是伴隨著人工智能的能力提升和廣泛普及，市場越來越接近于每個決策者都是數(shù)學(xué)家。但數(shù)學(xué)家也并非無所不能。面對足夠復(fù)雜、規(guī)模足夠大的問題，很多均衡方面的計算復(fù)雜性結(jié)果表明，即便每個人都配備了超級計算機，也很可能無法在可接受的時間里計算出均衡策略?，F(xiàn)在不能，將來也不能。借助計算復(fù)雜性理論，對P問題和NP—難問題（或者PPAD—難問題）做相應(yīng)的區(qū)分，可以幫助經(jīng)濟學(xué)者更加深入地理解計算性摩擦在不同場景下對市場運行效率的影響。

第二，理性的自負。從算法的視角來看，市場經(jīng)濟是一種分布式算法，而計劃經(jīng)濟則是一種中心化算法，需要把所有的私人信息集結(jié)起來，通過計算輸出生產(chǎn)和分配所有細節(jié)。市場經(jīng)濟的效率受計算復(fù)雜性理論的約束，而對于計劃經(jīng)濟來說，這種約束更加明顯。傳統(tǒng)上，經(jīng)濟學(xué)者對計劃經(jīng)濟的批判更多集中于激勵和信息，其實計算也是一種重要制約因素。他們一般默認，只要擁有足夠強大的超級計算機，計算問題總能解決。由現(xiàn)代計算復(fù)雜性理論可知，計算效率是有邊界的，有些問題不僅目前的超級計算機無法精確求解，將來很可能也制造不出能夠精確求解的新型計算機。所以，即便政府擁有了所有相關(guān)信息，即便所有的主體都不存在激勵問題，計劃經(jīng)濟依然不見得能有效實施。對人類理性抱有不切實際的自負，可能會釀成慘痛的悲劇，這種歷史一再重演。該視角對于市場設(shè)計以及更廣泛的機制設(shè)計理論依然有效：某些問題的最優(yōu)機制可能無法在可接受的時間內(nèi)精確計算出來，只能務(wù)實考慮足夠簡單的近似最優(yōu)機制，才可能在現(xiàn)實中順利實施并達到預(yù)期目的。

第三，信仰的力量。經(jīng)濟學(xué)是一種社會科學(xué)，在一定意義上也是一種哲學(xué)。任何理論都無法精確適用現(xiàn)實，理論的應(yīng)用依賴于堅信其具有一定的泛化能力，可以不必在意很多不重要的細節(jié)。計算復(fù)雜性也是一定意義上的哲學(xué)，因為千禧年猜想的P≠NP其實是一種信仰，迄今為止沒有人能證明P≠NP，也沒有人能證明P=NP。但絕大多數(shù)學(xué)者都相信P≠NP，這也是前面論述的邏輯起點。多數(shù)學(xué)者之所以持這種觀點而不是相反的觀點，是因為相信這個世界是復(fù)雜的，若P=NP則這個世界會過于簡單過于無趣（堵丁柱）。人類的認知是有邊界的，在超出目前認知、理性不該自負的領(lǐng)域，哲學(xué)和信仰勢必發(fā)揮出強大的作用。市場是社會交互的產(chǎn)物，其運行依賴于信念和信仰的互動。對待市場的態(tài)度，既不能過度迷信，又要有足夠的敬畏。這個世界沒那么簡單，市場也沒那么簡單，在沒有足夠的理論和實踐支撐我們對市場進行改造之前，不如對其予以充分信任。歷史上有太多慘痛的教訓(xùn)告訴我們，市場本身所產(chǎn)生的無效率和危害，遠沒有對其缺乏敬畏所產(chǎn)生的危害來得大。

市場、經(jīng)濟和社會都是復(fù)雜巨系統(tǒng)，對其深入理解和治理都需要系統(tǒng)思維和復(fù)雜性思維。計算復(fù)雜性理論是復(fù)雜性科學(xué)中較為成熟且少有的可以完全形式化的一個理論，并已在計算機科學(xué)的發(fā)展中發(fā)揮了基礎(chǔ)性作用。計算復(fù)雜性理論的基本思想應(yīng)該引起更多經(jīng)濟學(xué)者的關(guān)注，從而在計算機科學(xué)和經(jīng)濟學(xué)兩個“帝國主義”的激烈交鋒中起到更加重要的作用。

來源：中國社會科學(xué)網(wǎng)-中國社會科學(xué)報