💻 computer science

A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching

本文提出了一种在 CONGEST 模型下，仅使用少量共享随机比特，在一般二分图上计算近稳定匹配的常轮分布式算法，通过引入一种新颖的度数保护冻结规则，克服了以往需要多项式对数轮次或受限图结构的局限性。

原作者： Yijun Chang, Kushagra Chatterjee

发布于 2026-08-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Yijun Chang, Kushagra Chatterjee

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在计算机科学领域，有一个经典的谜题被称为“稳定婚姻问题”。想象一下，有一群人被分为两组，每个人都有一份关于他们更倾向于与谁配对的排名列表。目标是将每个人进行配对，使得没有任何两个人会比起目前的伴侣而更想和彼此在一起。如果存在这样一对人，他们被称为“阻碍对”（blocking pair），而这种排列就被视为是不稳定的。几十年来，计算机科学家一直知道如何找到完美的稳定排列，但在大型网络中进行此类操作需要大量的时间和通信。这个过程本质上是全局性的，这意味着每台计算机通常都需要等待信息传遍整个网络，这种延迟会随着网络规模的增大而增长。这为需要快速决策的现代系统制造了瓶颈。

为了解决这个问题，研究人员探索了“几乎稳定”匹配的概念。与其要求一个零阻碍对的完美排列，不如寻求一个足够好的解，允许存在极小且受控比例的不满意对。其希望在于，通过稍微放宽规则，使问题变得局部化，即计算机可以快速求解，而无需等待整个网络跟上进度。以往在通用网络（即某些人拥有许多连接，而另一些人连接很少）上解决此问题的方法，一直受限于随网络规模增长而增加的对数级延迟。问题在于：我们能否在常数步内找到一个近乎完美的解，而不受网络规模的影响？

由 Yi-Jun Chang 和 Kushagra Chatterjee 进行的一项新研究回答了这个问题：只要计算机共享极少量的随机信息，答案是肯定的。研究人员开发了一种方法，允许网络中的计算机在固定轮次内达到一种几乎稳定的匹配，即使网络规模扩大到包含数百万个节点，所需时间也不会增加。他们成功的关键在于一种被称为“度数保护冻结规则”（degree-guarded freezing rule）的巧妙新规则。在他们的系统中，当一个拥有许多连接的人与一个连接极少的人配对时，这对组合会立即被“冻结”。这意味着他们被锁定在原地，没有人可以尝试拆散他们。这种简单的机制防止了算法陷入高连接度个体不断更换伴侣的循环，而这曾是困扰以往尝试的问题。

研究人员发现，通过使用这种冻结规则，他们可以同时处理连接数差异巨大的网络，而无需将不同的人群分为不同的顺序阶段进行处理。这消除了对复杂多步阈值的需求，而正是这些阈值导致了早期算法的延迟。然而，这种方法产生的是统计意义上的平均优解，而非保证在每一步都得到完美结果。为了确保最终输出始终保持良好，计算机使用极少量的共享随机性——仅需几比特的公共数据——来商定处理过程中的特定停止时刻。这种共享种子使它们能够选择一个期望阻碍对数量保证较低的随机迭代点。

这项工作的意义超越了单纯的分布式系统理论模型。研究人员证明，该方法在分布式系统使用的标准通信模型中同样高效，在该模型中消息大小受到限制。他们还表明，共享随机性并非绝对必要；如果计算机在开始时没有共同的随机种子，它们也可以在稍长但仍高效的时间范围内在本地生成该种子。此外，该算法可以直接转化为现代数据中心使用的超大规模并行计算模型，在这些场景下，成千上欲千台机器协同工作且内存有限。在这种设定下，该方法实现了同样的常数时间性能，证明了其方案在不同计算架构下的鲁棒性。

该研究同时也阐明了问题的极限。作者证明，即使使用共享随机性，解决该问题的速度也不可能快于某个取决于稳定性严苛程度的最小时间。如果要求一个近乎完美的稳定解，所需时间会随着允许误差范围的缩小而增长。这为该问题建立了一个清晰的边界，表明虽然新方法是一项重大改进，但它并非消除所有约束的“万灵药”。这项工作留下的悬念是，是否有一种不依赖任何随机性的确定性方法也能实现同样的常数速度，但它明确了：只要有少许“共享的运气”，该问题可以在常数步内得到解决。

