稳定婚姻问题

在组合数学、经济学、计算机科学中，稳定婚姻问题（英语：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 [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 （页面存档备份，存于互联网档案馆）).

外部链接