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

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

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

计算机系的呢？开始也说一点这些基础的东西，但是教着教着风格就歪楼了——当然是从经济学的角度看：比如说一个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搞得，更关注的点比较不一样吧。