带平局的无初始禀赋房屋分配：扩展式代理人提议Gale-Shapley算法问询

好的，咱们来拆解这个针对无初始禀赋代理人、房屋带平局优先级的扩展GS算法，从执行逻辑到稳定匹配特性一一讲清楚：

一、执行逻辑 #

这个算法的核心还是延续了代理人主动发起提议的框架，但房屋的接受规则做了关键调整——允许在平局优先级时替换当前匹配。具体步骤可以拆成这样：

前置准备 #

• 每个代理人先明确自己的房屋偏好排序（毕竟是代理人提议，得知道自己想优先选哪些房）；
• 每个房屋拥有自己的代理人优先级排序（支持平局，比如多个代理人符合同一分配标准，处于同一优先级档位）。

具体执行步骤 #

1. 初始化：所有代理人处于未匹配状态，所有房屋的当前匹配对象为“无”。
2. 循环提议直到无未匹配代理人（或无提议可发起）：
   • 从所有未匹配的代理人中任选一位（提议顺序会影响平局场景下的最终匹配结果），让他向自己偏好列表里还没提过议的最高优先级房屋发起申请。
   • 房屋处理提议的规则是核心：
     • 如果房屋当前没有匹配对象，直接接受该代理人的提议，完成匹配。
     • 如果房屋已有匹配对象a'，则对比新提议代理人a和a'在房屋优先级中的位置：
       • 若a严格优于a'：立即抛弃a'，将匹配切换为a，a'回到未匹配状态。
       • 若a与a'优先级平局：同样抛弃a'，切换匹配为a，a'回到未匹配状态。
       • 若a弱于a'：直接拒绝提议，该代理人保持未匹配，继续向下一个偏好房屋发起申请。
3. 终止条件：当所有代理人要么匹配成功，要么已经向所有房屋提过议（无房可配），算法结束。

二、稳定匹配特性 #

由于引入了平局优先级和特殊的替换规则，这个扩展算法的稳定特性和标准GS有明显区别：

1. 不存在严格阻塞对 #

首先明确严格阻塞对的定义：一对（代理人a，房屋h）是严格阻塞对，当且仅当：

a严格偏好h胜于自己当前的匹配（或a未匹配），同时房屋h严格偏好a胜于自己当前的匹配。

在这个算法的结果中，这种严格阻塞对不可能存在——因为如果a真的更偏好h，他一定会向h提议；而如果h真的更偏好a，一定会接受提议替换掉原匹配，所以最终匹配里不会出现这种矛盾的情况。

2. 可能存在弱阻塞对，但不破坏弱稳定性 #

弱阻塞对指的是：a偏好h胜于当前匹配（或未匹配），且房屋h对a和当前匹配的代理人优先级平局。这种情况可能出现在最终匹配中，比如：

代理人a1和a2在房屋h1的优先级平局，a1先提议匹配到h1；之后a2向h1提议，h1按照规则替换为a2，a1变成未匹配。此时a1偏好h1胜于未匹配，h1对a1和a2平局，（a1, h1）就是一个弱阻塞对。

但这种情况并不违背弱稳定性——因为房屋已经在平局的代理人中做了选择，而a1没有机会再向h1提议（已经提过一次），所以不会出现双方都有动机打破当前匹配的情况。

3. 匹配结果不唯一（平局场景下） #

和标准GS不同，这个算法的最终匹配可能受代理人提议顺序影响：在存在平局优先级的房屋中，谁先提议、谁后提议，会决定最终房屋匹配的是哪一位平局代理人。比如上面的例子，若a2先提议，最终h1会匹配a1还是a2就会反过来。

4. 房屋优先，代理人可能面临“平局挤兑” #

标准代理人提议GS是代理人最优的，但这个扩展算法中，房屋会尽可能锁定优先级最高的代理人（包括平局的）——只要有平局的代理人提议，就会替换当前匹配。这意味着代理人可能会被和自己优先级平局的其他代理人挤掉，无法保证拿到自己能获得的最优匹配；反过来，房屋的匹配结果是其优先级最高的代理人集合中的一个，是房屋视角下的较优结果。

5. 退化为标准GS（无平局时） #

如果房屋的优先级排序中没有平局，这个算法就完全等价于标准的代理人提议Gale-Shapley算法——因为只有“优于”的情况才会触发替换，和标准规则一致。

内容的提问来源于stack exchange，提问作者Viktuhm