双边匹配的起源与发展的优化

关于双边匹配的研究最早可以追溯到20世纪初美国医学院毕业生与实习医院之间的双边匹配问题。1900年以后，随着医学技术的发展，美国医院进入快速发展阶段，随之对住院实习医生产生了大量需求，与之相矛盾的是每年医学院毕业生数量较少。各大医院为争夺毕业生资源，通常在毕业生尚未正式毕业前就招聘并雇佣学生，由此造成招聘日期不断提前而对学生学习产生巨大干扰。在此情形下，美国医学院协会介入给出了招聘的指定时间，由此又要求医学院毕业生和招聘医院必须在很短时间内作出决策，使得毕业生往往会错失好的实习医院而医院也可能招聘不到想要的学生。住院医生实习市场中存在的这种过早签约和指定时间内作出选择的拥挤现象，造成了市场的混乱无序，令医学院毕业生与实习医院对此比较失望。20世纪50年代美国医学院协会采用了一种新的匹配机制——集中化匹配机制，来对医学院毕业生与实习医院进行匹配。他们先后采用“Trial-run”和“NIMP”的算法，由此极大改善了环境，医学院毕业生和实习医院都非常满意这种机制，但美国医学院协会所做出的实践工作仅仅在医学院毕业生与实习医院市场中产生了较大影响，而尚未形成系统科学的理论，也未引起学者的关注。

1962年大卫·戈尔（David Gale）和劳埃德·沙普利（Lloyd Shapley）在期刊American Mathematical Monthly上发表了关于稳定婚姻和大学录取的双边匹配研究，在他们发表的开创性论文《College admissions and the stability of marriage》中，大卫·戈尔和劳埃德·沙普利提出了稳定匹配的概念，证明了稳定匹配的存在性、最优性和唯一性，并给出了获得稳定匹配的延迟接受算法[38]。大卫·戈尔和劳埃德·沙普利的开创性理论研究成为双边匹配和市场机制设计历史上的一座丰碑，奠定了双边匹配的理论基础，也标志着双边匹配正式进入学者研究的视野。但科学的发展往往不是一帆风顺的，而是不断螺旋式上升的，大卫·戈尔和劳埃德·沙普利关于双边匹配的伟大创举短时间内并未引起轰动而是陷入了沉寂。直到双边匹配和市场机制设计研究的另一位大咖的出现，才在学术界掀起了一股巨浪。20世纪80年代美国匹兹堡大学安德鲁-梅隆经济学教授、市场设计理论的开创者之一埃尔文·罗斯（Alvin E.Roth），一方面进一步对稳定匹配相关理论进行了深入研究，不断扩展和完善了双边匹配理论和方法[39-47]，另一方面不断将双边匹配理论应用于实践以解决现实问题。埃尔文·罗斯教授在博弈论、市场设计与实验经济学等领域作出了卓越贡献，他不仅是一位理论经济学家，同时也强调用经济理论解决现实问题。他成功主导设计了许多双边匹配系统，如针对美国国家实习医生匹配项目NRMP中实习生存在已婚夫妇情形的稳定匹配问题重新设计了算法、设计了纽约市公立学校入学匹配系统和波士顿公立学校入学匹配系统、设计了新英格兰肾脏交易系统等[48-52]。此后，国外许多学者加入双边匹配领域的研究，在双边匹配理论与方法以及实践应用方面都取得了丰硕成果。埃尔文·罗斯教授与加州大学的劳埃德·沙普利教授，更是凭借在稳定匹配理论和市场机制设计方面作出的突出贡献共同获得2012年度的诺贝尔经济学奖[53]。

双边匹配研究早期研究阶段学者们主要关注婚姻匹配问题、大学录取问题、医院和实习生匹配问题等，针对这些问题从偏好信息来看主要研究具有严格偏好序信息和具有无差异偏好序信息等简单偏好信息形式；从偏好列表来看主要研究具有完全偏好列表和不完全偏好列表等；从双边匹配目标来看，主要考虑双边匹配的稳定性和不同类型的公平性。随着经济社会的发展，许多新兴的双边市场随之涌现，如大数据交易市场中数据交易匹配问题、基于电子中介的商品买卖交易匹配问题、云计算环境下的任务与资源匹配问题、无线通信网络中的用户与无线频谱资源匹配问题、公路货物运输中的车源与货源双边匹配问题、金融行业中的风险投资商与风险投资企业匹配问题等，新兴双边市场出现的双边匹配问题亟须新的双边匹配理论与方法来解决。在出现的大量双边匹配问题中，从双边匹配类型来看，不仅有一对一双边匹配、一对多双边匹配，还有多对多双边匹配；从双边主体给出的偏好信息来看，还具有不确定偏好序信息、多指标评价信息、成对偏好序信息、同群信息、协同信息、互惠偏好信息等；从双边匹配优化的目标来看，还需要考虑不同类型的公平性、协同性以及大规模双边匹配问题的优化等。

随着埃尔文·罗斯与劳埃德·沙普利获得诺贝尔经济学奖，近年来国内外掀起了一股双边匹配研究的热潮，关于考虑双边市场及双边匹配问题的理论、方法与实践应用方面的研究越来越受到国内外学者的关注，研究双边匹配的国内外重要学者主要包括：

■国外学者，如Gale David、Shapley Lloyd S.、Roth Alvin E.、Gusfield，Dan、Irving Robert W.、Knuth Donald Ervi、Manlove David F.、Halldórsson Magnús M.、Király Zoltán、Mcdermid Eric、Miyazaki Shuichi、Yanagisawa Hiroki、Mullin Francis J、Hamada Koki、Sönmez Tayfun、Kojima Fuhito、Iwama Kazuo、Shuichi Miyazaki、Mc Vitie David G.，、Sotomayor Marilda、Chen Yan、Sönmez Tayfun、Abdulkadiroˇglu Atila、Klaus，Bettina、Klijn Flip等。(www.xing528.com)

■国内学者，如樊治平、姜艳萍、汪定伟、王应明、蒋忠中、陈希、乐琦、李铭洋、赵道致、张振华、梁海明、马辉民、聂海峰、张笛、刘勇、赵晓东、臧誉琪、万树平、李登峰、王中兴、陈圣群、林杨、黄帅、李建荣、熊新生、羊英、钟力炜、沈体雁、詹文杰、任磊等。

随着双边匹配研究成果的不断丰富，目前刊登双边匹配方面研究成果的国内外重要期刊数量也越来越多，这些期刊涵盖了经济学领域、管理科学领域、信息科学领域等，目前刊登双边匹配研究成果的国内外重要学术期刊包括：

●国外期刊，如Management Science、Operations Research、Mathematics of Operations Research、Expert Systems with Applications、Journal of the Operational Research Society、Computers&Industrial Engineering、Optimization Letters、Journal of Discrete Algorithms、Journal of Combinatorial Optimization等。

●国内期刊，如管理科学学报、系统工程理论与实践、中国管理科学、系统管理学报、系统工程学报、系统工程、运筹与管理、管理学报、控制与决策、系统工程与电子技术、系统仿真学报、系统科学学报、运筹学学报、科技与管理、科技进步与对策、科技管理研究、计算机集成制造系统、计算机工程与应用、计算机应用、计算机工程与设计、模糊系统与数学、数学的实践与认识、系统科学与数学、统计与决策、东北大学学报（自然科学版）、浙江大学学报（理学版）、山东大学学报（理学版）等。