这一突破改变了我们对局部算法如何处理全局问题的理解。通过引入“度数保护冻结规则”，研究人员找到了绕过传统上对不同网络密度进行顺序处理需求的方法。其结果是一个既快速又具扩展性的系统，能够应对现实世界网络中那种连接分布极不均匀的复杂情况（即某些节点是枢纽，而另一些是叶节点）。论文总结道，对于任何固定的可接受不完美程度，都可以快速找到稳定匹配，且与网络规模无关，这标志着分布式计算理论迈出了重要的一步。

技术摘要：少量共享随机比特即可实现常数轮近似稳定匹配

问题陈述

本文研究了分布式计算背景下的稳定婚姻问题（stable marriage problem）。给定一个二部图 $G = (Y \cup X, E)$ ，其中顶点代表男性和女性，且对各自的邻居具有严格的偏好排序，目标是找到一个不存在“阻塞对”（即双方都比当前伴侣更偏好彼此的边）的匹配。

虽然经典的 Gale–Shapley 算法可以保证得到精确的稳定匹配，但它本质上是全局性的，在分布式 LOCAL 模型中需要 $\Omega(n)$ 轮，在 CONGEST 模型中需要 $\Omega(\sqrt{n/\log^2 n})$ 轮，即使对于直径较小的图也是如此。为了规避这些下界，本文专注于近似稳定匹配（almost stable matching）：寻找一个匹配 $M$ ，使得期望的阻塞对数量 $bp(M) $至多为$ \epsilon|E| $，其中参数$ 0 < \epsilon \le 1/2$。

核心问题在于，在具有任意度分布的一般二部图上，是否可以在常数轮（与 $n$ 无关）内实现这种近似，特别是在 CONGEST 模型中。

方法论

1. 基于分位数的框架

作者构建在 Ostrovsky 和 Rosenbaum [OR15] 引入的框架之上，该框架将每个顶点的偏好列表划分为 $k = \Theta(1/\epsilon)$ 个分位数。算法通过若干次迭代进行，男性向特定分位数内的女性提出请求。一个“分位数匹配”程序确保在常数轮之后，男性要么被匹配，要么耗尽了当前的当前分位数。

2. 识别先前的局限性

作者识别了 Ostrovsky–Rosenbaum 算法在一般图中导致对 $n$ 依赖的两个来源：

极大匹配（Maximal Matching）： 算法重复计算极大匹配以解决冲突，这产生了多对数级的轮复杂度。
度阈值（Degree Thresholds）： 为了处理非均匀度分布，之前的算法根据几何递增的度阈值，通过 $\Theta(\log n)$ 次连续迭代来处理男性。这种顺序处理过程阻碍了常数轮复杂度的实现。

3. 提出的算法创新

本文引入了两个关键的技术修改，以实现常数轮复杂度：

基于边的近似极大匹配（Edge-Based Almost-Maximal Matching）： 算法不再每一轮提议时都计算完整的极大匹配，而是使用一种截断的随机化程序来计算近似极大匹配。这确保了残余边（未被匹配覆盖的边）的期望数量很小，从而消除了对极大匹配复杂度的依赖。
度保护冻结规则（Degree-Guarded Freezing Rule）： 这是核心贡献。算法引入了一条规则：如果男性的度显著超过女性的度（即 $d(m) > R \cdot d(w)$ ，其中参数 $R = \Theta(1/\epsilon)$ ），则该对 $(m, w)$ 被“冻结”（并且 $w$ 相连的所有其他活跃边都被删除）。
- 机制： 一旦被冻结，该对便无法被取代。这防止了高度数的男性在过程后期被取代，否则会导致阻塞对数量激增。
- 计费论证（Charging Argument）： 冻结规则允许进行单一全局计费论证，从而同时处理所有度数。当一个男性被取代时，度保护规则确保 $d(m) \le R \cdot d(w)$ ，从而允许将取代的代价计入女性的度数。这消除了对 $\Theta(\log n)$ 个度阈值的需求。

4. 共享随机性的作用

