The paper is concerned with zero-sum differential games and the asymptotic properties of their value functions. The games with a common dynamics, a running cost, and capabilities of players are considered. Each payoff represents an average of the running cost with respect to the given discount functions (densities); these games differ in densities only. We prove a Tauberian-type Theorem, that is, the fact that the existence of a uniform limit of the value functions for uniform density or for exponential density implies that the value functions uniformly converge to the same limit for arbitrary piecewise continuous density as the time scale parameter tends to zero.
∫ ∞
one considers the asymptotic behavior of the corresponding value functions as the scale parameter λ tends to zero. Usually, the densities of the uniform ϱ(t) = 1[0,1](t) (Cezaro mean) and exponential ϱ(t) = e−t (Abel mean) distributions are applied.
The existence of such a limit of value functions in view of some density means that the value function’s response to a change in the scale parameter λ is very weak when this parameter is sufficiently small. In particular, in the stochastic statement, this value (the asymptotic value) is customarily considered the game value when the planning horizon is infinite [Bewley et al., 1976]. In these statements, one could often obtain, in addition, an asymptotically optimal strategy such that a payoff is close to the optimal one (uniform value)—for sufficiently small values of the scale parameter [Mertens et al., 1981]; however, in this paper, we only consider the value function asymptotics. The existence of uniform limits of value functions for payoffs (1) when averaged with respect to the uniform and/or exponential densities was proved for a broad class of stochastic games [Ziliotto, 2016b], for optimal control problems [Gaitsgori, 1985, Lions et al., 1986, Gru¨ne, 1998, Artstein et al., 2000, Li et al., 2016, Gaitsgori et al., 2013], and for certain classes of differential games [Buckdahn et al., 2011, Cannarsa et al., 2015] in the so-called nonexpansive-like case.
It turns out that, for stochastic games with a finite number of states and actions [Mertens et al., 1981], for discrete-time control problems [Lehrer et al., 1992], for general control problems [Oliu-Barton et al., 2013], for differential games [Khlopin, 2016], and a broad class of stochastic games [Ziliotto, 2016a, Ziliotto, 2016b], there holds the following Tauberian theorem: the uniform convergence of value functions under payoffs (1) with one of these densities (uniform or exponential) guarantees that the value functions in view of the other payoff also converge uniformly—to the same limit. The general approach, which deduces these Tauberian theorems from the Dynamic Programming Principle, is considered in [Khlopin, in print].
Such Tauberian theorems guarantee that if there is a uniform asymptotics for one of these densities (uniform or exponential) then, in addition to the value function’s insensitivity to the choice of the discount parameter λ for payoff (1), this asymptotics is also insensitive to the choice between these two densities. Often, it is also possible to prove insensitivity to the choice of the density ϱ from quite a broad class.
Thus, we can find a sufficient asymptotic condition on the densities ϱλ, λ > 0, under which the uniform convergence of value functions as λ → 0 for the payoffs with uniform or/and exponential densities (for Cesaro and/or Abel means) implies the uniform convergence to the same limit (as λ → 0) of the value functions for the payoffs ∫ ∞
ϱλ(t)g(z(t)) dt.
0
For example, to this end, for discrete-time control processes, in paper [Monderer et al., 1993], the following sufficient asymptotic condition on a family of ϱλ, λ > 0 was proposed: all densities ϱλ are nonincreasing and (2) (3) (4) (5) ∫ T lim λ→0 0 ϱλ(t) dt = 0 ∀T > 0.
was refined in [Ziliotto, 2016c]; here, V0∞[µ] is the total variation of a real-valued function µ on R+ =△ [0, ∞).
For zero-sum differential games with the Isaacs condition, from the uniform convergence of the value functions
for Cesaro means, it follows
The main aim of this paper to prove that in zero-sum differential games with the Isaacs condition the existence of a uniform limit of the value functions for uniform density or for exponential density implies the uniform convergence (to the same limit) for the values in view of payoffs (1) for every piecewise continuous density ϱ.
To this end, first, we will improve condition (5) (see (12)), and, then, apply this improved sufficient asymptotic condition for payoffs (2). The cornerstone of this proof is the sufficiency of (3)&(5), proved in [Khlopin, 2015] for zero-sum differential games with Isaacs condition.
x˙ = f (x, p, q), x(0) ∈ Rm, t ≥ 0, p(t) ∈ P, q(t) ∈ Q; (6) here, P and Q are non-empty compact subsets of finite-dimensional Euclidean spaces.
Assume that the functions f : Rm × P × Q → Rm and g : Rm × P × Q → [0, 1] are continuous, and let these functions be Lipschitz continuous in the state variable; namely, there exists a constant L > 0 such that, for all x, y ∈ Rm, p ∈ P, and q ∈ Q,
f (x, p, q) − f (y, p, q) + g(x, p, q) − g(y, p, q) ≤ L x − y .
Denote by P and Q the sets of all Borel measurable functions R+ ∋ t 7→ p(t) ∈ P and R+ ∋ t 7→ q(t) ∈ Q, respectively. So, for each pair (p, q) ∈ P × Q, for every initial condition x(0) = x∗ ∈ Rm, system (6) generates the unique solution x(·) = y(·; x∗, p, q) defined for the whole R+.
We will essentially refer to the results proved in [Khlopin, 2015]. As a consequence, we need to admit all assumptions on differential games from [Khlopin, 2015]. To make it happen, we also impose the Isaacs condition (“the saddle point condition in a small game”) [Krasovskii et al., 1988]
[ ] [ mp∈aPx mq∈iQn ⟨s, f (x, p, q)⟩ + g(x, p, q) = min max ⟨s, f (x, p, q)⟩ + g(x, p, q) q∈Q p∈P ] ∀x, s ∈ Rm.
It is easy to see that, for each nonnegative function ϱ : R+ → R+, it implies that, for all t ∈ R+, x, s ∈ Rm, mp∈aPx mq∈iQn [⟨s, f (x, p, q)⟩ + ϱ(t)g(x, p, q)] = min max [⟨s, f (x, p, q)⟩ + ϱ(t)g(x, p, q)].
q∈Q p∈P
Let D be the set of all probability density functions having their support in R+. For a density ϱ ∈ D and a number r ∈ (0, 1), let the quantile q[ϱ](r) be the minimum number such that ∫ q[ϱ](r) 0
ϱ(t) dt = r.
For a given density ϱ ∈ D and an initial position x∗ ∈ Rm, let the goal of the first player be to maximize the payoff function c[ϱ](x∗, p, q) =△ ∫ ∞ ϱ(t)g(y(t; x∗, p, q), p(t), q(t)) dt,
0 and let the task of the second one be to minimize it.
There are many ways to define a game and the sets of strategies for each player; for a very well made review
encompassing a large number of formalizations, refer to [Subbotin, 1995, Subsect.14,15]. We will consider the
nonanticipating strategies
De nition 1 A map α : Q → P is called a nonanticipating strategy of the first player if, for all t > 0 and q, q′ ∈ Q, from q|[0,t] = q′|[0,t] it follows that α[q]|[0,t] = α[q′]|[0,t].
A map β : P → Q is called a nonanticipating strategy of the second player if, for all t > 0 and p, p′ ∈ P, from p|[0,t] = p′|[0,t] it follows that β[p]|[0,t] = β[p′]|[0,t].
We denote by A and B the sets of all nonanticipating strategies of the first player and of the second player, respectively.
For each density ϱ ∈ D, define the corresponding value function by the following rule: also, define
V[ϱ](x∗) =△ sup inf α∈A q∈Q 0
∫ ∞ V+[ϱ](x∗) =△ inf sup β∈B p∈P 0 ∫ ∞ ϱ(t)g(y(t; x∗, α[q], q), α[q](t), q(t))dt
∀x∗ ∈ Rm; ϱ(t)g(y(t; x∗, p, β[p]), p(t), β[p](t))dt
∀x∗ ∈ Rm.
(7)
(8)
(9)
For each density ϱ ∈ D with bounded supp ϱ, condition (7) guarantees
V+[ϱ] ≡ V[ϱ].
In the general case, for each density ϱ ∈ D, define the sequence of densities ϱn =△ n+n1 ϱ · 1[0,q[ϱ]( nn+1 )] ∈ D. Since supp ϱn is compact, passing to the limit as n → ∞ in (8) and (10), we see that the payoffs c[ϱn] converge to c[ϱ] and the value functions V[ϱn] = V+[ϱn] converge to V[ϱ] = V+[ϱ] as n → ∞. Now, we have proved (10) for all ϱ ∈ D. 3
λ For each density ϱ ∈ D and an arbitrary λ > 0, it is also possible to introduce the density ϱscale by the rule λ ϱscale(t) = λϱ(λt) ∀t ≥ 0.
Set ϖλ(t) = λ · 1[0,1/λ], πλ(t) = λ · e−λt, ∀λ > 0, t ≥ 0.
For an interval [a, b) ⊂ R and a function y : [a, b) → R ∪ {∞}, denote by Vab[y] the total variation of the function y in [a, b).
Theorem 1 Let a non-empty subset Ω ⊂ Rm be strongly invariant with respect to system (6).
For a given map U∗ : Ω → [0, 1], the following conditions are equivalent: 1) for each piecewise continuous on (0, ∞) density µ ∈ D, there holds 2) the value functions V[ϖλ] converge to U∗ uniformly in Ω as λ → 0, i.e., 3) the value functions V[πλ] converge to U∗ uniformly in Ω as λ → 0, i.e., lim sup V[µsλcale](x∗) − U∗(x∗) = 0; λ→0 x ∈Ω lim sup V[ϖλ](x∗) − U∗(x∗) = 0; λ→0 x ∈Ω lim sup V[πλ](x∗) − U∗(x∗) = 0; λ→0 x ∈Ω 4) for every family of densities µλ ∈ D, λ > 0, it follows from (3) and that the value functions V[µλ] converge to U∗ uniformly in Ω as λ → 0, i.e., lim sup V0q[µ ](r)[µ] · q[µλ](r) < +∞ λ→0
∀r ∈ (0, 1) lim sup V[µλ](x∗) − U∗(x∗) = 0. λ→0 x ∈Ω (10) (11) (12) (13) 4
The implications 2) ⇒ 3), 3) ⇒ 2) were proved in [Khlopin, 2016].
λ From (ϖ1)scale = ϖλ for all positive λ, it follows that 1) ⇒ 2).
It remains to verify 2) ⇒ 4) ⇒ 1). To do this, we need the following proposition proved in [Khlopin, 2015]: Proposition 1 Assume that the value functions V[ϖλ], λ > 0 converge to a function U∗ uniformly in Ω as λ → 0, i.e., (11) holds.
Let a family of µλ ∈ D, λ > 0, satisfy (3) and (5).
Then, for all positive δ < 1, there exists a positive λδ such that, for all positive λ < λδ,
V[µλ](x∗) > U∗(x∗) − 8δ ln
∀x∗ ∈ Ω. 1 δ 4.1
The proof is by reductio ad absurdum. Assume the converse. Then, for a positive ε < 1/20, there exists a family of densities µˆλ ∈ D, λ > 0 such that (3), (12), and hold. Choose positive δ < 1 and M such that lim sup sup |V[µˆλ](x∗) − U∗(x∗)| ≥ 3ε
λ→0 x ∈Ω 8δ ln Now, for all positive λ, define the mapping µλ : R+ → R+ by the following rule:
ε µλ(t) = µˆλ(t) + ∀t ∈ [0, q[µˆλ](1 − ε)]
q[µˆλ](1 − ε) and µλ(t) = 0 otherwise. Then, ∫ ∞ 0 ∫ q[µˆ ](1−ε)
0 µλ(t)dt = µλ(t)dt = ∫ q[µˆ ](1−ε) 0 µˆλ(t)dt + ε = 1, that is, µλ ∈ D.
Now, since µˆλ enjoys (3), we see that q[µˆλ](1 − ε) tends to ∞ as λ → 0, and lim sup λ→0 ∫ T 0
∫ T µλ(t) dt ≤ λli→m0 0 µˆλ(t) dt + λli→m0 0 ∫ min{T,q[µˆ ](1−ε)}
ε q[µˆλ](1 − ε) dt = 0 holds for all positive T ; thus, the family of µλ enjoys (3).
Next, note that, for all x, y > 0, there holds | ln x − ln y| = ln max{x, y} max{x, y} min{x, y} ≤ min{x, y} − 1 =
|x − y| ; min{x, y} moreover, by (15), q[µλ](r) < q[µˆλ](1 − ε) for all λ > 0 and r ∈ (0, 1). Then, we obtain
V q[µˆ ](1−ε)[µλ] V0q[µ ](r)[ln µλ] ≤ V0q[µˆ ](1−ε)[ln µλ] ≤ inft∈[0,q[µˆ ](1−ε)) µλ(t) ≤ 0
V0q[µˆ ](1−ε)[µˆλ] · q[µˆλ](1 − ε) ε <
M ε for all r ∈ (0, 1), λ > 0. Thus, the family of µλ enjoys (5).
Since the family of µλ enjoys all assumptions of Proposition 1, we can find a positive λδ such that 1 V[µλ](x∗) > U∗(x∗) − 8δ ln δ ∀x∗ ∈ Ω, λ ∈ (0, λδ).
Consider a new differential game. Define the sets P− =△ Q, Q− =△ P and the maps f −(x, p−, q−) =△ f (x, q−, p−), g−(x, p−, q−) =△ 1 − g(x, q−, p−) for all x ∈ Rm, p− ∈ P−, q− ∈ Q−. By (7) with s = −s−, we have max min [⟨s−, f −(x, p−, q−)⟩ + ϱ(t)g−(x, p−, q−)] = min max [⟨s−, f −(x, p−, q−)⟩ + ϱ(t)g−(x, p−, q−)] p ∈P q ∈Q q ∈Q p ∈P for all s−, x ∈ Rm, t ≥ 0, ϱ ∈ D. Thus, the Isaacs condition also holds.
In addition, by P− = Q and Q− = P, we obtain y−(x∗, p−, q−) =△ y(x∗, q−, p−) for all x∗ ∈ Rm, p− ∈ P−, q− ∈ Q−. Then, Ω is a strongly invariant set for this dynamics.
Moreover, thanks to Q− = P and A− = B, for each density ϱ ∈ D, the map (14) (15) (16) Ω ∈ x∗ 7→ 1 − V[ϱ](x∗) = 1 − V+[ϱ](x∗)
∫ ∞ = sup inf
β∈B p∈P 0 = =
sup inf α ∈A q ∈Q
sup inf α ∈A q ∈Q ∫ ∞
0 ∫ ∞
0 ϱ(t) 1 − g(y(t; x∗, p, β[p]), p(t), β[p](t)))dt ( ϱ(t) 1 − g(y−(t; x∗, α−[q−], q−), q−(t), α−[q−](t)))dt
( ϱ(t)g−(y−(t; x∗, α−[q−], q−), α−[q−](t), q−(t)))dt is the value function (9) of the new game. In particular, (11) holds for this game with asymptotics U∗− ≡ 1 − U∗.
Applying Proposition 1 for this game, we can choose a positive λδ− such that holds for all positive λ < λ−. Together with (16), it implies
δ
However, 1 1 − V[µλ](x∗) > 1 − U∗(x∗) − 8δ ln δ lim sup sup V[µλ](x∗) − U∗(x∗) ≤ 8δ ln λ→0 x ∈Ω
∀x∗ ∈ Ω therefore, by 0 ≤ g ≤ 1, for all x∗ ∈ Ω, α ∈ A, q ∈ Q, λ > 0, we have (17) ∫ ∞
0 ∫ ∞ inf q∈Q 0 |µλ(t) − µˆλ(t)|g(y(t; x∗, α[q](t), q(t)), α[q](t), q(t))dt ≤ 2ε, µλ(t)g(y(t; x∗, α[q](t), q(t)), α[q](t), q(t))dt − − qi∈nQf 0 ∫ ∞ µˆλ(t)g(y(t; x∗, α[q](t), q(t)), α[q](t), q(t))dt ≤ 2ε
V[µλ](x∗) − V[µˆλ](x∗) ≤ 2ε.
We obtain a contradiction with (17). This contradiction proves the implication 2) ⇒ 4). 4.2
The Proof of 4) ⇒ 1) Consider a piecewise continuous in (0, ∞) density ϱ. Fix a number ε > 0; now, there exists a sufficiently large natural n > 3 such that n5 < ε. For all n ∈ N, n > 3, set rn =△ q[ϱ](1/n),
sn =△ q[ϱ](1 − 1/n).
Since the piecewise continuous function ϱ is Riemann integrable on [rn, sn], there exists a staircase function µn : R+ → R, supp µn ⊂ [rn, sn] such that ∫rsnn µn(t) dt = ∫ sn ϱ(t) dt = n−n2 , ∫rsnn |µn(t) − ϱ(t)| dt < 1/n hold. In rn particular, its total variation in [0, ∞) is finite. Since ∫0∞ µn(t)dt = n−n2 , put
△ n µ¯n = n − 2 µn ∈ D,
M =△ snV0∞[µ¯n] = nn−sn2 V0∞[µn] ∈ R. ∫ ∞
0
V0∞[(µ¯n)scale] · q[(µ¯n)scale](1 − ε) λ λ
λ λ ϱscale(t) − (µ¯n)scale(t) dt = = λV0∞[µ¯n] ∫ ∞ 0 q[µ¯n](1 − ε)
λ ϱ(t) − µ¯n(t) dt < = V0∞[µ¯n]q[µ¯n](1 − ε) ≤ snV0∞[µ¯n] = M, (18) 3 n + ∫ sn ( rn
n ) 5 n − 2 − 1 ϱ(t) dt = n < ε. sup V[ϱsλcale](x∗) − V[(µ¯n)scale](x∗) ≤ ε
λ x ∈Ω ∀λ > 0.
(19) Consider some positive T . For all positive λ < rn/T , we have µ¯n|[0,λT ] ≡ 0 and ∫ T 0
λ (µ¯n)scale(t) dt = λ ∫ T 0
µ¯n(λt) dt = 0.
λ lim sup |V[(µ¯n)scale](x∗) − U∗(x∗)| = 0. λ→0 x ∈Ω lim sup sup |V[ϱsλcale](x∗) − U∗(x∗)| ≤ ε.
λ→0 x ∈Ω Thus, (3) holds for densities (µ¯n)sλcale, λ > 0.
Thanks to (18), the densities (µ¯n)sλcale, λ > 0 also satisfy (12). Applying condition 4) for this family, we give
Since the choice of a positive number ε was arbitrary, the implication 4) ⇒ 1) is proved. 5
Based on the results from [Khlopin, 2015], for differential games with the Isaacs condition, we managed to prove that their value functions’ insensitivity to the choice of the scale parameter for the exponential or uniform distribution family implies the same result with respect to all densities of a relatively general form. Apparently, it can be proved for all dynamic games by the game value map method (similar [Khlopin, in print]), however, this should be investigated further.
In addition, we propose a new condition (3)&(12), which is sufficient for (13). For control systems on a compact invariant set under the non-expansive dynamics assumptions, a more weak (than (3)&(5) or (4)) sufficient asymptotic condition was proposed in paper [Li et al., 2016]. Their tightness under the non-expansive dynamics assumption for control problems and for differential games remains to be tested. Whether asymptotic condition (4) is sufficient in the deterministic framework is likewise unknown.
Acknowledgements This work was supported by the Russian Science Foundation (project no. 17-11-01093).