Making a Swap: Network Formation with Increasing Marginal Costs

项目	论文元数据与核心信息
论文题目	Making a Swap: Network Formation with Increasing Marginal Costs（置换成网：边际成本递增下的网络形成理论）
论文作者	Evan Sadler（Columbia University / 哥伦比亚大学）
发表期刊	Journal of Political Economy (JPE), Vol. 134, No. 8, August 2026, pp. 2362–2394
文章标识	DOI: https://doi.org/10.1086/741274
JEL 分类号	C78 (Matching and Bargaining / 匹配与博弈谈判) D85 (Network Formation and Analysis: Theory / 网络形成与分析理论) L14 (Transactional Relationships; Contracts and Reputation; Networks / 交易关系与网络)

一、全文概要与核心贡献 (Executive Summary & Core Contributions)

现实世界中的大量经济与社会网络（如银行间同业拆借网络、国际军火与商品贸易网络、跨国公司研发联盟、学术合著网络以及社交网络）展现出极其显著且稳健的宏观拓扑经验规律：同配性（Assortativity / 类似地位节点倾向互连）、高聚类性（Clustering / 拥有共同邻居）、层级结构（Hierarchies / 核心-外围结构）以及集团行为（Cliques / 局部紧密子群）。然而，长期以来战略性网络形成文献（Strategic Network Formation）存在两大核心瓶颈：其一，绝大多数经典模型假设参与人是事前同质无差异的（Ex-ante Identical Players），无法解释网络中心度与个体外生能力/异质地位之间的内在关联；其二，现有理论普遍将上述拓扑结构的产生完全归因于复杂的连接外部性（Link Externalities / 如信息溢出、中介租金、传递性收益），缺乏一个基于个体微观基础和资源约束的基准理论。

由 Evan Sadler 发表在 2026 年《Journal of Political Economy》上的重磅论文《Making a Swap: Network Formation with Increasing Marginal Costs》，通过引入边际连接成本递增（Increasing Marginal Costs）与纵向异质性（Vertical Heterogeneity），在无任何参数化假定（Non-parametric / Revealed Preference Approach）的前提下，建立了一套普适、优美且极具解释力的战略性网络形成公理化理论体系。文章开创性地提出了置换稳健稳定性（Swap-Proof Stability）解概念，彻底解决了经典双边稳定性（Pairwise Stability）在非凸成本环境下面临的存在性缺失与多重非直观均衡顽疾。

【核心贡献归纳】Evan Sadler (2026) 对网络形成博弈的四大理论突破

**理论与方法论创新（Revealed Preference & Non-parametric Approach）**：突破传统网络博弈对特定效用函数的依赖，采用序数偏好与显示偏好进路，仅依赖效用的自身拟凹性（边际成本递增）与排序一致性，刻画了所有可能稳定的网络形态全集。

**均衡概念精炼（Swap-Proof Stability）**：提出置换稳健稳定性，允许两名参与人在建立新连接的同时各自断开至多一条既有连接（Improving Swap）。该概念在保持最小精炼度的同时，与双边纳什稳定性和匹配理论的阻塞对（Blocking Pair）形成深刻同构，从机制上消除了协调失败带来的次优网络。

**微观偏好到宏观拓扑的精确映射（Mapping Preferences to Topologies）**：严格证明了边际成本递增必然导致同配性（定理 2 给出了排序跨度的紧界 $O({\overline{d}}^{2})$ ）；排序一致性必然诱导弦图（Chordal Graph）与高聚类；渴望度（Desirability）与社交意愿（Sociability）同向时内生涌现强层级结构（Strong Hierarchies），反向时涌现区间重叠集团（Ordered Overlapping Cliques）。

**稳健性拓展与动态学习收敛基石（Robustness & Dynamic Foundations）**：将理论拓展至度相关外部性、水平异质性（通过伸缩求和证明存在性）以及大群体外生机会约束网络，并在附录中建立了边调整与参与人调整学习动态在马尔可夫链下以概率 1 全局收敛至唯一置换稳健网络的严格证明。

二、数理模型建立过程与公理体系 (Mathematical Model & Axiomatic Foundations)

2.1 参与人、图论符号与无外部性基准

