Solving Continuous Games through Discrete Approximations

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

Version 1 of 180 papers102 conceptsfrozen 2026-10-04

In classical game theory, we often deal with finite sets of actions—think Rock-Paper-Scissors or a simple 2x2 payoff matrix. However, real-world strategic interactions are rarely so constrained. Whether it is a defender allocating a continuous security budget across a city, a driver choosing a precise departure time to avoid traffic, or a bidder in a high-frequency auction, the "moves" available to players often exist in an infinite, continuous space.

Solving these continuous games is notoriously difficult because standard tools like Nash's existence theorem for finite games don't immediately apply to uncountable strategy sets. To bridge this gap, a robust research direction has emerged: discretization. By strategically carving continuous spaces into finite grids or multisets, researchers can transform intractable infinite problems into manageable computational tasks.

The Intuition of Smoothness

The fundamental reason discretization works is the concept of Lipschitz continuity. If a game is "smooth"—meaning a tiny change in a player's strategy results in only a tiny change in their payoff—then we don't need to check every single point in the infinite space. Instead, we can sample a representative "grid" of points.

Paul G. Spirakis and Argyrios Deligkas demonstrate in On Equilibrium Computation in Biased Games with Quadratic Penalties that Lipschitz continuity acts as the "secret sauce" for tractability. By searching a finite set of points rather than the entire continuum, they can approximate Nash equilibria within a specific error margin ($\epsilon$). This turns an infinite search into a finite, searchable grid where the density of the grid determines the precision of the solution.

From Grids to Convergence

A natural question arises: if we solve a simplified, discretized version of a game, does that solution actually mean anything for the original continuous game?

The answer lies in weak convergence. In Convergence of Bayesian Nash Equilibrium in Infinite Bayesian Games under Discretization, researchers prove that as the discretization interval approaches zero (i.e., the grid becomes infinitely fine), the sequence of equilibria found in the discrete games converges to the true equilibrium of the infinite game. This justifies discretization not just as a heuristic, but as a mathematically sound foundation for numerical solvers.

This principle is applied across diverse domains:

Finitely Supported Strategies

One of the most powerful insights in this field is that even in a game with infinite possible moves, an optimal strategy often only requires a few of them. This is the idea of finitely-supported mixed strategies.

In Double Oracle Algorithm for Computing Equilibria in Continuous Games, authors like Lukás Adam and Tomás Kroupa leverage this by iteratively adding discrete points to a subgame. Instead of discretizing the whole space upfront, they find a small, finite set of points that support an approximate Nash equilibrium. This reduces an infinite-dimensional optimization problem to a manageable linear program.

This "multiset" approach is particularly useful for making strategies operationalizable. In security contexts, Sara Marie Mc Carthy and her colleagues argue in The Price of Usability: Designing Operationalizable Strategies for Security Games that human guards cannot implement a continuous probability distribution. By approximating these distributions using a uniform distribution over a small multiset of pure strategies, they create protocols that are both mathematically sound and implementable by people.

Bridging Discrete and Continuous Worlds

Interestingly, the relationship between discrete and continuous is a two-way street. While we often discretize the continuous to solve it, researchers like R. Srikant and S. Rasoul Etesami have shown that the reverse is also valuable.

In Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach, they reformulate discrete combinatorial matching problems as continuous-action games. This allows them to apply continuous optimization and gradient-based learning tools to solve problems that were previously viewed through a purely discrete, algorithmic lens.

Computational Tractability

The ultimate goal of these approximations is to bypass the "curse of dimensionality." Finding equilibria in multi-player games is generally PPAD-complete, but structured discretization can offer a way out.

For instance, in Graphical Models for Game Theory, Michael J. Kearns and Satinder Singh use discretization to enable polynomial-time algorithms for games with local dependencies. Similarly, Krishnendu Chatterjee and Thomas A. Henzinger utilize k-uniform strategies—restricting probabilities to discrete multiples of $1/k$—to approximate the values of concurrent games where the exact solutions might be irrational and otherwise uncomputable (Strategy Improvement for Concurrent Reachability and Safety Games).

By treating the continuous world as a limit of increasingly refined discrete models, this research direction provides the mathematical and algorithmic tools necessary to solve the complex, high-stakes games of the real world.

Papers in this version

Showing 60 of 80 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_continuous_games_through_discret_999074e2,
  title = {Solving Continuous Games through Discrete Approximations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solving-continuous-games-through-discrete-approximations/rdr_999074e20b3e4ad39677a6c49dc1ec47},
  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_continuous_games_through_discret_999074e2_v1,
  title = {Solving Continuous Games through Discrete Approximations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solving-continuous-games-through-discrete-approximations/rdr_999074e20b3e4ad39677a6c49dc1ec47/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}