Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting

本文研究了带有平局和上下限配额的二部图多对多匹配问题，证明了临界松弛稳定匹配总是存在，并提出了一个多项式时间的 $\frac{2}{3}$-近似算法来求解最大基数的此类匹配。

要点

这是一篇关于**“如何在混乱中达成最佳配对”**的学术论文。为了让你轻松理解，我们把这篇论文里的复杂概念转化为一个生动的故事。

🎭 故事背景：大学里的“课程与导师”大匹配

想象一下，你是一所超级大学的教务系统。这里有两类人：

1. 学生（A 组）：他们需要选课，有些学生必须修满最低学分（比如 3 门课）才能毕业，有些学生最多只能选 5 门课。
2. 导师/课程（B 组）：有些导师必须带够最低数量的学生（比如 2 个）才开课，有些导师最多只能带 5 个学生。

这里的难点（也就是论文要解决的问题）：

• 有“平局”（Ties）： 学生可能觉得导师 A 和导师 B 一样好（都是“优秀”），导师也可能觉得学生甲和学生乙水平相当。这就导致没有绝对的“谁比谁好”，只有“谁和谁一样好”。
• 有“硬性指标”（Lower Quotas）： 就像上面说的，有些学生必须修满课，有些课程必须招满人。如果招不满，这门课就取消了，或者学生毕不了业。

目标： 我们要安排一种配对方案，满足两个条件：

1. 尽量满足硬性指标（Critical）： 让尽可能多的“必须修满课”的学生和“必须招满人”的课程得到满足。
2. 尽量让大家满意（Stable/Relaxed-Stable）： 尽量不让出现“我想换搭档，对方也想换我”的情况。

---

🚧 遇到的大麻烦

在传统的配对理论中，如果大家都严格排序（没有平局），我们很容易找到一个完美的“稳定匹配”。但是，一旦引入**“平局”（大家觉得差不多）和“硬性指标”**（必须招满），问题就炸了：

1. 完美稳定可能不存在： 有时候，无论你怎么排，总有人不满意，或者总有人没招满。
2. NP-Hard（超级难算）： 想要找到“人数最多”且“最稳定”的方案，计算机算到宇宙毁灭也算不出来（这是数学上的难题）。

---

💡 论文的核心贡献：一个聪明的“退一步”策略

既然找不到完美的，作者们提出了一个**“松弛稳定”（Relaxed-Stable）的概念，并设计了一个“打八折”的算法**。

1. 什么是“松弛稳定”？（退一步海阔天空）

在传统的“稳定”定义里，只要有一对学生和导师互相看对眼，且觉得对方比现在的搭档好，这就叫“不稳定”，必须拆散重组。

但在**“松弛稳定”**的世界里，我们允许一种特殊情况：

• 如果导师现在的学生已经**“爆满”了**（超过了最低要求），那么即使有个更好的学生想挤进来，导师也可以**“无视”**这个请求，维持现状。
• 比喻： 就像一家餐厅，如果它已经坐满了人（超过了最低营业人数），即使有个 VIP 想插队，老板也可以说：“抱歉，我们人满了，你等下一轮吧。”只要餐厅没亏本（满足最低人数），这种“插队失败”就不算餐厅“不稳定”。

结论： 作者证明了，在这种“退一步”的规则下，永远能找到一种配对方案，既满足了大家的硬性指标（Critical），又符合这种“松弛稳定”的规则。

2. 算法：像“升级打怪”一样的配对过程

作者设计了一个算法，让这个过程像游戏一样进行：

• 第一阶段（保底线）： 先不管谁好谁坏，先让那些“必须招满”的岗位和“必须修满”的学生先配对。这就像游戏里的“新手村任务”，先把最基础的生存指标（Lower Quotas）搞定。
• 第二阶段（处理平局）： 当基础指标搞定后，开始处理那些“觉得差不多”的平局情况。这里用了一个很巧妙的技巧，叫**“不确定提议”**（Uncertain Proposal）。
  • 比喻： 想象一个学生拿着简历去面试。如果面试官说“你和那个谁差不多”，学生就说：“那我暂时先不把你从名单上划掉，我保留一个‘不确定’的选项。”这样，如果后面发现有人更好，可以灵活调整；如果后面没人更好，这个选项就生效。这避免了因为死板的“平局”导致配对卡死。
• 第三阶段（查漏补缺）： 如果还有学生没招满，就让他们继续尝试，直到所有人都尽力了。

