Dominated Actions in Imperfect-Information Games

This paper introduces a polynomial-time algorithm for identifying and iteratively removing dominated actions in two-player perfect-recall imperfect-information games, enabling efficient game tree reduction as a preprocessing step for Nash equilibrium computation without the exponential blowup associated with normal-form conversion.

The Gist

Imagine you are playing a complex board game against a friend. You have a deck of cards, and every time you make a move, the game tree branches out into thousands of possible futures. To find the perfect strategy (the "Nash Equilibrium"), you need to analyze every single branch. But the game is so huge that your computer would need to run for a million years just to figure out the best move.

This paper is about a clever shortcut: finding and throwing away the "bad moves" before you even start the heavy lifting.

Here is the breakdown of the paper using simple analogies.

1. The Problem: The "Normal Form" Explosion

In game theory, there are two ways to look at a game:

• Normal Form: A giant spreadsheet listing every possible combination of moves.
• Extensive Form: The actual game tree (like a choose-your-own-adventure book).

In simple games (like Rock-Paper-Scissors), we can easily spot "dominated strategies." A dominated strategy is a move that is always worse than another move, no matter what your opponent does.

• Analogy: If you are playing a card game and you have a "3 of Hearts" and a "King of Hearts," and the rules say Kings always beat 3s, you should never play the 3. It's a "dominated" move.

In simple games, we can delete these bad moves quickly. But in complex games with hidden information (like Poker), if you try to convert the game into that giant spreadsheet to find the bad moves, the spreadsheet becomes exponentially huge. It's like trying to read a library of books by printing every single page of every book on a single sheet of paper. It's impossible.

2. The Trap: Why "Obvious" Bad Moves Aren't Enough

The author first tries to define a "bad move" in Poker-like games.

• The Naive Idea: "If Action A leads to a leaf node (end of game) with a lower score than Action B in every single scenario, then A is bad."
• The Problem: This is too strict. In Poker, you might have a move that looks bad in one specific scenario but is actually the best move overall because it forces your opponent to make a mistake later.
• The Analogy: Imagine you are a general. One path leads to a swamp (bad), but the other path leads to a mountain (good). However, the enemy only knows about the swamp. If you take the mountain path, you might win. A simple "look at the map" check might say "Don't go to the mountain, it's far," but it misses the strategic value.

The paper shows that previous definitions were too rigid. They would miss moves that are actually terrible, just because they looked okay in one tiny, unlikely scenario.

3. The Solution: The "Smart Filter" (Polynomial Time)

Sam Ganzfried (the author) proposes a new, smarter definition of a "dominated action."

• The Definition: An action is dominated if there is any other strategy (even a complex mix of moves) that beats it, assuming the game actually reaches this point.
• The Key Insight: He realized that in games where players remember what happened (Perfect Recall) and actions are visible to everyone (Publicly Observable), you can check for these bad moves without exploding the game size.

He uses a mathematical tool called Linear Programming (think of it as a super-smart calculator that solves optimization puzzles).

• The Metaphor: Instead of trying to read the whole library, he built a machine that scans the books and instantly highlights the pages that say "Don't do this."
• The Result: He created an algorithm that runs in polynomial time. In plain English: It's fast. It scales well. You can run it on a laptop in seconds, even for complex games.

4. The Experiment: Poker "All-In or Fold"

To prove this works, the author tested it on a simplified version of Texas Hold'em Poker called "All-In or Fold."

• The Setup: Two players. They can only do two things: Shove (bet all their chips) or Fold (give up).
• The Scale: There are 169 different starting hands (like Ace-King, Pair of 7s, etc.).
• The Process:
  1. The algorithm scans the game.
  2. It finds that for certain hands, "Folding" is always a terrible idea compared to "Shoving," or vice versa.
  3. It deletes those bad options.
  4. It repeats the process (Iterative Removal) because deleting one bad move might make another move look bad now.

The Outcome:

• In a game with 5 "Big Blinds" (a specific stack size), the algorithm reduced the decision points by over 50%.
• Player 1 went from having to decide on 169 hands down to just 25 hands.
• Player 2 went from 169 hands down to 16 hands.

It's like taking a maze with 10,000 dead ends and instantly painting over 5,000 of them, leaving you with a much shorter path to the exit.

5. Why This Matters

Why do we care about deleting bad moves?

1. Speed: If you have a smaller game, you can solve it much faster.
2. Complexity: Some games are so big that they are impossible to solve. But if you can cut out the "stupid" moves first, the remaining game might be small enough to solve.
3. Real World: The paper mentions that this technique helped solve a three-player poker game in 3 seconds that would have taken 24 hours without this cleanup.

Summary

Think of this paper as a game janitor.
Before you try to solve the most difficult puzzle in the world, this algorithm walks in with a broom and sweeps away all the obvious, terrible moves. It doesn't solve the game for you, but it makes the game small enough that a computer (or a human) can actually solve it.

It turns an impossible task into a manageable one by asking: "Is there any way this move could possibly be the best choice? If not, throw it in the trash."

Technical Summary

1. Problem Statement

In game theory, dominance is a fundamental concept where a strategy is considered inferior if another strategy yields a strictly (or weakly) better payoff regardless of the opponent's actions. In normal-form games, identifying and iteratively removing dominated strategies is a well-understood, polynomial-time preprocessing step that reduces game size before computing a Nash equilibrium.

However, in extensive-form games (games with sequential moves and imperfect information), applying standard dominance concepts is problematic:

