穩定婚姻問題求解器

穩定婚姻問題求解器

穩定婚姻問題求解器是 Gale-Shapley 延遲接受演算法的互動式實作。這套演算法由 David Gale 和 Lloyd Shapley 於 1962 年提出，證明了在給定每個成員對另一方完整排名的情況下，兩個規模相同的群組之間總能產生穩定的配對。此工具接收您的偏好清單，逐步運行演算法，並以穩定匹配結果、動畫二分圖視覺化、偏好熱圖以及不存在阻礙對的驗證證明來展示結果。

什麼是穩定婚姻問題？

給定兩個大小相等的互斥集合 — 例如 n 個男人和 n 個女人，或 n 個申請人和 n 個職位 — 且每個成員都對另一集合的所有成員有完整的排名，匹配是指這兩個集合之間的一一對應配對。如果匹配中不存在一對 (a, b) 相比目前的伴侶更喜歡彼此，則該匹配被稱為穩定的。

形式上，如果不存在阻礙對，則匹配 M 是穩定的。阻礙對 (a, b) 是指 a 與 b' 匹配且 b 與 a' 匹配，使得：

如果這兩個條件都成立，a 和 b 就會拋棄目前的伴侶，從而導致匹配不穩定。穩定匹配是指不存在此類配對的匹配。

Gale-Shapley 演算法

Gale 和 Shapley 以構造性的方式證明了對於任何偏好集，穩定匹配總是存在的，並給出了一種高效的演算法。演算法分輪進行：

1. 每個未訂婚的提議者向其名單中排名最高且尚未拒絕過他的接收者提議。
2. 每個收到一個或多個提議的接收者選擇其中最喜歡的一位（與目前暫時的未婚夫進行比較）並暫時接受；其餘提議被拒絕。
3. 被拒絕的提議者重新恢復自由，並在下一輪中向其次選對象提議。
4. 當每個提議者都已訂婚時，演算法終止 — 這保證在最多 n² 次提議內發生。

關鍵理論屬性

存在性與唯一性

穩定匹配總是存在的（Gale & Shapley, 1962），但並不一定是唯一的。對於給定的偏好集，可能存在多個穩定匹配，它們構成一個按聯合偏好排序的格。

提議者最佳化

當其中一方發起提議時，Gale-Shapley 會產生提議者最佳化的穩定匹配：每個提議者都獲得了他在任何穩定匹配中可能獲得的最佳伴侶。根據對稱性論證，這也是接收者最差化的匹配 — 接收方獲得了其最差的穩定伴侶。在此計算機中切換提議方通常會改變結果。

提議者的策略性

在 Gale-Shapley 演算法下，提議者沒有動機隱瞞其真實偏好：實話實說對他們來說是占優策略。然而，接收者有時可以通過策略性的虛假報告獲益 — 這也是為什麼美國醫學生匹配系統將學生設計為提議方的原因之一。

偏遠醫院定理

在所有穩定匹配中，未匹配的代理人集合是完全相同的。因此，如果您的實例大小不平衡（超出了此經典工具的範圍），在每個穩定解中，未匹配的人都是相同的。

輸入格式

此計算機要求每行一位成員，姓名後接冒號，然後是用逗號分隔的完整排名偏好清單：

要求：

• 兩個群組的成員數量必須完全相同。
• 每個成員必須對另一組的所有成員進行排名 — 不支援部分清單。
• 姓名可以使用字母、數字、下劃線、連字符、空格和常見的 Unicode 字母。
• 每側支援多達 15 名成員，以實現流暢的互動動畫。

如何使用這款計算機

1. 在左側文本區域輸入 A 組偏好 — 每行一位成員，提供完整的排名清單。
2. 在右側文本區域輸入 B 組偏好 — 格式相同，每行一位成員。
3. 選擇提議方。 選擇 A 組或 B 組。您可以嘗試兩者來比較 A 最佳化與 B 最佳化的結果。
4. 點擊『計算穩定匹配』。 計算機將運行 Gale-Shapley 並產生穩定配對、統計數據、動畫和穩定性證明。
5. 操作動畫播放控制 使用播放 / 單步 / 重置控制來按順序查看每次提議、接受、更換和拒絕。
6. 檢查熱圖。 每個單元格顯示排名；帶有黃色邊框的單元格構成最終匹配 — 觀察這些單元格的位置高低，即可了解雙方的『滿意度』。

