您的位置:首页

详情

专注算法博弈论研究 推动计算经济学发展——国家“千人计划”特聘专家邓小铁教授

2018-01-05

计算经济学(Computational Economics)是一门涉及计算机科学、经济学、数学、博弈论、社会科学等领域的交叉学科。网络,特别是互联网经济的发展,是计算经济学发展的一个重要推动力量。一方面,传统的经济形式和商业模式在网络时代已经发生了许多变化,经典的经济学理论需要不断地被检验和修正,从而产生新的经济学理论。另一方面,随着分布式系统、网络以及云计算等技术的发展,一个计算任务的完成往往需要多方合作,这就要求计算机协议或算法设计不仅要满足有效性、容错性等传统需要,还要考虑博弈论和经济学的约束。特别是在大规模网络环境下,个人自利行为的相互制约与系统机制的整体约束已经成为虚拟社会、经济系统以及互联网经济在成长过程中保持稳定的一类重要因素。由此,算法博弈论脱颖而出,人们可以利用它来研究在大规模网络环境下,人与人、人与网络的交互系统以及人与市场规则相互作用下的规律。

过去五年任职于上海交通大学致远学院的邓小铁教授长期从事算法博弈论研究、均衡计算和机制设计、互联网广告系统以及云计算定价及资源分配等研究课题。他从多个角度开展了以计算复杂性方法论研究博弈理论的工作,在某些方向上远远早于整个领域的觉醒:将计算复杂性定义为合作博奕论不同解之间合理性评价的关键因素,推进计算复杂性作为研究竞争市场中市场均衡定价与分配的方法论,建立金融市场摩擦因子及套利计算复杂性的关联,发现优化管理框架中广度和深度对决策计算难易的不同影响(扁平化)。他还长期坚持系统性地研究计算与经济金融学之间的关联性,从复杂性和快速算法以及社会效益的优化考虑来设计组合拍卖的算法、序列拍卖的定价、公共产品的设置、在线广告经济学分析等。

他针对经济学至关重要的博弈计算,对其数学关键基础不动点计算的方法论进行了深入研究,进而彻底解决了非合作博弈纳什均衡的计算复杂性。目前,邓小铁教授致力于推广“激励比”概念,用以刻画参与者针对经济学传统均衡理论的策略行为所带来的效益增加,对参与者进行激励分析研究,揭示均衡理论稳定性的缺陷并探讨这种行为模式下的更深一度空间的均衡存在分析和计算研究。更是基于大数据获取的高效率智能分析的广泛应用,将贝叶斯分布下经济学决策行为与统计分析确认分布的两阶段衔接,揭示最优拍卖原理的缺陷。从大数据科学基本原理上,探寻贝叶斯决策与其大数据统计推断的相容性。

一、二人博弈计算

冯·诺伊曼通过零和博弈的最小最大定理(1928年)开创博弈论并以此刻画人类经济行为。均衡概念描述的是所有博弈者均不愿独自改变当前策略的一种稳定状态。通过纳什的均衡在相当广泛环境下普遍存在的证明(1950年),以及阿罗(Arrow)的市场均衡存在性证明(1954年),博弈论得到了数理经济学研究的认可和广泛采纳。

纳什已知三人博弈的精确解中有无理数解,使其精确计算不能在有限步实现。Dantzig在数学规划领域的成就,特别是对线性规划和二人零和博弈的等价性证明(1951年),将二人零和博弈论归结到多项式时间可计算的算法复杂性类P,而遗留下二人非零和博弈的计算成为一个数理经济学和运筹学从Dantzig的工作以来瞩目的未决难题。但因为二人非零和博弈均衡解是有理数,类似的线性规划问题已有多项式解,学界的期盼是能找到多项式算法。

这一跨学科难题得以解决的动力、模型、方法和技巧分别来自于人工智能多智能体系统发展的需求、计算机科学对均衡计算的理论刻画,以及对不动点理论数学规律的深度分析。多智能系统的兴起让Kearns将博弈论中的策略和合作提升到决定性的理论框架的重要地位(2002年)。Papadimitriou对均衡计算复杂性的刻画借鉴Lemke Howson道路跟随算法计算二人博弈精确解特点,提出了PPAD完全类(1994年)并证明了许多PPAD完全类的问题。下一个突破性进展是Daskalakis等在多于3人博弈情形下,纳什均衡的计算问题属于PPAD完全类(2005年)。陈汐和邓小铁教授通过推动多项不动点模型计算复杂性研究最终将二人博弈纳什计算问题完整解决(2006年)。这项二人博弈均衡计算PPAD完全类的工作成为算法博弈论理论框架中的标志性成果。

这项成果从不同角度推动了计算机领域对经济学方法论的反思,也促醒了邓小铁教授重新探讨基于大数据环境的互联网经济学理论的新思维。

二、大数据收集和学习对市场机制理论的挑战

互联网市场的兴起,使得市场参与者的行为轨迹得以通过数据充分展示出来。参与者的私有信息、偏好行为和预算高低都可以在商业活动中学习、增加、了解。他们的策略行为可以使信息不对称的对手方,对他们的信息产生偏离,导致定价机制偏离设计初衷。

