Gale-Shapley 算法
- 提出者
- David Gale, Lloyd Shapley
- 年份
- 1962
- 类型
- algorithm
- 类别
- Game-theoretic
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
Gale-Shapley 算法解决了稳定婚配问题:如何匹配两组个体(例如,医科住院医师与医院,学生与学校)以至于不存在一对配偶更倾向于对方而非其当前匹配对象。该算法由 David Gale 和 Lloyd Shapley 于 1962 年提出,通过一种延期接受过程,其中一方按顺序提出匹配请求,另一方则作出回应,并根据更优选项的出现而调整选择,从而保证在多项式时间内找到一个稳定的匹配。
方法背后的直觉
设想匹配医生与医院。该算法的工作方式类似于抢椅子游戏:每位医生向其最偏好的医院提出申请;每家医院暂时接受可用的最佳医生。当医院收到更优的申请时,它们会调整选择,可能撤销之前的接受。被拒绝的医生则向其次优偏好的医院提出申请。此过程持续进行,直到没有医生愿意继续提出申请,也没有医院愿意更换其当前匹配对象。最终结果是稳定的:不存在医生-医院配对会同时倾向于匹配对方而非其当前匹配对象。
历史学
David Gale 和 Lloyd Shapley 于 1962 年发表了他们对稳定婚配问题的解决方案,证明了双边市场总是存在稳定的匹配。他们的算法催生了大量的匹配理论文献,其应用涵盖了医学、教育和劳动力市场。2012 年,Alvin Roth 因其在应用匹配理论于实际市场设计方面的实验和理论工作获得了诺贝尔经济学奖,这验证了 Gale-Shapley 框架的实际重要性。
何时使用
当匹配双边市场且稳定性至关重要时,应用 Gale-Shapley 算法:例如医科住院医师分配、学生与学校匹配、肾脏交换、劳动力市场匹配或在线约会市场。当存在匹配不稳定性(阻碍对)可能导致匹配在分配后被破坏时,应使用该算法。当一方具有战略优势且可以先行提出匹配请求时,该算法尤为理想。
局限与注意事项
- 非帕累托最优:匹配可能无法最大化总福利;可能存在阻碍对,所有相关方均可通过交换匹配对象而受益。
- 战略脆弱性:提出方可以通过虚报偏好来获益,而响应方则必须如实陈述。
- 不对称性:结果很大程度上取决于哪一方先提出匹配请求。
- 无法处理约束:在不进行算法修改的情况下,难以纳入复杂偏好(例如,情侣、地域偏好)。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 保证稳定性:最终匹配中不存在阻碍对。
- 多项式时间:复杂度为 O(n^2),对于大规模人群而言效率很高。
- 实现简单:在实践中易于执行,偏好收集过程透明。
- 战略激励:提出方具有战略优势,倾向于早期提出匹配请求。
- 普遍适用性:适用于任何偏好配置,无需假设凸性或传递性。
应用
- 医科住院医师匹配:通过 NRMP 将医学院毕业生与医院住院医师项目进行配对。
- 学校选择:根据偏好和容量限制将学生分配到公立学校。
- 肾脏交换:匹配器官捐赠者和受赠者以最大化兼容的移植。
- 就业市场匹配:在双边劳动力市场中连接求职者与雇主。
- 在线约会:匹配约会平台上的用户以提高匹配稳定性和用户满意度。
使用方式
使用方式
为所有个体创建偏好列表,代表其对另一方的排序。
在每一轮中,未匹配的提出方个体向其尚未提出过的、在对方中最受其偏好的对象提出申请。
接收方个体若未匹配,则暂时接受该申请;若该申请者比其当前匹配对象更受其偏好,则撤销之前的匹配关系。
当所有个体均已匹配且不再发生新的申请时,算法停止,产生一个稳定的匹配。
常见陷阱
- 假设仅稳定性足以保证公平或福利;稳定的匹配可能严重偏向一方。
- 混淆稳定性与最优性;稳定的匹配不一定是福利最大化的。
- 忽视提出方的战略优势:提出方的成员倾向于匹配到排名更高的对象。
- 忘记算法假设偏好列表是完整的;不完整的偏好需要修改。
常见问题
为什么稳定性在匹配中很重要?
缺乏稳定性,已匹配的配偶可能稍后发现他们更倾向于对方而非其当前匹配对象,从而产生打破匹配的激励。稳定的匹配可以防止此类阻碍对,确保匹配在无需重新谈判的情况下得以维持。
Gale-Shapley 算法总是产生相同的匹配吗?
否。不同的偏好列表或提出顺序可能产生不同的稳定匹配。然而,总会存在一个“男性最优”的稳定匹配(对所有提出方都是最优的)和一个“女性最优”的稳定匹配(对所有响应方都是最优的)。
Gale-Shapley 如何处理对群体的偏好(例如,情侣)?
标准算法不直接处理情侣或其他约束。存在如情侣算法等扩展,但它们更复杂,并且可能无法保证所有偏好配置的稳定性。