實作範例 — 經典 3×3

男方：Alex, Bryan, Chris。女方：Bea, Claire, Diana。偏好如下：

運行由男方提議的 Gale-Shapley 演算法，在單輪內即可產生 Alex–Bea, Bryan–Claire, Chris–Diana 的配對（每個男人的首選都與一位首選是別人的女人匹配 — 無衝突）。此匹配是穩定的：不存在任何一對男女會因為更換伴侶而讓雙方都過得更好，因此不存在阻礙對。

現實世界應用

為什麼 Lloyd Shapley 獲得諾貝爾獎

2012 年，瑞典皇家科學院將諾貝爾經濟學獎授予 Lloyd Shapley（因其理論貢獻，與已故的 David Gale 共享）和 Alvin Roth（因將該理論應用於實際市場，包括重新設計美國醫療住院醫師匹配和腎臟交換網絡）。該獎項旨在表彰『穩定分配理論及市場設計實踐』。

常見問題

什麼是穩定婚姻問題？

穩定婚姻問題是指：給定兩個規模相同的群組，且每個成員都對另一組的所有成員按偏好排序，我們能否將所有人配對，使得不存在兩個人彼此更喜歡對方而勝過目前的伴侶？這樣的配對稱為穩定匹配。Gale-Shapley 演算法以 O(n²) 的時間複雜度解決此問題，且總能找到穩定匹配。

Gale-Shapley 演算法如何運作？

Gale-Shapley 延遲接受演算法分輪進行。在每一輪中，每個目前未訂婚的提議者向其名單中排名最高且尚未拒絕過他的接收者提議。每個接收者暫時接受目前收到的最佳提議並拒絕其餘提議；任何被取代的提議者將再次恢復自由。當沒有提議者處於自由狀態時，演算法終止，這最多在 n² 次提議中發生。

穩定匹配是唯一的嗎？

不是。一個穩定婚姻實例可能有多個穩定匹配。然而，當其中一方提議時，Gale-Shapley 總是產生提議者最佳化的穩定匹配：每個提議者都獲得了他在任何穩定匹配中可能獲得的最佳伴侶。對稱地，這對另一方來說也是接收者最差的匹配。切換提議方通常會產生不同的穩定匹配。

什麼是阻礙對？

阻礙對是指目前未匹配的一對 (a, b)，其中 a 相比目前伴侶更偏好 b，且 b 也相比目前伴侶更偏好 a。如果存在任何阻礙對，則該匹配是不穩定的，因為這兩個人更願意與彼此配對。穩定匹配沒有阻礙對，此計算機在每次求解後都會自動驗證這一點。

穩定匹配有哪些實際應用？

Gale-Shapley 演算法為美國國家住院醫師匹配計劃（NRMP）提供支援、波士頓和紐約的學校選擇系統、大學錄取、器官捐贈腎臟交換鏈以及室友分配系統。Lloyd Shapley 和 Alvin Roth 因這項工作部分獲得了 2012 年諾貝爾經濟學獎。

兩個群組的大小必須相同嗎？

在經典的穩定婚姻表述中，是的。雙方必須擁有相同數量的成員，且每個人必須提供對另一方的完整排名。雖然存在不平衡的變體（例如具有不完整名單的穩定匹配或醫院-住院醫師問題），但需要修改演算法。此計算機強制要求等量規模和完整的偏好清單。

延伸閱讀

• 穩定婚姻問題 — 維基百科
• Gale-Shapley 演算法 — 維基百科
• 美國國家住院醫師匹配計劃 — 維基百科
• 2012 諾貝爾經濟學獎 — Shapley 與 Roth