Exit-and-Join Dynamics for Decentralized Coalition Formation：去中心化联盟形成的动态机制解析

背景

在多智能体系统（Multi-Agent Systems）和博弈论领域，联盟形成（Coalition Formation）是一个经典且核心的问题。传统上，联盟结构的构建往往依赖于全局协调或中心化的谈判机制，旨在通过全局优化来分配合作收益。然而，在大规模分布式系统、去中心化网络或开放市场中，全局信息往往不可得，或者全局协调的成本过高甚至不可行。

因此，研究者们开始关注**去中心化（Decentralized）**的联盟形成过程。这类过程通常由个体的局部决策驱动，即智能体根据自身的局部利益和环境状态，自主决定加入或退出某个联盟。这种基于局部互动的动态过程不仅更符合现实世界的复杂性，也为理解大规模系统中的自组织行为提供了理论框架。

本文发表于 arXiv 的 cs.AI 类别，提交于 2026 年 6 月 18 日，题为《Exit-and-Join Dynamics for Decentralized Coalition Formation》。该研究将联盟形成建模为一个由单边“退出-加入”（Exit-and-Join）决策驱动的去中心化动力学过程，并深入探讨了其稳定性、均衡特性及计算效率。

核心内容

本文的核心贡献在于建立了一个连接合作博弈论收益分配与非合作博弈最佳响应行为的统一框架。以下是文章的主要技术细节和逻辑推导：

1. 基于 Aumann-Dreze 价值的局部评估机制

在传统的去中心化联盟形成模型中，智能体往往使用简单的边际贡献或局部收益作为决策依据。然而，本文提出智能体在评估局部移动（Local Moves）时，使用 Aumann-Dreze 值（Aumann-Dreze value）来计算收益。

• Aumann-Dreze 值：这是合作博弈论中一种重要的收益分配概念，特别适用于联盟结构（Coalition Structure）并非单一全局联盟的情况。与 Shapley 值不同，Aumann-Dreze 值仅在智能体当前所在的联盟内部进行收益分配和计算，而不考虑全局联盟结构。
• 局部性：这意味着智能体的 payoff（收益）计算完全局限于其当前所在的联盟，无需获取全局信息，也无需进行全局谈判。这极大地降低了计算复杂度和通信开销，符合去中心化的要求。

2. 合作与非合作博弈的桥梁

文章指出，该模型巧妙地链接了合作博弈的收益分配与非合作博弈的最佳响应行为：

• 动态过程：智能体根据当前的 Aumann-Dreze 值，评估是否通过“退出当前联盟”或“加入其他联盟”来提升自己的收益。这是一种非合作的最佳响应（Best-Response）行为。
• 终端划分（Terminal Partition）：当动态过程达到稳定状态时，形成的联盟结构（Partition）具有以下性质：不存在任何智能体可以通过单边的“退出-加入”操作来获得更高的收益。
• 理论等价性：文章证明，这种终端划分恰好对应于一个没有可行且个体有利可图的单边退出-加入偏离（Admissible, Individually Profitable Exit-and-Join Deviation）的联盟结构。这在理论上证明了去中心化动态过程可以收敛到具有良好合作性质的稳定状态。

3. 均衡刻画与势函数表示

为了分析该动力学过程的收敛性和稳定性，文章进行了深入的数学分析：

• 均衡刻画：文章建立了该系统的均衡特征，明确了在什么条件下系统会达到稳定状态。
• 势函数表示：文章识别了动力学过程具有标量 Lyapunov 函数或**精确势函数（Exact-Potential）**表示的条件。
  • 如果存在精确势函数，则系统的动态过程等价于一个势博弈（Potential Game），这保证了动态过程必然收敛到纯策略纳什均衡（Pure Strategy Nash Equilibrium），即稳定的联盟结构。
  • Lyapunov 函数的存在则进一步保证了系统的稳定性，即使在没有精确势函数的情况下，也能证明系统不会无限振荡。

4. 切换成本与接受成本的影响

文章还分析了两种关键成本参数对局部稳定性的影响：

• 切换成本（Switching Costs）：智能体改变联盟成员身份所需的成本。
• 接受成本（Acceptance Costs）：其他智能体或联盟接受新成员或拒绝旧成员所需的成本。
• 分析结果：这些成本参数不仅影响智能体的决策阈值，还直接塑造了系统的局部稳定性。较高的成本可能导致系统陷入次优的局部稳定状态，但也可能防止系统因微小扰动而频繁震荡。

5. 数值实验与基准测试

为了验证理论分析，文章进行了数值实验，测试了以下方面：

• 有限时间稳定化（Finite-time Stabilization）：验证系统在有限步数内达到稳定状态的能力。
• 成本敏感性（Cost Sensitivity）：分析不同成本参数对收敛速度和最终联盟结构的影响。
• 凸博弈基准（Convex-Game Benchmark）：在一个特殊的凸博弈场景下测试模型的性能，以验证其在特定理论基准下的有效性。

关键要点

• 去中心化驱动：联盟形成由智能体的单边“退出-加入”决策驱动，无需全局协调。
• Aumann-Dreze 价值：智能体使用 Aumann-Dreze 值在局部联盟内计算收益，避免了全局信息需求。
• 理论连接：模型将合作博弈的收益分配（Aumann-Dreze 值）与非合作博弈的最佳响应行为统一起来。
• 稳定状态定义：终端划分对应于没有可行且个体有利可图的单边退出-加入偏离的联盟结构。
• 收敛性保证：在特定条件下，动力学过程具有标量 Lyapunov 函数或精确势函数表示，保证了收敛性。
• 成本影响：切换成本和接受成本显著影响系统的局部稳定性和收敛行为。
• 实证验证：数值实验验证了有限时间稳定化、成本敏感性及在凸博弈基准下的有效性。

意义与影响

这项研究在去中心化多智能体系统和计算博弈论领域具有重要的理论和应用意义：

1. 降低协调复杂度：通过引入 Aumann-Dreze 值作为局部评估标准，文章提供了一种无需全局信息即可实现稳定联盟形成的机制。这对于大规模分布式系统（如物联网、自动驾驶车队、去中心化金融 DeFi）中的资源分配和合作形成具有直接应用价值。

2. 理论严谨性：文章不仅提出了动态模型，还从势函数和 Lyapunov 稳定性的角度提供了严格的数学证明，确保了算法的收敛性和稳定性。这填补了去中心化联盟形成理论中关于稳定性分析的空白。

3. 现实可行性：通过引入切换成本和接受成本，模型更贴近现实世界中的摩擦因素（如通信延迟、信任建立、转换惩罚等），使得理论模型更具现实解释力。

4. 跨学科启发：该研究连接了合作博弈论和非合作博弈论，为理解自组织系统中的合作涌现提供了新的视角。它表明，即使个体仅追求局部利益，通过合适的收益分配机制（如 Aumann-Dreze 值），系统仍可能收敛到具有全局合作性质的稳定状态。

总之，《Exit-and-Join Dynamics for Decentralized Coalition Formation》为设计高效、稳定且去中心化的多智能体合作机制提供了坚实的理论基础和实用的算法指导。