An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems

• URL: http://arxiv.org/abs/2410.02400v1
• Date: Thu, 3 Oct 2024 11:27:55 GMT
• Title: An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems
• Authors: Sarah Sachs, Hedi Hadiji, Tim van Erven, Mathias Staudigl,
• Abstract summary: We introduce a new online feasible point method for generalized Nash equilibrium games. Under the assumption that limited communication between the agents is allowed, this method guarantees feasibility. We identify the class of benign generalized Nash equilibrium problems, for which the convergence of our method to the equilibrium is guaranteed.
• Score: 4.243592852049963
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider a repeatedly played generalized Nash equilibrium game. This induces a multi-agent online learning problem with joint constraints. An important challenge in this setting is that the feasible set for each agent depends on the simultaneous moves of the other agents and, therefore, varies over time. As a consequence, the agents face time-varying constraints, which are not adversarial but rather endogenous to the system. Prior work in this setting focused on convergence to a feasible solution in the limit via integrating the constraints in the objective as a penalty function. However, no existing work can guarantee that the constraints are satisfied for all iterations while simultaneously guaranteeing convergence to a generalized Nash equilibrium. This is a problem of fundamental theoretical interest and practical relevance. In this work, we introduce a new online feasible point method. Under the assumption that limited communication between the agents is allowed, this method guarantees feasibility. We identify the class of benign generalized Nash equilibrium problems, for which the convergence of our method to the equilibrium is guaranteed. We set this class of benign generalized Nash equilibrium games in context with existing definitions and illustrate our method with examples.

Related papers

• Independent RL for Cooperative-Competitive Agents: A Mean-Field Perspective [11.603515105957461]
  We address in this paper Reinforcement Learning (RL) among agents that are grouped into teams such that there is cooperation within each team but general-sum competition across different teams.
  arXiv  Detail & Related papers  (2024-03-17T21:11:55Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  Non-concave games introduce significant game-theoretic and optimization challenges. We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria. We also show that Online Gradient Descent can efficiently approximate $Phi$-equilibria in non-trivial regimes.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• Independent Learning in Constrained Markov Potential Games [19.083595175045073]
  Constrained Markov games offer a formal framework for modeling multi-agent reinforcement learning problems. We propose an independent policy gradient algorithm for learning approximate constrained Nash equilibria.
  arXiv  Detail & Related papers  (2024-02-27T20:57:35Z)
• Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
  We consider decentralized learning for zero-sum games, where players only see their information and are to actions and payoffs of the opponent. Previous works demonstrated convergence to a Nash equilibrium in this setting using double time-scale algorithms under strong reachability assumptions. Our contribution is a rational and convergent algorithm, utilizing Tsallis-entropy regularization in a value-iteration-based algorithm.
  arXiv  Detail & Related papers  (2023-12-13T09:31:30Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Differentiable Arbitrating in Zero-sum Markov Games [59.62061049680365]
  We study how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating. The lower level requires solving the Nash equilibrium under a given reward function, which makes the overall problem challenging to optimize in an end-to-end way. We propose a backpropagation scheme that differentiates through the Nash equilibrium, which provides the gradient feedback for the upper level.
  arXiv  Detail & Related papers  (2023-02-20T16:05:04Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution Concept over Nash Equilibria [61.093297204685264]
  An effective approach in multiagent reinforcement learning is to consider the learning process of agents and influence their future policies. This new solution concept is general such that standard solution concepts, such as a Nash equilibrium, are special cases of active equilibria. We analyze active equilibria from a game-theoretic perspective by closely studying examples where Nash equilibria are known.
  arXiv  Detail & Related papers  (2022-10-28T14:45:39Z)
• How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games [64.71476526716668]
  We study the (in)efficiency of any equilibrium players might agree to play. We obtain guarantees that refine existing bounds on the Price of Anarchy. Although the obtained guarantees concern open-loop trajectories, we observe efficient equilibria even when agents employ closed-loop policies.
  arXiv  Detail & Related papers  (2022-10-24T09:32:40Z)
• Personalized incentives as feedback design in generalized Nash equilibrium problems [6.10183951877597]
  We investigate stationary and time-varying, nonmonotone generalized Nash equilibrium problems. We design a semi-decentralized Nash equilibrium seeking algorithm. We consider the ridehailing service provided by several companies as a service orchestration.
  arXiv  Detail & Related papers  (2022-03-24T09:24:29Z)
• Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information [32.384868685390906]
  We examine the Nash equilibrium convergence properties of no-regret learning in general N-player games. We establish a comprehensive equivalence between the stability of a Nash equilibrium and its support. It provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games.
  arXiv  Detail & Related papers  (2021-01-12T18:55:11Z)

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.