🔢 mathematics

On Discrete-Time Approximations to Infinite Horizon Differential Games

This paper establishes that discrete-time and fully discrete approximations of infinite-horizon noncooperative $N$ -player differential games converge to the continuous-time value function, with their discrete Nash equilibria serving as $\epsilon$ -Nash equilibria for the original game as discretization parameters approach zero.

Original authors: Javier de Frutos, Víctor Gatón, Julia Novo

Published 2026-05-12

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Javier de Frutos, Víctor Gatón, Julia Novo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends playing a very long, complex game of chess, but instead of moving pieces on a board, they are making decisions that change the world around them every second. This is what mathematicians call a differential game. In this paper, the authors are trying to figure out how to solve these games when there are many players (N-players) and the game goes on forever (infinite horizon).

Here is a simple breakdown of what they did, using everyday analogies:

The Problem: Too Much Complexity

In the real world, these games involve continuous time (every fraction of a second counts) and continuous space (you can be at any point on a map). Trying to calculate the perfect strategy for everyone at once is like trying to solve a puzzle with infinite pieces. The math equations involved (called Hamilton-Jacobi-Bellman equations) are so messy and high-dimensional that you can't solve them with a pen and paper, except in very simple cases.

The Solution: The "Pixelated" Approximation

The authors propose a clever trick: Stop trying to solve the infinite game directly. Instead, break it down into tiny, manageable chunks.

They use two methods to do this:

Discrete-Time (The "Stop-Action" Method): Imagine taking a movie of the game and pausing it every few seconds. Instead of watching the players move smoothly, you only look at where they are at the exact moment the camera clicks. You calculate the best move for that specific second, then move to the next.
Fully Discrete (The "Pixelated Map" Method): This goes a step further. Not only do you pause the movie, but you also turn the smooth map of the world into a grid of pixels (like a video game). The players can only stand on the intersections of the grid lines.

The Big Discovery: "Good Enough" is Actually Good

The main goal of the paper is to prove that these "pixelated" and "paused" versions of the game aren't just approximations; they are almost perfect.

The Claim: If you make the time steps (the pauses) and the grid size (the pixels) small enough, the strategy the players find in the simplified game is almost the same as the strategy they would find in the real, continuous game.
The "epsilon-Nash" Concept: In game theory, a "Nash Equilibrium" is a state where no one wants to change their strategy because they are already doing the best they can. The authors prove that the strategy found in their simplified game is an "epsilon-Nash equilibrium."
- Analogy: Imagine you are playing a video game. The "perfect" move might require moving your finger 0.0001 millimeters to the left. Your simplified game tells you to move 0.001 millimeters. The difference is tiny (epsilon). The paper proves that this tiny difference is so small that, for all practical purposes, you are playing the optimal strategy.

How They Proved It

The authors didn't just guess; they did the heavy mathematical lifting:

Consistency: They showed that as the "pixels" get smaller and the "pauses" get faster, the simplified game's score gets closer and closer to the real game's score.
Convergence: They proved that if you keep shrinking the time steps and grid size, the error disappears.
Robustness: They showed this works even when the game is complex and non-linear (not just simple straight lines), provided the game doesn't explode into chaos.

The Real-World Test (The Experiments)

To make sure their math wasn't just theory, they tested it on two scenarios:

Pollution Control: Imagine two countries deciding how much pollution to emit. They want to maximize their economy but minimize the damage of pollution. The authors showed their method could calculate the best emission strategies for both countries.
Advertising War (Lanchester Game): Imagine two companies fighting for market share. One company's gain is the other's loss. They spend money on ads to win customers. The authors showed their method could find the best spending strategy for both companies.

In both cases, they ran the simulation with different "pixel sizes" and "time pauses." They found that as they made the simulation more detailed, the results stabilized and matched the expected behavior, proving their method works.

The Bottom Line

This paper provides a mathematical "user manual" for computers to solve complex, multi-player strategic games that go on forever. It proves that by breaking these infinite, smooth problems into tiny, discrete steps (like a video game), we can find strategies that are virtually indistinguishable from the perfect, real-world solutions. This allows computers to help us understand and solve problems in economics, environmental policy, and competition that were previously too difficult to calculate.

Technical Summary: Discrete Approximations to Infinite Horizon Differential Games

