盖尔和沙普利1962年的算法让配对市场变得诚实

1962年，大卫·盖尔和劳埃德·沙普利在《美国数学月刊》上发表了《大学录取与婚姻的稳定性》。他们提出了一个问题：在婚姻或大学录取这样的双边市场中，稳定匹配——即没有哪对参与者宁愿彼此在一起——是否总是存在。

他们的答案是建设性的：延迟接受算法，即一方提议，另一方持有临时报价，总是会终止于一个稳定匹配。同一过程给予提议方其可能的最佳稳定结果，这就是为什么真实排序是提议方的支配策略。

五十年后，瑞典皇家科学院将2012年经济学奖授予沙普利和阿尔文·罗斯，以表彰他们“对稳定分配理论和市场设计实践的研究”。罗斯已经证明，稳定性解释了哪些真实市场能够存活，并在此基础上重建了住院医师匹配、学校选择和肾脏交换。