穩定婚姻問題

在組合數學、經濟學、電腦科學中，穩定婚姻問題（英語：stable marriage problem，簡稱SMP）又稱為穩定配對問題（stable matching problem），是指在兩組同樣大小的元素集合中（例如集合1是男子組、集合2是女子組，而他們各有偏好），尋求一個穩定配對組合所遇到的問題。一個組合在以下情況下並不穩定：

在集合1中有一個元素A更偏好於集合2的一些元素B，但元素A已被配對；而元素B亦更偏好於元素A多於配對給他的元素。在男女婚姻的角度來說，可以寫成一名男子A獲安排與女子D結婚，但A實際上是更喜歡女子B的。反之，女子B亦被安排與男子C結婚，但B實際上也是更喜歡A的。

簡單來說，一個穩定的組合是指在任何一個組合中（含A及B），每一個元素都是最偏好目前的組合多於任何其他的元素。亦即是說，穩定婚姻配對是指在同等數量男女當中，每一名男子皆能與自己最喜歡的女子結婚，反之亦然。然而，這個配對方式卻引來不少難題。

解決辦法

1962年David Gale和Lloyd Shapley提出了Gale–Shapley演算法，這個系統可以確保如果男子組跟女子組的成員數皆相同（即N男N女）中，每一名男子和女子都能找到一名伴侶，以及每個婚姻都是穩定的。^[1][2]

假設在n男n女中的存在兩對夫婦(M, W)和(m, w)，M男對w女喜好度大於現任妻子W女，並且w女對M男喜好度也大於現任丈夫m男：

函數 穩定婚姻 { 初始所有 m ${\displaystyle \in }$  M 與 w ${\displaystyle \in }$  W 為 單身 當 ${\displaystyle \exists }$  單身 男子 m { w = m 是所有可考慮的女子中排名最高的 若 w 是 單身 撮合 (m, w) 否則 有些夫婦 (m', w) 存在 若 w 喜歡 m 多於 m' (m, w) 為 夫婦 m' 為 單身 否則 (m', w) 仍為 夫婦 } } 

參見

• 任務分配問題

參考

1. Gale, D.; Shapley, L. S. . American Mathematical Monthly. 1962, 69 (1): 9–14 [2019-09-07]. JSTOR 2312726. doi:10.2307/2312726. （原始内容存档于2017-09-25）. 
2. Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online （页面存档备份，存于互联网档案馆）).

外部連結

• ，張鎮華