通过网络形成实现的经典匹配

《Journal of Economic Theory》：Classical matching via network formation

　　

摘要 尽管探讨了相似的底层问题，但关于网络形成和匹配的研究文献在很大程度上是独立演进的。本文提供了一个共同框架，研究一个没有外部性的一般网络形成模型——等价于一个单边多对多匹配模型。我给出了稳定图存在性和唯一性的条件，证明了一个乡村医院定理，并指出了不同稳定图之间逐条链接的利益冲突。特殊情形包含并扩展了室友问题和双边匹配市场的经典结果。一种改编自 Gutin 等人（2023）的迭代删除算法提供了一个关键工具，将网络形成博弈还原为具有有用性质的标准型。

引言 匹配只是网络的另一个名字，那么为什么不一起研究它们呢？在本文中，我探索了策略性网络形成理论与匹配理论之间的关系。我从一个没有外部性的网络形成模型开始，意味着玩家的收益仅取决于谁是他们的邻居。经典匹配模型（例如双边市场、室友问题）是特殊情况，但我们也可以捕捉没有双方且不适合早期匹配框架的情景——国家间贸易协定的形成、金融机构间的贷款安排或研究人员间的合著关系。在适当的收益假设下，迭代删除算法将链接分为三类：稳定图必须包含的链接、稳定图必须排除的链接以及未定集合。利用这些未定边的性质，我补充了关于稳定图存在性和唯一性的已知结果，证明了一个无论是否存在双方都适用的乡村医院定理，并发现了当我们从一个稳定图移动到另一个稳定图时玩家之间的利益冲突。总的来说，这些结果突显了看似不同情景之间的共性。

网络形成博弈由一组有限的玩家、一组可行链接以及每个玩家的收益函数组成。收益取决于以玩家为顶点形成的图。如果没有任何个人能从切断链接中获益，且没有任何一对玩家能从形成链接中获益（同时每个玩家可能同时放弃一个邻居），我将称该图为稳定的——这等价于配对稳定匹配的标准定义。我对玩家的收益施加了两项可解释的限制。排名一致性意味着每个玩家可以对她的潜在邻居进行排名，并且总是会用排名较低的邻居交换排名较高的邻居。拟凹性意味着连接具有递减回报。较弱的版本，即链接拟凹性，要求如果给邻居集合添加 j 使玩家受益，那么给任何子集添加 j 也使她受益。较强的版本，即度数拟凹性，要求如果给邻居集合添加 j 使玩家受益，那么给任何弱小于该集合的邻居集添加 j 也使她受益。

基于 Gutin 等人（2023）的研究，我展示了如何将网络形成博弈还原为捕捉不同玩家偏好之间本质冲突的标准型。较早的论文研究的是双边一对一匹配市场，观察到每当玩家 i 是玩家 j 的首选搭档时，这为 i 提供了一个外部选择——稳定匹配不能将 i 与她不如喜欢 j 的人配对。因此，我们可以从 i 的偏好列表中删除此类玩家，并从这些玩家的偏好列表中删除 i，而不改变稳定匹配的集合。标准型是当我们尽可能迭代此推理后所得到的缩减匹配问题。

为了处理没有双方的多对多匹配，我在他们的算法上进行了两方面的创新。首先，因为玩家可以形成多个匹配，所以玩家首选搭档的对应物是她最希望链接的邻居集合。我称之为她的抱负集。如果玩家 i 在玩家 j 的抱负集中，我们就说玩家 j 在玩家 i 的安慰集中。由于任何此类玩家总是会与 i 互惠链接，她所做得不比从安慰集中获得她最喜欢的邻居集合更差——这充当了外部选择。如果我们使 i 与她不如从安慰集中选择的链接变得不可行，那么稳定图的集合保持不变。第二，在我们迭代此逻辑之前，我们必须考虑肯定会形成的链接。如果 i 和 j 都在对方的抱负集中，那么链接 ij 必须在任何稳定图中。当我们在下一次迭代中确定抱负集时，我们假设图中包含链接 ij。玩家 i 的抱负集可能会随着她获得更多搭档而缩小，因为递增的边际成本阻止她形成进一步的链接。如果在任何时间点 i 的抱负集为空，那么她在任何稳定图中的邻居恰好是她当前的邻居集合。

随着我们迭代此过程，我们将链接分为三组。如果两个玩家曾互在对方的抱负集中，我们将此链接分配到包含集 I。如果两个玩家中有一个曾在她的安慰集中有更好的选择，他们之间的链接永远无法形成，我们将其分配到排除集 O。剩余的链接构成未定集 U，它构成了网络形成博弈的标准型。原博弈中的每个稳定图都对应标准型中的一个稳定图，反之亦然，这使我们能够利用标准型更好地理解稳定图的集合。

