Algorithmic Game Theory 和经济学中的 Game Theory 相似度大吗？

Algorithmic Game Theory（算法博弈论）和经济学中的 Game Theory（博弈论）之间的关系，可以用“一脉相承，又各有侧重”来形容。它们之间有着极其深厚的渊源，可以说，前者是在后者基础上发展起来的，但又因为其关注的领域和工具的差异，形成了鲜明的特色。

深厚的渊源：共同的语言和思想

首先，它们最核心的相似之处在于，都使用了“博弈论”这套数学语言和思维框架来分析理性个体之间的互动。无论是经济学家还是计算机科学家，在研究这类问题时，都会用到诸如：

策略 (Strategy): 每个参与者可以选择的行动集合。
支付 (Payoff): 在不同的策略组合下，每个参与者获得的收益或损失。
纳什均衡 (Nash Equilibrium): 一种稳定的状态，在这种状态下，任何一个参与者单方面改变自己的策略都不会获得更好的结果。这是博弈论中最核心的概念之一。
信息结构 (Information Structure): 参与者对彼此的策略、支付或行动的了解程度。
完美信息博弈 vs. 不完美信息博弈: 参与者是否知道所有先前的行动。
合作博弈 vs. 非合作博弈: 参与者是否可以形成有约束力的协议。

这些基本概念和分析工具，在经济学博弈论和算法博弈论中都是通用的。经济学博弈论的先驱们，如约翰·纳什，约翰·冯·诺依曼等，为我们提供了研究战略互动的基石。

经济学博弈论：侧重于理解和预测现实经济现象

经济学中的博弈论，其主要目标是：

解释和预测经济行为： 为什么公司会形成卡特尔？为什么拍卖会有不同的策略？为什么国家之间会发生贸易战？经济学博弈论用博弈论的工具来分析这些问题，试图理解市场失灵、合作与竞争的动态，以及经济制度的设计。
建模经济市场： 股票市场、商品市场、劳动市场等都可以被看作是复杂的博弈。经济学家会构建模型来分析这些市场的效率、稳定性和参与者的行为。
设计经济机制： 如何设计一个有效的拍卖机制来最大化卖家的收入？如何设计一个投票系统来反映民意？经济学博弈论在机制设计领域扮演着至关重要的角色。
理解人性的局限： 虽然理性是基础，但经济学博弈论也常常讨论有限理性、认知偏差如何影响博弈结果。

经济学博弈论的研究往往更侧重于定性分析和理论推导，也包含一些基于现实数据的实证研究。它试图揭示经济世界背后深层的“规则”。

算法博弈论：侧重于设计和分析计算系统中的博弈

而算法博弈论，顾名思义，是在计算机科学的背景下，将博弈论的思想和工具应用到计算系统的设计和分析中。它关注的核心问题是：

计算效率 (Computational Efficiency): 寻找博弈的均衡（如纳什均衡）在计算上是否可行，以及找到它的复杂度如何？是否存在多项式时间算法来计算均衡？
激励兼容性 (Incentive Compatibility): 在一个由理性但可能“自私”的计算单元（例如，分布式系统中的节点，互联网用户）组成的系统中，如何设计一个协议或算法，使得即使每个单元都追求自身利益最大化，最终也能达到一个全局最优或者接近最优的结果？
机制设计在计算场景的应用： 如何设计算法来解决计算资源的分配、信息共享、网络路由、在线广告拍卖等问题？例如，在分布式系统中，如何设计一个奖励机制，让诚实地报告信息的节点获得更多收益？
算法的鲁棒性 (Robustness): 在一个存在“恶意”参与者（例如，网络攻击者）的环境中，算法的性能如何？
博弈的“不可靠性”(Price of Anarchy/Price of Stability): 在一个分布式系统中，即使所有参与者都遵循最优策略，但由于它们各自的“自私”行为，最终的系统效率可能会比中心化最优方案差多少？这是算法博弈论中一个非常重要的概念。

关键的差异与拓展

虽然渊源深厚，但算法博弈论相较于经济学博弈论，有几个显著的侧重点和拓展：

1. 计算复杂性是核心考量： 经济学博弈论通常关注的是“是否有均衡”或者“均衡的性质”，而算法博弈论则进一步追问“能否高效地计算出均衡？”“计算均衡的难度有多大？”。这使得算法博弈论特别关注那些具有计算效率的均衡概念，例如近似纳什均衡（approximate Nash equilibrium）或结构化均衡。
2. 从“预测”到“设计”的侧重转变： 经济学博弈论更多地扮演一个“解释者”的角色，试图理解和预测现实世界中的经济现象。而算法博弈论则更侧重于“设计者”的角色，利用博弈论的原理来设计出更有效、更公平、更鲁棒的计算系统和协议。
3. 对“大规模”和“分布式”系统的关注： 算法博弈论的研究对象往往是互联网、分布式计算系统、社交网络等规模庞大、参与者众多的场景。这与经济学博弈论研究的有限参与者模型有所不同，对算法的可扩展性提出了更高的要求。
4. 引入了新的均衡概念和评价标准： 除了经典的纳什均衡，算法博弈论还引入了诸如粗糙纳什均衡 (correlated equilibrium)、伪纳什均衡 (pseudoNash equilibrium)、囚徒困境的迭代次数等概念，并且更强调“可计算性”和“算法复杂度”作为评价一个博弈论模型好坏的标准。
5. “价格的无政府状态”(Price of Anarchy, PoA) 和“价格的稳定性”(Price of Stability, PoS): 这是算法博弈论中非常核心的衡量标准。PoA衡量的是在所有纳什均衡中，最差的均衡带来的系统效率损失；PoS衡量的是最好的纳什均衡带来的系统效率损失。这些概念直接量化了“自私”行为对系统整体性能的影响，这在经济学博弈论中虽然也有类似的讨论，但没有被如此系统化地量化和作为算法设计的重要依据。
6. 与人工智能的交叉： 随着机器学习和人工智能的发展，算法博弈论在强化学习、多智能体系统、博弈式学习等领域与AI研究产生了深刻的交叉。例如，如何让AI代理在与他人交互时学会合作或竞争，如何设计能够抵御对抗性攻击的AI系统等。

