Iterative Strategy Pruning for Scalable Game Solving

196 concepts117 papers

Game theory provides a powerful mathematical framework for predicting interactions among rational agents. However, when moving from simple textbook examples to real-world scenarios—such as Poker, security routing, or multi-agent coordination—solvers encounter a fundamental bottleneck: the exponential explosion of the strategy space. In a simultaneous-move or sequential game, the number of possible pure strategies grows combinatorially with the number of actions and decision nodes, rendering direct equilibrium computation computationally intractable.

Fortunately, the full game matrix is rarely filled with equally viable choices. In practice, game-theoretic solutions like Nash equilibria are often remarkably sparse; players only select from a tiny fraction of their available actions with non-zero probability. This subset of active actions is known as the equilibrium's support.

The core insight of iterative strategy pruning is that we do not need to solve the entire game at once. Instead, we can systematically identify and eliminate dominated or irrelevant strategies before or during the optimization process. By shrinking the game tree or payoff matrix down to its essential strategic core, solvers can find exact or approximate equilibria in massive games that would otherwise be completely unreachable.

Proving Suboptimality via Linear Programming

How can an algorithm confidently discard a strategy without first solving the entire game? The answer lies in identifying dominated strategies—actions that are guaranteed to yield a worse payoff than an alternative choice, regardless of what the opponents decide to do.

While it is easy to spot when one pure strategy is strictly worse than another pure strategy, an action can also be dominated by a mixed strategy (a probabilistic combination of other actions). Geometrically, if we treat the opponent's strategy as a probability distribution over a simplex, our payoffs for each action form hyperplanes over this space. If one action's hyperplane sits entirely below a convex combination of other actions' hyperplanes, that action is fundamentally irrational for a utility-maximizing agent.

As shown by Abdallah Saffidine et al. in the context of simultaneous-move games, we can formulate this check as a Linear Program (LP). An action is safely pruned if the LP proves that a mixed strategy of alternative options guarantees a strictly better payoff against all possible opponent responses. In multi-agent sequential settings, Eric A. Hansen et al. demonstrated that this exact dynamic programming approach can eliminate more than 99% of potential action sequences in specific coordination scenarios, transforming completely intractable partially observable stochastic games into solvable ones.

The Cascade: Iterated Elimination and Rational Closure

Pruning a single dominated strategy is valuable, but its true power is unlocked when applied recursively. When Player 1 eliminates a suboptimal action, the game matrix shrinks. Because Player 2 is rational, they know Player 1 will never play that eliminated action. This reduction alters the effective payoffs, which can cause some of Player 2's strategies—which might have been useful solely to counter Player 1's discarded move—to become dominated themselves.

This domino effect is known as the Iterated Elimination of Dominated Strategies (IEDS). By repeatedly filtering out actions that fail basic rationality checks, the strategy space contracts monotonically.

However, aggressive pruning carries a major risk: if an algorithm removes strategies too greedily based on local or incomplete information, the remaining subgame might no longer contain the true equilibrium of the original game, leaving the player highly vulnerable to exploitation by omitted strategies. To prevent this, algorithms must target subsets of strategies that are rationally closed.

As established by Tuomas Sandholm et al., we can compute Closed Under Rational Behavior (CURB) sets as a preprocessing step. A CURB set is a restricted strategy subspace that contains all best responses to any probability distribution over itself. By using linear feasibility programs to isolate these stable subspaces, the authors guarantee that the reduced game still contains at least one equilibrium point while safely discarding the surrounding irrelevant strategy space. Similarly, Patrick R. Jordan et al. leverage game "formations"—subsets closed under best responses to correlated play—to shrink massive games into manageable, unexploitable subgames.

Pruning Under Uncertainty: Bandit-Based Support Identification

The mathematical elegance of linear programming assumes we have perfect, explicit access to the game's reward matrix. In many modern machine learning applications, however, the game is a black box: we can only observe noisy, action-specific rewards by sampling interactions.

In these stochastic environments, pruning becomes a statistical challenge. Solvers must balance exploring the action space to estimate payoffs with permanently eliminating strategies that are statistically guaranteed to be suboptimal. Akshay Balsubramani et al. addressed this in dueling bandits by constructing frequentist confidence regions over preference matrices; once an action is proven to fall outside the support of the equilibrium strategy across all matrices in the confidence set, it is permanently removed.

To optimize this process in zero-sum matrix games, Arnab Maiti et al. introduced a multi-stage elimination framework based on median value estimation. Instead of wasting samples calculating precise point estimates for every single entry in a massive matrix, the algorithm determines whether a row or column is generally inferior to a potential equilibrium value. By proving that identifying a constant fraction of suboptimal entries is sufficient to prune half the remaining search space at each stage, the authors show that sample complexity can scale linearly with the dimensions of the matrix rather than multiplicatively.

[Full Action Space] 
       │
       ▼  (Bandit Sampling & Confidence Bounds)
[Identify Suboptimal Entries via Medians]
       │
       ▼  (Permanent Elimination)
[Reduced Support Matrix] 
       │
       ▼  (Exact LP Solver)
[Nash Equilibrium]

This learning-based pruning introduces its own algorithmic hurdles. Standard no-regret learning algorithms often suffer from an "efficiency trap" where they take exponentially long to eliminate iteratively dominated actions because they carry the heavy baggage of historical rewards. To bypass this barrier, Jibang Wu et al. developed algorithms that strategically diminish historical rewards. By forcing the learning agent to gradually "forget" the distant past, the algorithm can adapt to the newly pruned strategy space and achieve iterative dominance elimination in polynomial time.

Exploiting Game Structure: Graphical and Sequential Pruning

When games feature explicit structural topologies—such as networks of interacting players or deep sequential decision trees—pruning can be executed locally rather than globally, yielding massive computational savings.

In large-scale multi-player games where agents only directly affect their immediate neighbors, the game can be modeled as a graph. Luis E. Ortiz et al. introduced a message-passing framework called Nash Propagation (NashProp) for these loopy graphical games. Instead of analyzing global strategy profiles, neighboring nodes continuously pass tables of candidate equilibria back and forth. This local interaction acts as a monotonic contraction: nodes immediately prune strategy pairs that are locally inconsistent with their neighbors, rapidly narrowing down the search space to valid global Nash equilibria without ever unfolding the full joint action space.

[Node A] <---(Eliminate Inconsistent Pairs)---> [Node B]
   │                                               │
   └─────────> [Converged Global Equilibrium] <────┘

For sequential models like Multi-Agent Influence Diagrams (MAIDs), the bottleneck is often the sheer number of decision variables. Avi Pfeffer et al. proved that many structural variables do not actually influence an agent's optimal strategy. By analyzing the graphical representation of the game, their framework identifies decision nodes that lack fundamental strategic reasoning patterns (such as manipulation, signaling, or direct effect). These non-effective components can be completely pruned or replaced with random choices, stripping away unnecessary computational overhead and allowing downstream solvers to focus exclusively on the core strategic decision paths.

Key Foundational Work

A note on strategy elimination in bimatrix games (1988) — contributed 3 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 117 papers
  2. Version 1 · 2026-10-04 · 129 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_dominated_strategy_elimination_a11317a8,
  title = {dominated strategy elimination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dominated-strategy-elimination/rdr_a11317a88cf44718b7dd216070da4d1e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_dominated_strategy_elimination_a11317a8_v2,
  title = {dominated strategy elimination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dominated-strategy-elimination/rdr_a11317a88cf44718b7dd216070da4d1e/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake