IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2512.10279.html

Computing Evolutionarily Stable Strategies in Imperfect-Information Games

Author

Listed:
  • Sam Ganzfried

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.

Suggested Citation

  • Sam Ganzfried, 2025. "Computing Evolutionarily Stable Strategies in Imperfect-Information Games," Papers 2512.10279, arXiv.org, revised Dec 2025.
    • Handle: RePEc:arx:papers:2512.10279
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2512.10279
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
    2. Ingela Alger & Jörgen W. Weibull, 2013. "Homo Moralis—Preference Evolution Under Incomplete Information and Assortative Matching," Econometrica, Econometric Society, vol. 81(6), pages 2269-2302, November.
    3. Ross Cressman, 2003. "Evolutionary Dynamics and Extensive Form Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262033054, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lamantia, Fabio & Pezzino, Mario, 2016. "Evolutionary efficacy of a Pay for Performance scheme with motivated agents," Journal of Economic Behavior & Organization, Elsevier, vol. 125(C), pages 107-119.
    2. Bezin, Emeline & Ponthière, Gregory, 2019. "The tragedy of the commons and socialization: Theory and policy," Journal of Environmental Economics and Management, Elsevier, vol. 98(C).
    3. Ennio Bilancini & Leonardo Boncinelli & Jiabin Wu, 2016. "The Interplay of Cultural Aversion and Assortativity for the Emergence of Cooperation," Center for Economic Research (RECent) 121, University of Modena and Reggio E., Dept. of Economics "Marco Biagi".
    4. Gregory Ponthiere, 2024. "Epictetusian rationality and evolutionary stability," Journal of Evolutionary Economics, Springer, vol. 34(3), pages 647-673, July.
    5. Domenico De Giovanni & Fabio Lamantia, 2017. "Evolutionary dynamics of a duopoly game with strategic delegation and isoelastic demand," Journal of Evolutionary Economics, Springer, vol. 27(5), pages 877-903, November.
    6. Ennio Bilancini & Leonardo Boncinelli & Jiabin Wuz, 2016. "The Interplay of Cultural Aversion and Assortativity for the Emergence of Cooperation," Department of Economics 0084, University of Modena and Reggio E., Faculty of Economics "Marco Biagi".
    7. Domenico De Giovanni & Fabio Lamantia, 2016. "Control delegation, information and beliefs in evolutionary oligopolies," Journal of Evolutionary Economics, Springer, vol. 26(5), pages 1089-1116, December.
    8. Bilancini, Ennio & Boncinelli, Leonardo & Wu, Jiabin, 2018. "The interplay of cultural intolerance and action-assortativity for the emergence of cooperation and homophily," European Economic Review, Elsevier, vol. 102(C), pages 1-18.
    9. Ozgur Aydogmus & Erkan Gürpinar, 2022. "Science, Technology and Institutional Change in Knowledge Production: An Evolutionary Game Theoretic Framework," Dynamic Games and Applications, Springer, vol. 12(4), pages 1163-1188, December.
    10. Szabó, György & Borsos, István & Szombati, Edit, 2019. "Games, graphs and Kirchhoff laws," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 521(C), pages 416-423.
    11. Alger, Ingela, 2021. "On the evolution of male competitiveness," Journal of Economic Behavior & Organization, Elsevier, vol. 190(C), pages 228-254.
    12. Alger, Ingela & Weibull, Jörgen W., 2014. "Evolution leads to Kantian morality," TSE Working Papers 14-504, Toulouse School of Economics (TSE), revised Jun 2015.
    13. Christian Hilbe & Moshe Hoffman & Martin A. Nowak, 2015. "Cooperate without Looking in a Non-Repeated Game," Games, MDPI, vol. 6(4), pages 1-15, September.
    14. Nadine Chlaß & Peter G. Moffatt, 2017. "Giving in Dictator Games - Experimenter Demand Effect or Preference over the Rules of the Game?," Jena Economics Research Papers 2012-044, Friedrich-Schiller-University Jena.
    15. Takuya Sekiguchi, 2023. "Fixation Probabilities of Strategies for Trimatrix Games and Their Applications to Triadic Conflict," Dynamic Games and Applications, Springer, vol. 13(3), pages 1005-1033, September.
    16. Marie Claire Villeval, 2019. "Comportements (non) éthiques et stratégies morales," Revue économique, Presses de Sciences-Po, vol. 70(6), pages 1021-1046.
    17. Zhang, Bin, 2012. "Multi-tier binary solution method for multi-product newsvendor problem with multiple constraints," European Journal of Operational Research, Elsevier, vol. 218(2), pages 426-434.
    18. Sandholm, William H. & Izquierdo, Segismundo S. & Izquierdo, Luis R., 2019. "Best experienced payoff dynamics and cooperation in the Centipede game," Theoretical Economics, Econometric Society, vol. 14(4), November.
    19. Gaudeul, Alexia & Keser, Claudia & Müller, Stephan, 2021. "The evolution of morals under indirect reciprocity," Games and Economic Behavior, Elsevier, vol. 126(C), pages 251-277.
    20. Anirban Ghatak & K. Mallikarjuna Rao & A. Shaiju, 2012. "Evolutionary Stability Against Multiple Mutations," Dynamic Games and Applications, Springer, vol. 2(4), pages 376-384, December.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2512.10279. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.