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

• URL: http://arxiv.org/abs/2608.29388v1
• Date: Sat, 29 Aug 2026 17:55:34 GMT
• Title: Fully Distributed GNE Algorithms for Multi-Robot Placement without Consensus on Multipliers
• Abstract summary: We propose a fully distributed continuous-time algorithm for shared linear equality constraints that converge without multiplier exchange.<n>The method is validated on a multi-robot placement task.
• Score: 11.508428985972259
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus [0.0]
  Generalized Nash Equilibrium Problems (GNEPs) often arise in multi-agent engineering applications that require distributed algorithms.<n>Unlike traditional approaches that enforce consensus on multipliers, our method removes the need to share multipliers, reducing communication and improving privacy.
  arXiv  Detail & Related papers  (2026-09-07T03:19:36Z)
• Distributed GNEP Algorithms without Multiplier Sharing and Applications to Multi-Robot Coordination and Contextual Bandit-Based Active Learning [0.0]
  This work introduces fully distributed continuous-time algorithms and establishes convergence without requiring multiplier exchange.<n>I also propose several discretization schemes for the continuous-time algorithms.<n>The effectiveness of the proposed approach is demonstrated through applications in multi-robot coordination and placement.
  arXiv  Detail & Related papers  (2026-05-30T14:54:34Z)
• Lagrangian Relaxation Score-based Generation for Mixed Integer linear Programming [13.20958452268089]
  generative framework based on Lagrangian relaxation-guided differential equations (SDEs)<n>System generates diverse, high-quality solution candidates that collectively define compact and effective trust-region subproblems for standard MILP solvers.
  arXiv  Detail & Related papers  (2026-03-25T07:48:01Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations [3.280169909938912]
  parallel alternating multipliers (ADMM) is widely recognized for its effectiveness in handling large-scale distributed datasets. The proposed algorithms serve to demonstrate the reliability, stability, and scalability of a financial example.
  arXiv  Detail & Related papers  (2023-11-21T03:30:38Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• Ensure Differential Privacy and Convergence Accuracy in Consensus Tracking and Aggregative Games with Coupling Constraints [1.8661143694112918]
  We address differential privacy for fully distributed aggregative games with shared coupling constraints. By co-designing the generalized Nash equilibrium (GNE) seeking mechanism and the differential-privacy noise injection mechanism, we propose the first GNE seeking algorithm. We also propose a new consensus-tracking algorithm that can achieve rigorous epsilon-differential privacy while maintaining accurate tracking performance.
  arXiv  Detail & Related papers  (2022-10-28T20:33:37Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  This paper focuses on the most basic setting of competitive multi-agent RL, namely two-player zero-sum Markov games. We propose a single-loop policy optimization method with symmetric updates from both agents, where the policy is updated via the entropy-regularized optimistic multiplicative weights update (OMWU) method. Our convergence results improve upon the best known complexities, and lead to a better understanding of policy optimization in competitive Markov games.
  arXiv  Detail & Related papers  (2022-10-03T16:05:43Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints [3.2815423235774634]
  We propose a method of multipliers for solving a class of multiblock nonsmooth alternating optimization problem with nonlinear constraints. We employ a major sequenceization procedure in update of each block of the primal variables.
  arXiv  Detail & Related papers  (2022-01-19T15:31:30Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  We consider distributed variational inequalities (VIs) on domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that covers the settings of fully decentralized calculations. We theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone settings.
  arXiv  Detail & Related papers  (2021-06-15T17:45:51Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.