Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation

• URL: http://arxiv.org/abs/2509.14032v2
• Date: Tue, 14 Oct 2025 12:25:18 GMT
• Title: Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation
• Authors: Philip Jordan, Maryam Kamgarpour,
• Abstract summary: We study the existence and computation of Nash equilibria in continuous static games where the players' strategies are subject to shared coupling constraints.<n>Specifically, we focus on a class of games admissible by playerwise concave utilities and playerwise concave constraints.
• Score: 8.784438985280092
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the existence and computation of Nash equilibria in continuous static games where the players' admissible strategies are subject to shared coupling constraints, i.e., constraints that depend on their \emph{joint} strategies. Specifically, we focus on a class of games characterized by playerwise concave utilities and playerwise concave constraints. Prior results on the existence of Nash equilibria are not applicable to this class, as they rely on strong assumptions such as joint convexity of the feasible set. By leveraging topological fixed point theory and novel structural insights into the contractibility of feasible sets under playerwise concave constraints, we give an existence proof for Nash equilibria under weaker conditions. Having established existence, we then focus on the computation of Nash equilibria via independent gradient methods under the additional assumption that the utilities admit a potential function. To account for the possibly nonconvex feasible region, we employ a log barrier regularized gradient ascent with adaptive stepsizes. Starting from an initial feasible strategy profile and under exact gradient feedback, the proposed method converges to an $\epsilon$-approximate constrained Nash equilibrium within $\mathcal{O}(\epsilon^{-3})$ iterations.

Related papers

• An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems [4.243592852049963]
  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.
  arXiv  Detail & Related papers  (2024-10-03T11:27:55Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  We study tractable $Phi$-equilibria in non-concave games.<n>We show that when $Phi$ is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding $Phi$-equilibria.
  arXiv  Detail & Related papers  (2024-03-13T01:51:30Z)
• Exploiting hidden structures in non-convex games for convergence to Nash equilibrium [62.88214569402201]
  A wide array of modern machine learning applications can be formulated as non-cooperative Nashlibria. We provide explicit convergence guarantees for both deterministic and deterministic environments.
  arXiv  Detail & Related papers  (2023-12-27T15:21:25Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions [11.793922711718645]
  We address payoff-based decentralized learning in infinite-horizon zero-sum Markov games.<n>In this setting, each player makes decisions based solely on received rewards, without observing the opponent's strategy or actions nor sharing information.<n>By establishing novel properties of the value and policy updates induced by the Tsallis entropy regularizer, we prove finite-time convergence to an approximate Nash equilibrium.
  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)
• Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricing [0.0]
  We investigate Nash equilibrium learning in a competitive Markov Game (MG) environment. We develop a new model-free method to find approximate Nash equilibria. We demonstrate that an approximate Nash equilibrium can be learned, particularly in the dynamic pricing domain.
  arXiv  Detail & Related papers  (2022-07-13T19:27:07Z)
• Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics [28.815822236291392]
  We show that no game dynamics can converge to $epsilon$-Nash equilibria. We also prove a stronger result for $epsilon$-approximate Nash equilibria.
  arXiv  Detail & Related papers  (2022-03-26T18:27:40Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  We study the dynamics of "follow-the-regularized-leader" (FTRL) We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL. This result has significant implications for predicting the outcome of a learning process.
  arXiv  Detail & Related papers  (2020-10-19T13:49:06Z)

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.