为了使这一点更具体，考虑一个有六名玩家的例子。玩家 1 想要最多三个链接，并将其他玩家排名为 2?3?4?5?6。玩家 2、3 和 4 各想要最多两个链接，并同样偏好索引较低的邻居。最后，玩家 5 和 6 各最多想要一个链接，并共享偏好 4?1?2?3，同时将彼此排在最后。在自由选择邻居的情况下，玩家 1 会选择 2、3 和 4，玩家 2 会选择 1 和 3，玩家 3 和 4 会选择 1 和 2，而玩家 5 和 6 会选择 4——这些是抱负集。鉴于此，玩家 1 必须获得她最想要的链接，因为她是这三个玩家的首选搭档。同样，玩家 2 和 3 互相包含，所以这个链接必须形成。在第一次迭代中，这些都是我们添加到 I 的链接。

转到我们可以排除的链接，观察到玩家 1、2 和 3 已经形成了他们想要的链接数量，并且是与他们最喜欢的搭档，所以他们不会同意另一个链接——链接 15、16、24、25、26、34、35 和 36 移动到集合 O。玩家 4 获得了她最喜欢的链接（与玩家 1），但还想要一个。此外，她是 5 和 6 的首选搭档。因此，玩家 4 所做得不比从玩家 5 和 6 中获得她最喜欢的选项更差——由于她偏好 5 胜过 6，她永远不必接受 6，我们可以将 46 添加到 O。在下一次迭代中，我们形成玩家 4 和 5 之间的链接，并消除链接 56。没有链接剩下未定，所以标准型为空，我们看到唯一的稳定图包含链接 12、13、14、23 和 45。

更一般地，每当未定集 U 为空时，恰好存在一个稳定图，且我们的算法识别出它。即使原博弈不是双边的，标准型也可能实际上具有双方，使我们能够应用已知的存在性结果。在这种情况下，人们可以轻易表明，将一侧所有玩家分配给他们们的抱负集，另一侧所有玩家分配给他们们的安慰集，会产生一个稳定图。因此，如果 U 非空，则至少存在两个不同的稳定图。这一发现扩展了 Gutin 等人（2023）的主要结果，即唯一稳定图的充要条件，将其应用于双边多对多市场。

然后我利用标准型的关键性质建立双边匹配理论中经典结果的一边对应物。如果我们加强链接拟凹性至度数拟凹性，那么在标准型中，玩家的抱负集和安慰集总是大小相同。这导致了一边市场的乡村医院定理：每个玩家在每个稳定图中拥有相同数量的邻居。如果收益关于度数拟凹，那么每个玩家必须拥有至少与其安慰集中玩家数量一样多的连接。同样，没有玩家会维持比其抱负集中玩家数量更多的连接。由于这两个集合大小相等，我们得出结论，每个玩家在每个稳定图中拥有相同数量的连接。虽然乡村医院定理肯定排在经济学研究最广泛的结果之列，但据我所知，此前没有版本适用于一边市场。

随后，我们看到在不同稳定图之间移动涉及每条变化链接上的直接利益冲突。如果一条链接在一个稳定图中但不属于另一个，那么两名玩家中恰好有一人会从两个图的并集中选择它。因此，在每条不同的链接上，一名玩家获益而另一名玩家受损。此外，一条链接在两个图中当且仅当两名玩家都会从并集中选择它。应用于双边市场，这一发现意味着这种利益冲突的传统表述：稳定图集合形成一个格，使一方更好必要使另一方更差。我的结果突显了如果我们放弃双边假设后保留的结构。在主要结果之后，第 7 节详细讨论了替代偏好假设以及我们的单边市场发现如何与早期的双边市场发现相关联。

你可能会说，这些证明很巧妙，但这有什么用呢？一个原因是某些匹配市场并非完全是双边的，所以我们应该希望结果对该假设具有鲁棒性。供应链网络的形成就是一个例子。鉴于现代供应链的漫长和复杂性，某家公司或承包商可能出现在多个层级，为几家其他公司提供专业服务，这些公司又彼此交易。同样，虽然自由职业者与雇主的匹配（例如通过各种在线平台）在很大程度上是双边事务，但一旦有分包，我们就不能再依赖这种结构——如果一个被雇用的自由职业者决定雇用另一个自由职业者来完成工作的一部分，我们就失去了两个清晰界定的方。我的结果向我们保证，经典匹配理论确实对双边性的失败具有鲁棒性。乍一看，这可能显得是一个边缘发现，但要达到这一点需要根本不同的方法——拥有双方对于早期工作中的 Tarski 式论证是绝对必要的。

