Solving Games with Exponential Strategy Spaces

This direction is split into other directions: exponential strategy space. Its last version stays readable and citable here.

Version 1 of 1102 papers110 conceptsfrozen 2026-10-04

In classical game theory, we often represent a game using a "normal form" matrix. Each row is a strategy for Player 1, each column is a strategy for Player 2, and the cells contain the payoffs. This works perfectly for Rock-Paper-Scissors, where there are only three strategies. But as Daphne Koller and Avi Pfeffer noted in Generating and Solving Imperfect Information Games, this representation suffers from exponential growth.

In real-world scenarios—like scheduling air marshals across thousands of flights or protecting a city's power grid—the number of possible "strategies" (schedules or patrol routes) can exceed $10^{23}$. At this scale, you cannot even store the matrix, let alone solve it. The research direction here focuses on bypassing this "curse of dimensionality" by exploiting the underlying structure of the game.

The Bottleneck of Explicit Enumeration

The fundamental problem is that a "strategy" in a complex game is often a combinatorial object. For example, in a network security game, a defender's strategy might be a set of paths for several patrol units. As Joshua Letchford and Vincent Conitzer explain in Solving Security Games on Graphs via Marginal Probabilities, the number of ways to assign resources to these routes grows exponentially with the number of targets.

When you convert a sequential game tree into a simultaneous normal-form game, you create an "exponential explosion" of the strategy space. This makes traditional linear programming or exact solvers like those discussed in Spatial Branch-and-Bound for Computing Multiplayer Nash Equilibrium computationally intractable because they require iterating over or storing every possible action.

Iterative Discovery via Oracles

If we cannot look at all strategies at once, we can look at them one at a time. This is the intuition behind the Double Oracle algorithm and Column Generation.

Instead of solving the full game, we solve a "restricted" version containing only a small subset of strategies. We then use an "oracle"—a specialized sub-procedure—to find the best response to the current equilibrium. If the oracle finds a strategy that beats the current plan, we add it to the set and resolve.

Manish Jain, Milind Tambe, and colleagues demonstrated this in the ASPEN algorithm (Security Games with Arbitrary Schedules: A Branch and Price Approach). By combining branch-and-price with a network flow representation, they could navigate strategy spaces of $10^{23}$ schedules without ever enumerating them. Similarly, Jason Tsai and Thanh Hong Nguyen applied this to social networks in Security Games for Controlling Contagion, using PageRank-based oracles to find influential nodes in massive graphs.

Compact Representations and Marginalization

Another way to defeat the explosion is to change how we define a strategy. Instead of a probability distribution over every possible path (which is huge), we can use marginal probabilities—the probability that a specific resource is at a specific location at a specific time.

In Resource Graph Games: A Compact Representation for Games with Structured Strategy Spaces, Albert Xin Jiang and Hau Chan show that if the utility function is structured (e.g., it only depends on which resources are at which nodes), we can represent the strategy space as a polytope. This allows us to compute equilibria using the dimensions of the graph (nodes and edges) rather than the number of paths.

This "sequence-form" approach is also vital for sequential games. Branislav Bošanský and Jiri Cermak utilized this in Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games to find optimal commitment strategies in multi-stage games without the usual exponential blow-up.

Nash Equilibrium as Stochastic Optimization

When the game is too large even for compact forms, we turn to sampling. If we can't see the whole payoff matrix, can we still find the equilibrium?

Ian Gemp and Luke Marris have pioneered treating Nash Equilibrium finding as a stochastic optimization problem. In Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization, they introduce loss functions that allow for unbiased Monte Carlo estimation.

Instead of calculating the exact gradient of the entire game, you sample a few outcomes and update your strategy using Stochastic Gradient Descent (SGD). This approach, further refined with the Nash Advantage Loss (NAL) in Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games, allows researchers to solve games that are far too large to fit in memory, effectively trading off exactness for extreme scalability.

Papers in this version

Showing 60 of 102 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_solving_games_with_exponential_strategy__038ada0a,
  title = {Solving Games with Exponential Strategy Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solving-games-with-exponential-strategy-spaces/rdr_038ada0a5ca84793932b5ef692940849},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_solving_games_with_exponential_strategy__038ada0a_v1,
  title = {Solving Games with Exponential Strategy Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solving-games-with-exponential-strategy-spaces/rdr_038ada0a5ca84793932b5ef692940849/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}