現代計算復雜性理論對經濟學的啟示

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

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

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

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

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

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

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

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

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

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

　　　　（作者系北京交通大學經濟管理學院教授）