总结一下，可以说：

共同点： 都使用博弈论的数学语言和核心思想来分析理性个体间的战略互动。
不同点：
应用场景： 经济学博弈论关注经济系统，算法博弈论关注计算系统。
核心目标： 经济学博弈论侧重于解释和预测，算法博弈论侧重于设计和分析计算效率。
关键工具： 算法博弈论将计算复杂性、算法效率、PoA/PoS等计算概念引入博弈论分析。

所以，它们之间的关系不是“替代”，而是“延伸”和“专业化”。算法博弈论是在经济学博弈论的基础上，根据计算机科学的独特需求和工具，进行了重要的拓展和深化。就好像物理学中的经典力学和量子力学，后者是在前者基础上，为了解释微观世界的现象而发展出来的更普适的理论，但也保留了经典力学的许多核心思想。

计算机系的博弈论教的就和经济系不一个路子。

经济系的博弈论课，本科和研究生的课程都是很有意思的，就是大家平常喜闻乐见的囚徒困境啊，蜈蚣博弈啊，动态博弈啊什么的，一般都是会用人或者公司来做例子，代入一个商业场景或者互动场景，来说明博弈的结果是什么样的，大家就看着一个个四小方格，每个方格两个数字，然后挪来挪去不亦乐乎。即便是到了博士阶段，大家都开始黑化了，看的写的文章里出现各种希腊字母的花符号，但是一般目标也是在琢磨均衡的存在性、均衡时的性质和实施这个均衡的策略。

计算机系的呢？开始也说一点这些基础的东西，但是教着教着风格就歪楼了——当然是从经济学的角度看：比如说一个simple market，有A个seller，B个buyer，经济系就会说，你看这是一个典型的mechanism design的问题 （完全信息下，这个问题可以缩减为一个局部的供需均衡），每个人都有自己的信息空间和禀赋，我们要先证明存在一个均衡，然后描述出这个均衡的若干特征…… 然后计算机系考虑的就是另外的事情了，他们用图论！用seller和buyer组建了一个max-flow network，比如下面这样的：

考虑这个商品的flow从哪几个buyer流向哪几个seller？用什么样的算法能够做到市场出清？怎么才能最快的达到有效的分配这些商品？如何最快的确定均衡价格？

还有，我计算这个均衡的时间复杂度最低可以是多少？然后我用一个什么算法能够实现它？经济系讲博弈论，里面的人叫做agent或者player，计算机系讲起来，里面没有人，只有一个个的node^_^

--------

再说一下implementation，这个词在经济学和计算机科学里面的内涵也有微妙的差别，经济学的implementation是说mechanism，但是计算机系的implementation用的是algorithm。同一个均衡，经济系说起来implementation那就是我们设计一个机制，比如说让委托人提供一个什么样的合同，然后代理人如何回应，最后这个机制刚好实施了我们证明出来的均衡；而计算机系的implementation则是，我如何设计一个算法，当我遇到这一类情况的时候，计算机能够按照我设计的算法，一步步的把这个均衡推导出来。

--------

其实机器学习里面的梯度下降（Gradient Descent）和计量经济学的线性回归（OLS）的区别也可以看出双方思路的差异。如果数据理想的话，两者应该能得到差不多的参数结果。

OLS估计是数据分析的基础方法，计量经济学传统上更侧重于数学上的严谨求OLS的解析解，如果数据集相对比较小，性质很理想，矩阵转置相乘得到的参数从数学上保证就是统计上的无偏估计，但是GD就不能，无论学习多少次，都是在无限的逼近最优的参数。

而GD是机器学习的基础方法，侧重于工程上的算法实现，因为如果应用到大数据分析，通过矩阵乘法的算法复杂度是 ，其中n为矩阵的维度，数据增大一点，对算力的消耗会增加很多，但是GD就不存在这个问题，当矩阵乘法无力运算的时候，依然可以没什么障碍的应用到分析中来获取参数。

--------

前不久刚刚发生的一件事，也可以作为注脚。

那时候我邀请了一个专门做契约理论的朋友来我们院做一个seminar talk，于是他就讲了最近的一篇关于cheap talk的文章，研究当商品拥有垂直和水平差异的时候，卖家和买家通过cheap talk交换商品信息最后能得出的均衡，并且定义了该均衡的一些有趣的性质……非常标准的一篇应用博弈论的工作论文。

然后到了提问环节，其他经济学背景的教授和助理教授们也踊跃发言，大家讨论的你来我往不亦乐乎。直到一位同事说：

“嗯……请问这个模型有没有什么算法上的启示呢，或者说，有什么算法可以实现它呢？”

背景介绍：这位同事是计算机科学的博士学位，做的方向就包括algorithmic game theory。

感觉最不一样的部分应该是实用性吧，比如纳什均衡的求解是个NP问题这个已经被证明过了，那么如果一个Game里不存在Pure Nash Equilibrium的话，在CS里面用处就不大了吧；同理，Price of Anarchy这种问题肯定是CS的人更在乎啊。经济系搞的东西跟CS搞得，更关注的点比较不一样吧。