• Exponential Blowup: Converting an extensive-form game to normal form to apply standard algorithms causes an exponential increase in game size, making it computationally infeasible for large games.
• Local vs. Global Dominance: An action in an extensive-form game may be locally dominated even if the global strategy containing it is not dominated in the normal form. Conversely, standard definitions often fail to identify dominated actions because they do not account for the specific information sets and the requirement that players must reach those sets to make decisions.
• Existing Definitions are Flawed: The paper demonstrates that naive definitions of dominance (e.g., comparing leaf node payoffs directly) are too strong (missing valid dominated actions), while definitions based on global strategy comparison (Candidate Definition 3) are too weak or allow for unrealistic deviations from the path to the information set.

The core problem is to define a concept of dominated actions specific to extensive-form games and develop a polynomial-time algorithm to identify and iteratively remove them without converting the game to normal form.

2. Methodology

A. Refined Definitions of Dominance

The author proposes new definitions for strictly and weakly dominated actions that address the limitations of previous attempts.

• Constraint: The definitions apply to two-player perfect-recall games with publicly observable actions.
• Key Insight: The definitions restrict the set of opponent strategies ($\Sigma_{I_i}^{-i}$) to only those that do not prevent reaching the information set $I_i$. This prevents the "deviation" problem where an opponent's strategy avoids the information set entirely, rendering the comparison meaningless.
• Strict Dominance (Definition 1): An action $a_i$ at information set $I_i$ is strictly dominated if there exists a behavioral strategy $\sigma_{-a_i}^i$ (which never plays $a_i$) that yields a strictly higher expected utility than any strategy $\sigma_{a_i}^i$ (which plays $a_i$ with probability 1), for all opponent strategies that reach $I_i$.
• Weak Dominance (Definition 2): Similar to strict dominance, but the inequality is $\geq$ with at least one strict inequality.

B. Polynomial-Time Algorithm (Sequence Form)

The paper presents an algorithm to test for dominance using the Sequence Form linear programming (LP) representation, which avoids the exponential blowup of normal form conversion.

1. Formulation: The problem is modeled as a sequence-form optimization problem.
   • Let $x_1$ and $x_2$ be realization vectors for Player 1 and Player 2.
   • Let $y$ be the opponent's realization vector.
   • The algorithm constructs specific LPs to compare the value of playing action $c$ versus not playing it.
2. Decomposition:
   • Problem 1 & 2: The author proves that the complex min-max problem comparing strategies can be decomposed into two simpler subproblems (Problems 3 and 4) due to the "publicly observable actions" assumption.
   • Problem 3 ($v_5$): Maximizes the opponent's payoff against the player's strategy excluding action $c$. This is solved via a dual LP formulation.
   • Problem 4 ($v_6$): Maximizes the player's payoff including action $c$. This is treated as a single-agent optimization problem (since the player controls all nodes in this specific sub-game context).
3. Decision Logic:
   • Strict Dominance: If $v_5 > v_6$, action $c$ is strictly dominated.
   • Weak Dominance: If $v_5 = v_6$, a secondary check (Problems 7 and 8) is performed. If $v_7 > v_8$, the action is weakly dominated.
   • Not Dominated: If $v_5 < v_6$ or the secondary check fails.
4. Complexity: Since the number of actions is linear in the size of the game tree, and each check involves solving a constant number of Linear Programs (which are polynomial in time), the iterative removal of dominated actions runs in polynomial time.

3. Key Contributions

1. Formal Definitions: Introduced rigorous definitions for strictly and weakly dominated actions in extensive-form games that correctly handle imperfect information and perfect recall.
2. Polynomial-Time Algorithm: Proved that determining dominance in two-player perfect-recall games with publicly observable actions is solvable in polynomial time, a significant theoretical advancement over the exponential complexity of normal-form conversion.
3. Iterative Removal: Demonstrated that the iterative removal of these dominated actions preserves the set of Nash equilibria (for strict dominance) and can be performed efficiently as a preprocessing step.
4. Behavioral Strategy Dominance: The algorithm identifies actions dominated by any behavioral strategy (mixed strategies over actions at an information set), not just pure actions.

4. Experimental Results

The author tested the algorithm on "All In or Fold" No-Limit Texas Hold'em, a simplified poker variant where players can only choose to "Shove" (go all-in) or "Fold."

• Setup: Two-player games with stack sizes of 8, 5, 4, and 3 Big Blinds (BB).
• Results (8 BB Stack):
  • Initial game: 169 hands per player.
  • After one round of removal: Player 1 reduced to 84 hands, Player 2 to 70 hands.
  • Reduction: Over 50% reduction in decision points.
• Results (5 BB Stack):
  • Required 5 rounds of iterative removal.
  • Final reduced game: Player 1 with 25 hands, Player 2 with 16 hands.
• Results (3-4 BB Stacks): The game was solved completely (reduced to a single optimal action for every hand) after 2–4 rounds.
• Observation: The algorithm successfully removed a massive portion of the game tree, significantly simplifying the problem space.

5. Significance and Impact

• Efficient Preprocessing: The ability to reduce game size polynomially makes computing Nash equilibria in large imperfect-information games (like poker) significantly faster and more feasible.
• Scalability: While the paper focuses on two-player games, the author notes that the computational benefits would be even more profound for $n > 2$ player games, where equilibrium computation is generally PPAD-hard.
• Real-World Application: The paper cites subsequent work where this technique enabled the solution of a three-player imperfect-information game in under 3 seconds, a task that previously took 24 hours.
• Theoretical Foundation: It bridges the gap between normal-form dominance theory and extensive-form game solving, providing a necessary tool for modern game-theoretic AI (e.g., in poker bots and other strategic AI systems).

Conclusion

The paper establishes that dominated actions in imperfect-information games can be defined rigorously and identified efficiently. By leveraging the sequence form and linear programming, the author provides a polynomial-time method to prune game trees, offering a powerful preprocessing tool for solving complex strategic interactions.