本书是作者近年来在双边匹配领域的主要研究成果，主要内容包括四部分：第一部分是第一章绪论，主要介绍了双边市场、双边匹配及其起源和发展历程；第二部分是第二章双边匹配相关文献评述，这部分从现实典型行业领域中的双边匹配问题、双边匹配典型算法和基于不同优化目标的双边匹配方法三个视角，系统地对双边匹配已有研究成果进行了总结和评述；第三部分是第三章到第七章，这部分是本书的主要研究内容，分别研究了基于多指标评价信息的公平稳定匹配方法、基于序区间偏好信息的稳定双边匹配问题、基于互惠偏好信息的稳定双边匹配问题、家政服务人员与雇主的稳定双边匹配问题以及基于偏好序信息的大规模一对多稳定双边匹配问题；第四部分是第八章结论与展望，对本书主要研究内容、贡献、不足及后续研究展望进行了介绍。

在现实世界中存在这样一类决策问题：一方的选择不仅仅取决于自身的需求，同时还要受到所选择事物对自身偏好或态度的影响，比如在婚恋市场中，方无论自己对某个异性多么喜欢，如果这个异性对自己不感兴趣那也是徒劳的，如何从大量方中找到相互能接受的异性将是一项有挑战性的工作。这类问题可归纳为“如何能够获得既是我们所选择的，同时也是选择我们的事物”，这类决策问题被称为双边匹配问题。云计算环境下计算资源与计算任务匹配问题、大数据资源拥有者与需求者之间的交易问题、滴滴打车中乘客与空闲出租车匹配问题、高考录取中学生与学校选择问题、软件开发项目与开发人员匹配问题等都是典型的双边匹配问题。


双边匹配问题的研究起源于美国医学院毕业生寻找实与医院招聘实的问题。20世纪初随着医院对实需求量越来越大，医院之间为争夺实，出现了学生距离毕业还有很长时间而医院就与学生提前签约的现象，这对学生正常学巨大影响。美国医学院协会介入后给出了的招聘时间，然而招聘市场又出现了选择拥挤问题，为解决这一问题美国医学院协会采用集中化匹配机制取得了良好的效果。该机制的操作流程为：医学院毕业生向美国医学院协会提交个人对实的偏好列表，实通过对学生的面试和在校表现，向美国医学院协会提交招收名额和对学生的偏好列表，美国医学会协会采用匹配算法对毕业生与实行匹配。1962年大卫·戈尔（David Gale)和劳埃德·沙普利(Lloyd Shapley)从理论上研究了稳定婚姻和大学录取问题，性地提出了稳定匹配的概念，奠定了双边匹配的理论基础。美国哈佛大学经济学教授埃尔文·罗斯（AlvinE.Roth）从20世纪80年代对稳定匹配理行不断完善，同时将稳定匹配理论应用于解决现实问题，先后设计了美国国家实匹配项目（National Resident Matching Program,NRMP）中存在成对夫妻的稳定匹配算法、纽约市公立学校入学匹配系统（New York City Public School Matching System)、波士顿公立学校入学匹配系统（Boston’s Public School Matching System）、新英格兰肾脏交易系统（The New England Program for Kidney Exchange)等。由于在稳定匹配理论和市场机制设计方面的贡献，劳埃德·沙普利教授和埃尔文·罗斯教授共同分享了2012年的诺贝尔经济学奖。




本书是作年来在双边匹配领域的主要研究成果，主要内括四部分：部分是章绪论，主要介绍了双边市场、双边匹配及其起源和发展历程；第二部分是第二章双边匹配相关文献评述，这部分从现实典型行业领域中的双边匹配问题、双边匹配典型算法和基于不同优化目标的双边匹配方法三个视角，系统地对双边匹配已有研究成行结和评述；第三部分是第三章到第七章，这部分是本书的主要研究内容，分别研究了基于多指标评价信息的稳定匹配方法、基于序区间偏好信息的稳定双边匹配问题、基于互惠偏好信息的稳定双边匹配问题、家政服务人员与雇主的稳定双边匹配问题以及基于偏好序信息的大规模一对多稳定双边匹配问题；第四部分是第八章结论与展望，对本书主要研究内容、贡献、不足及后续研究展行了介绍。本书的研究内容一步丰富和发展双边匹配理论与方法，并对解决一些现实双边匹配问题具有一定的指导意义。


