互补偏好与偏好错位下稳定匹配何时存在？

互补性打破了替代性保证

标准多对一双边匹配理论假设偏好具有替代性：工人之间可以相互替代，因此企业对某个工人的需求不取决于它还雇了谁。在这一假设下，稳定匹配存在，延迟接受算法收敛。本文研究相反的情形——互补性，即工人之间彼此需要。论文给出的动机例子包括同伴效应；团队组建中只有某个特定成员加入后团队才有价值；交通中只有当路线的每一段都被确保后行程才能实现；以及分布式 AI 服务的服务链，只有所有处理步骤都执行服务才成立。

在互补性下，经典理论通常不再适用，稳定匹配甚至可能完全不存在。本文的模型是多对一双边的：企业对整个工人联盟持有效用，工人对自己所属的配置持有效用，关键在于双方的效用是独立给出的。正是这种独立性把本文与先前通过纳什议价等分配规则使双方排序一致的工作区分开来。例如在工资谈判中，工人希望高工资而企业希望压低支出，因此双方对同一联盟的评价正好相反，先前的对齐条件失效。

锚定工人加传递对齐

第一个条件是锚定假设：对每家企业，存在一个工人被包含在该企业所有可行联盟中。论文称这个工人为锚定工人。锚定使同一企业的任意两个可行联盟变得可比，并在后续收敛性证明中起核心作用，具体体现在势函数的单调性上。作者指出这一假设是温和的，因为对任何实例都可以通过为每家企业添加一个专属的虚拟工人来满足它；如果该虚拟工人的偏好与元排序一致，传递对齐得以保持，原实例的稳定匹配也不会丢失。

第二个条件是传递对齐。它要求在所有配置上存在一个弱序，即元排序，使得对每个工人以及该工人所属的每一对配置，工人的效用比较都与元排序一致。在共享工人的配置上，所有共享工人必须以相同方式排序，因此传递对齐蕴含了先前工作中成对对齐在工人之间比较上的限制。它对企业的效用不加任何限制，因此严格弱于成对对齐。论文指出，当所有工人的效用都能写成配置的同一个公共函数时，该函数本身就是元排序，传递对齐自动成立；对有限实例，元排序可以在多项式时间内判定和构造。

两个条件单独都不充分。论文给出一个反例：传递对齐成立但没有锚定工人，稳定匹配不存在；第二个反例中锚定条件和工人侧的成对对齐都成立，但工人偏好成环导致传递对齐失败，同样没有稳定匹配。两者合起来才是充分的：论文证明在锚定条件和传递对齐下，错位联盟匹配问题的每个实例都至少存在一个稳定匹配。作者还通过一个两个条件都不满足却仍存在稳定匹配的例子说明，这些条件是充分而非必要的。

CDAR 允许被拒联盟再次提案

CDAR 全称是带重新提案的组合延迟接受。它基于企业提案的延迟接受算法，本质区别在于允许重新提案，这是因为在互补偏好下，某个时刻被拒的联盟之后可能变得可接受。企业提出其尚未提案过的最佳联盟；算法记录拒绝集，即该联盟中不偏好它胜过当前配置的工人。如果拒绝集为空，则在释放该企业旧联盟、并解除雇佣了新联盟中工人的竞争企业的匹配之后，登记该配置。

重新提案规则是关键机制。被拒联盟从已提案列表中移除，从而有资格重新提案，但只有在它的拒绝集中所有工人都变为空闲的那一刻才允许。只要还有一个拒绝者仍被分配，就不允许重新提案，因为该工人可能偏好当前配置，允许重新提案会让阻塞对持续存在。算法只使用局部操作：不显式枚举联盟，也不构造元排序。

收敛性证明构造了一个 N 位势函数，把各企业的元排序等级读作以 m+1 为基的数的各位数字，其中 m 是元排序的等价类数量。论文证明 CDAR 在有限时间内终止并输出稳定匹配。论文还通过归约表明，CDAR 在先前成对对齐的设定下输出成对稳定匹配，因此本框架覆盖了那一类问题。在复杂度方面，论文报告对一般实例，每家企业可行联盟的数量可能是指数级的，使得选择尚未提案的最佳联盟成为主要开销；在可行联盟被隐式定义为图上路径的应用中，每次迭代可以借助 Yen 算法在不显式枚举的情况下完成。

稳定匹配内的帕累托最优需要严格偏好

