关于具有整数选择函数的稳定配对问题

《Discrete Applied Mathematics》：On a stable partnership problem with integer choice functions

　　

摘要
我们考虑众所周知的稳定室友问题和非二分图稳定分配问题的一个极其一般的推广。在该问题的设定中，给定一个有限非二分图 $G=(V,E)$，边容量为非负整数 $b(e)\in\mathbb{Z}^+$，$e\in E$，其中对于每个顶点（"代理"）$v\in V$，其关联边集 $E_v$ 上的偏好通过作用在容量有界的 $\mathbb{Z}^{E_v}_+$ 向量上的选择函数 $C_v$ 给出，该选择函数遵循可替代性和规模单调性的标准公理。我们将相关的稳定性问题称为带有整数选择函数的稳定伙伴关系问题，简称 SPPIC。

在推广已知特定情形结果的基础上，我们给出了 SPPIC 的可解性准则，并开发了一种寻找稳定解（称为稳定伙伴关系）或确定稳定伙伴关系不存在的算法。此外，该算法一般地构造一个对 $(x,\mathcal{K})$，其中 $x\in\mathbb{Z}^E_+$，$\mathcal{K}$ 是 $G$ 中一组两两边不相交的奇圈，具有如下性质：若 $\mathcal{K}=\emptyset$，则 $x$ 是一个稳定伙伴关系；若 $\mathcal{K}$ 非空，则稳定伙伴关系不存在，且此时集合 $\mathcal{K}$ 被典范地确定。我们的构造本质上使用了作者先前关于 SPPIC 对应二分图情形的结果。

引言
自 Gale 和 Shapley 关于稳定婚姻的著名工作[8]以来，已出现了许多关于有限二分图 $G=(V,E)$ 中稳定分配问题的宝贵研究。我们可以有条件地将"布尔"情形与"数值"情形区分开来，在前者情形中，分配指的是边的一个子集；在后者情形中，分配指的是定义在 $E$ 上的实值或整数值函数。一种流行的"数值"稳定性模型是 Baiou 和 Balinski[2]提出的稳定分配问题，其中（在实版本中）边 $e\in E$ 被赋予非负上界即容量 $b(e)\in\mathbb{R}^+$，顶点 $v\in V$ 被赋予配额 $q(v)\in\mathbb{R}^+$，每个顶点（"代理"）$v$ 的偏好通过其关联边集 $E_v$ 上的规定线性序给出。

作为稳定分配问题及其他已知问题（如"一对多"、"多对多"、"多样化"类型等）的极大推广，Alkan 和 Gale[1] 引入并研究了二分图 $G=(V,E)$ 上的一个一般稳定性模型，其中每个顶点 $v\in V$ 处的偏好依赖于选择函数（CF）$C_v$，该函数作用于盒子 $\{z\in\mathbb{R}^{E_v}_+: z(e)\leq b(e) \forall e\in E_v\}$ 的闭子集中的向量（整个盒子及其整数子格是典型样本）。假定每个 $C_v$ 遵循一致性和可替代性的标准公理（可追溯至 Kelso 和 Crawford[15]、Roth[17] 和 Blair[5]）。文献[1]中的核心结果是，在这些条件下，稳定分配（在该文中称为"稳定调度匹配"）总是存在的，且这些稳定分配构成一个格 $\mathcal{L}$。此外，通过增加规模单调性这一公理，格 $\mathcal{L}$ 变为分配格。

近期，Alkan–Gale 模型的整数版本在文献[14]中得到了深入研究，其中每个 $C_v$ 作用于整数盒子 $\mathcal{B}_v=\{z\in\mathbb{Z}^{E_v}_+: z(e)\leq b(e) \forall e\in E_v\}$；我们将此版本称为整数 Alkan–Gale 问题，简称 IAGP。文献[14]的主要结果之一，是开发了一种构造稳定分配格 $\mathcal{L}$ 的偏序表示 $(\mathcal{P},\preccurlyeq)$ 的算法（由于 $\mathcal{L}$ 是分配格，故存在这样的偏序表示）。更具体地说，$\mathcal{P}$ 是由某些边单圈（称为旋转）$R$ 及其权重 $\tau\in\mathbb{Z}_{>0}$ 组成的对 $(R,\tau)$ 的族（允许重复），$\preccurlyeq$ 是 $\mathcal{P}$ 上的一个偏序。它们具有如下性质：$\mathcal{L}$ 同构于 $(\mathcal{P},\preccurlyeq)$ 的闭函数格，其中函数 $\lambda:\mathcal{P}\to\mathbb{Z}^+$ 称为闭函数，是指它不超过 $\tau$，且对于满足 $(R,\tau)\preccurlyeq(R',\tau')$ 且 $\lambda(R',\tau')>0$ 的对 $(R,\tau),(R',\tau')\in\mathcal{P}$，有 $\lambda(R,\tau)=\tau$。

