医院与实习生的双边匹配及问题优化

（1）美国国家实习医生匹配项目

在美国，大约从1900年开始，医学院学生获得医生执照正式成为医院医生之前必须完成3～7年不等的住院实习，学生的这段经历被称为住院医生实习。1900—1945年期间，由于美国医院处于快速发展阶段需要大量的实习医生，而当时医学院毕业生数量相对较少，各医院为了争夺稀缺的毕业生资源而展开了激烈的竞争。为此，一些医院比其他医院更早地到校园招聘学生，到1945年甚至出现了学生距离毕业还有两年时就已经被医院雇佣并开始工作的现象。这种过早雇佣行为无论对医院还是对学生都产生了不利影响：医院过早进入校园招聘学生干扰了学生正常的学业，学生还未完成学业就要签约并进入医院进行实习，这对学生而言，由于过早签约很多专业课程尚未学习，造成对个人职业规划和未来就业的认识不足，进而导致实习一段时间后往往会发现当初所签订的医院并不是自己感兴趣的医院；对医院而言，单纯依据学生前两年的理论课程学习，可能很难全面准确判断学生的实际能力。

1945年美国医学院协会（Association of American Medical Colleges，AAMC）要求医学院在指定时间之前，禁止提供学生成绩单、推荐信，甚至是学生注册确认书，虽然该措施能有效控制医院提前招聘学生，但产生了一个新的问题：若医院给予学生一段时间考虑是否接受该职位，医院发现他们最偏好的一些学生可能拒绝了职位，而此时他们愿意招聘的另外一些学生可能已经接收了其他医院的职位；若医院要求学生在很短时间内决定是否接受职位，学生往往在不知道是否会有其他更好职位的情况下做出选择，导致学生丧失更好的就业机会。这种过早签约和拥挤现象不止存在于美国、加拿大、英国等的医院劳动力市场，也存在于其他的各类市场中[47，95，96]。

为了解决上述市场混乱无序的问题，20世纪50年代，美国医学院协会同意采用一个后来被称为国家实习医生匹配项目（National Resident Matching Program，NRMP）的集中化匹配机制来协调医院与实习生市场[97-99]。集中化匹配机制的工作流程为：首先，学生向医院申请实习岗位，医院组织对学生进行面试；然后，医院对参加面试的学生进行排序，学生也对面试他们的医院进行排序，医院和学生将偏好排序提交给一个集中化机构；最后，集中化机构依据医院和学生提交的信息，采用一个匹配算法来产生匹配结果[40，52]。美国医学院协会最初采用的匹配算法被称为“Trial-run”算法，该算法产生的匹配结果是不稳定的，随后于1952年被一个称为“NIMP”的算法替代[100，101]。20世纪60年代，随着医学院女生数量的逐步增加，医学院有越来越多的男女学生在校期间结婚，在选择实习医院时，夫妻双方都倾向于实习医院在地理位置上尽可能近。由于原有的集中化匹配算法只是针对未婚医生设计的，结果造成已婚男女学生对获得的匹配结果往往不满意，越来越多的已婚夫妻尝试绕过集中化匹配而直接与医院进行联系，导致参与集中化匹配的学生数量逐渐减少[52，101-103]。

（2）医院与实习生匹配相关研究

①医院与实习生传统匹配问题(www.xing528.com)