以市场均衡(Market Equilibrium)为例。根据买家的效用函数以及投入市场的预算,市场达到均衡能实现个人效用最大化,同时市场商品得到充分使用。然而赫维茨(诺贝尔奖得主)发现市场参与者利用效用函数是私有信息、不为他人所知的客观条件,有意识地谎报自己的效用函数,或按照错误效用函数采取相应行动,以此来影响市场均衡下商品的定价与分配,进而改进自己的收益。

为了有效地刻画博弈者效用的增加程度,邓小铁教授与他的研究团队引入“激励比(Incentive Ratio)”概念,即策略行为带来的最大效用与汇报真实效用函数时所得效用之比,并针对Fisher市场中不同类型的效用函数,分别计算均衡下各自的激励比。他们证明得出线性效用函数时,谎报效用函数策略的激励比等于2;Cobb-Douglas函数时,激励比改进为1.445;Leontief效用函数时,激励比为2。弱弹性替代函数(Weak Gross Substitute)这一类广泛的效用函数,激励比也等于2。在这样的激励比下,策略性行为即使在市场均衡下也非常有效。在电子商务环境中,这成为程序性博弈可能的理论依据,如互联网黑产的形成。

互联网市场最有效的方法是拍卖,而拍卖是一个买家与买家之间、买家与卖家之间的博弈过程。可信的拍卖机制使得在整个拍卖过程中每位买家真实汇报自己的心理预期价值,成为研究拍卖机制设计的圣杯。迈尔森(Myerson)提出“显示原理(Revelation Principle)”,并给出买家价值分布为共同知识下的最优拍卖机制。买家价值的概率分布为众人所知的状态是理想状态。在现实中,买家完全可以在多轮拍卖中通过不断改变自己的报价来影响真实的报价概率分布,进而影响迈尔森最优拍卖机制的分配与定价。这成为数据科学的兴起和大规模拍卖互联网市场形成,对经济科学完整性的挑战。

邓小铁及其团队考虑买家在多轮拍卖中的报价行为对迈尔森最优拍卖机制的影响,将贝叶斯分布下经济学决策行为与统计分析确认分布的两阶段衔接,揭示最优拍卖原理对于数据分布的依赖:如在均匀分布拍卖市场,拍卖者对分布的学习无法达到最优拍卖收益,但能够在人数增多时接近于古典最优拍卖的收益。买家隐藏真实分布的策略行为使他们达到双倍的效用函数值。

三、算法博弈论在互联网中的应用

无线通信技术与互联网技术的高速发展造就了点对点(Peer-to-Peer,P2P)网络系统,如BitTorrent成功地运用这种技术,实现信息资源的共享与连接。分析其原理,通俗说来便是上传越多的资源,则可以下载越多资源。比例反应协议就是用来设计刻画这种特性的,即参与者分配给邻居的带宽量,与它从该邻居处获得的带宽量成一定比例。比例反应协议的重要意义在于,如果将点对点网络上的带宽交换视为一类特殊的Arrow-Debreu市场模型,那么该协议最终的资源分配结果与市场均衡一致。在网络服务交换被认为是合作、竞争和公平集为一体的好协议。然而,上述的针对市场均衡的策略性行为是否可能实现成为重要挑战。邓小铁教授团队针对常见的策略行为——屏蔽IP地址和隐瞒带宽量,讨论市场均衡机制的可信性,证明了这类有广泛应用价值的市场均衡下对于删边或谎报权重的策略行为,市场均衡机制却为可信机制,相关结果也在算法博弈论国际研讨会和人工智能会议国际人工智能联合会议进行了报告。这也和BitTorrent协议的优良实用效果相呼应。

邓小铁对均衡计算和机制设计推动互联网经济和科技金融的作用抱有重大期望。他看到中国互联网的超越性发展在时时刻刻产生着需要新算法、新设计、新理论去解决的新问题。他认为创新的经济发展环境需要创新学科发展,有需求就会造就跨学科的人才,并造就创新型的科学研究。他为互联网和金融科技公司做过机制设计和博弈分析以及金融科技的咨询顾问和技术支持。这些工作对他在研究中产生创新元素具有极大的影响。他鼓励学生,成长中的创新科技将成为原创性科学研究的重要源泉。真切期望我们的科研发展能协同经济发展共同引领科技明天。

专家简介

邓小铁,博士,美国计算机协会会士(ACM Fellow),千人计划特聘专家。1997年回到香港城市大学,2012—2017年任上海交通大学致远学院讲席教授,2018年将正式加入北京大学。主要科研方向为算法及博弈论、互联网经济、在线算法、并行计算等。2008年凭借在博弈论算法方向的贡献获选美国计算机协会会士。近期研究兴趣包括算法博弈论研究、均衡和机制设计、互联网广告系统、云计算定价及资源分配、社交网络行为分析及推荐系统、交通及物流网络算法。作为项目负责人,曾承担加拿大、中国香港、英国、国家基金委及国家科技计划等十几项科研项目。发起网络经济学国际三大洲(亚洲、欧洲、美洲)循环举办的全球性会议——互联网国际经济会议(The Conference on Web and Internet Economics)。在算法博弈论方面及网络搜索的研究成果被国际同行广泛引用。发表论文200余篇,被引用数千次。曾获得IEEE理论计算机学术会议FOCS的最佳论文奖。