本文介绍了一项由Jialing Zhou（北京理工大学），Guanghui Wen（东南大学），Yuezu Lv（北京理工大学），Xinlei Yi（同济大学），Tao Yang（东北大学）以及Karl Henrik Johansson（瑞典皇家理工学院）共同完成的研究，该研究以论文形式《Distributed Nash equilibrium computation in multi-group resource allocation games over digraphs》发表于2026年的期刊 Automatica 第185卷。

研究背景

该研究属于分布式优化与控制领域，特别是多智能体系统（Multi-agent Systems）在博弈论（Game Theory）和资源分配（Resource Allocation）交叉方向的前沿探索。随着信息物理系统（如智能电网、云计算平台、多机器人系统）的普及，如何在网络化、分散式的环境中进行高效的资源决策成为一个核心挑战。传统的研究多集中于单一合作群体内的分布式资源分配（Distributed Resource Allocation, DRA），即所有智能体目标一致，共同优化一个全局目标。

然而，现实世界中存在大量具有竞争关系的多个利益集团（例如，不同公司旗下的多个业务部门、多个能源供应商）。每个集团内部合作，但集团之间为了争夺市场份额或优化自身收益而存在利益冲突。此外，在实际应用中（如电力系统的在线经济调度），不仅要求最终解决方案达到供需平衡，更希望在算法执行的每一次迭代过程中都严格维持这种平衡，这被称为硬平衡约束（Hard Balance Constraint）。同时，智能体间的通信网络往往是非对称的有向图（Digraph），这进一步增加了算法设计的难度。现有的DRA算法或分布式纳什均衡（Nash Equilibrium, NE）计算方法，大多难以同时应对多群体博弈、有向通信拓扑和硬平衡约束这三重挑战。本研究正是为了填补这一空白，从一个博弈论的视角出发，提出了资源分配博弈（Resource Allocation Game, RAG）模型，并致力于设计相应的分布式NE计算算法。

研究目标

本研究旨在开发一种能够在有向通信网络下，解决多群体资源分配博弈（RAG）问题的分布式算法。具体目标包括： 1. 设计算法，使得所有智能体的状态能够分布式地收敛到RAG的纳什均衡（NE）。 2. 确保在整个算法迭代过程中，每个群体内部的资源硬平衡约束（即总资源分配量等于群体可用资源总量）始终得到满足。 3. 算法仅依赖智能体的局部信息（自身状态、目标函数）以及与邻居的有限通信，适应通用的有向图拓扑结构。 4. 从理论上证明所提算法的线性收敛性。

研究流程与方法

本研究的主要工作流程分为问题建模、算法设计、理论分析和数值验证四个核心环节。

1. 问题建模与定义： 研究人员首先形式化地定义了多群体资源分配博弈（RAG）。考虑有n个群体（Group），每个群体i包含ni个智能体（Agent）。每个智能体ij有一个私有的局部目标函数fij，其决策变量（状态）为xij。群体i的总体目标是极小化其内部所有智能体目标函数之和fi(x) = Σ fij(x)，但此目标受到群体i内部所有智能体决策变量之和必须等于其总资源ri的等式约束。关键点在于，每个智能体的目标函数fij不仅依赖于本群体内其他智能体的决策，还依赖于所有其他群体的决策x_{-i}。这刻画了群体间的耦合与竞争。研究的核心是分布式地寻找该博弈的纳什均衡x*，即在该点，任何单个群体在满足自身约束的条件下，都无法通过单方面改变自己的决策来获得更好的收益。通信拓扑被建模为一个通用的有向图，并引入了关联的邻接矩阵、加权矩阵以及关键的出拉普拉斯矩阵（Out-Laplacian Matrix）等数学工具。

2. 算法设计： 这是本研究最具创新性的部分。为了同时解决有向拓扑和硬平衡约束的难题，作者提出了一种基于出拉普拉斯矩阵的设计框架。其核心洞见在于，利用出拉普拉斯矩阵Lo_i的性质（满足1^T * Lo_i = 0），可以构造一个从虚拟变量z_i到实际决策变量x_i的线性变换：x_i(k+1) = x_i(0) - Lo_i * z_i(k+1)。这种设计能天然保证在任意迭代k下，1^T * x_i(k) = 1^T * x_i(0) = ri，即硬平衡约束自动满足。研究团队随后基于此框架，开发了两种具有不同估计机制的分布式算法。

