Gale-Shapley Algorithms

简称“GS 算法”，也称为延迟接受算法。是 Gale 和 Shapley 为了寻找一个稳定匹配而设计出的市场机制。运行时间在算法输入的大小上是线性的。根据其使用方式，它可以找到对匹配一侧的参与者或另一侧的参与者最佳的解决方案。

问题描述给出一个 $n$ 个男性的集合 $M$ ，和 $n$ 个女性的集合 $W$ ，其中：

每位男性根据对所有女性的心仪程度从高至低进行排名；
每位女性根据对所有男性的心仪程度从高至低进行排名。

根据以上条件，我们需要找到一个“稳定匹配”。

基本概念

匹配 Matching

匹配 $S$ 是一个包含有序数对 $m-w$ 的集合，其中 $m \in M$ 且 $w \in W$ ，其中：

每个男性最多出现在一个数对中；
每个女性最多出现在一个数对中。

完美匹配 Perfect matching

不稳定因素 Unstable pair

给出一个完美匹配 $S$ ，如果其中存在一个男性 $m$ 和一个女性 $w$ 同时满足下列条件：

不在匹配 $S$ 中；
$m$ 比起他当前配偶，更喜欢 $w$ ;
$w$ 比起她当前配偶，更喜欢 $m$ 。

则称男性 $m$ 和女性 $w$ 是不稳定的，也就是说， $(m,w)$ 是不稳定因素。

稳定匹配 Stable matching

一个不存在不稳定因素的完美匹配。

Gale-Shapley 算法

一个直观的，确保能找到一个稳定匹配的算法

算法策略

男性策略：单身的男性会主动出击，根据喜好降序向所有女性求婚，直到有配偶为止；
女性策略：被动等待男性求婚，如果女性仍处于单身，则直接接受；有配偶的情况下被更心仪的男性求婚，则会抛弃原来的，接受更好的。

算法特征

G-S算法具有：有穷性、完美性、稳定性、男性最佳分配、女性最劣分配等特征

有穷性：算法最多在 $n^2$ 次 while 迭代后一定会结束。
完美性：算法中所有男性和女性都匹配完毕。
稳定性：算法产生的匹配中，不会有不稳定因素
男性最佳分配 Man-optimal Assignment：GS 算法中每个男性都能分配到最佳的正当配偶，所以 GS 算法得到的分配一定是男性最佳分配。
- 正当配偶 Valid Partner：如果存在一个稳定匹配中男性和女性匹配在一起，则称女性是男性的正当配偶。
女性最劣分配：GS 算法中女性一定分配到的是最差的正当配偶。

算法实现

# Gale-Shapley Algorithm (Stable Marriage Problem)
def gale_shapley(men_prefs, women_prefs):
    """
    实现 Gale-Shapley 算法来解决稳定婚姻问题。

    参数：
    men_prefs -- 一个字典，键是男性的名字，值是该男性按心仪程度排序的女性列表。
    women_prefs -- 一个字典，键是女性的名字，值是该女性按心仪程度排序的男性列表。

    返回：
    stable_matching -- 一个字典，键是女性，值是其配对的男性。
    """

    # 所有男性都未配对，加入空闲队列
    free_men = list(men_prefs.keys())

    # 初始化每个男性提亲的索引（谁还没向谁提过）
    men_next_proposal = {man: 0 for man in men_prefs}

    # 女性当前的配对情况
    engaged = {}  # woman -> man

    # 构建女性对男性的排名字典，便于快速比较
    women_rankings = {
        woman: {man: rank for rank, man in enumerate(prefs)}
        for woman, prefs in women_prefs.items()
    }

    while free_men:
        man = free_men[0]  # 拿到第一个空闲男性
        man_pref_list = men_prefs[man]
        woman = man_pref_list[men_next_proposal[man]]  # 下一位想要追求的女性

        print(f"{man} 向 {woman} 提出配对请求。")

        men_next_proposal[man] += 1  # 更新提亲索引

        if woman not in engaged:
            # 女性当前空闲，直接接受
            engaged[woman] = man
            free_men.pop(0)  # man 成功配对，从空闲队列中移除
            print(f"{woman} 接受了 {man} 的配对请求。")
        else:
            current_man = engaged[woman]
            # 比较当前配对与新求婚者的优先级
            if women_rankings[woman][man] < women_rankings[woman][current_man]:
                # 女性更喜欢新求婚者，替换
                engaged[woman] = man
                free_men.pop(0)
                free_men.append(current_man)  # 当前男友被甩，重新加入空闲队列
                print(f"{woman} 拒绝了 {current_man}，接受了 {man}。
")
            else:
                # 女性更喜欢现任，拒绝求婚者
                print(f"{woman} 拒绝了 {man}，继续与 {current_man} 配对。
")

    return engaged


# ===================== 测试代码 =====================
if __name__ == '__main__':
    # 示例偏好列表
    men_preferences = {
        'A': ['X', 'Y', 'Z'],
        'B': ['Z', 'Y', 'X'],
        'C': ['Y', 'X', 'Z']
    }

    women_preferences = {
        'X': ['B', 'A', 'C'],
        'Y': ['A', 'B', 'C'],
        'Z': ['C', 'B', 'A']
    }

    print("\n运行 Gale-Shapley 算法：\n")
    result = gale_shapley(men_preferences, women_preferences)
    print("\n最终的稳定匹配结果：")
    for woman, man in result.items():
        print(f"{man} 和 {woman} 配对")

Gale-Shapley Algorithms - 稳定匹配问题