考虑有限参与人集合 $N = \{ 1,2,\ldots,n\}$ ，形成的无向简单图为 $G = (N,E)$ 。对任意参与人 $i \in N$ ， $G_{i} = \{ j \in N|ij \in E\}$ 表示其邻居集，度为 $d_{i} = |G_{i}|$ 。其余边记为 $G_{- i}$ ，整个网络可表示为 $(G_{i},G_{- i})$ 。收益函数为 $u_{i}(G) = u_{i}(G_{i},G_{- i})$ 。基准模型假定无外部性（No Externalities），即 $u_{i}(G) = u_{i}(G_{i})$ 。

2.2 偏好公理体系 (Preference Axioms)

【核心公理定义 1】偏好的拟凹性与排序一致性

**公理 1.1：自身连接的拟凹性（Quasi-concavity in own links / 边际成本递增）**对于任意 $ij otin G$ 以及任意子集 $G_{i}^{\prime} \subseteq G_{i}$ ，若有： $u_{i}(G_{i} \cup \{ j\},G_{- i}) \geq ( > )u_{i}(G_{i},G_{- i}) \Longrightarrow u_{i}(G_{i}^{\prime} \cup \{ j\},G_{- i}) \geq ( > )u_{i}(G_{i}^{\prime},G_{- i})$ 【经济学含义】：建立和维护连接具有边际成本递增或收益递减特征。在拥有较少连接时，建立新连接的净激励更强。

**公理 1.2：排序一致性（Rank Consistency / 邻居偏好一维可排性）**若对于某个 $(G_{i},G_{- i})$ （满足 $j,k otin G_{i}$ ）有 $u_{i}(G_{i} \cup \{ j\},G_{- i}) \geq u_{i}(G_{i} \cup \{ k\},G_{- i})$ ，则对任意 $G_{i}^{\prime}$ （满足 $j,k otin G_{i}^{\prime}$ ），恒有： $u_{i}(G_{i}^{\prime} \cup \{ j\},G_{- i}) \geq u_{i}(G_{i}^{\prime} \cup \{ k\},G_{- i})$ 【经济学含义】：内生定义了一维序数偏好 $\geq_{i}$ 。 $j \geq_{i}k$ 表示参与人 $i$ 始终乐意放弃与 $k$ 的连接以换取与 $j$ 连边。

满足公理体系的两类代表性效用函数包括：

• 可分离线性加总减凸成本形式： $u_{i}(G) = \sum_{j \in G_{i}}^{}{}v_{ij} - c_{i}(|G_{i}|)$ ，其中 $c_{i}(d + 1) - c_{i}(d)$ 随 $d$ 单调递增。

• 凹变换收益形式： $u_{i}(G) = f(\sum_{j \in G_{i}}^{}{}v_{ij}) - c_{i}|G_{i}|$ ，其中 $f( \cdot )$ 为严格凹函数。

2.3 均衡解概念：双边稳定性 vs 置换稳健稳定性

稳定性概念	允许的偏离动作集合 (Allowed Deviations)	理论缺陷与局限性
双边稳定性 (Pairwise Stability)	1. 单边删除任意单条边 $ij \in G$ ； 2. 双边一致同意增加单条边 $ij otin G$ 。	在拟凹偏好下产生大量非自然的病态多重均衡。例如当度容量上限为 1 时，任意低质量配对网络都是双边稳定的（图 1、图 2）。
置换稳健稳定性 (Swap-Proof Stability)	1. 单边删除任意单条边； 2. 改进置换 (Improving Swap)：两名未连接者 $i,j$ 建立连接 $ij$ ，并允许各自同时断开至多一条既有边 $ik,jl$ 。	极小化精炼，完美解决协调摩擦；在严格偏好和互为最爱条件下保证唯一稳定网络的全局存在性与帕累托最优性。

【核心解概念定义 2】改进置换与置换稳健稳定性

**定义 2.1：改进置换（Improving Swap）**对于未连接对 $ij otin G$ ，若存在 $k \in G_{i} \cup \{ i\},l \in G_{j} \cup \{ j\}$ 使得： $u_{i}(G_{i} \cup \{ j\} \smallsetminus \{ k\}) \geq u_{i}(G_{i})且u_{j}(G_{j} \cup \{ i\} \smallsetminus \{ l\}) \geq u_{j}(G_{j})$ 且至少一个严格不等式成立，则 $(ij,k,l)$ 构成改进置换。

