Gale與Shapley 1962年的演算法讓媒合市場變得誠實

David Gale與Lloyd Shapley於1962年在《American Mathematical Monthly》發表〈College Admissions and the Stability of Marriage〉。他們追問：在婚姻或大學招生這類雙邊市場中，穩定配對——即沒有任何兩方會寧願彼此配對的指派——是否必然存在。

他們的答案具建設性：延遲接受演算法，由一方提出、另一方暫留提案，必定終止於穩定配對。同一程序會給提出方其可能的最佳穩定結果，這正是為何對提出方而言，真實排序是優勢策略。

五十年後，瑞典皇家科學院將2012年經濟學獎頒給Shapley與Alvin Roth，「表彰其穩定配置理論與市場設計實踐」。Roth已證明穩定性可解釋哪些真實市場得以存續，並以此演算法重建住院醫師媒合、學校選擇與腎臟交換。

延遲接受為每個人找到穩定配對

存在性加上演算法，使穩定性從抽象變得可用。

真實偏好清單成為提出方的優勢策略。

它為設計者提供一種視角：穩定市場得以存續，不穩定市場則崩解。

它推動了醫學、教育與器官交換的實際重新設計。

在建立市場之前，先檢查媒合機制是否穩定且具策略防禦性：若虛報有利可圖，市場就會充斥操縱。能讓誠實成為最優選擇的演算法，就是市場設計。

此演算法成為美國住院醫師媒合重新設計、波士頓與紐約學校選擇，以及腎臟交換鏈的引擎——這些全都在諾貝爾獎引文中被提及。Gale-Shapley如今已是市場設計、作業研究與電腦科學的標準詞彙。