【學習記錄】穩定婚姻問題

定義

題意：有 $n$n 男 $n$n 女，每一個人都對其他 $n$n 個異性有不同程度的喜愛，用一個長為 $n$n 的串列表示，串列中的異性按喜愛程度從高到低排列，問能否找出一個結婚方案，使得不存在兩對夫妻 $(m,w^{\mathrm{\prime }}),(m^{\mathrm{\prime }},w)$(m,w′),(m′,w)，使得 $m$m 比起 $w^{\mathrm{\prime }}$w′ 更喜愛 $w$w，$w$w 比起 $m^{\mathrm{\prime }}$m′ 更喜愛 $m$m，

如果兩對夫妻 $(m,w^{\mathrm{\prime }}),(m^{\mathrm{\prime }},w)$(m,w′),(m′,w) 沒有上述情況就稱這兩對夫妻是穩定的，否則就是不穩定的，

用圖論的語言描述，我們要找的結婚方案就是二分圖中的一個完美匹配，且要是一個穩定匹配，

Gale-Shapley 演算法

這是一個符合直覺的演算法，直接寫成偽代碼就能表述意思，

初始化：所有男女都沒有物件

WHILE 還有某個男性沒有物件，且其尚未追求過所有女性
    選擇這樣一個男性 m
    設 w 為 m 尚未追求過的，且 m 喜愛程度最高的女性

    IF w 沒有物件
        讓 (m, w) 暫時結對
    ELSE
        設當前 w 與 m' 是一對
        IF w 比起 m' 更喜歡 m
            讓 (m, w) 暫時結對，m' 變為沒有物件
        ELSE
            m 被拒絕，仍然沒有物件
END

最后所有結對的男女即成夫妻，

演算法正確性

1. 演算法是否會終止？

   會，在 $n^2$n2 輪內終止，原因顯然，

2. 演算法是否找到完美匹配？

   是，否則必然有一對男女都沒有物件，而該男性由于沒有物件一定會追求該女性，使得兩者結對，

3. 演算法是否找到穩定匹配？

   是，考慮最終結果中任意兩對夫妻 $(m,w^{\mathrm{\prime }}),(m^{\mathrm{\prime }},w)$(m,w′),(m′,w)，如果 $m$m 追求過 $w$w，那么 $w$w 比起 $m$m 更喜愛 $m^{\mathrm{\prime }}$m′；否則由于男性按照喜愛程度降序選擇女性，$m$m 比起 $w$w 更喜愛 $w^{\mathrm{\prime }}$w′，無論哪種情況，這兩對夫妻都是穩定的，

演算法其他特性

定義女性 $w$w 是男性 $m$m 的可行物件（valid partner），若存在某個穩定匹配，使得 $(m,w)$(m,w) 是一對夫妻，對女性的男性可行物件定義類似，

定理：無論以何種方式實作演算法，演算法都只會回傳唯一的結果，且該結果滿足：

1. 對任意男性最優：演算法給出的其妻子，都是所有可行物件中，他的喜愛程度最高的，
2. 對任意女性最劣：演算法給出的其丈夫，都是所有可行物件中，她的喜愛程度最低的，

證明：設演算法給出的匹配是 $S^{?}$S?，我們先證明第一點，

考慮反證，由于男性追求女性是按照喜愛程度降序，因此如果存在男性 $m$m，使得其妻子 $w$w 不是所有可行物件中，$m$m 的喜愛程度最高的，那么 $m$m 已經被之前的某個喜愛程度更高的可行物件 $w^{\mathrm{\prime }}$w′ 拒絕過了，

不妨假設 $m$m 是演算法執行程序中第一個受到如此待遇的男性，按照定義，存在另一個穩定匹配 $S$S，使得 $(m,w^{\mathrm{\prime }})$(m,w′) 是一對夫妻，

設 $S^{?}$S? 中，$w^{\mathrm{\prime }}$w′ 的丈夫是 $m^{\mathrm{\prime }}$m′，顯然 $w$w 喜愛 $m^{\mathrm{\prime }}$m′ 甚于 $m$m，

再設 $S$S 中，$m^{\mathrm{\prime }}$m′ 的妻子為 $w^{\mathrm{\prime }\mathrm{\prime }}$w′′，那么由于之前所設，$m$m 是第一個被更喜愛的可行物件拒絕的男性，那么 $m^{\mathrm{\prime }}$m′ 會在 $S^{?}$S? 中與 $w^{\mathrm{\prime }}$w′ 而不是 $w^{\mathrm{\prime }\mathrm{\prime }}$w′′ 結婚，就只能是因為 $m^{\mathrm{\prime }}$m′ 喜愛 $w^{\mathrm{\prime }}$w′ 甚于 $w^{\mathrm{\prime }\mathrm{\prime }}$w′′，否則，$m^{\mathrm{\prime }}$m′ 會先追求 $w^{\mathrm{\prime }\mathrm{\prime }}$w′′，被拒絕后才會追求 $w^{\mathrm{\prime }}$w′，而這與之前所設矛盾，

由此可得在 $S$S 中，$(m,w^{\mathrm{\prime }}),(m^{\mathrm{\prime }},w^{\mathrm{\prime }\mathrm{\prime }})$(m,w′),(m′,w′′) 是不穩定的兩對夫妻，這與 $S$S 是穩定匹配相矛盾，

再證明第二點，假設演算法給出的匹配 $S^{?}$S? 中存在女性 $w$w，使得其丈夫 $m$m 不是所有可行物件中，$w$w 的喜愛程度最低的，那么存在另一個穩定匹配 $S$S，使得 $w$w 與所有可行物件中喜愛程度最低的 $m^{\mathrm{\prime }}$m′ 結對，顯然，$w$w 喜愛 $m^{\mathrm{\prime }}$m′ 甚于 $m$m，

設 $m$m 在 $S$S 中的妻子是 $w^{\mathrm{\prime }}$w′，那么由于男性最優性，$m$m 喜愛 $w^{\mathrm{\prime }}$w′ 甚于 $w$w，這導致 $(m^{\mathrm{\prime }},w),(m,w^{\mathrm{\prime }})$(m′,w),(m,w′) 是不穩定的兩對夫妻，這與 $S$S 是穩定匹配相矛盾，

代碼實作

以 UVa 1175 為例，實作這一演算法，時間復雜度為 $O(n^2)$O(n2)，

int n, pref[1005][1005], rnk[1005][1005];
// 分別為男對女的喜愛值串列，女對男的喜愛值排名（降序）
int cur[1005], wife[1005], husband[1005];
// 當前追求到哪一個
queue<int> q;
// 用佇列輔助求解
void GS(){
    memset(wife, 0, sizeof(wife));
    memset(husband, 0, sizeof(husband));
    for (int i = 1; i <= n; ++i)
        cur[i] = 1, q.push(i);
    while (!q.empty()){
        int h = q.front();
        q.pop();
        int targ = pref[h][cur[h]++];
        if (!husband[targ] || rnk[targ][h] < rnk[targ][husband[targ]]){
            wife[h] = targ;
            if (husband[targ] > 0){
                wife[husband[targ]] = 0;
                q.push(husband[targ]);
            }
            husband[targ] = h;
        } else if (cur[h] <= n){
            q.push(h);
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", wife[i]);
}

參考資料

• 《Algorithm Design》