现代计算复杂性理论对经济学的启示

　　经济学经常被批判为“经济学帝国主义”。凭借其在方法论方面的优势，经济学已渗透到很多人文社会科学学科，包括政治学、心理学、社会学和历史学等，研究疆域不断扩充。计算机科学更是一个“帝国主义”，扩展至我们所能想到的几乎所有学科，包括数学和物理学这些基础科学。无疑，这两个“帝国主义”的相遇将激荡出一系列新的思想火花。

　　目前已有很多文章就人工智能特别是机器学习对经济学实证研究的影响做出很多普及性论述。这些论述主要围绕计算机科学作为与统计学类似的工具，对经济学实证研究的价值，特别是对计量经济学的补充乃至替代。笔者则主要介绍一个以往很少涉及的话题，即理论计算机特别是其计算复杂性理论对经济理论的启示。北京大学的邓小铁教授表示，计算机和市场都是人为创造的，这使得计算机科学和经济学都不是自然科学。安德鲁·麦克伦南也表示，互联网出现以后，计算机科学更是变为一门社会科学。我们可以把市场理解成一个分布式计算机，其智能程度和资源配置效率来源于其数据、算法和算力。数据即买家和卖家相关的信息，算法就是交易和分配等一系列市场规则，算力则取决于决策主体的理性程度。经济学者聚焦于“看不见的手”和“看得见的手”如何影响资源配置效率和公平，而计算机学者研究如何从硬件和软件两方面提高计算机的计算性能。这些天然的联系使得两个学科底层思想的碰撞交流有着坚实的逻辑基础。

　　理论计算机知识体系主要分为两大块即算法和复杂性，分别研究计算机能做什么和不能做什么。经济学者传统上对算法关注并不多。近些年，伴随着数字经济的蓬勃发展，我们生产生活的很多方面被算法接管，越来越多的经济学者也对算法这种特殊的技术越来越感兴趣，从算法对人的替代、算法合谋、算法公平性等角度展开研究。特别是新一轮人工智能兴起以来，由于数据、算法和算力成为众所周知的人工智能三大要素，经济学者对算法及其影响的兴趣日趋增加。算法不仅对经济发展本身产生了巨大影响，还成为经济学者进行理论研究的工具。微积分和优化等数学理论早已成为经济学研究的日常工具，但多数经济学者对算法这种新的研究工具并不熟悉。这背后的原因很多，比如经济学者一般不关注离散问题，而理论计算机涉及的多为离散问题、有限问题，其数学技巧通常也跟微积分关系不大。

　　上述情况正在发生缓慢变化。2012年诺贝尔经济学奖授予了罗伊德·沙普利与埃尔文·罗斯，以肯定他们在市场设计特别是稳定匹配方面的奠基性贡献。市场设计和稳定匹配主要涉及离散数学，其中的DA算法和TTC算法都是相关理论的核心内容。除经济学者外，该方向的发展进程也由理论计算机学者和运筹学研究者共同推动，使得经济学与理论计算机的交叉融合日趋紧密。另外，算法和机制也有天然的联系：任何复杂机制的运行都需要算法的支撑，而算法涉及人的激励后也可以看成一种机制。由于上述原因，过去的10多年越来越多的微观理论经济学者和理论计算机学者从机制设计的视角研究算法，这是算法机制设计和计算经济学的重要内容。

　　计算机和市场的创造过程有着明显的不同，即计算机是数学研究者有意识、有计划的创造，其每一次硬件的更新迭代、重要算法的发明都有明确的来源和历史；而市场是集体协同行为的无意识结果，是一种社会演化的产物，其各种交易规则通常没有明确的发明人，背后集结的是群体智慧。尽管起源方式不同，市场和计算机两种对象都极具复杂性。市场让最先领略到其精妙运行的经济学者对其充满敬意，正如领略到生物演化之美的生物学者对生命的敬意。不论是自然演化的市场还是中心设计的计算机，其自身局限和能力边界都特别值得关注。那么，计算机学者关于计算复杂性的研究对经济学者研究市场有着哪些启发呢？

