Fully Distributed GNE Algorithms for Multi-Robot Placement without Consensus on Multipliers

Shao-An Yin; Mingyi Hong; Nicola Elia

cs.LGAug 29, 2026

Fully Distributed GNE Algorithms for Multi-Robot Placement without Consensus on Multipliers

Authors: Shao-An Yin, Mingyi Hong, Nicola Elia

Organizations: Department of Electrical and Computer Engineering, University of Minnesota, USA

Abstract

Recent machine learning research has increasingly focused on equilibrium analysis in non-cooperative games rather than solely on optimal solutions. Many such problems involve shared constraints and can be formulated as Generalized Nash Equilibrium Problems (GNEPs). For strongly monotone games, existing methods compute consensus-based variational GNEs (v-GNEs) by exchanging Lagrange multipliers. We propose a fully distributed continuous-time algorithm for shared linear equality constraints that converges without multiplier exchange and reaches any GNE, reducing communication overhead and improving privacy. Discrete-time schemes are also provided, and the method is validated on a multi-robot placement task.

Figures & tables

	$\displaystyle z_{v}^{+}\leftarrow P_{Z_{v}}\Big\{z_{v}-\tau_{v}\cdot\big[$	$\displaystyle\nabla_{z_{v}}f_{v}(z_{v},z_{-v})$
		$\displaystyle+\lambda_{v}^{\top}\nabla_{z_{v}}g_{v}(z_{v},\mathbf{z}_{-v})\big]\Big\}.$

Algorithm 3 Forward-Backward for Each Agent

v

Fig. 1: Multi-robot placement with 12 robots and 4 tasks. Circles denote robots $v$ , rectangles their anchor points $A_{v}$ , and dotted boxes local constraint regions. Yellow stars $c_{j}$ mark task locations. Arrows indicate assignments ( $v\in N_{j}$ , $j\in M_{v}$ ), forming a bipartite robot–task structure.

Fig. 2: Converging trajectories from six random initializations (seeds 0–5). “x” marks the corresponding convergence points, all of which are GNEs.

Fig. 3: Comparison of Algorithm 3 (forward–backward discretization) with consensus-based approaches from [ 16 ] . Both are initialized at zero with learning rate $0.01$ , converging to a v-GNE.

Nash Equilibrium Computation

Nash equilibrium computation develops algorithms for finding stable strategies in strategic, stochastic, and imperfect-information games.

See all 69 papers

Distributed GNEP Algorithms without Multiplier Sharing and Applications to Multi-Robot Coordination and Contextual Bandit-Based Active Learning
May 30, 2026Shao-An YinGame Theory Distributed Optimization
UNIVERSITY OF MINNESOTA
Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus
Sep 7, 2026Shao-An YinPrimal-Dual Optimization Dynamical Systems
independent researcher
A Fast Convergent Algorithm for Solving Non-convex Partially-Decoupled Generalized Nash Equilibrium Problems
Jun 26, 2026Bennet Outland, Vishala AryaGame Theory Nonconvex Optimization
Smead Aerospace Engineering Sciences Department, 3775 Discovery Drive, Boulder, CO, USA

May 30, 2026J/K move · Enter open · S save

Distributed GNEP Algorithms without Multiplier Sharing and Applications to Multi-Robot Coordination and Contextual Bandit-Based Active Learning

Shao-An Yin

UNIVERSITY OF MINNESOTA

Game Theory Distributed Optimization Active Learning Contextual Bandits

Open paper AskPDF arXiv

Recent advances in artificial intelligence have expanded the focus from classical optimization to include equilibrium analysis in noncooperative games. Many such games involve shared constraints, leading to Generalized Nash Equilibrium Problems (GNEPs). Existing distributed algorithms typically require agents to exchange Lagrange multipliers to enforce consensus and compute variational-GNEs (v-GNEs). This work introduces fully distributed continuous-time algorithms and establishes convergence without requiring multiplier exchange, thereby reducing information exchange per iteration while improving privacy preservation. The analysis focuses on strongly monotone games with convex individual constraints and linear shared constraints. I also propose several discretization schemes for the continuous-time algorithms. The proposed approach converges to general GNEs, rather than being restricted to v-GNEs, with the attained equilibrium depending on the initialization. The effectiveness of the proposed method is demonstrated through applications in multi-robot coordination and placement. In the second part, this work includes research conducted in collaboration with Amazon scientists. One of the most challenging problems in real-world machine learning is labeled data collection, which typically requires substantial human effort and cost. Active learning aims to reduce this labeling requirement. Existing handcrafted active learning strategies, however, generally perform well only on specific types of datasets, which are often unknown in advance. In this work, I propose using contextual bandits to adaptively select the most suitable active learning strategy. The effectiveness of the proposed approach is demonstrated on publicly available external datasets.

Abstract

Nash Equilibrium Computation

Explore similar work

Distributed GNEP Algorithms without Multiplier Sharing and Applications to Multi-Robot Coordination and Contextual Bandit-Based Active Learning

Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus

A Fast Convergent Algorithm for Solving Non-convex Partially-Decoupled Generalized Nash Equilibrium Problems