**定义 2.2：置换稳健稳定网络（Swap-Proof Stable Graph）**网络 $G$ 既无单边断边激励，亦无改进置换。

三、核心定理推导、证明逻辑与网络拓扑机制 (Core Theorems, Proofs & Network Topology)

3.1 互为最爱性质与唯一稳定网络存在性 (Theorem 1 & Proposition 1)

【核心定理 1 与命题 1】全局存在唯一性与社会效率

**定义 3：互为最爱性质（Mutual Favorite Property）**给定任意候选边集 $E$ ，存在一条边 $ij \in E$ ，使得 $j$ 在 $E_{i}$ 中极大化 $i$ 的偏好，且 $i$ 在 $E_{j}$ 中极大化 $j$ 的偏好。

**定理 1：唯一置换稳健稳定网络的存在性定理**若偏好严格且满足互为最爱性质，则存在唯一的置换稳健稳定网络 $G^{*}$ 。

**数理证明要点**【贪心构造】：将所有可能边按互为最爱属性排成序列 $i_{1}j_{1},i_{2}j_{2},\ldots$ ，依次考察加边。拟凹性保证参与人一旦停止加边，绝不会接受后续更差的边，从而所得网络不存在改进置换。【唯一性反证】：设存在另一稳定图 $G^{\prime}$ ，取序列中第一条状态不一致的边 $i_{k}j_{k}$ ，可证明双方在 $G^{\prime}$ 中必定可通过置换后续低阶邻居形成对 $G^{\prime}$ 的改进置换，矛盾！

**命题 1：帕累托有效性（Pareto Efficiency）**在定理 1 假定下，唯一的置换稳健稳定网络 $G^{*}$ 必定是帕累托有效的。

3.2 共同排序、同配性与排序跨度上界定理 (Proposition 2 & Theorem 2)

【核心定理 2】度容量约束与极端同配性定理

**命题 2：秩序图（Rank-Order Graph）的充要刻画**在共同渴望度排序 $\geq_{d}$ 下，置换稳定网络 $G$ 绝不存在 $i >_{d}j,k >_{d}l$ 使得 $jk,il \in G$ 但 $ik otin G$ 。满足此条件的网络即为秩序图。

**定理 2：度受限下的排序跨度上界定理（Extreme Assortativity Bound）**按渴望度降序编号 $1,2,\ldots,n$ ，设每人至少有 1 条连接，最大度为 $\overline{d}$ 。则任意边 $ij \in G$ 的序号跨度受限于： $|i - j| \leq \left\lfloor \frac{\overline{d}}{2} \right\rfloor\left( \left\lfloor \frac{\overline{d}}{2} \right\rfloor + 1 \right)$

**数理优化推导**将 $i,j$ 之间的节点分为 $i$ 的邻居（ $m_{i}$ 个）和非邻居（ $m_{o}$ 个）。非邻居必须连接排在 $i$ 之前的节点集合 $S$ （ $|S| = r$ ）。由于 $S$ 内部必须互连且连向 $i$ ，向外最多提供 $r(\overline{d} - r)$ 条边。最大可容纳非邻居数 $m_{o} \leq \lfloor\overline{d}/2\rfloor\lceil\overline{d}/2\rceil = C$ 。解极值规划 $maxm_{i} + m_{o} + 1$ s.t. $m_{i} + r(m_{o}) + 1 \leq \overline{d}$ ，最优解精确为 $\lfloor\frac{\overline{d}}{2}\rfloor(\lfloor\frac{\overline{d}}{2}\rfloor + 1)$ 。

3.3 聚类特征、集团结构与弦图性质 (Proposition 3 & Corollary 1)

【核心命题 3 与推论 1】聚类与弦图无长圈特征

**命题 3：聚类与集团三大特征**(a) 高阶邻居互连：若 $ij,ik \in G$ 且 $i \leq_{d}j,i \leq_{d}k$ ，则必有 $jk \in G$ ； (b) 极小元邻域为完全子图：若 $i$ 为连通分支中最低阶节点，其邻域 $G_{i}$ 构成 Clique； (c) 顶层集团（Top-K Clique）：排名前 $K$ 的节点若度数均 $\geq K - 1$ ，则必构成完全子图。