Problem Statement
The paper addresses the numerical approximation of Markovian Nash Equilibria (MNE) in infinite-horizon, noncooperative $N$ -player differential games. In such games, $N$ players interact strategically over time, where each player $i$ seeks to maximize an objective functional $W_i$ subject to a state dynamics equation $\dot{x} = g(x, u_i, u_{-i})$ . The authors focus on state-feedback (Markovian) strategies, which are preferred for their subgame perfectness (time consistency) compared to open-loop equilibria.

The core challenge is that MNEs are characterized by a system of $N$ coupled Hamilton-Jacobi-Bellman (HJB) equations. Due to the high nonlinearity and dimensionality of these equations, analytical solutions are generally unavailable except for specific linear-quadratic or linear-state models. Consequently, numerical methods are required. The paper investigates whether discrete-time and fully discrete (time and state) approximations of these games converge to the continuous-time solution and whether the resulting discrete equilibria serve as valid approximations (specifically $\epsilon$ -Nash equilibria) for the original continuous game.

Methodology
The authors employ a semi-Lagrangian discretization approach, combining time discretization of the dynamics with a corresponding discretization of the objective functional.

Discrete-Time Approximation (Semi-discrete):
- The continuous time horizon is discretized with step size $h$ .
- The state dynamics are approximated using a forward Euler scheme: $x_{n+1} = x_n + h g(x_n, u_{i,n}, u_{-i,n})$ .
- The objective functional is approximated using the rectangle rule with a discrete discount factor $\beta_h = 1 - \rho h$ .
- The authors analyze the convergence of the discrete value function to the continuous value function and establish that a Markov Nash Equilibrium of the discrete game constitutes an $\epsilon$ -Nash equilibrium for the continuous game.
Fully Discrete Approximation (Time and State):
- The state space is discretized using a triangulation of a bounded polyhedron $\Omega$ with mesh size $k$ .
- Piecewise affine functions are used to approximate the value functions and strategies on the grid nodes.
- An auxiliary game is defined using interpolation operators ( $I_k$ ) on the state space to handle the discrete state dynamics.
- The analysis relies on defining an auxiliary continuous-time problem with interpolated strategies to bound the error between the fully discrete solution and the continuous solution.

Key Contributions and Results
The paper provides rigorous convergence proofs and error estimates for the proposed discretization schemes:

Consistency of Value Functions: The authors prove that as the time step $h \to 0$ (and subsequently $k \to 0$ for the fully discrete case), the value functions of the discrete games converge to the value function of the continuous differential game.
$\epsilon$ -Nash Equilibrium Property:
- Theorem 3 & 6: It is proven that for any $\epsilon > 0$ , there exists a sufficiently small discretization parameter ( $h$ or $h, k$ ) such that the Markov Nash Equilibrium of the discrete game is an $\epsilon$ -Nash equilibrium for the continuous game. This means no player can gain more than $\epsilon$ by unilaterally deviating from the discrete strategy in the continuous setting.
- Theorem 4 & 7: Under stronger hypotheses (specifically regarding the discount rate $\rho$ relative to the Lipschitz constants of the dynamics and cost functions), the authors derive explicit error bounds. They show that the approximation error is of order $O(h)$ for the discrete-time case and $O(h+k)$ for the fully discrete case.
Numerical Experiments: The theoretical results are validated using two examples:
1. A transboundary pollution game (linear-quadratic structure), where the numerical results confirm first-order convergence for both value functions and strategies.
2. A Lanchester-type differential game (nonlinear, non-quadratic), which also demonstrates convergence of the value function and strategies as discretization parameters decrease.

Significance and Claims
The paper claims to establish a theoretical foundation for using semi-Lagrangian methods to solve complex noncooperative differential games. The primary significance lies in proving that the computationally tractable discrete equilibria are not merely numerical artifacts but are mathematically guaranteed to approximate the true continuous-time equilibria with arbitrary precision.

The authors note that while the hypotheses required for the explicit error bounds (such as the condition $\rho > L$ ) are restrictive, they are often satisfied in practical applications, particularly when the dynamics remain within a bounded, positively invariant domain. The work extends previous results on single-player optimal control to the multi-player game setting, demonstrating that the semi-Lagrangian approach remains robust when strategic interactions are present. The paper concludes that these methods provide a viable path for computing Markovian Nash equilibria in models where analytical solutions are impossible.