各种匹配问题可不是仅仅用来娱乐的算法竞赛题目，它们在现实生活中都有着广泛的应用。比如稳定匹配原理作为一种资源的分配方法，就在美国的医疗体系中得到了广泛应用。19世纪40年代，在先进医疗技术的引领下，美国的医疗体系得到了巨大的发展，但是稀缺的医学院毕业生成了这个体系的心病。为了争抢稀缺资源，医院被迫在学生毕业前好几年就向他们提供实习机会。学生们则在还没有被证明有资格从事医疗工作的情况下就已经完成了工作配对，同时，如果医院提供的实习机会没有被学生接受，那么再向别的候选人提供机会就太晚了。很显然，这个市场没有稳定匹配，于是在19世纪50年代，美国启动了一个名为“国家住院医生匹配项目”（NRMP）的计划，旨在解决这个问题。从1984年开始，阿尔文•罗思（Alvin Roth）在论文中研究了这个项目使用的算法并发现了它与Gale-Shapley算法原理类似。他随之假设出NRMP项目成功的根本原因就是它使用了稳定匹配算法。后来，随着女医生越来越多，情侣们在一个地区寻找实习机会的现象越来越普遍，他们可不喜欢NRMP项目的这套匹配机制，这使得情侣们被很容易安排在两个地方，这又引入了不稳定因素，那就是会导致情侣分居两地。于是在1995年，罗思为这个项目设计了一个新算法，这个新算法在1997年被NRMP所采纳，从那个时候开始到现在，该算法每年为超过2万个医生找到了合适的工作岗位。 2012年诺贝尔经济学奖授予了两位美国学者：阿尔文•罗思和劳埃德•沙普利，以表彰他们在“如何让不同人为了互惠互利而联系在一起”这个课题上的出色研究。没错，这就是本章介绍的Gale-Shapley算法中提到的罗思和沙普利，他们被称为“数理经济学家”。 Gale-Shapley算法又称为“求婚拒绝算法”（propose-and-reject algorithm），以舞伴问题的整个求解过程来看，女孩从接受第一个邀请开始就有了舞伴，并且舞伴会越来越好，因为女孩可以根据自己的排序表确定是否选择更好的舞伴。与此同时，男孩如果被拒绝，他的选择对象会越来越差（因为男孩是根据自己的排序表从好到差开始选择的）。然而实际情况却并不是这样的，Gale-Shapley算法中“求婚”的一方总是以最佳可能的稳定岗匹配结束，被“求婚”的一方总是以最差可能的稳定匹配结束，因为选择的主动权掌握在“求婚”者手中。现实生活中的道理也是如此，婚姻中男人如果不主动争取，条件好的女孩就会投入别人的怀抱，留给自己的机会就越来越差。学校里那些勇气可嘉、敢于主动示爱的男生，都是学过Gale-Shapley算法的，不信你问问他们。