算法运行 $L = \Theta(1/\epsilon^3)$ 次迭代。分析表明，这些迭代中的平均阻塞对数量很小，但算法无法确定性地识别哪一次特定的迭代会产生好的匹配。

使用共享随机性： 所有顶点使用 $O(\log(1/\epsilon))$ 个共享随机比特，以就一个均匀随机的迭代索引 $J$ 达成一致，并输出该次迭代的匹配。这确保了期望的阻塞对数量 $\le \epsilon|E|$ 。
不使用共享随机性： 作者利用低直径分解（Miller, Peng, and Xu [MPX13]）将图划分为若干簇。在每个簇内生成局部共享随机性，并并行运行算法。簇间边被计为潜在的阻塞对。这为轮复杂度增加了一个加性的 $O(\log n / \epsilon)$ 项。

关键结果

理论界限

使用共享随机性（定理 1）：
- 模型： CONGEST。
- 复杂度： $O\left(\frac{\log(1/\epsilon)}{\epsilon^4}\right)$ 轮。
- 随机性： $O(\log(1/\epsilon))$ 位共享随机比特。
- 保证： $E[bp(M)] \le \epsilon|E|$ 。
- 意义： 对于常数 $\epsilon$ ，轮复杂度为 $O(1)$ ，与 $n$ 和最大度 $\Delta$ 无关。
不使用共享随机性（定理 2）：
- 模型： CONGEST。
- 复杂度： $O\left(\frac{\log(1/\epsilon)}{\epsilon^4} + \frac{\log n}{\epsilon}\right)$ 轮。
- 保证： $E[bp(M)] \le \epsilon|E|$ 。
- 意义： 将之前针对随机化算法的最佳界限从 $O(\log^2 n)$ （源自 Ostrovsky–Rosenbaum）提升至对于常数 $\epsilon$ 的 $O(\log n)$ 。
大规模并行计算 (MPC)（定理 3）：
- 模型： 全面可扩展的 MPC（局部内存 $n^\delta$ ，总内存 $O(n+|E|)$ ）。
- 复杂度： $O\left(\frac{\log(1/\epsilon)}{\epsilon^4}\right)$ 轮。
- 意义： 这是第一个在全规模可扩展 MPC 模型下的近似稳定匹配算法。
下界（定理 4）：
- 在带有共享随机性的 LOCAL 模型中，任何以概率 $> 1/2$ 计算 $(1-\epsilon)$ -稳定匹配的算法都需要 $\Omega(1/\epsilon)$ 轮。这是由 Floréen 等人 [FKP+10] 关于精确稳定匹配的下界推导而来的。

重要性与主张

本文声称解决了关于在一般二部图上能否在常数轮内求解近似稳定匹配这一开放性问题。

打破对数壁垒： 先前的针对一般图的算法其轮复杂度与 $n$ 呈多对数关系（特别是在随机化 CONGEST 设置下为 $O(\log^2 n)$ ）。本研究通过度保护冻结规则和共享随机性，实现了 $O(1)$ 轮（对于常数 $\epsilon$ ）的复杂度，消除了对 $n$ 的依赖。
处理任意度数： 度保护冻结规则被呈现为一种新颖的技术，它允许使用单一全局计费论证来取代以往工作中复杂的、顺序的度阈值机制。
MPC 中的效率： 对全面可扩展 MPC 模型的适配证明了该算法在面临严苛单机内存限制的环境下的鲁棒性，在这种环境下许多图问题都非常困难。

作者指出，虽然使用共享随机性来选择输出迭代，但算法的核心逻辑（提议过程和冻结规则）本身并不一定需要它，从而可以通过牺牲一个加性的 $O(\log n)$ 项来移除这一假设。

AI 披露

文中包含一项特定的披露，声明该手稿最初是在 2024–2025 年间开发的，但在作者于 2025 年 1 月发现一个当时无法修复的关键证明缺陷后，该项目被放弃。该项目在 2026 年在 OpenAI 的 ChatGPT (GPT-5.6 Sol) 协助下得以重启。AI 提出了度保护冻结规则，修复了存在缺陷的证明，并协助完成了文本的大量起草和修订。作者断言他们已验证所有 AI 生成的内容，并对论文的正确性承担全部责任。