　　迄今为止，专注于研究计算机不能做什么的计算复杂性理论很少被经济学者关注。计算复杂性和算法是现代计算机科学一枚“硬币”的两面。现代计算复杂性理论对经济学理论的启发同样不应被忽视。计算复杂性理论同时对市场和政府的能力设置了边界，可以从不同于经济学的视角为市场与政府的关系提供新的理解。正如“囚徒困境”揭示了个体理性与集体理性间的基本矛盾，“阿罗不可能定理”揭示了社会选择中的基本矛盾，蒙代尔“三元悖论”揭示了开放国家在制定经济政策时必须面对的一种基本矛盾，而均衡计算方面的计算复杂性结论可以从以下新颖的视角对理解市场运行提供有益启发。

　　第一，计算性摩擦。我们知道市场并非在真空中运行，理想中的完全竞争市场在现实中并不存在。市场失灵除市场势力和外部性等原因外，交易成本和信息摩擦等因素也是经济学者经常考虑的现实制约。还有一种经济学者很少能严格建模研究的有限理性，即决策主体计算能力的局限，可称为“计算性摩擦”。市场的有效运行依赖于买卖双方的精打细算，依赖于假设中理想的无穷计算能力。人们在诟病这种完全理性假设时经常表示，不能把市场中的决策主体想象成数学家。针对这种诟病有一种自然的回应，那就是伴随着人工智能的能力提升和广泛普及，市场越来越接近于每个决策者都是数学家。但数学家也并非无所不能。面对足够复杂、规模足够大的问题，很多均衡方面的计算复杂性结果表明，即便每个人都配备了超级计算机，也很可能无法在可接受的时间里计算出均衡策略。现在不能，将来也不能。借助计算复杂性理论，对P问题和NP—难问题（或者PPAD—难问题）做相应的区分，可以帮助经济学者更加深入地理解计算性摩擦在不同场景下对市场运行效率的影响。

　　第二，理性的自负。从算法的视角来看，市场经济是一种分布式算法，而计划经济则是一种中心化算法，需要把所有的私人信息集结起来，通过计算输出生产和分配所有细节。市场经济的效率受计算复杂性理论的约束，而对于计划经济来说，这种约束更加明显。传统上，经济学者对计划经济的批判更多集中于激励和信息，其实计算也是一种重要制约因素。他们一般默认，只要拥有足够强大的超级计算机，计算问题总能解决。由现代计算复杂性理论可知，计算效率是有边界的，有些问题不仅目前的超级计算机无法精确求解，将来很可能也制造不出能够精确求解的新型计算机。所以，即便政府拥有了所有相关信息，即便所有的主体都不存在激励问题，计划经济依然不见得能有效实施。对人类理性抱有不切实际的自负，可能会酿成惨痛的悲剧，这种历史一再重演。该视角对于市场设计以及更广泛的机制设计理论依然有效：某些问题的最优机制可能无法在可接受的时间内精确计算出来，只能务实考虑足够简单的近似最优机制，才可能在现实中顺利实施并达到预期目的。

　　第三，信仰的力量。经济学是一种社会科学，在一定意义上也是一种哲学。任何理论都无法精确适用现实，理论的应用依赖于坚信其具有一定的泛化能力，可以不必在意很多不重要的细节。计算复杂性也是一定意义上的哲学，因为千禧年猜想的P≠NP其实是一种信仰，迄今为止没有人能证明P≠NP，也没有人能证明P=NP。但绝大多数学者都相信P≠NP，这也是前面论述的逻辑起点。多数学者之所以持这种观点而不是相反的观点，是因为相信这个世界是复杂的，若P=NP则这个世界会过于简单过于无趣（堵丁柱）。人类的认知是有边界的，在超出目前认知、理性不该自负的领域，哲学和信仰势必发挥出强大的作用。市场是社会交互的产物，其运行依赖于信念和信仰的互动。对待市场的态度，既不能过度迷信，又要有足够的敬畏。这个世界没那么简单，市场也没那么简单，在没有足够的理论和实践支撑我们对市场进行改造之前，不如对其予以充分信任。历史上有太多惨痛的教训告诉我们，市场本身所产生的无效率和危害，远没有对其缺乏敬畏所产生的危害来得大。

