2025/04/13 by Sam Ganzfried, Ganzfried, Sam · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Economic theories and models #Game Theory and Applications #cs.AI #cs.GT #cs.MA #econ.TH
paper · pdf · doi:10.48550/arxiv.2504.09716
openalex publication_date 2025/04/13 · openalex created_date 2025/10/01 · openalex updated_date 2026/07/28
Dominance is a fundamental concept in game theory. In normal-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 normal 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 two-player perfect-recall games with publicly observable actions, which can be extended to iteratively remove 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 "All In or Fold" No-Limit Texas Hold'em poker.