3. 结果：虽然不完美，但足够好（2/3 近似）

作者承认，因为问题太难（NP-Hard），我们可能找不到人数最多的那个完美方案。
但是，他们保证：我们找到的方案，人数至少是完美方案的 2/3。

• 比喻： 如果满分是 100 分，完美方案是 100 分。我们的算法能保证你至少拿到 66 分。而且，这是在计算机能算得出来的时间内拿到的。
• 为什么是 2/3？ 这是目前数学界已知在“有平局”的情况下，能做到的最好成绩了。再想提高，可能就要推翻某些数学假设了。

---

🌟 总结：这篇论文到底说了什么？

1. 现实很骨感： 在现实世界（如选课、招聘）中，既有“必须满足的最低要求”，又有“大家觉得差不多”的平局情况，想要一个完美的、所有人都满意的方案是不可能的，甚至算不出来。
2. 换个思路： 我们不需要追求绝对的“完美稳定”，只要允许那些“已经超额完成任务”的岗位拒绝插队（松弛稳定），就能保证永远有解。
3. 高效算法： 作者发明了一个聪明的算法，能在短时间内算出一个方案。虽然它可能不是人数最多的那个（可能只有 66%），但它保证了大家的底线需求（Critical），并且非常稳定（Relaxed-Stable）。

一句话概括：
这就好比在安排一场盛大的舞会，虽然有人觉得舞伴“半斤八两”，也有人“必须凑够人数”才能跳舞，但作者发明了一套规则，保证每个人都能跳上舞（满足底线），而且没人能轻易把别人挤走（松弛稳定），虽然可能不是人数最多的那场舞会，但绝对是最靠谱、最可行的一场。

技术摘要

这是一份关于论文《Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting》（存在平局的多对多匹配中的关键松弛稳定匹配）的详细技术总结。

1. 问题背景与定义

核心问题：
该研究关注的是多对多二分图匹配问题（Many-to-Many Bipartite Matching），其中引入了两个复杂的现实约束：

1. 偏好中的平局（Ties）： 顶点（代理人）在偏好列表中允许对多个邻居表示无差异（即排名相同），而不仅仅是严格排序。
2. 双边下限配额（Lower Quotas, LQ）： 二分图两侧的顶点不仅有最大容量（上限配额 $q^+$），还有最小容量要求（下限配额 $q^-$）。如果匹配数量低于 $q^-$，该顶点被视为“不足”（deficient）。

关键概念定义：

• 关键匹配（Critical Matching）： 指在满足所有顶点下限配额方面达到最大程度的匹配。即最小化所有顶点的“不足度”（deficiency，定义为 $\max\{0, q^-(u) - |M(u)|\}$ 的总和）。如果不存在满足所有下限的可行匹配，则寻求最接近的解。
• 松弛稳定性（Relaxed Stability）： 传统的“弱稳定”（Weak Stability）在存在平局和下限时可能不存在。松弛稳定性是一种放宽的概念：允许某些阻塞对（blocking pairs）存在，但前提是这些阻塞对涉及的一方是“盈余”的（即其匹配数超过了下限配额，且该阻塞对不会破坏关键性）。
• 目标： 寻找一个既是关键匹配（Critical）又是松弛稳定（Relaxed-Stable, RSM）的匹配，并尽可能最大化匹配的基数（Cardinality）。

2. 方法论与算法设计

作者提出了一种多项式时间的近似算法，该算法结合了两种现有框架的思想：

1. Király 的算法 [Kir13]： 用于处理存在平局但没有下限配额的多对一/多对多稳定匹配，提供 $2/3$ 的近似比。
2. Nasre 等人的多层级算法 [NNRS24]： 用于处理存在严格偏好和双边下限配额的关键匹配。

算法核心机制：

• 多层级提案框架（Multi-level Proposal Framework）：

  • 算法将顶点 $A$ 的层级从 $0$到$s+t$（$s, t$分别为$A$和$B$ 侧下限配额之和）进行划分。
  • **阶段 1（层级 $0$到$t-1$）：** 仅允许$A$侧顶点向$B$侧的下限配额顶点（LQ-vertices）提案。此阶段旨在优先满足$B$ 侧的下限需求。
  • 阶段 2（层级 $t$ 和 $t^*$）： 对应 Király 的算法步骤。在此阶段，$A$ 侧顶点使用原始偏好列表（包含平局）进行提案。引入了**不确定提案（Uncertain Proposal）**的概念来处理平局，确保在存在平局时仍能获得近似最优的稳定性。
  • 阶段 3（层级 $t+1$ 到 $s+t$）： 针对 $A$ 侧仍“不足”的顶点，允许它们向所有邻居提案，以进一步满足 $A$ 侧的下限需求。

