蓋爾-沙普利演算法

出自 MBA智库百科(https://wiki.mbalib.com/)

蓋爾-沙普利運演算法（Gale-Shapley algorithm）

　　蓋爾-沙普利運演算法（Gale-Shapley algorithm）簡稱 “GS演算法”，也稱為 “延遲接受演算法”（deferred-acceptance algorithm），是大衛·蓋爾（David Gale）和羅伊德·沙普利（Lloyd Stowell Shapley）為了尋找一個穩定匹配而設計出的市場機制。^[1]

　　市場一方的對象 Ai，i=1,2,...,m 向另一方的對象 Bj，j=1,2,...,n 發出邀約，每個 Bj 會對接到的邀約進行比較，保留自己認為最好的，拒絕其它的。邀約被拒絕的 Ai 繼續向其它的 Bj 發出新的邀約，直到沒有 Ai 希望再發出邀約為止。此時各 Bj 才最終接受各自保留的邀約。該演算法的一個關鍵之處在於，合意的邀約不會立即被接受，而只是暫時保留不被拒絕，也就是 “延遲接受”。^[2]

　　經濟學是研究資源最優配置問題的，而真實世界里配置資源的方式多種多樣，市場或者說價格機制是經濟學研究最多的。但是有一些市場裡頭，價格的作用受到法律、習俗或倫理道德等限制。最明顯的例子就是找對象的時候不是價高者得，而是情投意合才結成夫妻。

　　^[3] 1960年，大衛·蓋爾問沙普利：“不論人們一開始的最佳選擇是誰，人們最終都能獲得穩定的婚姻嗎？”

　　沙普利最終在回信中回答：“讓每個男生先向自己最佳選擇求婚，然後讓女生們在追求者中選出最喜歡的那一個，但先不告訴這個男生，而是告訴其他男生他們已經被拒絕。直到再也沒有追求者出現，女生才告訴她最喜歡的那個男生，他被接受了。接著那些被拒絕了的男生會向他們的第二選擇、第三選擇求婚，直到被接受為止。最後，每個女生都只剩下一個追求者。這時候他們的婚姻就是穩定的，因為男方和女方都會對拒絕過他們的異性產生反感。”

　　徵婚選擇的最佳策略：“有n個美女逐個介紹與你約會，依序每次只見一個，你選了她就沒機會見到後面可能更好的；如果讓她走了，也許後面都不如她，問怎麼選結果最好？”這問題經數學推演後有個很簡單的一般結果，最大概率選到了心儀美女的策略是：對於n個依次來臨的機會，首先對前[n/e]個僅僅作瞭解，不做選擇，然後開始將約會的與前面所有見到的相比，如果更好就接受，否則等下一個。這裡e=2.71828…，[n/e]是n/e的整數部分。

　　1962年沙普利和大衛合寫了論文《高校招生與婚姻穩定性》，併發表在《美國數學月刊》上。文中寫到：以10名男子和10名女子“婚配”為範例，設想如果由每一名女子先作選擇並向最中意男子“求婚”，然後再由每一名男子審視所獲所有“求婚”並回絕除了最中意女子以外的其他所有“求婚”，就可以實現穩定分配。設想的核心，是男子保留並延遲接受最中意女子的“求婚”。這一方法獲稱“蓋爾-沙普利運演算法則”，又稱“延遲接受運演算法則”。

　　看似兩個風馬牛不相及的事情，被這二位發現了相同的數學形式，不得不佩服數學家的敏銳目光。在這篇文章的基礎上，後人不斷將其應用於社會的各個方面，比如高校招生、腎臟匹配等，大大促進了社會的發展與穩定。

　　1984年，羅思研究全國住院醫師匹配項目所採用的運演算法則，發現它與蓋爾-沙普利運演算法密切關聯。在隨後將近10年間對類似項目的研究中，包括對英國的研究，他發現，演算法是否能夠實現穩定匹配，關係到實際效果的好壞。

　　1995年，羅思受邀設計一種新演算法，以改善全國住院醫師匹配項目，滿足多種新需求，如畢業生男女情侶想在同一座城市就業。羅思及其同事設計的新演算法1997年投入應用，如今每年為美國醫院超過2萬個崗位提供匹配。

　　應用於“移植” 。沙普利和羅思的研究在其他領域同樣得到應用，如美國小學生選擇自己“中意”的公立中學，而公立中學同樣選擇小學生。這類選擇、匹配或分配的主體都具備決策能力，有能動性。

　　另一種情形下，選擇、匹配或分配完全帶有被動性質，如腎臟等人體捐獻器官如何與需要這些器官的病人匹配。沙普利及其同事建議採用一種非常簡單的運演算法則，如今在美國一些州已經形成相當複雜的捐獻器官交換網路。

　　設有 5 位男士 A、B、C、D、E 和 4 位女士 a、b、c、d，他們的擇偶偏好順序如下：

　　對於以上案例，Gale-Shapley 匹配演算法的執行過程如下：

• 演算法第一輪，a 女士沒有接到邀約，b 接到 A 的邀約，c 接到 B、C 的邀約，d 接到 D、E 的邀約。C、E 先生被拒絕；

• 演算法第二輪，C 先生對 b 發出邀約被拒（因為 A>C），E 先生對 c 發出邀約被拒（因為 c已收到B、C的邀約，且c 只接受 A、B、C、D）；

• 演算法第三輪，C 先生對 a 發出邀約被拒（因為 a 只接受 A、B），E 先生對 b 發出邀約被拒（因為 A>E）；

• 演算法第四輪，C 先生對 d 發出邀約，此時 d 拒絕了 D，而 E 先生對 a 發出邀約被拒；

• 演算法第五輪，D 先生對 c 發出邀約被拒（因為 B>D），E 先生退出；

• 演算法第六、七輪，D 先生對 b、a 相繼發出邀約被拒，第八輪 D 先生退出。

• 至此，D、E 先生和 a 女士單身，b 女士正式接受 A 先生，c 女士正式接受 B 先生，d 女士正式接受 C 先生，匹配完畢。

　　最後實現的匹配是 A-b，B-c，C-d。基於以上執行過程有如下幾個結論：

• 1、Gale-Shapley 演算法不一定得到最大匹配。例如 A-a，B-b，C-c，D-d 的匹配能成 4 對，但不是穩定匹配。因為 A 偏好 b 而 b 也偏好 A。穩定匹配條件要求沒有配對的兩人不能相互 “喜歡”（單方面偏好可以）；

• 2、在演算法執行過程中，有可能出現先前保留的邀約後來被拒絕的情況。比如 d 女士開始時保留了 D 先生的邀約，但後來又拒絕他，轉而接受 C 先生，體現了演算法的延遲選擇性。如果不允許延遲選擇，必須當即拍板，則問題轉化為秘書問題，與 Gale-Shapley 演算法假設的情形不同；

• 3、如果把男女角色對調，女士發出邀約，男士來接受或拒絕，在本案例中得到的匹配結果也是 A-b，B-c，C-d。這是因為本案例中只有一個穩定匹配。當存在多個穩定匹配時，只要邀約的發出方不濫發邀約（一輪只邀約一個人），匹配的結果對邀約的發出方有利。如果濫發邀約（例如每輪邀約所有可接受者），則相當於角色對調，結果對邀約的接收方有利。

　　諾貝爾經濟學獎評選委員會在聲明中指出，沙普利採用合作博弈理論和比較不同匹配的方法進行研究，確保配置的穩定性，併在匹配過程中限制變數的影響，從而保證匹配的雙方不會被對方干擾。

　　沙普利和其研究團隊的成果展現了一種特定方法的設計如何系統地有益於市場中的一方或另一方。而羅斯發現，沙普利的理論能夠闡明一些重要市場在實踐中的運作機制。通過一系列實驗，他發現“穩定”是瞭解特定市場機制成功的關鍵因素。此外，他還重新設計了現有的體系以匹配醫生和醫院、學生和學校、患者和志願者。這些新的發展都基於沙普利的匹配穩定理論，羅斯還就涉及道德限制和特定情況的方面進行了修正。

　　“沙普利值”提出了一個好的方法和機制，可以幫助企業如何根據邊際貢獻進行分配。這種方法是由沙普利在1951年首創的，對於一個參與者而言，不確定結局（如“賭博”、“抽彩”等）的值是以其效用大小對預期結局的評價：這是他期望獲得的先驗測度（這是“效用理論”的主題）。

　　類似的方式，人們感興趣評價一種對策，即，測量該對策中每個局中人的值。由於“沙普利值”強烈的直觀吸引力及數學上的易處理，它已成為很多研究的應用的焦點，尤其是在大型經濟模型中。交換經濟模型已成為許多經濟理論研究的焦點。

　　主要解答的概念是競爭均衡，其中價格以總供給等於總需求的方式確定。通過允許每個聯盟能自由地相互交換所擁有的商品而獲得的合作對策，被稱為市場對策。人們可以求得相應於市場對策的價值。在一個大型交換經濟中（單個的交易者是無關緊要的），所有價值配置具有競爭性；因而，若效用是光滑的，那麼，所有競爭的配置也是價值的配置。

　　這一值得註意的結果包括兩個很不相同的方面：其一，產生於供給和需求的競爭價格；其二是經濟行為的邊際貢獻。“沙普利值”在經濟理論上的其他應用包括稅收模型，其中，政治權力結構建立在交換經濟或生產經濟的基礎之上。此外，確定“沙普利值”的那些公理可以方便地轉換為適合於解決諸如以一種“公平”的方式考察配置聯合成本的問題。

　　羅斯意識到了沙普利的理論計算結果可以讓實踐中重要市場的運作方式變得更清晰。在一系列的經驗性研究中，羅斯和他的同事展示，為了理解某個特定市場制度為何成功，研究其穩定性是關鍵。羅斯後來成功地通過系統性的實驗室實驗支持了這個結論。羅斯在匹配理論和GS演算法的基礎上，親身參與了諸多社會實際問題的解決，比如紐約市學生入學問題，醫學院學生分配問題以及腎臟移植的匹配問題等。

　　正如前面已經提到的，這類市場設計可以被推廣到大量價格的作用受限的市場里，其中最主要的一類應用是學生擇校與就業。學生要選到自己的理想學校和就業單位，而學校和就業單位也想挑選最佳學生，這顯然屬於兩個群體之間如何最優配對且能穩定配對的問題。中國有不少研究高考擇校問題的學者，已經在這方面做了一些探索，比較不同的擇校機制之間的優劣。

　　事實上，沙普利和後來的研究者已經對蓋爾-沙普利運演算法做了改進，也可以被應用到價格起作用的市場中，例如拍賣，尤其是網路拍賣。

• 博弈論
• 代際分配
• 擇優分配原理