CS Paper Radar

Distributed Nash Equilibrium Seeking for Open Multi-Coalition Games: A Mass-Preserving Gradient-Tracking-Based Algorithm

Daning Lei, Jiamin Wang, Jian Liu, Feng Xiao, Yuanshi Zheng

eess.SY ·submitted 2026-10-06 13:16 UTC · v1

Abstract

This paper studies distributed information aggregation and Nash equilibrium seeking over open multi-coalition networks, where both agents and coalitions may dynamically enter and leave the network. The varying network population poses a fundamental challenge to conventional gradient-tracking methods, as agent departures may cause the loss of gradient information required for distributed aggregation. To overcome this issue, a mass-preserving gradient-tracking method is designed, in which the gradient information carried by departing agents is redistributed to the remaining agents within the same coalition. The proposed method preserves the aggregate gradient information of the coalition objective over the intra-coalition communication network and achieves gradient tracking under dynamic population changes without imposing additional initialization conditions beyond those of conventional gradient-tracking methods. Based on the proposed gradient-tracking mechanism, a distributed Nash equilibrium seeking framework is developed, and its convergence is established under both uncoordinated fixed and diminishing stepsizes. Furthermore, to alleviate the slowdown of convergence caused by classical diminishing stepsize schemes ($\frac{η_0}{t}$, where $η_0>0$ is a constant), an exponential-interval diminishing stepsize scheme is designed based on the agents' exploration intervals. Finally, a numerical simulation based on an open connecting control game demonstrate the effectiveness of the proposed information-tracking and Nash equilibrium seeking framework.

Comment
13 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Gradient-extrapolation-based distributed mirror descent algorithm for multi-cluster aggregative games

cs.GT math.OC ·2026-08-25 ·Rui Zhu, Fuyong Wang, Zhongxin Liu, Zengqiang Chen
similarity 0.68
Abstract

This paper studies a class of multi-cluster aggregative games characterized by the coexistence of cooperation and competition, where each agent's cost function depends on its own strategy and the aggregate of all agents' strategies. To address the Nash equilibrium seeking problem for such games in the non-Euclidean setting, a distributed mirror descent algorithm with gradient extrapolation is proposed over time-varying intra-cluster and inter-cluster networks. The mirror descent framework employs a general Bregman divergence as the distance measure, providing greater flexibility than Euclidean-based methods, while gradient extrapolation exploits historical gradient information to improve convergence performance. Under the restricted strong monotonicity characterized by the Bregman divergence, the convergence of the proposed algorithm is established, and it achieves the $\mathcal{O}(1/k)$ convergence rate with the appropriately selected step-size and parameters. Finally, the effectiveness of the proposed algorithm is verified by an example on the demand response of energy systems.

0.20

Cooperative Learning of Shared Latent Dynamics for Distributed Online Optimization

eess.SY ·2026-11-11 ·Shivanshu Tripathi, Maziar Raissi
similarity 0.63
Abstract

We study networked agents that must agree on a decision minimizing the sum of their local costs, where each cost contains unmeasurable stochastic parameters that evolve with linear but unknown dynamics shared by all agents. Each agent receives only finitely many noisy gradient measurements and must then keep tracking the moving minimizer. Our scheme reconstructs the parameters from windows of gradients, learns the shared dynamics cooperatively by averaging instrumental-variable moment matrices over the network, and tracks the minimizer by gradient tracking on forecast gradients. We bound the error of every agent in learning the dynamics and in tracking the minimizer, and show that the learning error, and through it the tracking error, decreases with the number of agents. We demonstrate the approach on two case studies.

0.14

Distributed Optimization with Streaming Data: A Temporal Weighting Perspective

eess.SP cs.AIcs.LGeess.SY+1 ·2026-08-10 ·Muhammad Faraz Ul Abrar, Nicolò Michelusi, Erik G. Larsson
similarity 0.62
Abstract

Optimization theory is a widely used tool for intelligent decision-making. While classical optimization deals with fixed, time-invariant objective functions, many modern applications operate in dynamic environments where data arrive sequentially, and the learning objective evolves over time, often under decentralized data and communication constraints. Motivated by these trends, we study decentralized optimization from streaming data through a structured time-varying formulation in which the global objective is a temporally weighted average of losses observed across the network. We analyze multi-iteration decentralized first-order methods, including decentralized gradient descent. For strongly convex and smooth losses, we develop guarantees for the Euclidean-norm \emph{tracking error} through a contraction-mapping viewpoint. The resulting bounds decompose the tracking error into a fixed-point tracking component and a bias term induced by decentralization and data heterogeneity. We specialize our analysis to uniform and exponentially discounted weights, as well as their finite-memory \emph{windowed} counterparts. The bounds explicitly characterize the roles of the temporal weighting rule, per-step iteration budget, step size, and network connectivity. Uniform weighting yields a vanishing fixed-point tracking contribution of order $\mathcal O(1/t)$, whereas discounted and windowed strategies generally induce non-vanishing tracking floors governed by the discount factor and effective memory, respectively. In all cases, decentralization induces an additional non-zero bias floor under a constant step size. Numerical experiments illustrate the predicted trends.

0.04

Finite-Sample Convergence in Networked Average Reward MARL: Decentralization Pitfalls and Entropy Remedies

cs.LG cs.MA ·2026-11-02 ·Yizhou Zhang, Yashaswini Murthy, Laixi Shi, Adam Wierman
similarity 0.61
Abstract