**推论 1：无长诱导圈与弦图性质（Chordal Graph Property）**在严格共同排序下，置换稳健稳定网络必为弦图（不存在长度 $\geq 4$ 的无弦诱导圈）。

3.4 渴望度与社交意愿的双重交互：层级 vs 集团 (Theorem 3)

【核心定理 3】强层级结构 vs 有序重叠集团

**定义 4：社交意愿排序（Sociability Ranking $\ge_s$）**在度数相同时，若 $j$ 愿意建立某连接蕴含 $i$ 亦愿意，则称 $i \geq_{s}j$ 。

**定理 3(a)：意愿同向 $\implies$ 强层级结构（Strong Hierarchy）**若 $i \geq_{d}j \Longleftrightarrow i \geq_{s}j$ ，则稳定网络为强层级网络（排名高者度数更高且邻居排名更高），涵盖嵌套分裂图（Nested Split Graphs）。

**定理 3(b)：意愿反向 $\implies$ 有序重叠集团（Ordered Overlapping Cliques）**若 $i \geq_{d}j \Longleftrightarrow i \leq_{s}j$ ，则稳定网络由有序重叠集团构成（每个参与人的邻域均为排序区间）。

四、理论扩展与稳健性边界 (Extensions & Robustness Boundaries)

4.1 度相关外部性 (Degree-Based Externalities)

当效用依赖于邻居度数 $u_{i}(G_{i},d_{G_{i}})$ 时：

• 渴望度随度递增（富者愈富效应）：定理 2 跨度界限被打破，但命题 4 证明弦图性质依然成立，命题 5 证明容量约束下稳定网络存在。

• 渴望度随度递减（拥挤效应）：弦图性质被打破，网络中可能产生稳定的诱导 4-圈。

4.2 水平异质性与可加可分离匹配模型 (Proposition 6)

【核心命题 6】水平异质性与伸缩求和反证

**命题 6：特质冲击模型与伸缩求和证明**考虑效用函数 $u_{i}(G_{i}) = \sum_{j \in G_{i}}^{}{}(v_{i} + w_{j} + \varepsilon_{ij}) - c_{i}(|G_{i}|)$ ，其中 $\varepsilon_{ij} = \varepsilon_{ji}$ 。若存在置换循环，则必有： $\varepsilon_{i - 1,i} < w_{i + 1} - w_{i - 1} + \varepsilon_{i,i + 1}$ 将全循环 $1 \rightarrow K$ 累加展开产生伸缩对消，导出 $\varepsilon_{K1} < \varepsilon_{K1}$ 矛盾！因此互为最爱性质恒成立，稳定网络唯一。

4.3 大群体混合模型与动态学习收敛 (Propositions 7–10)

• 图论分类（命题 7–8）：秩序图是强弦图（排除图 6 的 $n$ -sun）且排除图 7 的三向相交结构。

• 学习动态收敛性（命题 9–10）：边调整动态与参与人调整动态在马尔可夫链下以概率 1 全局收敛至唯一置换稳健稳定网络。

五、论文全景图表展示与数理机制深度解释 (Visualized Figures & In-depth Analysis)

5.1 图 1： $c(2) = 2$ 时双边稳定网络不存在的循环激励机制

论文模型与机制示意图

图 1：边际成本 $c(2)=2$ 时双边稳定网络的非存在性（三个状态间的循环加边/断边路径）

【数理机制解析】：参与人集合 $\{ 1,2,3\}$ ，第一条边成本为 0，第二条边边际成本为 2。在子图 (a) 中，存在边 (3,2)，孤立的 1 与 2 均有严格激励加边转移至 (b)；在子图 (b) 中，拥有 2 条边的节点 2 发现单边切断与 3 的边收益从 2 提升至 3，因而单边断边转移至 (c)；在 (c) 中 1 与 3 又有动力加边转移至 (a)。博弈陷入死循环，双边稳定网络不存在！