（注意，如文献[14]所示，$|\mathcal{P}|$ 不超过 $b_{\max}|E|$，其中 $b_{\max}:=\max\{b(e):e\in E\}$，且该偏序可以在伪多项式时间内构造。另一方面，文献[14]给出了一个小图 $G$ 和大容量的例子，使得 $|\mathcal{P}|=b_{\max}$；在该例子中只有两个旋转，从 $\mathcal{L}$ 的最小元素到最大元素移动时交替出现 $b_{\max}$ 次。）

关于计算复杂性方面，假设每个选择函数 $C_v$ 由一个预言机给出，当被询问容量 $b$ 有界的向量 $z\in\mathbb{Z}^{E_v}_+$ 时，输出"可接受"的向量 $C_v(z)$。通常假设 $C_v$ 的每次调用（"预言机调用"）所需时间为 $|E_v|$ 的多项式；此外，有时认为估算预言机调用的次数比估算其实现的复杂性更为合理，这在涉及预言机的广泛问题范围内都是如此。

接下来我们进入本文关注的话题。自1980年代中期以来，除了大量关于二分图稳定性模型的研究外，其非二分图对应物也出现了重要结果。通常，非二分图问题看起来更为复杂，且稳定解的存在性不获保证；对于经典稳定婚姻问题的非二分图类似物——稳定室友问题（简称 SRP）——的一个简单反例早在文献[8]中已由 Gale 和 Shapley 展示。Irving[10] 提出了一个线性时间算法，要么找到 SRP 的一个解——即一个稳定匹配——要么声明没有解存在。Tan[18] 建立了 SRP 中稳定匹配存在的充要条件，依赖于在该工作中引入的新结构——稳定划分。文献[18]证明了对于任意图 $G=(V,E)$ 及集合 $E_v$（$v\in V$）上的线性序，稳定划分总是存在的，且可在线性时间内找到。粗略地说，稳定划分由两部分组成：$G$ 中的一个匹配 $M$ 和一组奇圈 $\mathcal{K}$；该 $\mathcal{K}$ 被典范地确定，并作为 SRP 可解性的"障碍"，即稳定匹配存在且 $M$ 是其中之一当且仅当 $\mathcal{K}$ 为空。另见文献[19]关于 SRP 中稳定划分的附加结果，以及文献[9]关于将问题归结为具有对称线性序的对称二分图中的稳定婚姻问题。

此后，在非二分图上更一般的稳定性问题上获得了宝贵结果；我们指出以下三篇相关工作（其中两篇将在我们后续描述中使用）。文献[4]和[6, 第5节]考虑了稳定整数分配问题的非二分图版本，文献[7]处理了一个非二分图"布尔"稳定性问题，其中偏好依赖于可替代且递增（即规模单调）的选择函数。注意文献[4]、[7]完全刻画了稳定解存在性的障碍；这些障碍同样由两两边不相交的简单（文献[4]中）或边简单（文献[7]中）奇圈集合构成。

本文致力于上述整数 Alkan–Gale 问题（IAGP）的非二分图版本。在这里，给定一个具有边容量 $b(e)\in\mathbb{Z}^+$（$e\in E$）的非二分图 $G=(V,E)$，其中每个顶点 $v\in V$ 配备一个将整数盒子 $\mathcal{B}_v$ 映射到自身的选择函数 $C_v$，且遵循可替代性和规模单调性公理。我们将相关的稳定性问题称为带有整数选择函数的稳定伙伴关系问题，简称 SPPIC。这推广了上述非二分图稳定性问题，我们的主要目标是为 $(G,b,C)$ 找出一个合理的方法来确定稳定伙伴关系，或确定稳定伙伴关系不存在。

