Gale-Shapley 後續文獻和一般問題
Gale-Shapley 算法是一種在兩個不同實體之間進行匹配的方法。它保證每個單獨的玩家都匹配並且匹配是穩定的。
在此基礎上創作了什麼樣的文學作品？當兩個實體中的個人數量不同時，社會福利如何變化，以至於不是每個人都可以匹配？是否有更快的方法來匹配個體（執行時間更短？）。最重要的是，Gale-Shapley 算法在經濟學中有哪些應用？
這似乎是一個非常奇怪的博弈論模型，因為當我閱讀算法有效性的證明時，問題似乎不是“離散的”；也就是說，優化誰與誰匹配並找到帕累託有效結果不能通過最大化連續函式來解決。（作為一個附帶問題，Gale-Shapley 分配帕累託有效嗎？）
編輯我的意思是，在第二段中，“問題似乎是“離散的”。所以我很抱歉。
> > 當兩個實體中的個人數量不同時，社會福利如何變化，以至於不是每個人都可以匹配？ > > >
在這種情況下，該算法可以正常工作。重要的假設仍然是基礎圖是二分的（並且偏好是可傳遞的）。如果我們允許給定類型的成員相互求婚，那麼我們就會失去收斂。假設我們有三個玩家： $ A, B, C $ . 我們有 $ A $ 的偏好為 $ (B, C, A) $ ; $ B $ 的偏好為 $ (C, A, B) $ ; 和 $ C $ 的偏好為 $ (A, B, C) $ . 所以 $ A $ 建議 $ B $ , 接受。然後 $ B $ 建議 $ C $ , 接受。這無與倫比 $ A $ . 下一個， $ C $ 建議 $ A $ , 接受。這無與倫比 $ B $ . 然後我們重複。
> > 是否有更快的方法來匹配個體（執行時間更短？） > > >
Gale-Shapley 的執行時復雜度為 $ \Theta(n^{2}) $ . 在圖論中，大多數二分匹配算法採用 $ \Omega(|E| \sqrt{|V|}) $ 時間。在最壞的情況下， $ |E| = |V|^{2}/4 $ . 所以我不會指望更好。
此外，這不是一個適合分而治之的問題。這真是一個貪婪的問題。您可以通過選擇隨機排序來降低預期的執行時間。不過，分析會涉及到。
> > 這似乎是一個非常奇怪的博弈論模型，因為當我閱讀算法有效性的證明時，問題似乎不是“離散的”；也就是說，優化誰與誰匹配並找到帕累託有效結果不能通過最大化連續函式來解決。 > > >
實際上，它是一個離散模型。在更傳統的經濟學領域，我們有連續變數。所以線性規劃是有意義的。如果我們從圖論的角度來看，我們實際上可以為穩定婚姻問題制定一個整數線性規劃。匹配問題可以用流的語言來表述。我們可以將流問題寫成 LP。流動約束形成一個凸多面體。如果圖是二分圖，則多面體的頂點是匹配的。這裡的技巧是我們必須添加額外的約束以確保我們最終得到正確的匹配（因為來自 Gale-Shapley 算法的匹配是唯一的，無論男人提出的順序如何）。
即使我們不遺餘力地制定線性程序，用手或電腦解決這個問題的 LP 也比使用算法效率低。
> > （作為一個附帶問題，Gale-Shapley 分配帕累託有效嗎？） > > >
Gale-Shapely 算法生成的匹配是核心。屬於核心的歸責滿足了任何联盟都不能串通其初始禀賦並改善其成員成果的屬性。如果沒有一組代理人可以在另一個參與者的結果不那麼有利的情況下改善他們的結果，則插補是帕累托最優的。所以核心分配是帕累托最優的。
有關 Gale-Shapley 的更多資訊，請查看我的部落格：https ://michaellevet.wordpress.com/2015/05/22/algorithmic-game-theory-stable-marriage-problem/