5.2 图 2： $c(2) = 4$ 时双边稳定性的多重次优均衡与置换精炼

论文模型与机制示意图

图 2：边际成本 $c(2)=4$ 时双边稳定的非自然多重性与置换稳健性精炼剔除机制

【数理机制解析】：当第二条边成本提高至 4 时，各单边网络均无法直接加边，导致 (a)、(b)、(c) 全为双边稳定网络。然而在 (a) 中，节点 2 与 3 相连得 1，但其面对孤立的 1 时，可通过改进置换（断开与 3 并与 1 连边）使双方收益均跃升至 3。置换稳健稳定性消除了协调失败带来的低效网络。

5.3 图 3：定理 2 跨度紧界网络结构 ( $\overline{d} = 6 \Longrightarrow |4 - 16| = 12$ )

论文模型与机制示意图

图 3：定理 2 跨度上界紧界网络拓扑构造（最大度 $\bar{d}=6$ 时的 16 节点树状集团）

【数理机制解析】：顶层 4 个节点 $\{ 1,2,3,4\}$ 构成完全子图，各消耗 3 条连接，剩余 3 条连接分别连向专属底层节点。核心节点 4 与底层节点 16 相连，序号跨度 $|4 - 16| = 12 = \lfloor 6/2\rfloor(\lfloor 6/2\rfloor + 1)$ ，严格验证了定理 2 理论上界的紧性！

5.4 图 4：非弦图（诱导 4-圈）与共同排序假设的不相容性

论文模型与机制示意图

图 4：非弦图（顶部 4 节点诱导圈 $C_4$）无法在共同排序下作为稳定网络存在

【数理机制解析】：若存在诱导 4 圈，圈上排名最低的节点必拥有两个排在其之上的高阶邻居。根据命题 3(a)，这两个高阶邻居必直接相连产生对角弦，破坏诱导圈定义。因此稳定网络必为弦图。

5.5 附录图 5–7：无差异反例、禁止阳伞图与三向相交

论文模型与机制示意图

图 5（附录 A）：对称同质参与人存在无差异时的置换循环与非存在性边界

论文模型与机制示意图

图 6（附录 C）：强弦图与秩序图的禁止诱导子图族（3-sun, 4-sun, 5-sun）

论文模型与机制示意图

图 7（附录 C）：秩序图在拓扑上严格禁止的三向相交诱导子图（树状与三角相交）

六、全文结论、政策与管理启示 (Conclusions, Policy & Managerial Insights)

6.1 核心理论结论总结

• 微观机制去神秘化：同配性、聚类、层级与集团等现实网络核心特征，不必然依赖外部性，仅凭边际成本递增与排序一致性即可自然内生涌现。

• 维度映射精确定理化：边际成本增长速度决定连接跨度上界；渴望度与社交意愿的协同或对立，分别决定了强层级结构与有序重叠集团结构。

• 实证识别与结构反推：弦图性质与秩序图充要条件为实证学者根据网络拓扑反推个体微观偏好提供了非参数检验工具。

6.2 现实经济学与管理启示

• 金融与银行同业拆借监管：大行处于核心可能是因为其违约风险低且边际成本低，监管层需区分能力差异与网络外部性，避免盲目限制中心节点连接配额。

• 国际贸易与供应链韧性：核心大国与边缘小国的贸易网络格局是边际协调成本的稳定均衡，降低通关与交易边际成本是帮助中小经济体融入核心网络的根本手段。

• 企业研发联盟与组织设计：高端创新网络中顶尖学者精力有限导致闭门俱乐部，平台化设计（降低跨界沟通边际成本）是促进跨层级知识扩散的关键。

参考文献 (References)

Akerman, Anders, and Anna Seim. 2014. "The Global Arms Trade Network 1950–2007." Journal of Comparative Economics 42:535–51.

Bala, Venkatesh, and Sanjeev Goyal. 2000. "A Noncooperative Model of Network Formation." Econometrica 68:1181–229.

Becker, Gary. 1973. "A Theory of Marriage: Part I." Journal of Political Economy 81:813–46.

Belleflamme, Paul, and Francis Bloch. 2004. "Market Sharing Agreements and Collusive Networks." International Economic Review 45:387–411.

