去中心化联盟形成的退出与加入动态

# 退出与加入动态下的去中心化联盟形成

**来源**: https://arxiv.org/html/2606.19683

**作者**: Quanyan Zhu  
**机构**: 纽约大学坦登工程学院电气与计算机工程系  
**地址**: 美国纽约州布鲁克林  
**邮箱**: [email protected]  

###### 摘要  

本文研究联盟形成作为一种去中心化动态过程，该过程由单边退出与加入决策驱动。每个智能体使用 Aumann–Drèze 值评估局部移动，因此收益是在该智能体当前联盟内计算的，而非通过全局协商的联盟结构。所得到的模型将合作收益分配与非合作最佳响应行为联系起来：一个终止划分恰恰是一个不存在可接受、且对个体有利的退出与加入偏离的联盟结构。我们建立均衡特征，确定动力学允许标量 Lyapunov 或精确势函数表示的条件，并分析切换和接受成本如何塑造局部稳定性。数值实验测试了有限时间镇定、成本敏感性以及一个特殊的凸博弈基准。

*关键词*: 联盟形成 · Aumann–Drèze 值 · 退出与加入动力学 · 势博弈 · Lyapunov 分析 · 多智能体系统

## 1 引言

在许多经济、社会和社会技术系统中，智能体持续地在组织边界之间移动。个体离开现有群体，加入新群体，或完全形成新组织。这些转变并非由中央权威机构协调，而是源于大量自利智能体做出的去中心化决策。因此，联盟结构并非事先设计，而是从持续的退出与加入行为中内生涌现，正如内生和动态联盟形成模型所描述的那样[15 (https://arxiv.org/html/2606.19683#bib.bib41), 27 (https://arxiv.org/html/2606.19683#bib.bib43), 19 (https://arxiv.org/html/2606.19683#bib.bib37), 32 (https://arxiv.org/html/2606.19683#bib.bib50)]。尽管存在这一现实，现有文献大多将联盟形成建模为自上而下的过程。经典的分裂与合并算法、层次聚类方法以及集中式优化方法通常假设全局信息、协调决策或一个能够在系统层面评估备选联盟结构的规划者[28 (https://arxiv.org/html/2606.19683#bib.bib48), 9 (https://arxiv.org/html/2606.19683#bib.bib49)]。虽然这些模型在分析上很方便，但它们掩盖了实践中观察到的联盟形成的分布式本质。

本文采用了一种根本不同的视角。我们将联盟形成研究为一种去中心化动态过程，该过程由局部退出与加入决策驱动。每个智能体仅基于局部收益比较来评估是留在当前联盟、加入另一个联盟，还是形成一个单元素集。没有任何智能体需要了解全局联盟结构，也不假设存在集中式协调或协商。因此，联盟结构是作为分布式个体决策的结果出现的，而非作为集中式设计问题的解。这种局部决策观点在精神上接近于享乐型联盟形成，其中每个智能体通过自己群体的成员来评估联盟[10 (https://arxiv.org/html/2606.19683#bib.bib40), 7 (https://arxiv.org/html/2606.19683#bib.bib30)]。扩展到有限信息环境，例如通过学习或信念更新，自然契合于此框架，并留待未来工作[8 (https://arxiv.org/html/2606.19683#bib.bib9), 14 (https://arxiv.org/html/2606.19683#bib.bib10)]。

在这个去中心化过程中，当联盟不再为其成员产生足够价值时，它们可能会解散，而随着智能体分裂并重组，新的联盟可能会出现。由此产生的形成、解散和重组模式与在企业、联盟、在线社区和模块化社会技术系统中观察到的模式高度相似。从博弈论的角度看，此情境下的联盟形成处于非合作博弈与合作博弈的交汇点。智能体以非合作的方式行事，因为她们通过单边退出与加入行动追求个体理性改进。同时，每个联盟内的收益是通过合作解概念（如 Aumann–Drèze 值或 Owen 值）合作确定的。因此，联盟结构本身是一个涌现对象，由个体激励与合作收益分配规则相互作用而形成[3 (https://arxiv.org/html/2606.19683#bib.bib23), 25 (https://arxiv.org/html/2606.19683#bib.bib25), 26 (https://arxiv.org/html/2606.19683#bib.bib24)]。

### 1.1 相关应用

在人工智能多智能体系统中，智能体必须决定参与哪些任务、项目或工作流。一个智能体可能最初基于部分或局部信息加入一个协作任务，随后在出现一个价值更高或更匹配的任务时退出。这类决策通常是自主做出的，没有集中式协调，而是依赖于对预期效用、资源需求或与其他智能体兼容性的局部评估。因此，智能体到任务的分配是从分布式的退出与加入决策中涌现的，而非来自全局规划机制。在这种解释中，任务对应于联盟，而接受则反映了任务容量、兼容性或协调约束[30 (https://arxiv.org/html/2606.19683#bib.bib47), 28 (https://arxiv.org/html/2606.19683#bib.bib48)]。

劳动力市场提供了退出与加入动态的经典例子。当工人期望获得更高的报酬、更好的工作条件或更好的职业前景时，他们会离开现有组织并加入新组织。这些决策是去中心化的，并且通常是短视的，基于本地信息如工作机会、同行结果和内部组织政策。企业通过招聘决策、薪酬结构和晋升规则施加接受约束。公共政策和制度因素，包括招聘摩擦、竞业禁止条款和劳动法规，直接影响切换成本和接受条件，从而塑造劳动力流动性和人才流动的模式。由此产生的劳动力市场组织结构从个体激励与这些约束的相互作用中内生涌现，与可接受划分由局部激励和制度规则塑造的联盟形成模型相呼应[15 (https://arxiv.org/html/2606.19683#bib.bib41), 4 (https://arxiv.org/html/2606.19683#bib.bib44)]。

订阅市场，如移动服务提供商或数字流媒体平台，也表现出类似的去中心化重新配置动态。消费者定期重新评估他们的会员资格，并可能根据价格、质量、捆绑产品或网络效应退出一个服务并加入另一个。服务提供商通过定价层级、合同条款和服务差异化间接影响接受。从建模角度看，平台对应于竞争性联盟，而消费者充当反复评估是留下还是切换的智能体。因此，市场结构，包括用户分布和流失率，源于许多个体的退出与加入决策，而非集中式协调。

在这些应用中，联盟形成由分布式个体决策驱动，受局部收益比较和接受约束塑造，而非全局优化。随着智能体响应不断变化的激励、成本和机会，联盟形成、成长、收缩或消失。这种共同结构使得退出与加入动态成为人类和人工系统中组织形成与重新配置的统一建模框架。

本文做出四项贡献。首先，它将联盟形成表述为一个异步退出与加入过程，其中智能体仅使用联盟局部的 Aumann–Drèze 收益。其次，它将终止联盟结构刻画为诱导的非合作最佳响应问题的不动点。第三，它分离了底层合作博弈的效率性质与动态可实现性，表明标量 Lyapunov 和精确势函数表示需要明确的激励对齐条件。第四，它使用数值实验来检验有限终止、切换和接受摩擦，以及一个特殊凸基准，其中大联盟被动态地选择。

## 2 相关工作

联盟形成在合作与非合作博弈论中有着悠久的历史。经典的合作分析通过诸如核心和 Shapley 值等解概念研究联盟的稳定性和效率[13 (https://arxiv.org/html/2606.19683#bib.bib33), 29 (https://arxiv.org/html/2606.19683#bib.bib1), 20 (https://arxiv.org/html/2606.19683#bib.bib18), 24 (https://arxiv.org/html/2606.19683#bib.bib26), 22 (https://arxiv.org/html/2606.19683#bib.bib27)]，而内生联盟形成模型则研究划分如何从策略行为中产生，而非外生强加。早期且具有影响力的处理包括通过博弈形式和约束性协议进行联盟形成[15 (https://arxiv.org/html/2606.19683#bib.bib41), 27 (https://arxiv.org/html/2606.19683#bib.bib43)]，具有外部性的序贯联盟形成[6 (https://arxiv.org/html/2606.19683#bib.bib42)]，动态联盟形成过程[19 (https://arxiv.org/html/2606.19683#bib.bib37)]，用于 Shapley 公平联盟形成的分裂合并动态[32 (https://arxiv.org/html/2606.19683#bib.bib50)]，以及动态合作博弈[12 (https://arxiv.org/html/2606.19683#bib.bib38), 5 (https://arxiv.org/html/2606.19683#bib.bib39)]。本文在精神上最接近这些动态文献，但不同之处在于使用 Aumann–Drèze 值作为每个中间划分处的收益规则，并关注具有接受和切换成本的局部退出与加入偏离。

第二类相关工作研究享乐型联盟形成，其中每个智能体的偏好仅取决于其自己联盟的成员。享乐型联盟由 Drèze 和 Greenberg[10 (https://arxiv.org/html/2606.19683#bib.bib40)] 引入，享乐型划分的稳定性概念在后来的工作中得到了广泛发展，包括 Bogomolnaia 和 Jackson 对享乐型联盟结构的分析[7 (https://arxiv.org/html/2606.19683#bib.bib30)]。后续工作研究了稳定划分和通用联盟形成程序[2 (https://arxiv.org/html/2606.19683#bib.bib20), 1 (https://arxiv.org/html/2606.19683#bib.bib34)]，以及在单边或群体偏离下的核心稳定性的简单模型[4 (https://arxiv.org/html/2606.19683#bib.bib44)]。我们的模型共享享乐型博弈的局部性，因为智能体的收益由其当前联盟计算得出。然而，偏好不是原始的：它们由一个可转移效用博弈和一个合作分配规则内生诱导产生，这使得可以将局部激励与剩余和势函数联系起来。

这里使用的分配规则直接建立在具有联盟结构的合作值之上。Aumann–Drèze 值在固定划分的每个联盟内分配值[3 (https://arxiv.org/html/2606.19683#bib.bib23)]，而 Owen 值则首先在商博弈中将联盟视为先验联盟，然后在每个联盟内进行分配[25 (https://arxiv.org/html/2606.19683#bib.bib25), 26 (https://arxiv.org/html/2606.19683#bib.bib24)]。相关的合作模型还研究由网络或通信结构引起的限制，例如 Myerson 的图限制博弈[23 (https://arxiv.org/html/2606.19683#bib.bib46)]，而策略性网络形成模型则研究链路和合作结构如何从个体激励中产生[18 (https://arxiv.org/html/2606.19683#bib.bib19)]。这些方法提供了将组织约束嵌入收益分配的替代方式。本文使用 Aumann–Drèze 值，因为其联盟局部结构与去中心化的退出与加入更新以及由目标联盟执行的局部接受测试兼容。

还有大量的计算和多智能体文献涉及联盟形成。联盟结构生成算法通常寻求最大化总价值或在大型搜索空间下提供近似保证的划分[28 (https://arxiv.org/html/2606.19683#bib.bib48), 9 (https://arxiv.org/html/2606.19683#bib.bib49)]。多智能体系统的任务分配方法在资源和兼容性约束下使用联盟形成将智能体分配给任务[30 (https://arxiv.org/html/2606.19683#bib.bib47)]，联盟控制使用合作博弈工具进行网络化控制和协调[11 (https://arxiv.org/html/2606.19683#bib.bib11)]，基于学习的方法则研究不确定性下的联盟形成[8 (https://arxiv.org/html/2606.19683#bib.bib9)]。相比之下，本文研究的退出与加入动态并不解决集中式联盟结构生成问题。它们描述了一种去中心化调整过程，其中智能体短视地移动，目标联盟应用局部接受约束，收敛性通过 Lyapunov 或势论证而非全局优化来建立。

最后，收敛性分析与势博弈和学习动态相关。势博弈展示了单边激励如何由一个标量函数表示[21 (https://arxiv.org/html/2606.19683#bib.bib45)]，合作博弈工作已连接了值、势和一致性条件[16 (https://arxiv.org/html/2606.19683#bib.bib8), 17 (https://arxiv.org/html/2606.19683#bib.bib21)]。最近关于联盟博弈中学习的工作也强调了分布式适应和收敛[14 (https://arxiv.org/html/2606.19683#bib.bib10), 31 (https://arxiv.org/html/2606.19683#bib.bib35)]。本文的贡献在于识别 Aumann–Drèze 退出与加入激励何时允许与联盟剩余精确或序数对齐。这种分离阐明了为什么合作凸性可以暗示大联盟的效率，但不能保证短视的去中心化动态会选择它。

## 3 Aumann–Drèze 值

### 3.1 动机

令 \(N = \{1, \dots, n\}\) 为一个有限的智能体集合，并令 \(v: 2^N \to \mathbb{R}\) 为一个可转移效用 (TU) 合作博弈，满足 \(v(\varnothing) = 0\)。Shapley 值 \(\phi(v)\) [29 (https://arxiv.org/html/2606.19683#bib.bib1)] 假定大联盟 \(N\) 形成，并且整个剩余 \(v(N)\) 根据所有玩家排列上的期望边际贡献分配给智能体。在此假设下，特征函数 \(v\) 中编码的所有潜在协同效应都是完全可实现的，而不考虑任何中间的组织、制度或技术约束。然而，在许多社会技术、经济和组织系统中，合作受到现有*联盟结构* \(T = \{T_1, \dots, T_m\} \in \Pi(N)\) 的约束，该结构指定了那些具有可行约束性协议、转移和协调的联盟。属于 \(T\) 中不同联盟的智能体不能形成约束性子联盟或直接共享剩余，即使特征函数 \(v\) 赋予了这种跨联盟合作以正价值。例如，具有严格