穩定婚姻問題求解器

穩定婚姻問題求解器

穩定婚姻問題求解器是 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

進階數學計算:

• 鄰接矩陣計算機 新
• antilog計算機
• Beta函數計算機
• 二項式係數計算機
• 二項機率分布計算機
• 按位計算機
• 布林代數化簡器 新
• 中央極限定理計算機
• 中國剩餘定理計算機
• 組合計算機 熱門
• 互補誤差函數計算機
• 複數計算機 熱門
• 連分數計算機
• 錯排 子階乘計算機
• 戴克斯特拉最短路徑計算機
• 熵計算機
• 誤差函數計算機
• 歐拉函數計算機
• 指數衰減計算機（高精度）
• 指數增長計算機 高精度
• 指數積分計算機
• 指數計算機（高精度）
• 擴展歐幾里得演算法計算機
• 階乘計算機 熱門
• 伽瑪功能計算機
• 黃金比例計算機
• 圖著色計算機 新
• 圖度數序列驗證器
• 群論階數計算機 新
• 半衰期計算機
• 漢密爾頓路徑檢查器 新
• 容斥原理計算機 新
• 卡諾圖 (K-Map) 求解器 新
• 線性規劃求解器 新
• 馬可夫鏈穩態分布計算機
• 最小生成樹計算機
• 模冪運算計算機 新
• 模乘逆元計算機
• 負二項分布計算機 新
• 網路最大流計算機 新
• 百分比增長率計算機 熱門
• 排列計算機
• 重複排列計算機 新
• 鴿巢原理計算機
• 平面圖檢查器 新
• 泊松分佈計算機
• 多項式根計算機與詳細步驟
• 原根計算機
• 機率計算機
• 機率分布計算機
• 比例計算機 熱門
• 二次公式計算機 熱門
• 環與體計算機 新
• 四捨五入計算機 熱門
• 科學計算機
• 科學記數法計算機 熱門
• 集合論計算機
• 有效數字計算機 熱門
• 穩定婚姻問題求解器 新
• 斯特林數計算機
• 立方和計算機
• 連續數之和計算機
• 平方和計算機
• 拓撲排序計算機 新
• 旅行推銷員問題求解器 (TSP) 新
• 真值表產生器
• 韋恩圖產生器3集合