• 克隆图构造（Cloned Graph Construction）：

  • 为了证明算法的正确性（关键性和松弛稳定性），作者构建了一个克隆图 $G_M$。
  • 将每个多对多顶点 $v$ 克隆为 $q^+(v)$ 个单对一副本。
  • 将多对多匹配 $M$ 映射为克隆图上的单对一匹配 $M^*$。
  • 利用分层结构分析 $G_M$ 中的边和路径，证明不存在能减少总不足度的增广路径，从而证明关键性。

• 拒绝与标记规则：

  • 当 $B$ 侧顶点拒绝提案时，如果涉及“不确定提案”，会进行特殊的标记处理，防止算法陷入死循环或产生不稳定的匹配。
  • 定义了“最喜爱邻居”（Favorite Neighbor）的广义定义，以处理多对多场景下顶点可能同时参与多个不确定提案的情况。

3. 主要贡献

1. 模型扩展与存在性证明：

   • 首次将松弛稳定性的概念推广到多对多、双边存在平局且双边存在下限配额的通用设置中。
   • 证明了在此复杂设置下，关键松弛稳定匹配（Critical-RSM）总是存在。

2. 算法设计与近似比：

   • 提出了一个多项式时间算法来计算关键松弛稳定匹配。
   • 证明了该算法计算出的匹配大小至少是最大可能大小关键松弛稳定匹配的 $2/3$。
   • 该近似比与已知处理平局的最优稳定匹配问题的最佳近似比一致。

3. 技术修正与改进：

   • 指出了 Király [Kir13] 中关于“不确定提案”定义的一个技术缺陷（即要求提案者必须完全订阅），并给出了修正后的定义，使其适用于多对多场景。
   • 将 Király 的框架成功扩展并整合到多层级提案框架中，解决了多对多场景下顶点容量大于 1 带来的复杂性（如一个顶点可能同时参与多个不确定提案）。

4. 复杂性结果：

   • 证明了在存在平局和下限时，判断是否存在“稳定且关键”的匹配是 NP-完全 的。
   • 证明了寻找最大基数的关键松弛稳定匹配是 NP-难 的。
   • 在“小集合扩张假设”（Small Set Expansion Hypothesis）下，证明了 $2/3$ 的近似比是紧的（即无法在多项式时间内获得更好的近似比）。

4. 研究结果

• 定理 1： 对于给定的二分图 $G=(A \cup B, E)$，其中顶点具有下限配额、上限配额及含平局的偏好，关键松弛稳定匹配总是存在的。此外，存在一个多项式时间算法，能计算出最大基数关键松弛稳定匹配的 $2/3$ 近似解。
• 运行时间： 算法的时间复杂度为 $O(m^2)$，其中 $m$ 是边的数量。
• 紧性： 除非小集合扩张假设失效，否则该近似比 $2/3$ 是最优的。

5. 意义与影响

• 理论价值： 填补了稳定匹配理论中的一个重要空白。之前的研究大多局限于严格偏好、单侧下限或单对一/多对一场景。本文统一并推广了这些模型，展示了在更复杂的现实约束下（如学生选课、医院招聘中的名额限制和并列排名），依然可以找到具有良好性质（关键性 + 稳定性）的解。
• 实际应用： 该模型直接适用于现实世界中的资源分配问题，例如：
  • 学生 - 课程分配： 学生有最低选课数要求，课程有最低报名人数要求，且学生可能对多门课程无差异。
  • 工人 - 企业分配： 某些工人必须被雇佣，企业有最低用工需求，且企业可能对多个工人无差异。
• 算法实用性： 提出的算法基于 Gale-Shapley 算法的扩展（提案 - 接受机制），易于实现，且提供了理论保证的近似解，为处理大规模实际数据提供了可行的工具。

总结来说，这篇论文通过创新的算法设计和严谨的理论分析，解决了带有平局和双边下限配额的多对多匹配问题中的存在性和近似优化难题，为相关领域的算法设计提供了新的基准。