We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its $k$-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

0.18

Optimistic Distributed Submodular Coordination with Applications to Multi-Target Tracking with Multiple Robots

eess.SY ·2026-10-14 ·Pranjal Sharma, Atharva Navsalkar, Zirui Xu, Vasileios Tzoumas
hot direction similarity 0.61
Abstract · 8 pages, 1 figure, under review for the American Control Conference (ACC 2027)

We provide a distributed online algorithm for multi-agent submodular coordination in bandit environments, i.e., environments whose evolution is unknown a priori and may even adapt to the agents' actions. We are motivated by multi-robot tasks such as target tracking, where the optimal actions change over time and the agents must track them rather than a single fixed optimum. To address such problems, we provide the Optimistic Distributed Online Greedy (O-DOG) algorithm, that leverages predictions about the environment's behavior and improves regret guarantees. The agents select actions simultaneously over arbitrary, possibly time-varying, network topologies, and each agent acts optimistically, i.e., leveraging predictions of its upcoming rewards, e.g., from forecasts of the targets' motion and of its neighbors' actions. We bound O-DOG's tracking regret in terms of the agents' prediction error and the bound never exceeds its prediction-free counterpart. Particularly, it is sublinear even when the optimal action changes at every time step, provided the predictions are accurate enough. We further quantify the suboptimality due to decentralization as a function of the network structure, and show that accurate predictions accelerate convergence. We validate O-DOG in simulated multi-robot target tracking.

0.31

Budget-Constrained Multi-Consensus Decentralized Gradient Descent

eess.SY math.OC ·2026-10-06 ·Shuyi Ren, Nicol`o Michelusi, Erik G. Larsson
hot direction similarity 0.61
Abstract

We investigate decentralized gradient descent (DGD) with emphasis on efficient communication and computation resource utilization under budget constraints. As a first step toward the broader communication-computation allocation problem, we consider and analyze a \textit{multi-consensus decentralized gradient descent} (mcDGD) scheme, where the number of consensus rounds and the stepsize are allowed to vary across iterations. Building on a unified analytical framework for DGD, we derive finite-time convergence bounds that explicitly characterize the interaction between consensus quality and optimization dynamics. Our analysis requires only convexity of the local objective functions while assuming smoothness and strong convexity of the global objective. The resulting bounds enable a principled consensus-allocation strategy under resource constraints, for which we show that equal allocation of consensus rounds across iterations is optimal under our stepsize rule, up to integer rounding. Numerical experiments corroborate the theoretical findings and demonstrate favorable communication-computation tradeoffs compared with existing multi-consensus decentralized optimization baselines.

0.30

Last-Iterate Convergence of Policy Dynamics in Zero-Sum Networked Separable Markov Games

cs.GT ·2026-09-08 ·Zailin Ma
similarity 0.60
Abstract

Solving Nash equilibria for general multi-player Markov games is computationally intractable, while two-player zero-sum Markov games admit fast last-iterate policy-optimization methods. Zero-sum networked separable Markov games occupy an important middle ground: they retain global multi-player competition structure through pairwise interactions, while preserving computational tractability of Nash equilibria (NE) in the finite-horizon setting. Existing algorithms for this class either proceed through equilibrium-collapse arguments for a simplified setting where a single controller determines the transition probability, or backward dynamic programming that relies on equilibrium solvers at each stage. However, the design and analysis of direct policy-update approaches remain inadequate. To address this issue, we propose the entropy-regularized optimistic multiplicative weights update (ER-OMWU), a complementary single-loop policy dynamic that updates players' policies symmetrically and returns an approximate NE in the last iteration. We provide the first last-iterate convergence analysis of policy dynamics in the games of interest: after $\widetilde O\left(1/ε\right)$ iterations, the returned policy is an $ε$-approximate Nash equilibrium. The result preserves the near-linear convergence rate achieved by policy optimization in two-player zero-sum Markov games, but extends the policy-dynamics viewpoint to a more complicated but structured multi-player setting.

0.20

Scalar Communication via Random Direction Refreshing for Distributed Optimization

cs.MA ·2026-10-05 ·Mohammadreza Rostami, Solmaz S. Kia
similarity 0.59
Abstract

Distributed optimization over networks requires agents to repeatedly exchange decision variables with their neighbors. When the decision dimension $d$ is large, these exchanges dominate the communication cost, which is critical for bandwidth-constrained agents. Existing remedies quantize or sparsify the exchanged vectors, yet each message still scales with $d$ and the compression error must be compensated by additional states. To address this limitation, we propose a scalar-communication mechanism in which every neighbor message carries a single real number regardless of $d$. Agents regenerate a common random direction from a shared seed, transmit only the inner product of their state with that direction, and act on the resulting rank-one surrogate of their neighbors' states while retaining full local gradients. We develop and analyze the mechanism for an existing continuous-time distributed optimization algorithm. For strongly convex local costs with Lipschitz gradients, we show that the optimizer remains the unique consensus equilibrium, that a fixed direction admits spurious equilibria, and that refreshing the direction at a sufficiently high rate yields exponential mean-square and almost-sure convergence with constant gains and no residual error. The framework admits any isotropic fixed-norm direction distribution, including Rademacher, scaled-coordinate, and sphere-normalized Gaussian directions; all three attain lower fresh-encoding variance than unnormalized Gaussian directions. The effects of the direction distribution and the refresh interval are illustrated in~simulations.

0.53