Stable Matching(稳定婚姻)问题浅析

发布于 2020-12-21  340 次阅读


Stable Matching问题

假设有 $n$ 个男生,$n$个女生$~(n \le 10^3)$,每个人都在自己心中对 $n$ 个异性有一定的心仪程度排序。

我们定义一个Unstable matching为:如果存在一对不是情侣的男女符合以下情况:

对于该男,该女在他的心仪列表中处于现任女友的前面,对于该女,该男在他的心仪列表中亦处于现任男友的前面,那么这对男女必然有私奔的倾向、、

这样的情景即为Unstable matching。反之,若不存在这样一对有私奔倾向的男女,即为Stable matching。

现在,我们的任务就是构造一种Stable Matching。

Gale-Shapley算法:

(没错 Gale-Shapley 是两个老哥的名字)

1、$n$个男生去匹配他们的最心仪女生;

2、所有女生挑选喜欢他中的最心仪的男生;

3、被拒绝的男生把女生从心仪列表里面删掉(伤心了);

4、之后男生再选择最心仪的女生,女生依然选择向他表白的最心仪的男生(可以淘汰原来的);

PS:这里有一个很重要的特点:一旦一位女性找到配偶,她将不会再单身,只会替换成更好的(下文会提到)。

伪代码:

首先初始化所有男生的状态为自由

while 当男生没有未曾被匹配过,并且也没有向所有女生表白过{

每个男生按照对女生的喜欢程度选择舞伴

if 女生未被匹配到,则与男生进行配对

if 女生与已匹配的男生相比更喜欢当前的这个男生,则拆散重新匹配
else 该女生拒绝成为男生的舞伴

}

一、正确性证明:


先来考虑一下存不存在匹配:

假设:存在男性 Z 在算法终止后仍然未匹配到女性(孤独终老)

由此可知,一定有一位女性,假设为 A,也没有匹配到男性(抵制一夫多妻制

根据算法,一位单身女性一定会同意向她求婚的男性,且女性一旦有配偶就不会再次单身,所以女性 A 一定没有被求过婚

根据算法 while 循环条件,男性 Z 一定向所有女性求过婚算法才会终止

因此男性 Z 向女性 A 求过婚

产生矛盾,假设不成立,证明完毕

考虑 $B_i$ 匹配到 $G_i$,$B_j$ 匹配到 $G_j$ 并且是一个不稳定匹配。

那么就有 $B_i$ 更喜欢 $G_j$,$G_j$更喜欢$B_i$

那么 $B_i$ 一定会在 $G_i$ 之前先选择向 $G_j$ 表白,而 $G_j$ 也会同意(不稳定情况的定义),但是 $G_j$ 最后却是跟 $B_j$ 走了,这是违反我们的定义的(双方互相喜欢,女方却选择了一个更差的男生,不科学啊)

二、时间复杂度


在最差情况下,显然是 $O(n^2)$ 的。。

三、一个有趣的更强的结论


我们直接给出结论:

所有男生最后找到的一定是最佳的伴侣,而所有女生找到的一定是最差的伴侣。

咳咳,听起来感觉很离谱,因为男生有可能因为女生找到了更好的伴侣而被抛弃(惨)

诶,但是我们理性分析一波:

对于男生 A,

设最后他的女友是在他当初的心仪列表的第i位,那么在i位之前的那些女生,他是怎么追也追不到的:

因为即使那个女生X,也必然会有比他心仪的对象——男生Y,

而男生Y既然在当时向该女生表白,表明他认为比Y更好的女生都拒绝了他,而如果Y也拒绝了他,他最后在一起的女生必定排在Y之后。

所以,X 和 Y 是注定要在一起的,男生 A 选择女生X只是造成了一个 Unstable Matching。

诶,所以嘛,男生没有追到的那些女生,都是他太逊了硬实力不够,那么换句话说,他最后追到的女生是他最好的选择了。

女生最劣分配同理也可以证明。

这是一种感性的证明方法,意会即可。

四、代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1005;

int n;
int Map_Man[N][N],Map_Woman[N][N];
int Man_Partner[N],Woman_Partner[N];
int Propose[N];     //男生的求婚目标(第几顺位的女生) 
queue <int> Free_Man;       //未婚男生队列(男生追女生) 

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

int main(){
    n=read();
    memset(Man_Partner,-1,sizeof(Man_Partner));
    memset(Woman_Partner,-1,sizeof(Woman_Partner));

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            Map_Man[i][j]=read();   
    //第i个男生的第j顺位心仪女生是Map_Man[i][j] 

    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            int x=read();
            Map_Woman[i][x]=j;
        }
    //注意:第i个女生对第j个男生的心仪程度是Map_Woman[i][j] 

    for (int i=1;i<=n;i++)
        Free_Man.push(i);       //将所有男生加入未婚男生队列

    while (!Free_Man.empty()){
        int i=Free_Man.front();
        Propose[i]++;
        int like=Map_Man[i][Propose[i]];        //like为求婚目标 
        if (Woman_Partner[like]==-1){   //如果女生未婚 
            Woman_Partner[like]=i;      //互相选定
            Man_Partner[i]=like;
            Free_Man.pop();     //退出未婚队列 
        }
        else if (Map_Woman[like][i]<Map_Woman[like][Woman_Partner[like]]){      //女生找到了更好的男生 
            Man_Partner[Woman_Partner[like]]=-1;        //男生被淘汰,进入未婚状态
            Free_Man.push(Woman_Partner[like]); 
            Woman_Partner[like]=i;      //互相选定
            Man_Partner[i]=like;
            Free_Man.pop();
        }
    }

    for (int i=1;i<=n;i++)
        printf("%d\n",Woman_Partner[i]);
    return 0;
}

部分内容引用自:

1.https://www.cnblogs.com/jielongAI/p/9463029.html
2.https://blog.csdn.net/alwaysik/article/details/78949250
3.https://zhuanlan.zhihu.com/p/225925804

我们无法选择过去,但我们可以改变未来。