Evolutionary Algorithms for Computing Nash Equilibria in Dynamic Games

• URL: http://arxiv.org/abs/2601.02397v1
• Date: Sat, 27 Dec 2025 15:00:27 GMT
• Title: Evolutionary Algorithms for Computing Nash Equilibria in Dynamic Games
• Authors: Alireza Rezaee,
• Abstract summary: Classical methods for computing Nash equilibria, especially in linear quadratic settings, rely on strong structural assumptions.<n>We show through examples that such methods can fail to reach the true global Nash equilibrium even in relatively small games.<n>We propose two population based evolutionary algorithms for general dynamic games with linear or nonlinear dynamics and arbitrary objective functions.
• Score: 0.5482532589225553
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic nonzero sum games are widely used to model multi agent decision making in control, economics, and related fields. Classical methods for computing Nash equilibria, especially in linear quadratic settings, rely on strong structural assumptions and become impractical for nonlinear dynamics, many players, or long horizons, where multiple local equilibria may exist. We show through examples that such methods can fail to reach the true global Nash equilibrium even in relatively small games. To address this, we propose two population based evolutionary algorithms for general dynamic games with linear or nonlinear dynamics and arbitrary objective functions: a co evolutionary genetic algorithm and a hybrid genetic algorithm particle swarm optimization scheme. Both approaches search directly over joint strategy spaces without restrictive assumptions and are less prone to getting trapped in local Nash equilibria, providing more reliable approximations to global Nash solutions.

Related papers

• Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games [0.0]
  We present an approach to approximation in multiplayer imperfectinformation games that solves a quadratically-constrained program based on a nonlinear approximation.<n>We also lead to a new approach for computing Nash equilibrium in multiplayer strategic-form games.
  arXiv  Detail & Related papers  (2025-09-30T00:28:21Z)
• Nash Equilibria via Stochastic Eigendecomposition [4.190518009892366]
  We show a Nash equilibrium can be approximated with purely calls to parameter, iterative variants of value decomposition and power. We provide pseudocode and experiments demonstrating solving for all equilibria of a general-sum game using only readily available linear algebra tools.
  arXiv  Detail & Related papers  (2024-11-04T17:32:21Z)
• 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)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• 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)
• 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)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation. We propose a novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap.
  arXiv  Detail & Related papers  (2022-08-10T14:21:54Z)
• Efficiently Computing Nash Equilibria in Adversarial Team Markov Games [19.717850955051837]
  We introduce a class of games in which a team identically players is competing against an adversarial player. This setting allows for a unifying treatment of zero-sum Markov games potential games. Our main contribution is the first algorithm for computing stationary $epsilon$-approximate Nash equilibria in adversarial team Markov games.
  arXiv  Detail & Related papers  (2022-08-03T16:41:01Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
  arXiv  Detail & Related papers  (2021-08-17T07:06:46Z)

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.