• 算法1（领导者-跟随者跟踪算法）：

  • 设计思路：为了执行基于伪梯度下降的虚拟变量zi更新，每个智能体需要估计其群体级目标函数fi的偏导数信息。由于fi是全局信息，算法为每个智能体ij设计了两组辅助变量：(a) 变量s{ij}^{pq}，用于跟踪（估计）所有其他智能体pq的状态x{pq}； (b) 向量变量η{ij}^{il}，用于跟踪本群体内每个智能体il的个体目标函数偏导数 ∂f_{il}/∂x_i。算法通过领导者-跟随者共识协议（Leader-follower Consensus Protocol）来更新这些估计变量。
  • 更新流程：每个智能体ij在每一步迭代中：(1) 根据邻居的z值和估计的梯度差更新自己的虚拟变量z{ij}（公式2b）；(2) 利用邻居的η值和局部计算的梯度更新其梯度估计器η{ij}^{il}（公式2c）；(3) 利用邻居的状态估计值更新其对全网状态的估计s{ij}^{pq}（公式2d）；(4) 最后，通过出拉普拉斯变换x{ij}(k+1) = x{ij}(0) - d{ij}^{out} * z{ij}(k+1) + Σ z{im}(k+1) 更新自己的实际决策状态（公式2a），该步骤自动确保了硬平衡。
  • 特点：算法结构清晰，便于理论分析，但需要维护的辅助变量维度较高（每个智能体需维护1 + n_i^2 + n_sum个变量）。

• 算法2（降阶梯度跟踪算法）：

  • 设计思路：为了降低计算和通信复杂度，算法2采用了梯度跟踪机制（Gradient-tracking Mechanism）。与算法1估计每个个体的偏导数不同，算法2让每个智能体ij维护一个标量变量ξ{ij}^{il}，其目标是跟踪一个加权的群体级梯度分量 (v{ij}/n_i) * (∂fi/∂x{il})，其中v_{ij}是与通信矩阵相关的常数。
  • 更新流程：迭代步骤与算法1类似，但关键区别在于梯度估计部分的更新（公式15c）：ξ{ij}^{il}(k+1) = Σ c{ij}^{im} ξ{im}^{il}(k) + [∂f{ij}/∂x{il}(s{ij}(k+1)) - ∂f{ij}/∂x{il}(s_{ij}(k))]。这是一种典型的梯度跟踪形式，通过扩散（diffusion）和增量修正来估计平均梯度。
  • 特点：显著降低了辅助变量的维度（每个智能体维护2 + n_i + nsum个变量），计算复杂度更低。此外，由于智能体之间传递的是跟踪变量ξ而非原始梯度∂f{ij}/∂x_i，更好地保护了个体目标函数的隐私。不过，其初始化和收敛分析相对复杂。

3. 理论分析（收敛性证明）： 研究团队为两种算法分别建立了严格的线性收敛性证明。证明的核心是构造合适的李雅普诺夫（Lyapunov）函数V(k)，该函数综合了状态误差、梯度估计误差和全局状态估计误差。通过细致分析每一步迭代中V(k)的变化，并利用目标函数的强单调性（Assumption 3）和Lipschitz连续性（Assumption 2）等假设，最终证明了存在一个步长α（或β）的上界，使得V(k+1) ≤ (1-ε)V(k)，其中0<ε。这直接意味着决策变量x(k)能够以线性速率O((1-ε)^k)收敛到纳什均衡x*。附录中提供了详细的证明过程，展示了如何处理由有向图和分布式估计引入的复杂耦合误差系统。

