一种可以解决医生和医院的实习生匹配问题的算法。
将问题建模，令医生和医院的数量相等均为 $n$，且分别有一个喜好排列，表示对每个医院或医生的喜好程度。定义一种匹配是稳定的，当且仅当不存在某个不稳定因子：未匹配的医生 $\alpha$ 和医院 $B$ 都更喜好对方，而不是原匹配对象。
一些错误的想法
一开始，我们难以说明一定存在一种稳定匹配。考虑先得到任意一种匹配，尝试每次消除一个不稳定因子。不幸的是，消除一个的代价可能会增加新的一些。事实上，这种渐进的改进方法可能会导致循环。
另一个方向，可以尝试将流程分为多回合。在每一回合中，所有未匹配的医院，向它们最倾向的医生发送 offer，收到 offer 的医生选择一家医院。但是这种情况仍不能保证稳定性。
Gale-Shapley 算法
过程
基于贪心，在每一回合中，任选一个未完成匹配的医院，向最倾向且未曾拒绝过该医院的医生发送 offer。若该医生觉得该医院是更优的选择，则进行替换。
运行时间
共存在 $n^2$ 个医院和医生的匹配，对于每一回合，可以在 $O(1)$ 时间内得到并检查一个匹配，所以复杂度为 $O(n^2)$。
正确性
容易发现，这种算法一定会运行完且得到一组匹配。对于每一家医院，比最终匹配的更倾向的医生，一定是因为有了更好的医院而拒绝了它，所以最终匹配一定不存在不稳定因子。
最优性
- 对于每一家医院，得到的最终匹配一定是所有可以达成合法匹配中最优的医生。可以在运行回合中，归纳证明所有比最终匹配更倾向的医生，都不能匹配使得最终达成稳定匹配。
- 对于每一个医生，得到的最终匹配一定是所有可以达成合法匹配中最劣的医院。考虑在流程结束后，对于每一个医生，比得到的匹配更差的医院，一定不能达成匹配，因为若该医院更倾向于该医生，则在过程当中，该医院一定考虑过了该医生，并无法完成匹配，可能存在两种情况：
- 在该医院检查该医生时，该医生已经和更优的医院匹配，那么强行拆散原匹配，由主动匹配方的最优性可得，最终会造成不合法。
- 在该医院检查该医生时，该医生一度与该医院匹配，那么若后来的医院考虑“抢”该医生时，若仍保持现状，由主动匹配方的最优性可得，最终也会造成不合法。
