上财ITCS主任陆品燕教授：探索算法博弈论的重点与三条主线

 　　原标题：上财ITCS主任陆品燕教授：探索算法博弈论的重点与三条主线

　　2017 年10月19——21日，中国计算机学会学科前沿讲习班（CCF —— ADL）在上海财经大学举办。本期主题是《计算经济学的理论与应用》，邀请了七位来自清华、上海财经大学、上海交通大学、香港大学的计算经济学领域专家以及蚂蚁金服、万向集团的负责人，从计算机经济学（算法博弈论）的基本原理、到拍卖、采购机制设计、区块链及分布式商业，并结合理论在实际中的应用场景进行了详尽的分享和解读。

　　陆品燕是上海财经大学信息学院教授，理论计算机科学研究中心（ITCS）主任。在获得清华大学计算机系博士学位后，他加入微软亚洲研究院，2015年离开微软研究院加盟上海财经大学领衔组建了ITCS。有50余篇科研论文在STOC、FOCS、SODA、EC等顶级计算机理论及博弈论的国际会议和杂志发表，荣获ICALP2007、FAW2010、ISAAC2010等重要国际会议最佳论文奖。2017年担任计算经济学方向重要国际会议WINE 2017的程序委员会主席。他的主要研究方向是理论计算机，并注重与其它学科的交叉，例如与经济学、博弈论交叉后诞生的算法博弈论（algorithmic game theory)，主要关注拍卖理论及机制设计。

　　计算经济学，或称算法博弈论。作为本次课程的首位讲师，他首先作了一个关于算法博弈论的简单介绍，并重点分享了算法博弈论研究中的三条主线。

　　算法博弈论在现实中的应用有如，搜索引擎网址排序、淘宝卖家排序等。总的来说，在市场行为、交通道路设计、导航问题、在线广告拍卖、选举等方面，算法博弈论都能发挥作用。他告诉雷锋网，他认为业界从业者也有必要了解算法博弈论，尤其是上述搜索引擎、电商平台等产品负责人，减少可能的作弊行为，为用户带来更良好的体验。除了主动学习，业界主动引进相关理论人才也是一种选择。此外，陆品燕教授还重点讲解了设施选址问题的机制设计和最佳拍卖机制（optimal competitive auctions）。

　　博弈论的基本要素

　　博弈论的一大基本假设就是，游戏中的玩家或者参与的人是理性的。当然，游戏不一定是字面意义上的游戏，现实中任何涉及到多方不同利益的情况都可以认为是博弈。但事实上人并不理性，例如行为经济学就已经指出这一点。那么什么叫理性的人？这里讨论的不是哲学的理性而是数学的理性。数学的理性是指，当一个人他有很多行为选择的时候，他会有非常强的欲望实现效用函数即收益最大化，或者说成本最小化，并依据此来做出选择。当然，不同的人可能有不同的效用函数或者成本函数，每个人对同一件事情的衡量标准不同，但是决策标准是相同的。这个假设有两个层面，第一层是模拟出个人的效用函数，第二是他总是去最优化函数。

　　第二个重要因素是竞争的环境。这是指同一时间有多个玩家参与博弈，多个玩家都想最优化他们各自的利益，而且他们不同的行为会影响到彼此的利益。

　　所以，博弈论试图分析的就是在一个竞争的环境里面，理性的玩家是怎么选择，行为又会产生什么后果。最简单的例子就是石头剪刀布，收益的关系可以利用类似的矩阵来展示。

　　这里还引入了均衡的概念，博弈均衡是指使博弈各方实现各自认为的最大效用，在博弈均衡中，所有参与者都不想改变自己的策略的这样一种相对稳定、静止的状态。

　　与以前一般的优化问题不同，一般的优化问题总是在寻找最优解或者近似最优解，但在博弈论中很难找到全局最优，每个玩家希望最大化自己的收益，但是处在有很多玩家的竞争环境，所以它的解一般是用均衡或者稳态来描述。稳态的意思是，大家卡在一种状态，谁也不想离开这个状态，因为单独离开对他没有好处。但实际上，这样的稳态也有一些问题，比如说囚徒困境。

　　还有一个问题是，在一个定义了每个人的效能函数，或者成本函数的博弈中，稳态是不是总是存在。

　　冯诺依曼在1928年的时候就证明，如果是在两个玩家参与，并且是类似石头剪刀布的零和博弈（两个玩家完全对抗，效能函数之和是定值或0）的情况下，稳态总是存在的，而且用比较简单的线性规划方法来找到。而在其他更复杂的，如多个玩家、不是零和博弈的情况下，纳什证明稳态也总是存在，就是所谓的纳什均衡。

　　算法博弈论简介

　　在传统博弈论中，涉及的玩家很少，只有两三个，但当竞争环境变得非常复杂，比如资本市场，传统博弈论就不太适配。而算法有一个重要特性就是复杂性，在加入复杂性这个维度后的博弈论，玩家行为会更加多元化，这也是算法博弈论研究的重点。

　　刚刚提及，博弈论认为，模拟出来后的最终状态应该是稳态，如果这是很简单的游戏，基本有预测能力。但当系统非常大时，还能不能做这样的预测？

　　从纯粹博弈论的角度来说，肯定可以，比如能够证明纳什均衡的存在。但在实际中，研究者能否有效地计算出均衡呢？如果计算不出，那么就不能进行有效的预测。

　　还有一个更深刻的问题，理论上的预测能否出现在现实中。当计算机都不能算出均衡的时候，市场为什么就能达到这个均衡？如果不能达到，预测有何意义？这些都是系统变得越来越复杂时，我们需要去研究和回答的。