本书的研究与出版工作得到了人文社会科学研究青年项目（项目编号：18YJC630062）和江苏省智能工厂工程研究中心开放课题的支持资助，也得到了燕山大学出版社的大力支持。此外，本书在撰写过程中参考和借鉴了大量国内外相关领域专家学者的研究成果，在此一并表示衷心的感谢。


本书适合高等院校管理科学、系统工程、信息科学等专业高年级本科生、研究生和教师使用，也可供从事双边匹配决策、系统建模与优化、市场机制设计等领域的科研人员使用。


由于作者的科研和能力有限，另外，双边匹配决策理论与方法作为一个新兴的学术领域其相关的理论和方法还在不断发展和完善之中，书中难免有疏漏之处，恳请相关领域的专家学者批评指正。

第1章绪论


1.1双边匹配研究背景


1.1.1双边匹配概述


1.1.2双边匹配的起源与发展


1.2双边匹配类型


1.2.1一对一双边匹配


1.2.2一对多双边匹配


1.2.3多对多双边匹配


1.3匹配方案的类型·


1.3.1个体理性匹配


1.3.2稳定匹配


1.4双边匹配研究的必要性


1.5双边匹配问题提炼


1.5.1考虑匹配主体性的双边匹配问题


1.5.2基于序区间偏好信息的双边匹配问题


1.5.3基于互惠偏好信息的双边匹配问题


1.5.4家政服务人员与雇主的双边匹配问题


1.5.5大规模双边匹配问题


1.6研究内容


1.7本书内容安排


第2章双边匹配相关文献评述


2.1典型行业领域中的双边匹配问题·


2.1.1婚恋市场中的双边匹配问题


2.1.2医院与实边匹配问题


2.1.3学生与学校双边匹配问题


2.1.4人力资源市场中的双边匹配问题


2.1.5房交易中的双边匹配问题


2.1.6社会资源市场中的双边匹配问题


2.1.7技术、知识与服务市场中的双边匹配问题


2.1.8投融资市场中的双边匹配问题.


2.1.9物流服务市场中的双边匹配问题


2.2双边匹配经典算法·


2.2.1 Gale-Shapley算法


2.2.2 Hospital-Resident算法


2.2.3波士顿算法


2.2.4匈牙利算法


2.2.5大基数匹配算法


2.2.6大权匹配算法·


2.3基于不同优化目标的双边匹配方法


2.3.1考虑单一优化目标的双边匹配方法


2.3.2考虑多优化目标的双边匹配方法


2.4本章小结


第3章基于多指标评价信息的稳定匹配方法


3.1研究问题的实际背景·


3.2符号说明与问题描述


3.3决策思路


3.4双边匹配相关概念


3.5双边匹配模型的构建


3.6模型求解


3.7算例分析


3.8本章小结


第4章基于序区间偏好信息的稳定双边匹配方法


4.1研究问题的实际背景


4.2符号说明与问题描述


4.3决策思路


4.4相关概念


4.5双边主体度计算


4.6多目标优化模型构建


4.7模型求解


4.8算例分析


4.9本章小结


第5章基于互惠偏好信息的稳定双边匹配方法


5.1问题的研究背景


5.2考虑双边互惠偏好信息的稳定匹配方法


5.2.1符号说明与问题描述


5.2.2决策框架


5.2.3概念界定及相关理论分析


5.2.4双边主体满意度计算


5.2.5优匹配方案的确定


5.2.6算例分析


5.3考虑单边互惠偏好信息的稳定匹配方法


5.3.1符号说明与问题描述


5.3.2研究框架及框架说明


5.3.3相关概念界定


5.3.4双边匹配决策方法


5.3.5算例分析


5.4本章小结


……
第8章结论与展望·


8.1本书的主要研究成果及结论


8.2本书的主要贡献


8.3本书研究的局限


8.4未来研究工作展望


参考文献

第1章绪论


1.1双边匹配研究背景


1.1.1双边匹配概述


