稳定婚姻问题

组合数学经济学计算机科学中,稳定婚姻问题(英语: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提出了盖尔-沙普利算法,这个系统可以确保如果男子组跟女子组的成员数皆相同(即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页面存档备份,存于互联网档案馆)).

外部链接

编辑