Roth（1984）[26]研究发现美国医学院协会在1952年采用的双边匹配算法等同于Gale和Shapley提出的延迟接受算法中由医院一方发出匹配邀约，这意味着美国国家实习医生匹配项目最初采用的匹配机制对医院一方是有利的，对医学院毕业生是不利的。鉴于美国国家实习医生匹配项目的成果实施经验，Roth受邀对英国国民健康服务项目在不同地区的匹配项目进行研究，研究发现虽然该项目都采用了集中化的匹配机制，但只有那些采用稳定匹配算法的地区，这些项目一直在顺利开展而没有采用稳定匹配机制的地区项目往往都失败了[43，44]。Sönmez（1997）[107]研究了医院与实习生双边匹配市场中医院操纵策略问题，指出医院可以通过少报招聘实习生数量来获得更好的匹配结果，此外研究表明不存在防止医院操纵招聘数量的稳定匹配机制。Irving（2000）[104]等针对具有无差异偏好信息的医院与实习生匹配问题，首次提出了获得超稳定匹配的线性时间算法，新的研究结果表明所提算法对于美国的NRMP项目及类似项目具有重要应用价值。Gent等（2002）[108]以苏格兰的医院与实习生匹配问题为背景，研究了具有不完全偏好列表和无差异偏好的稳定婚姻问题（SMTI），给出了SMTI问题的布尔编码，并将SMTI问题转化为合取范式的可满足问题SAT，采用Chaff优化器可以对大规模的SMTI进行有效求解。Konishi和Unver（2002，2006）[109，110]以现实初级劳动力市场中青年医生寻求医院实习岗位为背景，研究了医院与实习生市场中的招收限额操纵博弈问题，研究表明在医院的招收限额报告博弈中，通常不存在一个纯策略均衡；当一个纯策略均衡存在，每个医院对于均衡结果的偏好弱优于对任意大的招收限额的结果，提出了保证存在纯策略均衡结果的条件偏好。Kojima（2006）[111]研究了医院与实习生匹配中的招收限额操作博弈问题，研究结果表明不管是纯策略均衡还是混合策略均衡，与任意大的招收限额相比，每个医院更偏好纳什均衡的匹配结果，即与提供真实的医院招收限额相比，每个医院更偏好纳什均衡的匹配结果。Hamada（2011，2016）[105，106]等研究了医院岗位既有下限又有上限数量要求的医院与实习生匹配问题，指出此类问题可能不存在稳定匹配，但对于一个实例问题是否具有稳定匹配是多项式时间可解的；若对于没有稳定匹配的实例问题，为了获得具有最少阻塞对数量的尽可能稳定的匹配，提出了一个近似算法。Delorme等（2019）[115]给出了一个新的整数线性规划优化模型，将其扩展到具有无差异偏好的医院与实习生一对多双边匹配问题（HRT）中，并以苏格兰医院匹配为例，展示了获得最大规模稳定匹配情形下如何从SMTI扩展到HRT。

②考虑成对夫妻偏好的医院与实习生匹配问题

Roth（1984）[40]针对医院与实习生匹配市场中成对夫妻提交成对偏好的匹配问题，研究发现传统的稳定匹配可能并不存在，这有可能导致医院和实习生对NRMP项目失去信心。为了解决已婚夫妻共同申请实习医院的实习生与医院匹配问题，美国医学院协会委托Roth教授为NRMP项目重新设计一个有效的算法，Roth在延迟接收算法的基础上了设计了新算法，通过实证研究发现该匹配机制重新吸引成对夫妻参与集中化匹配，目前该算法已被广泛应用于许多人力资源市场[48]。Marx和Schlotter（2011）[112]研究了一个经典稳定婚姻问题的变体问题，也是医院与实习生匹配问题的扩展问题，即允许具有夫妻关系的成对实习生给出医院联合偏好排序的医院与实习生匹配问题，给出了获得具有夫妻关系的最大匹配的随机固定参数处理算法和局部搜索算法。McBride（2015）[113]研究了医院与实习生匹配的一个变种问题，即成对夫妻提交联合偏好的问题，研究表明即使限制匹配主体偏好列表的长度和结构，确定是否存在稳定匹配也是一个NP-complete问题，然而，对匹配主体偏好列表长度进行一定的限制，可以在多项式时间算法内找到一个最大基数稳定匹配或者判断是否存在稳定匹配。Manlove（2017）[114]针对医院与实习生匹配中成对夫妻向成对医院提交联合偏好信息的稳定匹配问题，研究了具有最小数量阻塞对，即尽可能稳定的匹配存在性，研究表明具有最小数量阻塞对的匹配是一个NPhard问题，并针对单个实习生和医院给出偏好列表最长为2的情况，给出了一个多项式时间算法。

（3）评述与展望

关于双边匹配的研究最早起源于美国医院与实习生匹配问题，也是到目前为止双边匹配理论与方法在现实最成功的典型案例。关于美国医院与实习生匹配问题的研究包括如何解决过早签约与市场拥挤问题、集中化匹配算法、不同类型偏好信息下的稳定匹配存在性、医院岗位不同数量及招收限额下的稳定匹配求解、医院与实习生操纵策略问题、成对夫妻提供偏好的稳定匹配存在性等，可以说医院与实习生匹配问题是当前研究最广泛的现实双边匹配问题，几乎囊括了双边匹配领域研究的所有问题，也取得了大量的成果，为其他领域双边匹配问题的解决提供了范本。目前美国、英国、加拿大等许多国家都已经成功将双边匹配理论应用于医院与实习生匹配，取得了显著成绩。而目前针对中国医院与实习生匹配市场的研究非常少，随着我国国民生活水平的不断提高以及国民对医疗意识与医疗服务质量需求越来越高，如何将每年大量的医学院毕业生分配到不同的地区的实习医院，实现医疗资源的均衡化发展，改变当前偏远农村人民群众看病难、大城市医院就医人群数量多、城乡就医资源不均衡等难题，切实提高人民群众对医疗资源的获得感，是未来需要研究的重要课题。