下载掌阅APP，畅读海量书库
立即打开
博弈论以理性和信息为基础，以规则为约束，研究主体决策及互动均衡问题。基于提升博弈绩效的基本目标，博弈论的发展遵循了从对立、合作、演化到机制设计的一系列变化，博弈论研究也经历了一般决策、非合作博弈、合作博弈、匹配博弈等几个阶段 [10] [11] [12] 。近年来，以算法匹配为主要特征的计算机辅助市场飞速发展，已经从交易平台阶段发展为交易匹配智能化阶段，研究的重点是如何对买卖双方进行智能化匹配以提升市场效率 [13] 。对计算机辅助市场的研究主要集中于定价策略、稳定匹配、推荐算法以及算法博弈论等方面。
机制设计的最早雏形。早期机制设计的思想可追溯至20世纪30年代一些学者关于计划经济的争论。兰格（Oskar Lange，1936）和勒纳（Abba Lerner，1944）认为在计划经济下，中央政府比私有企业家掌握更多的有关知识，也能比竞争市场更快地获得均衡价格，从而使供求达成平衡，最终实现资源的合理配置。由于社会主义经济贯彻决策的一致性和执行决策的效率法则，政府干预会达到社会的最优。 [14] 哈耶克（Friedrich von Hayek，1945）、米塞斯（Ludwig von Mises，1920）认为中央计划当局缺乏必要的信息，信息传导到计划体系的中央部门需要很长时间，分散化决策比计划经济能更好地利用信息。因此，市场经济在资源配置方面要优于计划经济 [15] 。
早期的机制设计理论主要侧重于信息成本最小化，用于解决信息不对称问题。赫维茨（Leonid Hurwicz）认为机制设计理论研究如何制定有效机制，最小化信息成本。赫维茨的弟子田国强则是国内最早从最小信息成本角度研究最优机制问题的专家 [16] [17] 。
利奥·赫维茨（Leonid Hurwicz）、埃瑞克·马斯金（Eric S. Maskin）、罗格·迈尔森（Roger B. Myerson）三位美国经济学家因为对机制设计理论的杰出贡献，获得2007年诺贝尔经济学奖。主要成果有赫维茨的“资源配置过程中的信息效率和最优化”（1960） [18] 和“论信息分散系统”（1972） [19] 、马斯金的论文“纳什均衡与福利最优化（1977）” [20] 、迈尔森的论文“最优拍卖设计（1981）” [21] 。
迈尔森（Roger B. Myerson）于1981年发表的“最优拍卖设计”将机制设计拓展到更一般的贝叶斯纳什均衡（Bayesian Nash Equilibrium）上。而Maskin在纳什均衡可实施机制上的贡献具有里程碑式的意义。“可实施”（或者叫激励相容）是机制设计的重要原理。可实施表示，参与人接受机制将获得比拒绝机制更多的收益。
对于一个机制来讲，除了要有效率，还必须保证存在足够的交易。我们通常可以通过制度或机制设计将交易成本降低，但是，一个现实的问题是：在这种机制下，参与者是否有足够的动机按照机制设计者的要求（不说谎）参与其中。因此，机制设计必须满足激励相容的条件。Gibbard（1973）最早在隐藏信息情形下提出占优显示原理（Dominant-Strategy Revelation-Principle） [22] ，即存在占优战略时，必有占优激励相容机制（Dominant-Strategy-Incentive Compatible Mechanism）。迈尔森（Myerson，1979）归纳出更完整的一般形式。在贝叶斯博弈的条件下，提出贝叶斯纳什显示原理（Bayesian-Nash Revelation-Principle），即存在贝叶斯纳什均衡时，必有贝叶斯纳什激励相容机制（Bayesian-Nash Incentive-Compatibility Mechanism） [23] [24] [25] 。显示原理是机制设计的核心概念，是在参与者掌握私人信息时进行博弈设计的重要工具。它表明如果存在一项社会选择功能的实现机制，必然有一个激励相容直接机制（An Incentive-Compatible-Direct-Mechanism ）可实现相同的功能 [26] 。
早在1989年，McCabe等对燃气市场中的批发商、管道商、气井商之间的密封拍卖市场进行分析，通过计算机算法进行分配和非歧视定价，最大化整体收益 [27] 。1991年，McCabe等进行了实验，分散的主体通过计算机分发中心进行报价，计算机算法决定价格和分配，以最大化交易收益。通过实验，研究了解除管制的市场设计的可行性、限制因素、激励因素和性能 [28] 。David Easley和Jon Kleinberg（2010）对匹配市场的价格形成进行了研究，在买卖方数量相等的情形下，最终卖方在不低于底价的情况下清仓，买方得到溢价最多的商品 [29] 。K. Willett（2013），R. Sivak（2014）对空气质量控制的计算机辅助市场进行了设计，提出了总量管制与交易政策的定价机制和安全边际允许范围内的定价规则 [30] [31] 。
在许多情况下，价格并不是市场配置唯一决定因素，有时甚至不是关键因素，如企业招工问题、学生就业问题、婚姻匹配问题等，这是匹配市场研究的重要内容 [32] [33] 。随着互联网的发展，算法匹配问题成为匹配市场研究的热点。早期的匹配理论研究开始于Gale和Shapley（1962）的“大学录取和稳定婚配”一篇论文，他们对匹配稳定性和最优性进行了定义，提出的延迟认可算法（Gale-Shapley Algorithm，Deferred Acceptance Algorithms）可寻求稳定匹配，匹配博弈理论开始形成。 [34] 。
Dubins和Freedman证明了Gale-Shapley机制是抗操作的 [35] 。在此之后，Roth，Balinski和Abdulkadiroglu的一系列论文较全面地讨论了Gale-Shapley机制的帕累托最优和稳定性等问题。他们证明了如果市场的两边都具有严格偏好，那么一定存在一个两边都稳定的匹配，且这个匹配满足抗操作和帕累托最优 [36] [37] [38] 。Gusfield等针对稳定婚配问题的结构和算法进行了较为详细的研究 [39] 。Abdulkadiroglu和Sonmez全面总结了过去出现的两种最优匹配机制（Gale-Shapley机制和Top Trade Cycles机制），开启了匹配理论研究的一个新阶段 [40] 。
从匹配双方是否均拥有对另一方的偏好序，匹配问题可分为单边匹配和双边匹配两大类。其中，单边匹配指匹配双方中有且仅有一方拥有针对另一方的偏好序，而另一方的偏好序是完全无差异的。通常对离散资源（不可分割商品）的分配，如房屋、寝室、课程等都可看作为单边匹配。Shapley和Scarf（1974）在“核和不可分性”一文中研究了单边匹配问题（匹配一方的偏好是一致的）。他们提出了一种最大交易圈子算法（TTC算法），算法具有稳定、帕累托最优和抗操作性，能够保证产生稳定匹配 [41] 。Roth（1982）证明了通过TTC（最大交易圈子）算法表达偏好和交换禀赋得到的唯一稳定均衡，对所有参与者来说都是占优策略和激励兼容的 [42] 。
双边匹配是指如何在两个不相交的主体集合中依据各主体针对潜在匹配对象给出的偏好信息来确定合适的匹配结果 [43] 。Roth对双边匹配市场概念进行了明确说明，“双边”是指市场中的主体分属于两类不相交的集合，匹配则具有典型的“双边交换性质（Bilateral Nature of Exchange）” [44] 。双向匹配市场中存在两组相互分离参与者，每一方都有针对另一方的偏好序，不管是两两配对还是配额录取问题，均是以“参与者配对”为基础的，如买卖双方、雇主工人、学校学生，只有在互相匹配的情况下才能实现相应的功能。
Kesten，Erdil，Ergin，Abdulkadiroglu等人从不同的角度探讨了弱偏好（弱优先序）条件下的双边匹配机制及其特性。Kesten（2004）提出了有效适应延期接受机制。在“合理公平”的定义拓展后，该机制能够产生一个稳定的匹配结果 [45] 。Erdil和Ergin（2007）提出了稳定改进循环机制，这个机制在弱优先序的条件下，可以达到稳定和帕累托最优，但却不能保证抗操作 [46] 。Abdulkadirogl（2006）证明了不存在任何一种机制优于消除弱优先序的最优机制，同时还能保证抗操作 [47] 。Takehiro Ito（2017）则从合作博弈的角度对匹配问题进行了研究，讨论了网络稳定的组合优化问题，得到了一个完整的复杂性理论分类 [48] 。Jung等考虑了交易双方的匹配需求，构建了买方和卖方的匹配代理模型，并获得基于算法代理的匹配结果 [49] 。Janssen 和Verbraeck（2008）对互联网的供需匹配机制进行了研究，对匹配规则、匹配分值及匹配系统进行了讨论 [50] 。Sarne和Kraus（2008）对多主体系统的双边匹配活动进行了分析，构建了面向多主体的分布式双边匹配机制 [51] 。
樊治平等（2014）指出，双边匹配问题是指如何在两个不相交的主体集合中依据各主体针对潜在匹配对象给出的偏好信息来确定合适的匹配结果，其在经济管理领域中存在着大量的实际背景 [52] 。魏立佳认为，在双边偏好序（优先序）均不一致和偏好序（优先序）弱的情况下，匹配机制是不能同时满足稳定、帕累托最优和抗操作的。他将弱偏好序的匹配算法研究拓展到单边匹配领域，设计了“挤出”匹配算法，并证明该算法满足稳定、抗操作和帕累托最优的算法，且匹配后总效用最高 [53] 。王烨等从纳什均衡的角度出发，考虑图论中的稳定匹配问题，发现稳定匹配可以用纳什均衡理论进行直观解释 [54] 。樊治平等（2014）针对双边主体给出偏好序值信息的双边匹配问题，给出了一种考虑稳定匹配条件的双边满意匹配决策方法。李铭洋等（2013，2017）针对基于序值偏好信息的一对多双边匹配问题，提出了一种兼顾双方主体利益的稳定匹配决策方法 [55] [56] 。徐晓辉和陈剑（2000）对电子商务匹配度进行研究，从标准化、顾客体验和顾客态度三方面来构建电子商务匹配模型 [57] 。乐琦（2016，2017）在考虑匹配意愿及不确定心理行为的条件下对双边匹配决策问题进行了研究 [58] [59] 。
在推荐算法方面，Dao等（2012）将数据挖掘算法融入协同过滤方法中进行个性化推荐，从而提高推荐质量 [60] 。Woerndl等（2016）提出二阶段的情景移动推荐模型，该模型结合客户情景状态进行权重的设置，当权重满足规定的阀值时则进行个性化推荐 [61] 。此外，20世纪90年代以来出现的算法博弈论，对算法匹配博弈机制的研究起了很大的促进作用。算法博弈论研究因特网环境下经济个体之间以及个体与网络之间的交互规律，包括均衡问题、优化问题以及可计算问题，通过计算机算法设计、建立新的博弈规则 [62] [63] 。算法博弈论已经在互联网相关的经济领域得到了广泛应用，如电子商务交易行为分析、网上拍卖、云计算定价、排序理论、大数据系统等 [64] [65] 。
梁昌勇等（2013）对推荐算法的原理进行了系统分析，认为推荐算法通常基于内容、协同过滤或数据挖掘等算法，通过对海量信息的分析，提供个性化服务，满足消费者需求 [66] 。翟丽丽等（2016）在使用协同过滤算法进行个性化推荐时，考虑了移动电子商务的状态情景，并使用K-means算法对用户进行情景聚类，从而改善了推荐准确率 [67] 。还有学者对算法歧视的产生和综合治理问题进行了探索研究 [68] [69] 。
GS算法和TTC算法较好地解决了稳定匹配问题，该领域的许多研究成果已经被广泛运用于现实生活中的许多方面，包括美国实习医生的分配、高中学生录取、器官移植排队、电子商务供需匹配等等 [70] [71] [72] [73] 。特别是计算机和网络技术的飞速发展较好地解决了匹配机制的运算速度问题，许多学者投入GS算法和TTC算法的研究之中 [74] [75] [76] [77] 。
Roth（1982）证明了通过TTC算法表达偏好和交换禀赋得到的唯一稳定均衡，对所有参与者来说都是占优策略和激励兼容的 [78] 。Roth（2008）、Ashlagi（2011，2012，2018）、Rees Michael A（2012）等还发表了一系列文章，对匹配理论中的匹配机制问题进行了深入探讨 [79] [80] [81] [82] [83] [84] [85] 。Roth（Alvin E. Roth）将匹配理论应用到实践，运用其算法的基本理论，结合经验观察、实验和实践设计，改善了许多现有市场的绩效 [86] 。Roth认为一个足够成熟的市场环境应该：足够厚度（Thickness，足够的买卖双方）、足够畅通（有足够的时间选择）、足够安全（披露真实偏好）。传统的“立即接收式”劳动力市场中，企业常常采用逼签（Exploding Offers）方式，求职者需要迅速做出决定，不能对各种工作进行比较，导致厚度不够、畅通不够，双方都不能达到满意。此外，传统的“波士顿”式入学机制规定学生根据优先序递交第一、第二等志愿，学校在第一志愿中优先录取，哪怕是很差的学生。填写志愿将存在“巨大的风险”，也显得过分的重要。“延迟接收算法”则让学校按照一定标准录取学生（可以拒绝不符合标准的学生），如果第一志愿录取不足，可以同时考虑是否可接收其他非第一志愿的学生，这样可防止匹配市场无法出清，这种方法已经被普遍使用。 [87]
此外，Aleksander（2000）认为电子商务已经从交易平台阶段（eBusiness Flatform）发展为交易匹配智能化阶段（e-Business Intelligent Matching），如何对买方和卖方进行智能化匹配成为这个阶段的一个重要问题 [88] 。
从上述研究进展可以看出，在市场匹配博弈研究领域的大多研究工作集中在基于算法设计的博弈规则重构，主要还停留在初步的理论探索阶段。一是相关研究没有充分考虑算法的社会选择博弈特征。算法主体参与后的博弈局势将发生根本变化，只有充分考虑算法的社会选择和参与激励功能，才能保证参与人能积极参与到这种算法约束下的博弈中来。二是相关研究没有对有限理性带来的信息问题进行探讨。没有充分考虑信息问题所导致的一系列交易缺陷，如获取信息、辨别信息、处理信息的有限能力问题，导致不能及时发现足量的候选交易对象、不能快速交易、不能显示真实信息等。三是市场匹配机制设计的方法体系没有形成。市场设计体现了委托人的博弈诉求或社会目标导向，这种社会目标是通过博弈机制来实施的。参与约束、激励相容、显示原理、实施原理为市场设计指明了方向，但是如何找到上述实现机制，还没有规范化的方法。这就使得市场匹配理论很难形成一种普适性的方法体系，影响了匹配理论的整体发展和在市场匹配实践中的应用。对上述问题的系统研究，将有助于深入理解算法匹配博弈的机制原理，并为社会选择匹配提供科学的算法设计依据。