4. 数值验证： 为了验证算法的有效性，论文设计了一个基于互联网公司多业务线古诺竞争（Cournot Competition）的仿真案例。三个公司（群体）分别拥有3、5、4个业务线（智能体），竞争两个细分市场。每个业务线的收益取决于自身分配的计算资源、市场总供应量（受其他公司决策影响）以及成本。通信拓扑如图1所示，是一个通用的有向图。仿真分别运行算法1（α=0.0005）和算法2（β=0.01）。结果表明： * 两种算法都能成功驱动所有智能体的决策变量收敛到预先计算好的纳什均衡。 * 在每个迭代步，每个公司内部所有业务线的资源分配总和都严格等于其总计算资源，验证了硬平衡约束的满足。 * 算法2在此算例中表现出比算法1更快的收敛速度。 * 作者还探讨了步长对收敛性能的影响，指出了收敛的临界步长值，并观察到算法2允许的步长范围更宽，这在某些情况下有助于获得更快的收敛速率。

主要结果

1. 提出了通用的多群体RAG模型与基于出拉普拉斯矩阵的设计框架：这是本研究的理论基石，成功地将硬平衡约束的满足转化为出拉普拉斯矩阵的一个代数性质，从而允许算法在任意有向图下工作。
2. 设计了两种新型分布式纳什均衡计算算法：
   • 算法1（领导者-跟随者跟踪）提供了清晰的设计范例，便于理论延伸。
   • 算法2（降阶梯度跟踪）显著降低了计算和通信负担，并具有隐私保护潜力。
3. 建立了严格的线性收敛性理论：在目标函数满足凸性、连续可微、强单调等标准假设下，证明了两种算法都能以线性速率收敛到RAG的精确纳什均衡。
4. 通过数值仿真验证了算法的有效性和优势：仿真结果直观展示了算法在解决实际问题时的性能，包括收敛性、约束满足情况以及不同算法在收敛速度上的比较。

结论与意义

本研究成功解决了在有向通信网络下，带硬平衡约束的多群体资源分配博弈的分布式纳什均衡计算问题。其科学价值在于： * 理论创新：提出的“出拉普拉斯矩阵框架”是对现有分布式优化和博弈算法工具箱的一个重要补充，为处理有向图上的等式约束提供了新思路。 * 算法贡献：设计的两种算法拓展了分布式NE计算的应用范围，使其能够适用于更符合实际通信场景的有向、非平衡拓扑，并满足在线执行过程中的实时平衡需求。 * 桥梁作用：将单群体合作的分布式资源分配问题，推广到多群体既合作又竞争的博弈场景，建立了分布式优化与博弈论之间更紧密的联系。

其应用价值非常广泛，可直接应用于： * 智能电网：多个分布式能源供应商（群体）在电力市场中的在线经济调度，需实时保持发电与负荷的平衡。 * 云计算/边缘计算：多个云服务商为其内部不同虚拟机或边缘节点分配计算资源，以在竞争市场中最大化收益。 * 物流与供应链管理：多个物流公司内部车队资源的调度，受到市场运价（受其他公司影响）的耦合。

研究亮点

1. 问题新颖性与挑战性：首次系统性地研究了同时包含有向图拓扑、硬平衡约束和多群体博弈的分布式资源分配问题，抓住了实际应用中的关键难点。
2. 方法创新性：提出的出拉普拉斯矩阵设计框架是核心亮点，它巧妙地将状态更新与约束满足解耦，是解决该复杂问题的关键。
3. 算法设计的完备性：不仅提出了一种基础算法（算法1），还进一步开发了性能更优的降阶算法（算法2），在降低复杂度和保护隐私方面做出了改进，体现了研究工作的深度。
4. 理论分析的严密性：为两种算法都建立了线性收敛性证明，这通常比次线性收敛更有吸引力，并且分析过程中需要处理多个耦合的误差动态系统，技术难度高。
5. 明确的实用导向：强调“硬平衡约束”和“有向图”，直指许多实际在线部署场景（如经济调度）的核心需求，使理论研究更具现实意义。

其他有价值的内容

论文还简要讨论了所研究RAG模型的两个特例： * 内部独立资源分配博弈（IIRAG）：当智能体的收益仅取决于自身状态和其他群体的状态，而与本群体内其他智能体状态无关时，算法1可以进一步简化，降低变量维度。 * 与现有工作的对比：作者明确指出，当群体数n=1时，IIRAG退化为标准的单群体DRA问题。因此，本研究可视为对现有DRA文献向多群体博弈场景的自然推广。同时，文章详细对比了与近期相关工作的区别，突出了本工作在处理非平衡有向图方面的独特优势（前人工作多限于无向图或平衡有向图）。