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

求问CS系搞的Algorithmic Game Theory/Mechanism Design和经济系搞的Game Theory/Mechanism Design相似处大吗?感觉好奇啊?这是Microeconomics的第二春吗? 本题已加入知乎圆桌 » 日常经济学 · 博弈人生,更多「博弈论」话题讨论欢迎关注
关注者
253
被浏览
12429

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


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


计算机系的呢?开始也说一点这些基础的东西,但是教着教着风格就歪楼了——当然是从经济学的角度看:比如说一个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是机器学习的基础方法,侧重于工程上的算法实现,因为如果应用到大数据分析,通过矩阵乘法的算法复杂度是O(n^3) ,其中n为矩阵的维度,数据增大一点,对算力的消耗会增加很多,但是GD就不存在这个问题,当矩阵乘法无力运算的时候,依然可以没什么障碍的应用到分析中来获取参数。

--------

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


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

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

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


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