研究问题的现实背景与优化

一对多双边匹配是指匹配决策者依据双边匹配主体提供的需求信息，为一方匹配主体寻求一个匹配对象而为另一方匹配主体需求多个匹配对象的过程。关于一对多双边匹配问题的研究最早可以追溯到1962年Gale和Shapley对大学录取问题的研究[38]。随后，许多学者围绕一对多双边匹配问题进行了研究，并取得了大量的理论和实际应用成果。近年来，随着经济和社会的发展，一对多双边匹配的研究也已经从传统的大学录取、医院和实习生匹配等领域扩展到了一些新兴领域，如商品买卖交易匹配、IT服务中的供给方与需求方匹配、人力资源管理中的人员与岗位匹配、无线通信网络中的网络用户与通信资源的匹配等。

在一对多双边匹配问题研究中，针对双边主体给出偏好序信息的双边匹配问题，一直是国内外学者研究的重点。Gusfield和Irving研究了采用扩展的G-S算法，即H-R算法，来解决医院与实习生匹配问题且认为婚姻匹配问题是医院与实习生匹配问题的一个特例[3]。Roth分析了婚姻匹配和大学录取问题之间的关系，研究表明虽然可以通过H-R算法获得大学和学生最优稳定匹配，但婚姻匹配问题的许多性质并不能简单地推广到大学录取问题[117]。Balinski和Sönmez研究了土耳其的大学录取机制，指出土耳其当前采用的多类别序列独裁机制存在许多严重缺陷，该机制既不是帕累托有效的，也不是防操纵的，研究认为Gale-Shapley学生最优机制对土耳其大学录取而言是可以采用的最好机制[119]。Irving等研究了具有无差异偏好信息的医院与实习生匹配问题，研究表明采用H-R算法总是可以获得一个弱稳定匹配[15]。Roth对美国医院与实习生匹配项目NRMP进行了研究，研究表明在1952年NRMP采用的NIMP算法等同于由医院提出的H-R算法，二者产生的都是医院最优稳定匹配[104]。Jorswieck认为在无线通信网络资源分配中，基于得分、最大吞吐量和比例公平调度的资源分配方式不能保证得到稳定匹配，而采用一对多双边匹配理论中用户和资源提出的延迟接受算法可以获得稳定匹配结果[390]。Korkmaz等针对军队人员与岗位的双边匹配问题，提出了一种基于AHP方法和双边匹配的决策支持系统，用于辅助军事人员的分配，在决策支持系统中，通过AHP方法产生岗位需求偏好和人员能力信息，采用扩展的H-R算法实现岗位与人员的最优匹配[134]。(www.xing528.com)

需要指出的是，在已有的一对多双边匹配问题研究中，大多采用H-R算法或扩展的H-R算法来获得双边主体的稳定匹配结果。但由于基于H-R算法获得的稳定匹配结果对一方主体是最优的稳定匹配，同时对另外一方主体而言也是最差的稳定匹配，因而不能获得双边主体满意度都尽可能高的匹配方案。若单纯考虑匹配的满意性而忽视了匹配的稳定性，则可能会出现有些匹配主体放弃已有匹配对象，绕过原有匹配机制而私下进行匹配，从而导致原有匹配机制失效的现象。因此，在考虑双边匹配的稳定性条件下，如何获得双方主体满意度尽可能大的匹配方案是一个值得研究的问题。此外，在现实的一对多双边匹配问题中，问题的规模往往都比较大，例如，美国的医院与实习生匹配项目NRMP中，每年都有几百家医院和20 000多名实习生参与匹配项目[391]，在中国的大学录取中，每年都有几百万学生和上千所高校参与，在58同城二手房交易网站中每天有多达几十万甚至上百万条房源信息。因此，在不改变一对多双边匹配问题的稳定匹配集合的情形下，有效地降低问题的规模，提高问题的求解效率，显得非常必要。基于此，本书针对一对多双边匹配问题的特点，设计了一种用于降低一对多双边匹配问题规模的偏好列表简化规则，在此基础上，提出了一种同时考虑稳定性和满意性的双边匹配方法。