第二个原因是网络形成文献一直难以超越简单例子，更系统的理论构建方法可能促进进步。除少数例外，策略性网络形成模型施加了鲜明的简化假设，例如拥有事前对称玩家1，这阻碍了对基本问题的研究，如一个人的网络位置如何与其他属性相关。此外，与匹配文献不同，我们缺乏一个广泛适用的工具包。每个新模型通常需要定制分析，这为未来作者提供的教训有限。虽然缺乏外部性显然是这里的重要限制，但对于即使这种基本情况的全面理解也是缺失的。正如我在 Sadler (2025) 中论证的那样，这种理解是迈向更丰富理论的关键一步。

尽管有独特的历史，我们可以富有成效地应用相同技术来研究匹配和网络形成。核心贡献是迭代删除算法，它精确地突显了玩家在哪里面临利益冲突。

期望集与安慰集的双重概念为经典结果的证明提供了简洁路径，并对关键结论为何成立提供了新的洞见。本文横跨战略网络形成与匹配两大文献。与前者类似，玩家可以与任意其他玩家建立多条连接；与后者典型设定一样，我假设连接决策中不存在外部性，尽管近期几篇匹配论文在纳入外部性方面取得了进展（如Pycia和Yenmez, 2023; Uetake和Watanabe, 2020）。我期望丰富这两大文献，表明关键匹配结果在不再存在双边市场时依然稳健，并为相对简单设定下的网络形成立起基准结论。

历史上，战略网络形成与匹配文献各自独立发展。Jackson和Wolinsky（1996）提出了网络形成中应用最广泛的解概念——双边稳定性（pairwise stability）。网络形成中的双边稳定性与匹配中的双边稳定性不同，因为它仅考虑添加或删除连接偏离，而不考虑同时切断一条连接并添加另一条的偏离。这一较弱的解概念使我们能够借助势函数（Chakrabarti和Gilles, 2007; Jackson和Watts, 2001）或利用连接之间的互补性（Hellmann, 2013）来证明存在性。Goyal和Vega-Redondo（2007）引入了"双边均衡"（bilateral equilibrium），允许玩家对同时建立一条连接并切断任意多条现有连接——这更接近匹配中的标准双边稳定性概念，事实上在温和的收益假设下二者等价。网络形成文献的一个重要焦点是预测将形成的网络结构。该领域的重要贡献包括Goyal和Joshi（2006）、Hellmann（2021）、Sadler和Golub（2022）以及Sadler（2025）。后两篇尤为接近本文，因为它们明确排除了连接之间的外部性。

匹配理论有着更为悠久的历史，可追溯至Gale和Shapley（1962）的开山之作。双边匹配中一个著名的结果被称为农村医院定理（Rural Hospital Theorem）。每位玩家在所有稳定匹配中拥有相同数量的搭档（Roth, 1984b），且任何未能满额配对的玩家在所有稳定匹配中与相同的其他玩家配对（Roth, 1986）。近期研究大幅弱化了获得这些结果所需的假设（Alkan, 2002; Echenique和Oviedo, 2006; Klijn和Yaz?c?, 2014）。第二个关键结果是：在稳定匹配的集合中，双方利益相对立：对一方所有人都更好的匹配，必然对另一方所有人都更差（Knuth, 1976; Roth, 1984a）。这种利益冲突在室友问题中也有类似表现（参见Gusfield和Irving, 1989第4章）。本文的核心贡献是将这些结果推广至单边多对多匹配。具体而言，定理2推广了农村医院定理，定理3揭示了不同稳定图之间逐条连接的利益冲突。第7节详细讨论了我的结果与假设在专化至双边市场时与先前工作的关系。

在婚姻市场中稳定匹配总是存在的，更一般地，在双边市场中，只要玩家的偏好函数满足可替代性，稳定匹配也存在。最早的存在性证明是构造性的，依赖于延迟接受算法的变体；而较新的结果则采用不动点论证（如Echenique和Oviedo, 2006）。在每种情况下，寻找稳定匹配可通过迭代一个映射来实现，该映射暂时为每位玩家分配一个在当前可用选项中最优的搭档集合。我提出的迭代删除算法同样在每一步确定最优搭档集合，但我们的使用方式截然不同。我们并非进行可能在后续步骤中被更改的暂定分配，而是识别出必定在图中存在的连接子集和不可能在图中的连接子集。后续迭代将已分配和已排除的连接视为固定。