我们的方法基于将其归结为对应的对称二分图情形，即归结为 IAGP 的对称版本（类似于在文献[6]、[9]中对先前问题所做的那样）。更具体地说，我们为 $G=(V,E)$ 关联一个二分图 $G^\diamondsuit=(V^\diamondsuit,E^\diamondsuit)$，其顶点为 $V$ 中顶点 $v$ 的副本 $v_0, v_1$，边为 $E$ 中边 $uv$ 的副本 $u_0v_1$ 和 $v_0u_1$。$G^\diamondsuit$ 的边容量 $b^\diamondsuit$ 和选择函数 $C^\diamondsuit$ 以自然方式继承自 $b$ 和 $C$。所得结构 $(G^\diamondsuit,b^\diamondsuit,C^\diamondsuit)$ 具有如下性质：$(G,b,C)$ 的稳定伙伴关系 $x\in\mathbb{Z}^E_+$（若存在）与 $(G^\diamondsuit,b^\diamondsuit,C^\diamondsuit)$ 的对称稳定向量 $\tilde{x}\in\mathbb{Z}^{E^\diamondsuit}_+$ 一一对应（即对所有 $uv\in E$ 满足 $\tilde{x}(u_0v_1)=\tilde{x}(v_0u_1)=x(uv)$）。

依据文献[14]，我们找到 $(G^\diamondsuit,b^\diamondsuit,C^\diamondsuit)$ 的所有加权旋转族 $\mathcal{P}$，并从 $\mathcal{P}$ 中提取所有自对称旋转 $R$ 的集合 $\mathfrak{O}$，其权重 $\tau_R$ 为奇数。我们证明这些旋转两两边不相交，并稍微修改文献[14]中的方法，构造一个稳定向量 $\tilde{x}\in\mathbb{Z}^{E^\diamondsuit}_+$，具有如下附加性质：$\tilde{x}$ 在 $\mathfrak{O}$ 中出现的边之外是对称的，且对所有包含在 $\mathfrak{O}$ 中旋转内的对称边 $u_0v_1,v_0u_1$，有 $|\tilde{x}(u_0v_1)-\tilde{x}(v_0u_1)|=1$。此外，证明任何在 $\mathfrak{O}$ 之外对称的稳定 $\tilde{x}$ 在 $\mathfrak{O}$ 所覆盖的每对对称边上取不同的值（因此 $\mathfrak{O}$ 在某种意义上起到"障碍"的作用）。因此，$(G^\diamondsuit,b^\diamondsuit,C^\diamondsuit)$ 的对称解存在当且仅当集合 $\mathfrak{O}$（是典范的）为空。

现在取 $\tilde{x}$ 和 $\mathfrak{O}$ 在原图 $G$ 中的自然像，我们得到向量 $x\in\mathbb{Z}^E_+$ 和一组两两边不相交的边简单奇圈 $\mathcal{K}$，使得：若 $\mathcal{K}=\emptyset$，则 $x$ 是一个稳定伙伴关系；反之，若 $\mathcal{K}\neq\emptyset$，则不存在稳定伙伴关系。此外，无需明确诉诸上述归结到 IAGP 的过程，我们能够给出 $(G,b,C)$ 的适当对 $(x,\mathcal{K})$ 的内禀定义，将其称为稳定半伙伴关系（借用文献[7]中的术语）。以此方式，推广文献[7]中带有选择函数的"布尔"情形的对应结构结果（以及更早的类似结果，例如文献[18]中关于稳定划分的结果），我们关于 SPPIC 的主要结构定理（定理 5.1）指出，$(G,b,C)$ 的稳定半伙伴关系 $(x,\mathcal{K})$ 总是存在的，且部分 $\mathcal{K}$ 对所有半伙伴关系是相同的。

另外注意，寻找 $(x,\mathcal{K})$ 的计算复杂性本质上与 IAGP 中构造旋转变序 $(\mathcal{P},\preccurlyeq)$ 的复杂性相同。