　　市场、经济和社会都是复杂巨系统，对其深入理解和治理都需要系统思维和复杂性思维。计算复杂性理论是复杂性科学中较为成熟且少有的可以完全形式化的一个理论，并已在计算机科学的发展中发挥了基础性作用。计算复杂性理论的基本思想应该引起更多经济学者的关注，从而在计算机科学和经济学两个“帝国主义”的激烈交锋中起到更加重要的作用。

　　2023年8月30日清晨，在山东省荣成市桑沟湾海洋牧场周边的风力发电场，风力发电机映着朝霞、渔船、海洋牧场，源源不断输送绿色能源

　　近年来，江苏省海安高新区社区教育中心为丰富社区退休人员的业余文化生活，坚持从老年人的特点出发，以欣赏—模拟—学创的舞蹈课教学模式，积极探索应对老龄化的舞蹈教学，受到了退休人员的喜爱。

　　2023年8月21日，重庆市梁平区屏锦镇万年社区，错落有致的村庄、金色的稻田、蜿蜒的乡村道路相映成景，勾勒出一幅乡村美丽画卷。

　　光明网联合中国图片社精选中国图片大赛历届获奖作品，以“乡村振兴、共同富裕”为主题，展现乡村振兴新图景。用图片讲好中国故事，以影像传播中国声音。

　　甘肃省张掖市肃南裕固族自治县康乐镇、大河乡、白银蒙古族乡境内的外星谷星际主题地质公园，是联合国教科文组织张掖世界地质公园的重要组成部分。公园总占地面积17.34平方公里,包括游客服务中心及火星谷、水星谷、木星谷、天选大炼钢铁遗址四大景区

　　2023年8月17日，数十只热气球飞舞在甘肃省张掖七彩丹霞景区上空，为游客上演了一场热气球与彩虹山的唯美邂逅。

　　世界自然遗产、世界地质公园、国家5A级旅游景区——三清山位于江西省上饶市东北部，景区内千峰竞秀、万壑奔流、古树茂盛、珍禽栖息，终年云缠雾绕，充满仙风神韵，自古以来便有“天下第一仙山”的美誉。

　　合肥市长江路第二小学栢景湾校区8名少先队员来到某干休所看望抗美援朝老兵郑尊礼，通过聆听战斗故事、参观荣誉史馆等活动，教育引导青少年珍惜现在来之不易的幸福生活，激发青少年爱党爱国的热情，争当新时代的好少年。

　　2023年7月30日，湖北宜昌雨过天晴，三峡大坝附近云雾缭绕宛如画卷，美不胜收。

　　2023年7月27日，江西省瑞昌市武蛟乡，俯瞰蓝天白云下的瑞昌虹源光伏发电站达尔湖场区，排列整齐的太阳能光伏板与周边景致相映成景

　　郁金香花以其特有的徇烂多彩，娇艳妩媚地高雅身姿吸引着无数人的目光，其花也像牵牛花一样，白天舒展开美丽的花瓣，迎风起舞，将最美的身姿展现在人们面前，到了夜晚又好像害羞的姑娘逐渐收拢起多彩的花衣，以待朝阳升起时再一次绽放。

　　2023年7月18日，在安徽省淮北市经济开发区实验学校的足球场上，来自乡村小学的小球员们正在进行足球训练。

　　天津首个数据知识产权交易、一体化综合服务平台上线日，天津首个数据知识产权交易平台、数据知识产权一体化综合服务平台上线仪式在科创中国知识产权服务中心举行。

　　2023年7月17日，山东荣成寻山海洋牧场，养殖工人驾驶船只在云海之间收获江篱，构成耕海牧渔的美景画卷。

　　2023年7月12日，甘肃敦煌雨过天晴，游客在敦煌鸣沙山月牙泉景区观光游览

　　每当幕色降临，晚霞就像一杯泼洒在天空的葡萄酒，把整个黄昏浸在微微的醉意里，光的色彩把原本白色的云染成了血红和金黄色。

　　2023年7月9日，在广西桂林市临桂区四塘镇界牌村，农民正抢抓农时进行晚稻插秧。宛如镜面的稻田与错落有致的民居，构成了一幅美丽的夏日田园画卷。天选团队