2017年10月19-21日，中国计算机联合会前沿研讨会在上海财经大学举行。本期的主题是计算经济学的理论与应用。邀请了清华、上海财经大学、上海交通大学、香港大学的7位计算经济学专家，以及蚂蚁金服、万向集团的负责人，结合理论的实际应用场景，对计算机经济学、拍卖、购买机制设计、区块链、分布式商务的基本原理进行了详细的分享和解读。
陆上海财经大学信息学院教授，理论计算机科学研究中心主任。在清华大学获得计算机科学博士学位后，他加入了微软亚洲研究院。2015年，他离开微软研究院，加入上海财经大学，领导ITCS的成立。在STOC、FOCS、SODA、EC等计算机理论和博弈论的顶级国际会议和杂志上发表了50多篇科研论文。，并获得ICALP2007、FAW2010、ISAAC2010等重要国际会议的最佳论文奖。2017年担任计算经济学重要国际会议WINE 2017的程序委员会主席。主要研究方向是理论计算机，注重与其他学科的交叉，比如算法博弈论，就是在与经济学、博弈论交叉后诞生的。
没有参加过CCF线下课程的朋友不用担心。AI海量开放在线课程学院，雷锋网人工智能培训平台。com，获得CCF独家网络视频版权。观看本次工作坊完整视频+PPT可盖章:http://www.mooc.ai/course/193.再现各路专家现场授课交流的场景。
以下为鲁教授演讲原文，由雷在不改变原意的情况下编辑:
博弈论的基本要素
博弈论的一个基本假设是，博弈的参与者或参与者都是理性的。当然，游戏不一定是字面意思的游戏。现实中，任何涉及多方不同利益的情况，都可以看作是一场博弈。但事实上，人们并不理性，行为经济学已经指出了这一点。那么什么是理性的人呢？这里讨论的不是哲学的合理性而是数学的合理性。数学理性是指当一个人有多种行为选择时，他会有非常强烈的愿望去实现效用函数，即利润最大化，或者成本最小化，并据此做出选择。当然，不同的人可能有不同的效用函数或成本函数。每个人对同一件事的标准不同，但决策标准是一样的。这个假设有两个层次。第一个层次是模拟个人的效用函数，第二个层次是他总是优化函数。
第二个重要因素是竞争环境。这意味着有很多玩家同时参与游戏，很多玩家都想优化各自的利益，他们的不同行为会影响彼此的利益。
所以博弈论试图分析在竞争环境下，理性的玩家如何选择，他们的行为会产生什么后果。最简单的例子就是石头剪子布，收入之间的关系可以用一个类似的矩阵来表示。
这里也引入了均衡的概念。博弈均衡是指所有参与者都不想改变策略的相对稳定的静态状态，在这种状态下，所有参与者都实现了自己的效用最大化。
与以往的一般优化问题不同，一般优化问题总是在寻找最优解或近似最优解，而在博弈论中很难找到全局最优解。每个局中人都想最大化自己的利润，但又是在多人竞争的环境中，所以其解一般用均衡或稳态来描述。稳态就是大家都卡在一个状态，谁都不想离开这个状态，因为一个人离开对他不好。但实际上，这样的稳定状态也存在一些问题，比如囚徒困境。
另一个问题是，在一个定义了每个人的绩效函数或成本函数的博弈中，稳态是否总是存在。
冯·诺依曼在1928年证明，如果有两个玩家参与，而且是像石头剪子布一样的零和游戏，稳态总是存在的，通过简单的线性规划方法找到了稳态。在其他更复杂的情况下，比如多人非零和博弈，纳什证明了稳态总是存在的，这就是所谓的纳什均衡。
算法博弈论导论
在传统的博弈论中，只有两三个参与者参与，但是当竞争环境变得非常复杂时，比如资本市场，传统的博弈论就不适用了。然而，算法的一个重要特征是复杂性。在博弈论中加入复杂性后，玩家的行为会更加多样化，这也是算法博弈论研究的重点。
刚才提到，博弈论认为模拟后的最终状态应该是一个稳态。如果这是一个很简单的游戏，基本上是预测性的。但是当系统非常大的时候，还能做出这样的预测吗？
从纯博弈论的角度来看，肯定可以，比如可以证明纳什均衡的存在。但在实践中，研究人员能有效地计算出均衡吗？如果不能计算，那么就不能有效预测。
还有一个更深刻的问题，理论预测能否出现在现实中。为什么计算机计算不出来，市场却能达到这个均衡？如果没有，预测有什么意义？这些都是在系统越来越复杂的情况下，我们需要研究和回答的。
博弈论在现实中的应用包括公共基础设施规划、电子商务平台和车牌拍卖。其实我们可以通过算法和策略来设计游戏。比如车牌拍卖，根据不同的需求设计不同的规则，需求可能是控制数量，减少污染；还是维护公平。游戏规则会影响玩家的表现功能。
综上所述，算法博弈论或者说计算经济学是从计算机科学的维度来研究博弈论，包括可计算性、复杂性和算法设计。
算法博弈论的三条主线
1.我们研究博弈论和经济学中的计算问题，包括复杂性。博弈论为计算机科学提供了一些新的问题。
第一个问题，经济学告诉我们纳什均衡和市场均衡总是存在的，那么如何计算均衡呢？这种计算平衡问题不同于以往的研究方向:判断问题或优化，计算相应的不动点，为计算机科学创造了新的计算问题和计算复杂性类别。
第二个问题更像是一个优化问题。但是传统的优化问题有约束和目标函数。但在博弈的最优策略中，它不仅仅是一个计划，更是一个除了自己的想法之外，预测对方行为的互动过程。
真正的问题是如何给商品定价以实现利润最大化。比如苹果如何给新发布的产品定价？市场调查可以得到预期的反馈，包括价格和购买者数量。如果只有一种产品，我们只需要研究基本需求曲线。但是当产品配置不一样，定价不一样的时候，如何才能让高价产品有足够的消费者，如何才能让低价产品不要有太高的性价比来吸引原来高价产品的客户？传统的优化问题是在设定价格和分配方式后，收益是一定的。但在博弈情境下，需要预测潜在购买者对不同价格策略的反馈。
第三个问题是如何计算合作博弈中的“核心”和shapley值。合作博弈(Cooperative game)是指一些参与者以联盟和合作的形式进行的博弈，博弈活动是不同群体之间的对抗。
2.本质上是一个算法设计和优化的问题，但是考虑到很多理性人和竞争环境，传统的算法设计就变成了机制设计的问题。机制设计被称为“经济学中的工程”，因为大多数经济学研究都是为了解释世界，机制设计就是设计。
在竞争环境下，设计出来的算法实际效果未必那么好。比如搜索引擎和淘宝商家排名。比如搜索引擎的PageRank排名，这是Google发明的技术，是根据网页之间的超链接来计算的。谷歌用它来反映网页的相关性和重要性。算法会根据用户的搜索关键词来匹配网页，一些公司开始利用这个规律，产生了一个专门的职业——SEO，搜索引擎优化。工程师通过一些技术手段在页面上互相添加链接或者使用看不见的关键词，使得搜索引擎的算法认为网页和关键词的匹配度非常高，从而破坏了PageRank和页面排名的初衷。
类似的还体现在淘宝卖家身上。他们会通过刷信誉、刷销量来提升排名。这些都是背后的公司和用户想要消除的。
这些都有一个共同点:设计师无法掌握网页或者卖家的信息，也就是无法掌握所有输入信息的真实性。其次，输出结果能否真正实现也不确定。
当与这些理性或自私的玩家互动时，简单的算法设计就变成了机制设计问题。不仅要满足计算机科学中有效性的要求，还要从博弈论的角度考虑用户反馈。这在网络时代，尤其是网络经济时代是非常重要的。
3.引入计算机视角，研究对象仍然是游戏系统。
比如学习经济学中的纳什均衡。从社会福利的角度，经济学早就知道不一定最优，比如囚徒困境。但之前，经济学只能决定哪种博弈最优与否，计算机科学有近似比的概念。当它不是最优时，它可以研究它是否近似最优，所以它引入了最差均衡效率。
这也体现在宏观上市场调节是否有效。在一些领域，在充分市场竞争结束时，社会整体利益处于非常好的状态。而在其他领域，相互之间的恶性竞争可能会失败，整个社会处于非常糟糕的状态，所以我们会研究是否需要政府干预才能走出这个博弈。
所以我们引入近似比的概念来衡量有多差，因为有些非最优的情况可以接受，有些非最优的情况可能相差太多，需要改变。
第二，从时间的角度研究有效性。纳什均衡是参与者不断改变策略，从而最终收敛到一个动态均衡的结果。也就是说，这是一个动态的过程。这个动态过程是趋于平稳还是快速？如果是纯数学的，一般结论是最终会收敛，
那么在不同的动态假设下会收敛到多快，比如是否在一个多项式时间内收敛到纳什均衡，这也是计算机技术引入的新概念。以前经济学只研究收敛或者不收敛，但现实中这种差异很重要。如果他们能快速收敛，他们的行为可能会更符合现实。如果动态很慢，你可能会假设系统还在动态变化的过程中，另一个方向就是你能不能干预系统使其收敛得更快。
带着问题:
问题:当用户面临信息过载时，传统经济学中的理性人假设可能不太适用。这是否超出了计算经济学的研究极限？
回答:这是个好问题。让我们假设每个用户优化自己的性能函数或成本。当用户处于一个复杂的系统中时，可能会出现信息过载，使得用户没有收集到足够的信息，或者没有足够的可能计算能力。所以他想不出什么是最优。实际上，传统博弈论中也存在有限理性假设，比如计算能力有限，这也是计算经济学的一个重要研究方向。