本文的组织如下：第2节包含基本定义和设定。第3节回顾了文献[14]中关于一般二分图中稳定性问题 IAGP 的构造和结果。第4节描述了从非二分图稳定性问题 SPPIC（针对 $(G,b,C)$）到 IAGP 对称版本的归结。我们详细分析对称情形中旋转变序 $(\mathcal{P},\preccurlyeq)$ 的性质，解释 $(G^\diamondsuit,b^\diamondsuit,C^\diamondsuit)$ 的对称稳定性问题如何与该偏序中的所谓平衡和准平衡闭函数相关联，并建立此类函数的关键性质（定理 4.5）。在第5节中我们回到初始的非二分图 $(G,b,C)$，给出 SPPIC 中稳定半伙伴关系 $(x,\mathcal{K})$ 的定义，并证明关于这些对象的主要结果（定理 5.1）。第6节简要概述两个附加主题：通过对选择函数施加额外公理而得到的 SPPIC 特殊情形（遵循文献[14, 第7节]中考虑的 IAGP 特殊情形），以及文献[13]中研究的松弛稳定分配问题的非二分图版本，其中顶点的强线性序被弱线性序取代。

定义和设定
在我们关注的稳定伙伴关系模型中，我们处理一个有限图 $G=(V,E)$，其中边 $e\in E$ 被赋予非负整数容量 $b(e)\in\mathbb{Z}^+$。我们假设图 $G$ 是连通的且无重边。则 $|V|-1\leq|E|\leq\binom{|V|}{2}$。连接顶点 $u$ 和 $v$ 的边可记为 $uv$。

对于顶点 $v\in V$，其关联边集记为 $E_v$。我们记非负整数盒子为 $\mathcal{B}=\mathcal{B}(b)=\{x\in\mathbb{Z}^E_+: x\leq b\}$。对于 $v\in V$，$\mathcal{B}$ 在集合 $E_v$ 上的限制记为

二分图情形中的背景
本节中我们处理图 $G=(V,E)$ 为二分图且边容量 $b$ 和选择函数 $C_v$（$v\in V$）为整数值的情形。$G$ 的顶点被划分为两部分（或两侧、色类）$W$ 和 $F$，分别称为工作者集合和企业集合。

如前所述，我们分别用 $\mathcal{A}$ 和 $\mathcal{S}$ 表示我们模型的 $(G,b,C)$ 的可接受向量和稳定向量（"伙伴关系"）$x\in\mathbb{Z}^E_+$ 的集合。同样地，对于??∈??，我们记对称二分情形下偏序集的特征。在本节中，我们考虑如第2节末尾所述的对称 ???=(???=??0∪??1,???)、???、???，并利用第3节中的术语和结果。为与第3节的记号相匹配，部分??0和??1也分别被记为??（“工人”）和??（“企业”）。设??表示作用在???中的对象以及???上的函数的对称算子。该??将顶点????∈????映射到??1???，将边??0??1∈???映射到??0??1=??1??0，将环??=(??0,??1,??1,…,????,????=??0)映射到环??(??)=(??(??0),??(??1),??(??1),…,??(????),??(????))，将向量??∈?m

转移到非二分情形。在本节中，我们使用前一节的构造和结果来证明当基础图??=(??,??)为非二分图且稳定伙伴关系未必存在时，某种结构（推广了[18]中的稳定划分和[7]中的稳定半伙伴关系）的存在性。在此之前，我们对上述关于???、???、???的偏序集(??,?)中的（闭）拟平衡函数??作一个额外的观察。事实是??在族??上取零值（参见定理4.5(i)），并且

结论性评述。在本文的结尾，我们简要概述如何将上述“双重拷贝”方法应用于非二分图上稳定问题的另外两个版本。

I. [14]的第7节致力于二分图上整数Alkan–Gale稳定问题（IAGP）的一个特殊情形。它通过在选择函数上施加一个额外的公理来指定，即所谓的无间隙条件。类似的规定也可以在非二分版本中作出。更确切地说，考虑

致谢。我感谢匿名审稿人提出的有用意见和建议。

Alexander V. Karzanov