IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2504.09716.html
   My bibliography  Save this paper

Dominated Actions in Imperfect-Information Games

Author

Listed:
  • Sam Ganzfried

Abstract

Dominance is a fundamental concept in game theory. In strategic-form games dominated strategies can be identified in polynomial time. As a consequence, iterative removal of dominated strategies can be performed efficiently as a preprocessing step for reducing the size of a game before computing a Nash equilibrium. For imperfect-information games in extensive form, we could convert the game to strategic form and then iteratively remove dominated strategies in the same way; however, this conversion may cause an exponential blowup in game size. In this paper we define and study the concept of dominated actions in imperfect-information games. Our main result is a polynomial-time algorithm for determining whether an action is dominated (strictly or weakly) by any mixed strategy in n-player games, which can be extended to an algorithm for iteratively removing dominated actions. This allows us to efficiently reduce the size of the game tree as a preprocessing step for Nash equilibrium computation. We explore the role of dominated actions empirically in the "All In or Fold" No-Limit Texas Hold'em poker variant.

Suggested Citation

  • Sam Ganzfried, 2025. "Dominated Actions in Imperfect-Information Games," Papers 2504.09716, arXiv.org.
    • Handle: RePEc:arx:papers:2504.09716
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Ehud Kalai & Eitan Zemel, 1988. "On The Order of Eliminating Dominated Strategies," Discussion Papers 789, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    2. Itzhak Gilboa & Ehud Kalai & Eitan Zemel, 1989. "The Complexity of Eliminating Dominated Strategies," Discussion Papers 853, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    3. Itzhak Gilboa & Ehud Kalai & Eitan Zemel, 1993. "The Complexity of Eliminating Dominated Strategies," Mathematics of Operations Research, INFORMS, vol. 18(3), pages 553-565, August.
    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. Marx, Leslie M. & Swinkels, Jeroen M., 2000. "Order Independence for Iterated Weak Dominance," Games and Economic Behavior, Elsevier, vol. 31(2), pages 324-329, May.
    2. Pablo Guillen & Róbert F. Veszteg, 2021. "Strategy-proofness in experimental matching markets," Experimental Economics, Springer;Economic Science Association, vol. 24(2), pages 650-668, June.
    3. Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 193-236, January.
    4. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    5. Costa-Gomes, Miguel & Crawford, Vincent P & Broseta, Bruno, 2001. "Cognition and Behavior in Normal-Form Games: An Experimental Study," Econometrica, Econometric Society, vol. 69(5), pages 1193-1235, September.
    6. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    7. , & ,, 2013. "The order independence of iterated dominance in extensive games," Theoretical Economics, Econometric Society, vol. 8(1), January.
    8. Itzhak Gilboa, 1989. "A Note on the Consistency of Game Theory," Discussion Papers 847, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    9. Xiao Luo & Xuewen Qian & Chen Qu, 2020. "Iterated elimination procedures," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 437-465, September.
    10. Joseph Y. Halpern & Rafael Pass, 2018. "Game theory with translucent players," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(3), pages 949-976, September.
    11. Manili, Julien, 2024. "Order independence for rationalizability," Games and Economic Behavior, Elsevier, vol. 143(C), pages 152-160.
    12. Itzhak Gilboa & Ehud Kalai & Eitan Zemel, 1989. "The Complexity of Eliminating Dominated Strategies," Discussion Papers 853, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    13. Patricija Bajec & Danijela Tuljak-Suban, 2022. "A Strategic Approach for Promoting Sustainable Crowdshipping in Last-Mile Deliveries," Sustainability, MDPI, vol. 14(20), pages 1-17, October.
    14. Mamoru Kaneko & Shuige Liu, 2015. "Elimination of dominated strategies and inessential players," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 25(1), pages 33-54.
    15. Michael Trost, 2012. "An Epistemic Rationale for Order-Independence," Jena Economics Research Papers 2012-010, Friedrich-Schiller-University Jena.
    16. Hillas, John & Samet, Dov, 2020. "Dominance rationality: A unified approach," Games and Economic Behavior, Elsevier, vol. 119(C), pages 189-196.
    17. Chen, Yi-Chun & Long, Ngo Van & Luo, Xiao, 2007. "Iterated strict dominance in general games," Games and Economic Behavior, Elsevier, vol. 61(2), pages 299-315, November.
    18. Dufwenberg, Martin & Stegeman, Mark, 1999. "When Order matters for Iterated Strict Dominance," Research Papers in Economics 1999:2, Stockholm University, Department of Economics.
    19. Stahl, Dale O., 1995. "Lexicographic rationalizability and iterated admissibility," Economics Letters, Elsevier, vol. 47(2), pages 155-159, February.
    20. Balkenborg, Dieter, 2018. "Rationalizability and logical inference," Games and Economic Behavior, Elsevier, vol. 110(C), pages 248-257.

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