Dominated Actions in Imperfect-Information Games
This work addresses a computational bottleneck in game theory for researchers and practitioners analyzing complex games like poker, though it is incremental as it builds on existing dominance concepts.
The paper tackles the problem of identifying dominated actions in imperfect-information games, which can cause exponential blowup when using traditional methods, and presents a polynomial-time algorithm for this task, enabling efficient game tree reduction as a preprocessing step for Nash equilibrium computation.
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.