由于我建立了原博弈中稳定图与其约简中稳定图之间的等价关系，我的结果隐含地推广了关于存在性的先前结论，如Chung（2000）中的无奇圈条件——我们总可以将已知结果应用于标准型。同样，我推广了保证唯一性的先前结果（如Clark, 2006; Romero-Medina和Triossi, 2013; Romero-Medina和Triossi, 2021），因为这些条件确保了算法能够分配或排除每一条连接。Gutin等人（2023）是最接近的先例，他们为双边一对一匹配市场引入了类似的迭代删除算法，并给出了唯一稳定匹配存在的紧致条件。我将此算法推广至无边侧的多对多匹配模型，并将其紧致刻画推广至双边多对多匹配市场。

许多近期论文超越了经典匹配框架，纳入了契约（Hatfield和Kominers, 2012; Hatfield和Milgrom, 2005）、更大的联盟（Baccara和Yariv, 2013; Pycia, 2012）或两者兼有（Rostek和Yoder, 2020）。联盟形成模型与网络形成相关但不同——玩家选择包含许多其他人的单一联盟，而在网络形成模型中，所有联盟都仅包含两名玩家，但一名玩家可能加入多个联盟。Rostek和Yoder（2020）的框架比本文所考虑的更为一般，允许玩家任意重叠地组成联盟并签订契约。一个关键分歧在于契约之间的互补性假设，这使得可以用Tarski定理建立稳定结果的存在性并研究单调比较静态。而在本文中，关键假设涉及关系之间的可替代性。如果我们转而假设连接之间存在互补性，Hellmann（2013）的结果保证了存在性，但其他结果可能不再成立。

**边际成本递增下的稳定图**

我采用Sadler（2025）的框架研究边际成本递增且无外部性的网络形成博弈。一个网络形成博弈 $(N, F, \{u_i\}_{i \in N})$ 包含玩家有限集 $N = \{1, 2, \ldots, n\}$、可行边集 $F$，以及每位玩家 $i$ 的收益 $u_i(G)$。效用函数 $u_i$ 以顶点集为 $N$ 的简单无向图 $G$ 为输入，仅使用 $F$ 中的边。

**被支配选项的迭代删除**

我现在介绍我们的主要分析工具——一种将边划分为三个集合的算法：必须包含的边集 $I$、被排除的边集 $O$，以及剩余未确定的边集 $U$。我采用如下约定：不带下标的大写字母表示边的集合（即无序玩家对），带下标的大写字母表示对应的玩家集合——若 $U$ 是未确定边的集合，则 $U_i$ 是所有满足 $ij \in U$ 的玩家 $j$ 的集合。在每一步……

**双边市场中的唯一性**

引理1使我们能够加强推论2。若 $U$ 非空，且对应的图不含奇圈，则我们可直接从期望集与安慰集中识别出两个稳定图。这进而推广了Gutin等人（2023）的主要发现——在双边市场中，当且仅当 $U$ 为空时，存在唯一的稳定图。

**命题2** 假设偏好严格。若仅包含边 $U$ 的图非空且不含奇圈，则至少存在两个稳定……

**网络形成中的农村医院定理**

若偏好严格且在度数上是拟凹的，则每位玩家 $i$ 在所有稳定图中拥有相同数量的邻居。

**定理2** 假设收益严格且在度数上是拟凹的。若存在稳定图 $G$，则在每个稳定图 $G'$ 中，$|G_i'| = |G_i|$。此外，若 $\tilde{G}$ 在标准型 $(\tilde{N}, U, \{\tilde{u}_i\}_{i \in \tilde{N}})$ 中稳定，则必然有 $|\tilde{G}_i| = |A_i| = |C_i|$。

*证明* 由引理1(c)部分，对每位玩家 $i$，$|A_i| = |C_i|$。对每位玩家 $i \in \tilde{N}$，度数上的拟凹性意味着她永远不会添加……

**稳定图中的利益冲突**

双边匹配市场的经典结果凸显了双方之间的利益冲突。在稳定匹配集合中，使一方玩家境况变好必然使另一方玩家境况变差。在没有双边的情况下，当我们从一个稳定图转向另一个时，无法将玩家干净地划分为赢家与输家。尽管如此，若我们考察每一条发生变化的连接，两位参与玩家中必然有一位选择该连接，而另一位则不会。

**利益冲突声明**

我声明本论文研究不涉及任何相关财务利益。

Evan Sadler