论文把一项已知结果推广到互补设定：在严格偏好下，任何稳定匹配在稳定匹配集合内都是帕累托最优的，CDAR 的输出尤其如此。这里的帕累托最优只在稳定匹配集合上定义，而非在所有匹配上，且收益对企业与工人统一定义。

严格性很重要。论文表明当存在并列时，稳定匹配可能不是帕累托最优的。一个引理说明了原因：如果一个稳定匹配帕累托支配另一个，那么对任何支配主体，必然存在另一个收益不变的代理人，因此对帕累托最优的违反只能在存在并列时出现。作者建议用扩展的两位数收益来缓解并列，它把原始收益放在首位，并用次级效用值打破并列，但他们指出即使这种扩展收益也不一定能消除所有并列。

交通路径中两个条件由构造自动成立

论文把框架映射到面向交通安全的车辆路径分配。企业是车辆，工人是时空槽位，联盟是可行路线，锚定工人是车辆的出发槽位。企业效用是负到达时间，工人效用是沿路线的负行人总数。两辆车若路线占用同一槽位则相撞，可行路线必须与其他已匹配车辆的路线无碰撞。由于车辆的出发槽位必然包含在每条可行路线中，锚定条件由构造自动成立；由于槽位效用是对所有槽位共同的函数，它本身就是元排序，传递对齐也由构造自动成立。

数值验证使用 5×5 网格路网，含 25 个交叉口和 40 条路段，合成数据中车辆数 N 取 {5, 10, 20, 30, 40, 50, 100}，10 个随机种子，每条路段的行人计数从 0 到 10 均匀抽取。每辆车的出发槽位通过一个专用虚拟节点路由，该节点由长度为零、行人计数为零的虚拟边连接，从而由构造保证锚定条件。对所有 N 和所有种子，CDAR 都在有限时间内终止并输出稳定匹配。

有两项比较值得注意。第一是运行时间：当 N 至少为 30 时，实测运行时间低于定理 4 的理论上界，拟合实际迭代次数得到 O(N^4.8)，低于上界 O(N^m)。第二是消融实验：禁用重新提案的延迟接受变体总能终止，因为它对每个联盟最多提案一次，但其输出仍保留阻塞对，且残余阻塞对数量随 N 单调增加。CDAR 则始终有零个残余阻塞对。

该保证是充分而非必要且受范围限制

锚定条件和传递对齐是存在性的充分条件而非必要条件，论文用一个两个条件都不满足却仍存在稳定匹配的实例说明了这一点。因此该框架刻画的是一个存在性与可计算性都有保证的类，而不是稳定匹配何时存在的完整边界。

交通应用的复杂度结果是在一个额外结构假设下给出的，即仅通过出发延迟解决碰撞：碰撞只通过在锚定槽位推迟出发时间来解决，路线中间交叉口不发生等待。在该假设下，总复杂度对固定 m 是 N 的多项式；由于行人计数范围由网络决定且与车辆数无关，m 不随 N 增长，因此在任何固定网络上 CDAR 的运行时间是 N 的多项式。论文称其为关于 m 的切片多项式（XP）。数值验证是合成的，且局限于 5×5 网格网络；作者把策略可操纵性与公平性分析、扩展到服务链和工资谈判，以及用真实数据验证列为未来工作。

信任保证前先检查锚定与元排序

对于要判断该框架是否适用于某个分配问题的读者，论文自身的变量给出了一份具体清单。第一，每家企业是否存在一个被包含在其所有可行联盟中的工人？在交通路径中出发槽位自动回答了这一点；在其他设定中，论文指出可以添加一个虚拟工人来满足它，且不会丢失原实例的稳定匹配。第二，工人偏好是否在其所属配置上承认一个共同的元排序？当所有工人的效用是配置的同一个公共函数时它自动成立，正如交通情形中的负行人计数；对有限实例它可以在多项式时间内判定和构造。

论文中最具决策意义的区分是这两个条件各自带来什么。仅有锚定条件不保证稳定性，仅有传递对齐也不保证；只有两者合起来才保证每个实例都存在稳定匹配，且 CDAR 能找到它。第二个区分是存在性与构造性：先前工作证明了成对对齐下的存在性，却没有给出过程，而本文的贡献是一个只使用局部操作、不枚举联盟也不构造元排序的算法。第三个是重新提案规则本身，消融实验表明它并非装饰：禁用它会留下随车辆数增长的阻塞对，而 CDAR 不留任何阻塞对。

本文引用的文献