在高考录取中，能去清华大学或北京大学等这类大学读书是中国考生梦寐以求的，但对大多数学生而言这也只能是一个梦想，因为这些大学可能对大多数学生毫无兴趣，他们关注的往往都是每个省市的“高考状元”这一类学生，但这也不意味着这些大学可以随意决定录用哪个“高考状元”，因为这还取决于高考状元是否对这些大学感兴趣，即考生与高校之间是一种双向选择关系。在毕业生就业中，毕业生对华为、腾讯、、百度等都崇拜，纷纷向这类大公司投简历，大多数情况下这些简历犹如泥牛入海，杳无音信；同样，这些大公司向一些优秀毕业生抛出的橄榄枝也不见得都能被接受，因为毕业生与企业之间也是一种双向选择关系。本书将高考录取、毕业生就业等双向选择问题所处的市场称为双边市场。


双边市场在现实生活中广泛存在，如商品买卖交易市场、婚恋市场、投融资市场、人力资源市场、大数据交易市场等。在这些双边市场中需要关注的一个重要问题是如何对市场中的双边主行有效匹配，例如，在婚恋市场中，需要根据男士的要求为其选择一位合适的女士，同时也要保证男士能够满足该女士的要求，即女士对这位男士也是满意的；在毕业生与企业形成的人力资源市场中，需要为毕他们感兴趣的企业，同时也要为企业选择他们所需要的毕业生。这类双边市场不同于传统的商品市场，商品市场中价格是决定由谁获得商品的因素，价格调节着市场的供求关系，供给价格等于需求价格时的价格即均衡价格引导买卖双方完成交易，而在婚姻市场、人力资源等双边市场中，价格不是决定资源配置的决定因素，例如在婚姻市场，无论男士还是女士选择对方都不会看哪个异性出的价格高就选择哪个异性，对方的外貌、学历、性格等都是影响选择的重要因素；在人力资源市场中，毕业生可能宁愿降低自己对薪资的要求，也要去自己心仪的企业，企业也不会降低工资招聘一些技能不符合岗位需求的毕业生，企业所在的城市、工作未来发展空间等对于毕业生而言也是至关重要的，毕业生的学历、综合素质、工作热情等也是企业看重的。


在双边市场中，存在由两类市场主体组成的两个不相交主体集合，如男士集合和女士集合，毕业生集合和企业集合等，两个主体集合中的双边主体有供需要求或相互有偏好，并且每个主体集合中的一个或多个主体需要与对方主体集合中的一个或多个主行匹配，需要考虑的是如何对两个主体集合中的主行匹配以满足双边需求。这类依据双边市场中两类主体提供的供需信息或偏好信息对两类主行匹配的问题，通常称为双边匹配问题（Two-sided Matching)[1-1。双边匹配可描述为：在双边匹配市场中，存在甲方主体集合和乙方主体集合称之为双边主体集合，其中参与匹配的甲方主体集合表示为A=《A1，A2，…，Am}，乙方主体集合表示为B={B1，B2，…，B}，甲方主体A；给出集合B的一个子集中所有乙方主体的偏好信息P（A,），乙方主体B；给出集合A的一个子集中所有甲方主体的偏好信息P（B），匹配中介通过某种决策方法获得甲方主体和乙方主体的优匹配方案μ={（A1,B1),（A2,B,),…,（Am,B,)}，t{1,2,…,n),p=1,2,…,m。


双边市场及双边匹配与传统商品市场相比，具有以下特点：


（1）双边匹配是一个双向选择过程，例如，在婚恋市场中，男方对自己选择的女方有要求，女方对男方也有着自己的条件，只有双方都符合对方的要求，之间才有可能实现婚恋关系，双边匹配不是“单相思”而是双向满意选择的过程。


双边匹配研究对象具有广泛性和普遍性，传统双边匹括婚恋匹配、大学录取、医学院毕业生与实匹配、人员与岗位匹配等年来新兴的匹配市场如大数据环境下数据交易匹配、云计算中计算资源与任务匹配、共享经济环境下资源需求者与资源提供者匹配等。


（2）在双边市场中，市场价格不是确定双边主体达成交易的决定性因素，价格不再起型作用。例如，在婚恋市场中，无论男方还是女方都不会以对方给出的价格来选择自己的婚恋对象，而是要综合考虑对方的外貌、受教育程度、性格、工作、家庭背景等因素，传统商品市场中的理论和方法已经不能有效解决双……