Standard game theory excels at solving finite matrices—think Rock-Paper-Scissors or classic matrix games. However, real-world strategic interactions are rarely so neatly bounded. Whether bidding a real-valued dollar amount in an auction, allocating fractional budgets across security checkpoints, or navigating continuous physical coordinates, agents routinely operate within infinite strategy spaces.
In these continuous domains, finding a Nash equilibrium becomes an infinite-dimensional optimization problem. We cannot simply enumerate strategies or compute standard best-responses because the action space is uncountably infinite. To make these problems computationally tractable, a powerful research direction has emerged: mapping continuous strategy and payoff spaces into discrete structures.
Why Discretization Works: Smoothness and Finite Support
At first glance, forcing an uncountably infinite space onto a finite grid seems like it would discard vital strategic nuances. Why does this approximation preserve the underlying game-theoretic structure? The answer lies in two core mathematical properties: smoothness and finite support.
First, many continuous games exhibit Lipschitz continuity—the property that a small change in an agent's action leads to a predictably small change in their payoff. As demonstrated by Fearnley et al., this continuity allows algorithms to approximate points within a continuous convex hull using a small number of discrete vertices, bounding the approximation error and enabling polynomial-time searches for equilibria.
Second, even when players have an infinite number of pure strategies to choose from, the optimal mixed strategies often only require mixing over a finite number of points. Adam et al. leverage this insight to solve continuous games by identifying a finite set of points that support an approximate Nash equilibrium. This reduces an infinite-dimensional optimization problem to a manageable sequence of finite linear programs. Similarly, Stein et al. prove that a broad class of continuous interactions—known as separable or low-rank games—always possess Nash equilibria where players use only a finite number of strategies. This rank-based bound ensures that computational complexity scales with the game's structural rank rather than the size of its action space.
Granular Probability Grids and $k$-Uniform Strategies
The most direct way to discretize a continuous strategy space is to restrict mixed strategy probabilities to a grid of rational numbers—specifically, multiples of a small fraction $1/k$. These are known as $k$-uniform strategies.
By forcing probabilities onto a discrete grid, the uncountably infinite simplex of mixed strategies collapses into a finite combinatorial search space. This mechanism provides provable approximation guarantees across diverse game structures:
- Polymatrix and Anonymous Games: Fearnley et al. use $k$-uniform distributions to transform continuous equilibrium searches in polymatrix games into discrete combinatorial problems. For anonymous games, Daskalakis et al. demonstrate that the strategy space can be restricted to a grid of fixed small fractions while keeping the approximation error entirely independent of the number of players.
- Refining Exact Solutions: In games with binary rewards, Auger et al. show that Nash equilibria are composed of rational numbers with bounded denominators. This allows approximate strategies generated by bandit algorithms to be snapped directly to a discrete grid, refining them into exact solutions.
- Hierarchical and Concurrent Games: In robust Stackelberg settings, Gan et al. combine $k$-uniform strategy searches with binary searches over convex regions to find near-optimal leader strategies in quasi-polynomial time. For concurrent safety and reachability games, Chatterjee et al. show that increasing the granularity of these $k$-uniform fractions allows algorithms to approximate optimal strategies to any arbitrary precision.
Beyond pure computational convenience, $k$-uniform strategies mirror real-world operational constraints. In security games, Mc Carthy demonstrates that approximating optimal mixed strategies through a uniform distribution over a small multiset of pure strategies makes complex randomized defense plans "operationalizable" for human personnel without sacrificing theoretical performance guarantees.
Dynamic Particles and Grid-Based State Spaces
Instead of fixing a rigid grid ahead of time, some modern techniques dynamically optimize the discrete representation. A prominent example is the particle-based approach introduced by Wang et al.. They represent continuous mixed strategies as a finite collection of "particles," where each particle is defined by a spatial position and a scalar weight. By simultaneously updating both the locations and weights of these particles, their algorithm achieves exponential local convergence toward the exact mixed Nash equilibrium of continuous zero-sum games.
Continuous Simplex Discretized Grid / Particles
(Infinite) (Finite)
/\ /\
/ \ / \
/ \ ───► • •
/ \ / \ / \
/________\ •───•───•
For complex dynamic or multi-agent environments, discretization is often applied directly to the underlying state or type distributions rather than just the actions:
- Bayesian Markov Games: Chandrasekaran et al. discretize continuous mixed-strategy spaces into a multi-dimensional grid, allowing them to frame equilibrium discovery as a constraint satisfaction problem in environments with finite belief hierarchies.
- Mean-Field Type Games: In games where continuous populations cooperate internally and compete externally, Shao et al. discretize the space of all possible population distributions. This mapping enables tabular reinforcement learning methods, such as Nash Q-learning, to find stable equilibria with guaranteed convergence.
Simultaneous Payoff and Utility Discretization
Discretizing the action space alone is sometimes insufficient, particularly when player interactions are highly coupled or non-convex. To resolve this, several frameworks discretize the payoff space alongside the strategy space.
Ortiz et al. employ this dual-discretization technique in tree-structured graphical games. By creating a discrete grid for expected payoffs, their algorithm bounds the search space and decouples a player's optimal response from the infinite combinations of their neighbors' strategies, yielding a fully polynomial-time approximation scheme (FPTAS). This builds on earlier foundational work by Ortiz et al., which demonstrated that continuous action spaces could be reduced to finite sets to enable discrete message-passing algorithms like NashProp.
This dual mapping also unlocks solutions in mechanism design and auction theory. Chen et al. show that discretizing both available actions and underlying probability distributions transforms the continuous search for a Bayesian Nash Equilibrium in first-price auctions into a discrete optimization problem solvable via matching algorithms.
In the domain of "game design"—where a defender actively manipulates an attacker's payoffs under a budget—Tang discretizes the continuous space of possible payoff modifications into a finite set of choices. This transformation converts a non-convex optimization problem into a solvable Mixed Integer Linear Program that provides provable approximation guarantees.
Bridging the Continuous-Discrete Divide
Ultimately, discretization acts as a universal bridge that allows discrete algorithms—like dynamic programming, linear programming, and backward induction—to operate on continuous domains.
For instance, Daskalakis et al. discretize mixed strategies and expected utilities in Action-Graph Games to make them amenable to dynamic programming. In strategic fair division, Branzei et al. approximate continuous intervals with a fine grid to translate discrete equilibrium properties into approximate continuous equilibria. Even in continuous resource allocation processes, Aziz et al. discretize the consumption phase into a finite, perfect-information extensive-form game, allowing backward induction to prove the existence of subgame perfect equilibria.
In relaxed settings where exact optimization is strategically problematic, Rajasekaran et al. show that equilibria derived from discrete satisficing thresholds serve as valid approximations for $\epsilon$-Nash equilibria in continuous reward models. Even in simulation-heavy environments where analytical models fail entirely, Empirical Game-Theoretic Analysis (EGTA), introduced by Michael P. Wellman, relies on selecting a discrete set of candidate strategies to construct a solvable, finite payoff matrix from complex simulators.
The Risk of Choice Paralysis
While discretization makes infinite games solvable, researchers must remain cautious of its long-term dynamical consequences. As Anderson demonstrates in evolutionary game theory, finite-dimensional grid approximations are highly reliable for short-term numerical simulations, but they can fail in the long run. This occurs due to "choice paralysis"—a phenomenon where adding more discrete options to approximate a continuous space alters the asymptotic convergence behavior, preventing a population from reaching the true infinite-dimensional equilibrium. Discretization is therefore not a silver bullet, but a finely tuned instrument balancing computational tractability against the topological realities of continuous spaces.
Key Foundational Work
Nash Propagation for Loopy Graphical Games (2002) — contributed 1 concept elements to this direction.
Methods for Empirical Game-Theoretic Analysis (2006) — contributed 1 concept elements to this direction.