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

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

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

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

延迟接受算法为每个人找到稳定匹配

存在性加上算法使得稳定性变得可用，而不是抽象。

真实偏好列表成为提议方的支配策略。

它给了设计者一个视角：稳定的市场存活，不稳定的崩溃。

它推动了医学、教育和器官交换领域的实际重新设计。

在建立市场之前，检查匹配机制是否稳定且策略-proof：如果虚假报告能带来利益，市场将充满操纵。让诚实成为最优选择的算法就是市场设计。

该算法成为美国住院医师匹配重新设计、波士顿和纽约学校选择、以及肾脏交换链的引擎——所有这些都在诺贝尔奖引文中被提及。盖尔-沙普利现在是市场设计、运筹学和计算机科学中的标准术语。