穩定婚姻問題

在組合數學、經濟學、電腦科學中，穩定婚姻問題（，簡稱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提出了盖尔-沙普利算法，這個系統可以確保如果男子組跟女子組的成員數皆相同（即N男N女）中，每一名男子和女子都能找到一名伴侶，以及每個婚姻都是穩定的。Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online ).

假設在n男n女中的存在兩對夫婦(M, W)和(m, w)，M男對w女喜好度大於現任妻子W女，並且w女對M男喜好度也大於現任丈夫m男：
 -{}-函數 穩定婚姻 {
     初始所有 m  M 與 w  W 為 單身
     當  單身 男子 m {
        w = m 是所有可考慮的女子中排名最高的
        若 w 是 單身
          撮合 (m, w)
        否則 有些夫婦 (m', w) 存在
          若 w 喜歡 m 多於 m'
            (m, w) 為 夫婦
            m' 為 單身
          否則
            (m', w) 仍為 夫婦
     }
 }

 參見 
 任務分配問題

參考

 外部連結 
 相異代表系面面觀，張鎮華

Category:組合數學
Category:博弈论
Category:數學問題