Bloch, Francis, and Matthew Jackson. 2007. "The Formation of Networks with Transfers among Players." Journal of Economic Theory 133:83–110.

Chakrabarti, Subhadip, and Robert Gilles. 2007. "Network Potentials." Review of Economic Design 11:13–52.

Farber, Martin. 1983. "Characterizations of Strongly Chordal Graphs." Discrete Mathematics 43:173–89.

Fulkerson, Delbert, and Oliver Gross. 1965. "Incidence Matrices and Interval Graphs." Pacific Journal of Mathematics 15:835–55.

Furusawa, Taiji, and Hideo Konishi. 2007. "Free Trade Networks." Journal of International Economics 72:310–35.

Goyal, Sanjeev, and Sumit Joshi. 2006. "Unequal Connections." International Journal of Game Theory 34:319–49.

Goyal, Sanjeev, and Fernando Vega-Redondo. 2007. "Structural Holes in Networks." Journal of Economic Theory 137:460–92.

Habib, Michel, Ross McConnell, Christophe Paul, and Laurent Viennot. 2000. "Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition, and Consecutive Ones Testing." Theoretical Computer Science 234:59–84.

Hellmann, Tim. 2013. "On the Existence and Uniqueness of Pairwise Stable Networks." International Journal of Game Theory 42:211–37.

Hellmann, Tim. 2021. "Pairwise Stable Networks in Homogeneous Societies with Weak Link Externalities." European Journal of Operational Research 291:1164–79.

Jackson, Matthew, and Anne van den Nouweland. 2005. "Strongly Stable Networks." Games and Economic Behavior 51:420–44.

Jackson, Matthew, and Alison Watts. 2001. "The Existence of Pairwise Stable Networks." Seoul Journal of Economics 14:299–322.

Jackson, Matthew, and Asher Wolinsky. 1996. "A Strategic Model of Social and Economic Networks." Journal of Economic Theory 71:44–74.

Johnson, Cathleen, and Robert Gilles. 2000. "Spatial Social Networks." Review of Economic Design 5:273–99.

Joshi, Sumit, Ahmed Saber Mahmud, and Sudipta Sarangi. 2020. "Network Formation with Multigraphs and Strategic Complementarities." Journal of Economic Theory 188:105033.

König, Michael, Claudio Tessone, and Yves Zenou. 2014. "Nestedness in Networks: A Theoretical Model and Some Applications." Theoretical Economics 9:695–752.

Möhlmeier, Philipp, Agnieszka Rusinowska, and Emily Tanimura. 2016. "A Degree-Distance-Based Connections Model with Negative and Positive Externalities." Journal of Public Economic Theory 18:168–92.

Morrill, Thayer. 2011. "Network Formation under Negative Degree-Based Externalities." International Journal of Game Theory 40:367–85.

Romero-Medina, Antonio, and Matteo Triossi. 2013. "Acyclicity and Singleton Cores in Matching Markets." Economics Letters 118:237–39.

Romero-Medina, Antonio, and Matteo Triossi. 2021. "Two-Sided Strategy-Proofness in Many-to-Many Matching Markets." International Journal of Game Theory 50:105–18.

Rose, Donald, Robert Tarjan, and George Lueker. 1976. "Algorithmic Aspects of Vertex Elimination on Graphs." SIAM Journal on Computing 5:266–83.

Sadler, Evan. 2022. "Ordinal Centrality." Journal of Political Economy 130:926–55.

Sadler, Evan. 2024. "Classical Matching via Network Formation." Working paper.

Sadler, Evan. 2026. "Making a Swap: Network Formation with Increasing Marginal Costs." Journal of Political Economy 134(8):2362–94.

Sadler, Evan, and Ben Golub. 2022. "Games on Endogenous Networks." Working paper.

Soramaki, Kimmo, Morten Bech, Jeffrey Arnold, Robert Glass, and Walter Beyeler. 2007. "The Topology of Interbank Payment Flows." Physica A 379:317–33.

Making a Swap: Network Formation with Increasing Marginal Costs

边际成本递增下的网络形成与置换稳定性

受欢迎的隐藏数学：网络形成解读

社交圈层博弈

一、全文概要与核心贡献 (Executive Summary & Core Contributions)