　　算法博弈论在现实中应用包括公共基础设施规划、电商平台、车牌拍卖。实际上，我们可以通过算法和策略设计博弈。比如车牌拍卖，各地根据不同的需求设计不同的规则，需求可能是控制数量，减少污染；或者保持公平性。博弈的规则会影响玩家的效能函数。

　　归纳来说，算法博弈论或者计算经济学是从计算机科学的维度来研究博弈论，包括可计算性、复杂性、算法设计的角度。

　　算法博弈论三个主线

　　1、研究的是博弈论、经济学中的计算问题，包括复杂性等，博弈论为计算机科学提供了一些新问题。

　　第一个问题，经济学告诉我们，纳什均衡和市场均衡总是存在，那么如何计算平衡？这一类计算平衡问题不同于以往研究方向：判定问题或者优化，对应不动点计算，给计算机科学创造了新的计算问题和计算复杂类。

　　第二个问题更像优化问题。但是传统的优化问题约束、目标函数可知。但是在博弈的最优策略的时候，不止是一个方案，除了自己的想法，还要预测对方的行为，是一个交互式的过程。

　　现实中的问题有，如何给商品定价以达到利益最大化。比如苹果怎样给新发布的产品定价。市场调查可以得到预期反馈，包括价格和购买人数。如果只有一个产品，我们只要研究需求曲线基本就可以了。但是在产品配置不同，定价也不同的时候，如何能让高价产品有足够多的消费者，如何让低价产品不至于出现太高性价比吸引走原高价产品的客群等。传统的优化问题就是，定完价格、分配方式，收益是确定的。但是博弈情况下，需要预测潜在买家对于不同的价格策略有什么反馈。

　　第三个问题，如何计算合作博弈中的“核”(Core)及沙普利值(Shapley value)。合作博弈是指一些参与者以同盟、合作的方式进行的博弈，博弈活动就是不同集团之间的对抗。

　　2、本质上是算法设计、优化问题，但是考虑到众多理性人和竞争环境，传统的算法设计就变成了机制设计问题。机制设计被称作“经济学中的工程学”，因为大多数的经济学研究是去解释世界，而机制设计是设计。

　　在竞争环境下，设计的算法运行实际效果可能并没有那么好。例如搜索引擎和淘宝商家排名。比如搜索引擎的PageRank网页排名，是由Google发明的一种由根据网页之间相互的超链接计算的技术，Google用它来体现网页的相关性和重要性。算法会根据用户的搜索关键字匹配网页，而一些公司就开始利用这种规则，衍生了一种专门的职业——SEO，搜索引擎优化。工程师通过一些技术手段，彼此增加链接或者在页面上使用隐形的关键词，使得搜索引擎的算法认为该网页与关键字的匹配度很高，这样就破坏了PageRank和页面排名的初衷。

　　类似的也体现在淘宝卖家。他们会通过刷信誉刷销量等方式提高自己的排名。而这些，是背后公司和用户都希望杜绝的。

　　这些都有一个共同点：设计者并不能掌握网页或者卖家的信息，即无法掌握所有的输入信息真实性。第二，输出的结果能否真实实现也是不能确定的。

　　在与这些理性或者说自私的玩家进行交互的时候，简单的算法设计就变成了机制设计问题。不仅需要满足计算机科学方面的有效性要求等，还需要满足从博弈论的角度，考虑用户的反馈。这是在网络时代，特别网络经济时代非常重要的。

　　3、引入计算机视角，研究对象还是博弈系统。

　　举一个例子，比如研究经济学中的纳什均衡。从社会福利方面来看，经济学其实很早就知道不一定最优，比如囚徒困境。但之前经济学只能确定，哪一类博弈是最优或者不是最优的，计算机科学有近似比的概念，当它不是最优的时候，可以研究是否是近似最优，于是引入了最差均衡效率(PoA)等。

　　这也体现在宏观看市场调节是否有效方面。在某些领域，市场充分竞争的最后，整体的社会利益是一个非常好状态。但是在另外一些领域，彼此的恶性竞争可能就会失效，整个社会在非常不好的状态，于是会研究是否需要政府干预走出这个博弈。

　　所以，我们引入了近似比的概念来衡量它多不好，因为有些不是最优的情况能够接受，有些不是最优的情况可能相差太大，需要改变。

　　第二从时间的角度来研究有效性。纳什均衡是玩家不断改变自己的策略，以至于最终慢慢收敛到一个动态平衡的结果。也就是说这是一个动态的过程，这个动态过程是不是趋向于稳态或者很快的趋向于稳态。如果纯粹从数学方面来说，一般得出的结论是最终会收敛，

　　那么在不同动态的假设中，收敛究竟会多快呢，比如它是不是在一个多项式时间里收敛到纳什均衡，这也是计算机科技引入的新概念。以前经济学只研究收敛或不收敛，但是在现实中这个区别非常重要。如果能够很快收敛，他们的行为可能与现实比较相符。如果动态非常慢，你可能可以假设，系统还处在动态变化的过程，另一个方向就是，可否去干预该系统，使它能够比较快的收敛。

　　附提问：

　　提问：当用户面临信息过载的情况，面对传统经济学的理性人假设可能就不是很适用，这是否超出了计算经济学的研究上限？

　　回答：这是一个很好的问题。我们假设每个用户最优化自己的效能函数或者成本，当用户在一个复杂的系统中，可能出现信息过载，以至于用户没有收集到足够的信息，或者是没有足够的可能计算能力。这样他无法算清什么是最优。实际上，在传统的博弈论中也有有限理性的假设，比如计算能力有限等，这也是计算经济学一个重要的研究方向。