NRMP住院医师匹配算法结果是否唯一？相关算法与差异问询

背景 #

每年住院医师申请者要给全国住院医师匹配项目（NRMP）提交一份严格排序的可选项目列表（称为排名顺序列表（rank order list）或排名列表（rank list）），明确个人偏好；住院医师项目同样需向NRMP提交申请者的排名列表。NRMP运行算法完成匹配，不同项目的岗位数量存在差异，最终生成的匹配结果具备稳定性——即不存在两名申请者，互相都更愿意前往对方匹配到的项目。

核心问题解答 #

1. 是否存在可确保匹配结果唯一的算法？ #

没有任何算法能保证在所有NRMP场景下都得到唯一的稳定匹配结果。NRMP采用的是延迟接受算法（Gale-Shapley算法的多岗位变体），只要申请者与项目的偏好结构存在冲突，就可能出现多个稳定匹配。只有当所有参与方的偏好满足极严格的唯一性条件（类似Clark论文中经典稳定婚姻问题的充分条件，但需适配多岗位场景）时，才会产生唯一结果，但这类情况在实际NRMP中非常少见。

2. 匹配结果非唯一性的影响程度如何？ #

结果波动没有固定上限，但实际案例中通常幅度有限：

• 多数情况下，申请者的匹配结果仅会在自身排名列表里的相邻或相近项目间变动；
• 极端场景（如大量申请者偏好高度重合、项目岗位数与申请者数量严重失衡）下，少数申请者可能匹配到远低于预期排名的项目，但这类情况极为罕见。

相关研究说明 #

Clark的论文给出了经典稳定婚姻问题中稳定匹配唯一性的充分条件，但该结论无法直接套用到NRMP这种多岗位的稳定匹配变体上，目前针对NRMP场景的唯一性条件研究仍较为有限。

内容的提问来源于stack exchange，提问作者rorty