Computing Evolutionarily Stable Strategies in Imperfect-Information Games

• URL: http://arxiv.org/abs/2512.10279v2
• Date: Fri, 12 Dec 2025 04:13:37 GMT
• Title: Computing Evolutionarily Stable Strategies in Imperfect-Information Games
• Authors: Sam Ganzfried,
• Abstract summary: We present an algorithm for computing evolutionarily stable strategies (ESSs) in symmetric perfect-recall extensive-form games of imperfect information.<n>Our main algorithm is for two-player games, and we describe how it can be extended to multiplayer games.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an algorithm for computing evolutionarily stable strategies (ESSs) in symmetric perfect-recall extensive-form games of imperfect information. Our main algorithm is for two-player games, and we describe how it can be extended to multiplayer games. The algorithm is sound and computes all ESSs in nondegenerate games and a subset of them in degenerate games which contain an infinite continuum of symmetric Nash equilibria. The algorithm is anytime and can be stopped early to find one or more ESSs. We experiment on an imperfect-information cancer signaling game as well as random games to demonstrate scalability.

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)
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
  arXiv  Detail & Related papers  (2024-06-23T00:27:28Z)
• Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games [21.168085154982712]
  equilibria in multiplayer games are neither unique nor non-exploitable. This paper takes an initial step towards addressing these challenges by focusing on the natural objective of equal share. We design a series of efficient algorithms, inspired by no-regret learning, that provably attain approximate equal share across various settings.
  arXiv  Detail & Related papers  (2024-06-06T15:59:17Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This work shows that certain regularized equilibria do not possess the aforementioned non-correspondence problem. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games.
  arXiv  Detail & Related papers  (2023-01-22T16:54:06Z)
• 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)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  We consider the problem of simultaneous learning in games with many players in the finite-horizon setting. While the typical target solution for a game is a Nash equilibrium, this is intractable with many players. We turn to a different target: algorithms which generate an equilibrium when they are used by all players.
  arXiv  Detail & Related papers  (2022-10-25T19:02:03Z)
• 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)
• Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games with Persistent Imperfect Information [1.7132914341329848]
  We present an algorithm for approximating Nash equilibrium in multiplayer general-suming games with persistent imperfect information. Using a new procedure, we are able to demonstrate that our algorithm computes a strategy that closely approximates Nash equilibrium in this game.
  arXiv  Detail & Related papers  (2020-10-26T19:27:26Z)
• Algorithm for Computing Approximate Nash Equilibrium in Continuous Games with Application to Continuous Blotto [1.7132914341329848]
  We present a new algorithm for approximating Nash equilibrium strategies in continuous games. In addition to two-player zero-sum games, our algorithm also applies to multiplayer games and games with imperfect information.
  arXiv  Detail & Related papers  (2020-06-12T19:53:18Z)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  We show how adapting the reward can give strong convergence guarantees in monotone games. We also show how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium.
  arXiv  Detail & Related papers  (2020-02-19T21:36:58Z)

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.