“蓋爾-沙普利算法”（the Gale-Shapley algorithm），也被稱為“延遲接受算法”（deferred-acceptance algorithm），簡稱“GS算法”。是蓋爾和沙普利為了尋找一個穩定匹配而設計出的市場機制。市場一方中的對象（醫療機構）向另一方中的對象（醫學院學生）提出邀約，每個學生會對自己接到的邀約進行考慮，然後抓住自己青睞的（認為它是可接受的），拒絕其它的。該算法一個關鍵之處在於，合意的邀約不會立即被接受，而只是被“抓住”（hold on to），也就是“延遲接受”。邀約被拒絕後，醫療機構才可以向另一名醫學院學生髮出新的邀約。整個程式一直持續到沒有機構再希望發出新的邀約為止，到那個時候，學生們才最終接受各自“抓住”的邀約。
基本介紹
- 中文名：蓋爾-沙普利算法
- 外文名：the Gale-Shapley algorithm
- 又稱：延遲接受算法
- 簡稱：GS算法
起源,發展,實踐意義,啟示,
起源
經濟學是研究資源最優配置問題的，而真實世界裡配置資源的方式多種多樣，市場或者說價格機制是經濟學研究最多的。但是有一些市場裡頭，價格的作用受到法律、習俗或倫理道德等限制。最明顯的例子就是找對象的時候不是價高者得，而是情投意合才結成夫妻。1962年，沙普利與同事戴維·蓋爾在《高校招生與婚姻穩定性》一文中寫到：以10名男子和10名女子“婚配”為範例，構想如果由每一名女子先作選擇並向最中意男子“求婚”，然後再由每一名男子審視所獲所有“求婚”並回絕除了最中意女子以外的其他所有“求婚”，就可以實現穩定分配。構想的核心，是男子保留並延遲接受最中意女子的“求婚”。這一方法獲稱“蓋爾-沙普利運算法則”，又稱“延遲接受運算法則”。
發展
1984年，羅思研究全國住院醫師匹配項目所採用的運算法則，發現它與蓋爾-沙普利運算法則密切關聯。在隨後將近10年間對類似項目的研究中，包括對英國的研究，他發現，算法是否能夠實現穩定匹配，關係到實際效果的好壞。
1995年，羅思受邀設計一種新算法，以改善全國住院醫師匹配項目，滿足多種新需求，如畢業生男女情侶想在同一座城市就業。羅思及其同事設計的新算法1997年投入套用，如今每年為美國醫院超過2萬個崗位提供匹配。
套用“移植” 沙普利和羅思的研究在其他領域同樣得到套用，如美國小學生選擇自己“中意”的公立中學，而公立中學同樣選擇小學生。這類選擇、匹配或分配的主體都具備決策能力，有能動性。另一種情形下，選擇、匹配或分配完全帶有被動性質，如腎臟等人體捐獻器官如何與需要這些器官的病人匹配。沙普利及其同事建議採用一種非常簡單的運算法則，如今在美國一些州已經形成相當複雜的捐獻器官交換網路。
實踐意義
諾貝爾經濟學獎評選委員會在聲明中指出，沙普利採用合作博弈理論和比較不同匹配的方法進行研究，確保配置的穩定性，並在匹配過程中限制變數的影響，從而保證匹配的雙方不會被對方干擾。沙普利和其研究團隊的成果展現了一種特定方法的設計如何系統地有益於市場中的一方或另一方。而羅斯發現，沙普利的理論能夠闡明一些重要市場在實踐中的運作機制。通過一系列實驗，他發現“穩定”是了解特定市場機製成功的關鍵因素。此外，他還重新設計了現有的體系以匹配醫生和醫院、學生和學校、患者和志願者。這些新的發展都基於沙普利的匹配穩定理論，羅斯還就涉及道德限制和特定情況的方面進行了修正。
“沙普利值”提出了一個好的方法和機制，可以幫助企業如何根據邊際貢獻進行分配。這種方法是由沙普利在1951年首創的，對於一個參與者而言，不確定結局（如“賭博”、“抽彩”等）的值是以其效用大小對預期結局的評價：這是他期望獲得的先驗測度（這是“效用理論”的主題）。類似的方式，人們感興趣評價一種對策，即，測量該對策中每個局中人的值。由於“沙普利值”強烈的直觀吸引力及數學上的易處理，它已成為很多研究的套用的焦點，尤其是在大型經濟模型中。交換經濟模型已成為許多經濟理論研究的焦點。主要解答的概念是競爭均衡，其中價格以總供給等於總需求的方式確定。通過允許每個聯盟能自由地相互交換所擁有的商品而獲得的合作對策，被稱為市場對策。人們可以求得相應於市場對策的價值。在一個大型交換經濟中（單個的交易者是無關緊要的），所有價值配置具有競爭性；因而，若效用是光滑的，那么，所有競爭的配置也是價值的配置。這一值得注意的結果包括兩個很不相同的方面：其一，產生於供給和需求的競爭價格；其二是經濟行為的邊際貢獻。“沙普利值”在經濟理論上的其他套用包括稅收模型，其中，政治權力結構建立在交換經濟或生產經濟的基礎之上。此外，確定“沙普利值”的那些公理可以方便地轉換為適合於解決諸如以一種“公平”的方式考察配置聯合成本的問題。
羅斯意識到了沙普利的理論計算結果可以讓實踐中重要市場的運作方式變得更清晰。在一系列的經驗性研究中，羅斯和他的同事展示，為了理解某個特定市場制度為何成功，研究其穩定性是關鍵。羅斯後來成功地通過系統性的實驗室實驗支持了這個結論。羅斯在匹配理論和GS算法的基礎上，親身參與了諸多社會實際問題的解決，比如紐約市學生入學問題，醫學院學生分配問題以及腎臟移植的匹配問題等。
啟示
正如前面已經提到的，這類市場設計可以被推廣到大量價格的作用受限的市場裡，其中最主要的一類套用是學生擇校與就業。學生要選到自己的理想學校和就業單位，而學校和就業單位也想挑選最佳學生，這顯然屬於兩個群體之間如何最優配對且能穩定配對的問題。中國有不少研究高考擇校問題的學者，已經在這方面做了一些探索，比較不同的擇校機制之間的優劣。事實上，沙普利和後來的研究者已經對蓋爾-沙普利算法做了改進，也可以被套用到價格起作用的市場中，例如拍賣，尤其是網路拍賣。
