Computing Evolutionarily Stable Strategies in Imperfect-Information Games

2025/12/11 by Sam Ganzfried, Ganzfried, Sam · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence in Games #Game Theory and Applications #cs.AI #cs.GT #cs.MA #econ.TH #q-bio.PE

paper · pdf · doi:10.48550/arxiv.2512.10279

openalex publication_date 2025/12/11 · openalex created_date 2025/12/13 · openalex updated_date 2026/07/30

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 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.

Cited by

• Evolutionarily Stable Stackelberg Equilibrium

Related

• Computing Evolutionarily Stable Strategies in Multiplayer Games
• Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values
• Computational Complexity of Multi-Player Evolutionarily Stable Strategies
• Optimization-Based Algorithm for Evolutionarily Stable Strategies against Pure Mutations
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity