穩定婚姻問題

組合數學經濟學電腦科學中,穩定婚姻問題(英語: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   M 與 w   W 為 單身
       單身 男子 m {
       w = m 是所有可考慮的女子中排名最高的
        w 是 單身
         撮合 (m, w)
       否則 有些夫婦 (m', w) 存在
          w 喜歡 m 多於 m'
           (m, w) 為 夫婦
           m' 為 單身
         否則
           (m', w) 仍為 夫婦
    }
}

參見编辑

參考编辑

  1. ^ Gale, D.; Shapley, L. S. College Admissions and the Stability of Marriage. American Mathematical Monthly. 1962, 69 (1): 9–14. JSTOR 2312726. doi:10.2307/2312726. 
  2. ^ Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online页面存档备份,存于互联网档案馆)).

外部連結编辑