# Weak KAM Solutions of a Discrete-Time Hamilton-Jacobi Equation in a Minimax Framework

Authors: Porfirio Toledo
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

The purpose of this paper is to study the existence of solutions of
a Hamilton-Jacobi equation in a minimax discrete-time case and to show
different characterizations for a real number called the critical value, which
plays a central role in this work. We study the behavior of solutions of
this problem using tools of game theory to obtain a “fixed point” of the
Lax operator associated, considering some facts of weak KAM theory to
interpret these solutions as discrete viscosity solutions. These solutions
represent the optimal payoff of a zero-sum game of two players, with
increasingly long time payoffs. The developed techniques allow us to study
the behavior of an infinite time game without using discount factors or
average actions.


---

## Body

## 1. Introduction

The Hamilton-Jacobi equation is a very important tool for the study of Lagrangian systems and control theory. In the case of convex Lagrangians, Fathi, Mather, and Mañe have perfected several techniques to understand the solutions of this equation ([1–7]). These techniques can be translated to a discrete case where, instead of a Lagrangian, there is a function V(x,y) of two variables in the configuration space.The aim of this paper is to study a discrete-time system that emulates a convex and concave Lagrangian. We need to study the behavior of solutions of a discrete-time version of a Hamilton-Jacobi equation in the context of game theory. A real number, called the critical value, plays a central role in this work; this number is the asymptotic average action of optimal trajectories. We study the existence and characterization of solutions of a Hamilton-Jacobi equation for this kind of game. A relevant aspect is that these techniques allow us to study infinite-time games without using discount factors or average actions.Consider the compact metric spacesM and N, which are the state spaces for players JM and JN, respectively. For (x,y)∈M×N, a continuous function g:M×N→ℝ, and a Lipschitz function V:M×N×M×N→ℝ, we define the static game payoff by
(1)Pg(x1,y1):=g(x1,y1)-V(x,y,x1,y1).
The function P is the amount that player JM obtains from JN and vice versa; so player JM wants to maximize the payoff P, while player JN wants to minimize it. The lower game value is defined by
(2)ℒ1g(x,y):=supx1∈Minfy1∈NPg(x1,y1).
It is observed in [8] that it is possible to express the lower game value as follows:
(3)ℒ1g(x,y)=infθ(z)supz∈MPg(z,θ(z)),
where the function θ:M→N is called a strategy for player JN. These functions are very important in this work and will be defined in general for a zero-sum game with finite horizon.Forn∈ℤ+, consider the finite horizon problem, where players JM and JN alternate their moves beginning at initial state (x0,y0) and setting with them the state trajectories determined by finite sequences x¯(n)⊂M and y¯(n)⊂N, denoted by x¯(n):={x0,x1,…,xn} and y¯(n):={y0,y1,…,yn}, respectively. The state of the system depends on the initial condition (x0,y0) and the players decisions to get from (xi,yi) to (xi+1,yi+1), where i=0,1,…,n-1. For (x,y)∈M×N, we will denote by
(4)SM(x,n):={x¯(n)={xi}i=0n:x0=x},SN(y,n):={y¯(n)={yi}i=0n:y0=y},
the sets of finite sequences in M and N, with initial states x∈M and y∈N. We define the action by
(5)An(x¯(n),y¯(n)):=∑i=0n-1‍V(xi,yi,xi+1,yi+1),
and the game payoff by
(6)Pg(x¯(n),y¯(n)):=g(xn,yn)-An(x¯(n),y¯(n)).Then, the lower game value with finite horizonn and initial state (x,y)∈M×N is
(7)ℒng(x,y):=supxn∈Minfyn∈Nsupxn-1∈Minfyn-1∈N⋯supx1∈Minfy1∈NPg(x¯(n),y¯(n)).
However, ℒn can be defined directly using progressive strategies (see [8–10]). The idea is to use a tool that allows player JN to select one point yi knowing the current and past opponent choices, without knowing the future choices. To this end, we define a progressive strategy Θ(n) for player JN as a function Θ(n):SM(x,n)→SN(y,n) which satisfies the following property: for each m∈ℤ such that 0≤m≤n and x¯(n),z¯(n)∈SM(x,n), we have
(8)xi=zi,0≤i≤m⟹Θ(n)[x¯(n)]i=Θ(n)[z¯(n)]i,0≤i≤m,
where Θ(n)[x¯(n)]i is the ith element of sequence Θ(n)[x¯(n)]∈SN(y,n). The set of progressive strategies for player JN is denoted by
(9)ℰN(x,y,n)≔{Θ(n):SM(x,n)≔⟶SN(y,n)progressivestrategy}.
Finally, the lower game value can be expressed as
(10)ℒng(x,y)=infΘ(n)supx¯(n)Pg(x¯(n),Θ(n)[x¯(n)]),
where x¯(n)∈SM(x,n) and Θ(n)∈ℰN(x,y,n). This function is called Lax operator and will be essential for understanding the asymptotic behavior of game payoffs. The Proposition 6 shows that
(11)ℒng(x,y)=ℒ1∘⋯∘ℒ1︸ntimesg(x,y).In the next section of this paper, the objective is to prove the existence of a kind of “fixed point” of the Lax operator. We will adapt the methods developed in the work of Fathi ([3]) about weak KAM theory, now in a minimax context of game theory. It will be necessary to prove that the Lax operator ℒn, defined as in (10), satisfies some important properties: the semigroup property that is also call Dynamic Programming Principle (see [8–10]), a regularity property, monotony, and weak contraction.Theorem 1.
IfM and N are compact metric spaces and V:M×N×M×N→ℝ is a Lipschitz function, then there exist a Lipschitz function u∈C(M×N,ℝ) and a unique constant c∈ℝ, such that
(12)ℒnu=u+nc.The functions in the previous result are called fixed points of the Lax operator with critical valuec. These fixed points are solutions of the following discrete-time Hamilton-Jacobi equation associated to V:
(13)supx1∈Minfy1∈N{u(x1,y1)-u(x,y)-V(x,y,x1,y1)}=c.
See [11] for a minimal discrete-time case.In the third section, we will consider an infinite horizon problem, which will help us to find a different characterization of critical valuec. To this end, we define the lower Peierls barrier hk- as follows, given a real number k and an initial state (x,y)∈M×N:
(14)hk-(x,y):=liminfn→∞{supΘ(n)infx¯(n)An(x¯(n),Θ(n)[x¯(n)])+nk},
where x¯(n)∈SM(x,n) and Θ(n)∈ℰN(x,y,n), see [3, 12, 13].It is possible to prove that there exists a numberc-∈ℝ, such that
(15)c-=inf{k∈ℝ:hk-=+∞}=sup{k∈ℝ:hk-=-∞},
where the value of hk- does not depend on (x,y)∈M×N. The critical value c has a new interpretation characterized by the following result.Theorem 2.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, and (x,y)∈M×N, then hc--(x,y)∈ℝ and c-=c, where c is the critical value.Analogously, we can define the upper Peierls barrierhk+ by
(16)hk+(x,y):=limsupn→∞{supΘ(n)infx¯(n)An(x¯(n),Θ(n)[x¯(n)])+nk},
for which we can obtain similar results.Considering thathc-(x,y)∈ℝ and hc+(x,y)∈ℝ, for every (x,y)∈M×N, we prove that
(17)supn∈ℤ+|nc+supΘ(n)infx¯(n)An(x¯(n),Θ(n)[x¯(n)])|<+∞,
and therefore,
(18)-c=limn→∞supΘ(n)infx¯(n)1nAn(x¯(n),Θ(n)[x¯(n)]).In addition, using a solution of the Hamilton-Jacobi equation, we can find an optimal strategy, from which optimal sequences are obtained for both players for all times. In particular, we prove the following result.Theorem 3.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, and (x,y)∈M×N, then there are sequences {xi*}i=0∞⊂M and {yi*}i=0∞⊂N such that
(19)supn∈ℤ+|nc+An(x¯*(n),y¯*(n))|<+∞,
where x¯*(n):={xi*}i=0n∈SM(x,n) and y¯*(n):={yi*}i=0n∈SN(y,n), where c is the critical value.From this, it follows immediately that(20)-c=limn→∞1nAn(x¯*(n),y¯*(n)).The sequences obtained in the previous result satisfy the Bellman principle of optimality, because from each state(xi*,yi*) in the optimal trajectory, the complement remains optimal. The optimality of the remaining decisions from (xi*,yi*) depends on this last state, which is the result of the previous decisions.In last section, we will show another characterization for the solutions of the Hamilton-Jacobi equation.Fork∈ℝ, a function g∈C(M×N,ℝ) is called k-supersolution if
(21)ℒ1g≥g+k.
Analogously, a function g∈C(M×N,ℝ) is called k-subsolution if
(22)ℒ1g≤g+k.
The function g is a k-solution if g is k-supersolution and k-subsolution (see [4]).Clearly,g is a k-solution if and only if g is a fixed point of the Lax operator with critical value k. According to Theorem 1, if there exists a unique constant for fixed points of the Lax operator, then there is only one kind of k-solutions, in fact for k=c. The c-solutions are called critical solutions. From this, we get another characterization of c, which appears in the following result.Theorem 4.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, and u∈C(M×N,ℝ) is a fixed point of the Lax operator ℒn with critical value c∈ℝ, then
(23)c=supSU(u)=infSL(u),
where
(24)SU(u):={k∈ℝ:uisk-supersolution},SL(u):={k∈ℝ:uisk-subsolution}.Finally, we will show that-hc- is a critical solution and therefore a solution of the Hamilton-Jacobi equation.


## 2. Lax Operator

LetM and N be compact metric spaces, V:M×N×M×N→ℝ a Lipschitz function, and n∈ℤ+. Consider a zero-sum game of two players, JM and JN, with finite horizon n, where M and N represent the state spaces and sequences x¯(n)={x0,x1,…,xn}⊂M and y¯(n)={y0,y1,…,yn}⊂N determine the state trajectories, respectively, for players JM and JN. The function An(x¯(n),y¯(n)), defined by
(25)An(x¯(n),y¯(n)):=∑i=0n-1‍V(xi,yi,xi+1,yi+1),
is the game action. For g∈C(M×N,ℝ) and (x,y)∈M×N, the game payoff Pg:SM(x,n)×SN(y,n)→ℝ is defined by
(26)Pg(x¯(n),y¯(n)):=g(xn,yn)-An(x¯(n),y¯(n)).
If ℰN(x,y,n) is the set of progressive strategies for player JN, the Lax operator is the lower game value, defined by
(27)ℒng(x,y):=infΘ(n)supx¯(n)Pg(x¯(n),Θ(n)[x¯(n)]),
with x¯(n)∈SM(x,n) and Θ(n)∈ℰN(x,y,n). We prove the following regularity property for the Lax operator.Lemma 5.
The Lax operatorℒng is K-Lipschitz, for any n∈ℤ+ and g∈C(M×N,ℝ), where K is the Lipschitz constant of V.Proof.
We will consider(x,y),(z,w)∈M×N, g∈C(M×N,ℝ), and ɛ>0. There exists Θ1(n)∈ℰN(z,w,n) such that
(28)ℒng(z,w)>supz¯(n)Pg(z¯(n),Θ1(n)[z¯(n)])-ɛ,
where z¯(n)∈SM(z,n).
For a finite sequencex¯(n)={x,x1,…,xn}∈SM(x,n), we define Θ2(n)∈ℰN(x,y,n) as
(29)Θ2(n)[x¯(n)]i={y,i=0Θ1(n)[{z,x1,…,xn}]i,1≤i≤n.
For this strategy, we have(30)ℒng(x,y)≤supx¯(n)Pg(x¯(n),Θ2(n)[x¯(n)]),
where x¯(n)∈SM(x,n). It follows that there is x¯*(n)={x,x1*,…,xn*} such that
(31)ℒng(x,y)<Pg(x¯*(n),Θ2(n)[x¯*(n)])+ɛ.
We definez¯*(n)∈SM(z,n) as z¯*(n)={z,x1*,…,xn*}. Combining (28) with (31), we obtain
(32)ℒng(x,y)-ℒng(z,w)<Pg(x¯*(n),Θ2(n)[x¯*(n)])-Pg(z¯*(n),Θ1(n)[z¯*(n)])+2ɛ.
Since xi*=zi* and Θ2(n)[x¯*(n)]i=Θ1(n)[z¯*(n)]i, for 1≤i≤n, we have
(33)ℒng(x,y)-ℒng(z,w)<V(z,w,x1*,Θ1(n)[z¯*(n)]1)-V(x,y,x1*,Θ1(n)[z¯*(n)]1)+2ɛ≤Kd[(x,y),(z,w)]+2ɛ,
where K is the Lipschitz constant of V and d is a distance in M×N. Similarly, we obtain the opposite inequality. Thus,
(34)|ℒng(x,y)-ℒng(z,w)|≤Kd[(x,y),(z,w)].From above result, we prove the semigroup property for the Lax operator, also called the Principle of Dynamic Programming.Proposition 6 (Semigroup Property).
Form,n∈ℤ+,
(35)ℒm+ng(x,y)=ℒm∘ℒng(x,y)=infΘ(m)supx¯(m){ℒng(xm,Θ(m)[x¯(m)]m)=infΘ(m)sup-Am(x¯(m),Θ(m)[x¯(m)])},
where Θ(m)∈ℰN(x,y,m) and x¯(m)∈SM(x,m).Proof.
We will considerɛ>0 and g∈C(M×N,ℝ). To prove the relation ℒm+ng=ℒm∘ℒng, we will see that, for every (x,y)∈M×N, the inequalities ℒm+ng(x,y)≤ℒm∘ℒng(x,y) and ℒm+ng(x,y)≥ℒm∘ℒng(x,y) take place simultaneously.
(I) Let us first prove thatℒm+ng≤ℒm∘ℒng. To do this, take Θ1(m)∈ℰN(x,y,m) such that
(36)ℒm(ℒng)(x,y)>supx¯(m){ℒng(xm,Θ1(m)[x¯(m)]m)>supx¯(m)-Am(x¯(m),Θ1(m)[x¯(m)])}-ɛ,
where x¯(m)∈SM(x,m).
On the other hand, for each(z,w)∈M×N,
(37)ℒng(z,w)=infΘ(n)supz¯(n){g(zn,Θ(n)[z¯(n)]n)-An(z¯(n),Θ(n)[z¯(n)])},
where Θ(n)∈ℰN(z,w,n) and z¯(n)∈SM(z,n). Hence, there is Θ(z,w)2(n)∈ℰN(z,w,n) such that
(38)ℒng(z,w)>supz¯(n){g(zn,Θ(z,w)2(n)[z¯(n)]n)-An(z¯(n),Θ(z,w)2(n)[z¯(n)])}-ɛ.
We will define aΘ*(m+n)∈ℰN(x,y,m+n) using the previous strategy Θ1(m) and the family Θ(z,w)2(n). Given a sequence in SM(x,m+n), the associated sequence in SN(y,m+n) is defined as follows: the fist m terms are given by the Θ1(m) strategy and the second part is given by Θ(z*,w*)2(n), for a specific (z*,w*). More precisely, for x¯(m+n)∈SM(x,m+n),
(39)Θ*(m+n)[x¯(m+n)]i={Θ1(m)[x¯1(m)]i,0≤i≤mΘ(z*,w*)2(n)[x¯2(n)]i-m,m+1≤i≤m+n,
where x¯1(m)={x,x1,…,xm}, (z*,w*)=(xm,Θ1(m)[x¯1(m)]m), x¯2(n)={z*,xm+1,…,xm+n}, and Θ(z*,w*)2(n)∈ℰN(z*,w*,n). Taking any x¯(m+n)∈SM(x,m+n) and combining (36) with (38), we obtain
(40)ℒm(ℒng)(x,y)>ℒng(xm,Θ1(m)[x¯1(m)]m)-Am(x¯1(m),Θ1(m)[x¯1(m)])-ɛ>g(xm+n,Θ(z*,w*)2(n)[x¯2(n)]n)-An(x¯2(n),Θ(z*,w*)2(n)[x¯2(n)])-Am(x¯1(m),Θ1(m)[x¯1(m)])-2ɛ=g(xm+n,Θ*(m+n)[x¯(m+n)]m+n)-Am+n(x¯(m+n),Θ*(m+n)[x¯(m+n)])-2ɛ.
Therefore,
(41)supx¯(m+n){g(xm+n,Θ*(m+n)[x¯(m+n)]m+n)supx¯(m+n)-Am+n(x¯(m+n),Θ*(m+n)[x¯(m+n)])}≤ℒm(ℒng)(x,y)+2ɛ,
with x¯(m+n)∈SM(x,m+n). This implies that
(42)ℒm+ng(x,y)=infΘ(m+n)supx¯(m+n){g(xm+n,Θ(m+n)[x¯(m+n)]m+n)-Am+n(x¯(m+n),Θ(m+n)[x¯(m+n)])}≤ℒm(ℒng)(x,y)+2ɛ,
and consequently ℒm+ng≤ℒm∘ℒng.
(II) It remains to prove thatℒm+ng≥ℒm∘ℒng. To this end, we will consider Θ*(m+n)∈ℰN(x,y,m+n) such that
(43)ℒm+ng(x,y)>supx¯(m+n){g(xm+n,Θ*(m+n)[x¯(m+n)]m+n)>supx¯(m+n)-Am+n(x¯(m+n),Θ*(m+n)[x¯(m+n)])}-ɛ,
where x¯(m+n)∈SM(x,m+n).
We will defineΘ1(m)∈ℰN(x,y,m) as the m-time restriction of Θ*(m+n). Given a sequence z¯(m)∈SM(x,m), the associated sequence in SN(y,m) is defined as follows: the m terms are given by the fist m terms of Θ*(m+n) strategy applied to some extension of z¯(m) in SM(x,m+n), adding any sequence w¯(n)∈SM(zm,n). Since Θ*(m+n) is a strategy, it follows that the function Θ1(m) is well defined and it is a strategy. More precisely, for z¯(m)∈SM(x,m), taking any w¯(n)={zm,w1,…,wn}∈SM(zm,n), we define Θ1(m)∈ℰN(x,y,m) as
(44)Θ1(m)[z¯(m)]i=Θ*(m+n)[x¯(m+n)]i,
for i=0,1,…,m, where x¯(m+n)={x,z1,…,zm,w1,…,wn}. So
(45)ℒm(ℒng)(x,y)≤supz¯(m){ℒng(zm,Θ1(m)[z¯(m)]m)-Am(z¯(m),Θ1(m)[z¯(m)])},
where z¯(m)∈SM(x,m). Consequently, there is z¯1(m)∈SM(x,m) such that
(46)ℒm(ℒng)(x,y)<ℒng(zm1,Θ1(m)[z¯1(m)]m)-Am(z¯1(m),Θ1(m)[z¯1(m)])+ɛ.
Once that zm1∈M is fixed so will be Θ1(m)[z¯1(m)]m∈N. We now define Θ2(n)∈ℰN(zm1,Θ1(m)[z¯1(m)]m,n), for w¯(n)∈SM(zm1,n), as
(47)Θ2(n)[w¯(n)]i=Θ*(m+n)[x¯(m+n)]i+m,
for i=0,1,…,n, where x¯(m+n)={x,z11,…,zm1,w1,…,wn}. We have
(48)ℒng(zm1,Θ1(m)[z¯1(m)]m)≤supw¯(n){g(wn,Θ2(n)[w¯(n)]n)≤supw¯(n)-An(w¯(n),Θ2(n)[w¯(n)])},
where w¯(n)∈SM(zm1,n). Therefore, there is z¯2(n)∈SM(zm1,n) such that
(49)ℒng(zm1,Θ1(m)[z¯1(m)]m)<g(zn2,Θ2(n)[z¯2(n)]n)-An(z¯2(n),Θ2(n)[z¯2(n)])+ɛ.
Define x¯*(m+n)∈SM(x,m+n) as
(50)x¯*(m+n)={x,z11,…,zm1,z12,…,zn2}.
Combining (43) and (46) with (49) we obtain:
(51)ℒm(ℒng)(x,y)<ℒng(zm1,Θ1(m)[z¯1(m)]m)-Am(z¯1(m),Θ1(m)[z¯1(m)])+ɛ<g(zn2,Θ2(n)[z¯2(n)]n)-An(z¯2(n),Θ2(n)[z¯2(n)])-Am(z¯1(m),Θ1(m)[z¯1(m)])+2ɛ=g(xm+n*,Θ*(m+n)[x¯*(m+n)]m+n)-Am+n(x¯*(m+n),Θ*(m+n)[x¯*(m+n)])+2ɛ<ℒm+ng(x,y)+3ɛ,
for this reason ℒm∘ℒn≤ℒm+n.Lemma 7.
Ifg,f∈C(M×N,ℝ), then(1)
(monotony) ifg≤f, then ℒng≤ℒnf;(2)
ifk∈ℝ, then ℒn(k+g)=k+ℒng;(3)
(weak contraction)∥ℒng-ℒnf∥∞≤∥g-f∥∞.Proof.
The first two properties are a direct consequence of the definition. For last the claim, choose(x,y)∈M×N, then
(52)f(x,y)+∥g-f∥∞≤g(x,y)≤f(x,y)+∥g-f∥∞.
The previous items imply that
(53)ℒnf(x,y)+∥g-f∥∞≤ℒng(x,y)≤ℒnf(x,y)+∥g-f∥∞.
So |(ℒng-ℒnf)(x,y)|≤∥g-f∥∞, for every (x,y)∈M×N. As a result,
(54)∥ℒng-ℒnf∥∞≤∥g-f∥∞.Theorem1 is analogue to Weak KAM Theorem. We use the same argument of Fathi (see [3]) to prove the existence of fixed points of this discrete-time case of the Lax operator.According to this result, we say thatu is a fixed point of the Lax operator with critical value c.Proof.
(I) To prove the existence of a fixed point, we will use the same argument used by Fathi ([3]) for the continuous-time case.
LetE be the quotient of the set of continuous functions C(M×N,ℝ) modulo constants, E=C(M×N,ℝ)/ℝ·1. The norm ∥·∥:E→ℝ is defined as
(55)∥[u]∥=infa∈ℝ∥u+a∥∞,
for [u]∈E. Then, (E,∥·∥) is a Banach space. We define the operator ℒ^n:E→E as
(56)ℒ^n[u]=[ℒnu],
which satisfies the weak contraction property. Thus, [u]↦λℒ^n[u], with λ∈(0,1), is a contraction; so there are fixed points [u]λ∈E of λℒ^n. As ℒn is equi-Lipschitz, since Arzela-Ascoli theorem, it follows that {[u]λ} has a uniformly convergent subsequence when λ→1. Then, ℒ^n has a fixed point [u]*∈E, which in terms of ℒn means that there is a constant cn∈ℝ such that
(57)ℒnu*=u*+cn,
for each positive integer n. From the semigroup property, there is c∈ℝ such that
(58)ℒnu*=u*+nc,
for all positive integers n.
Functionu* is a Lipschitz function, because ℒnu* is also a Lipschitz function. In fact, according to Lemma 5, u* is K-Lipschitz, where K is the Lipschitz constant of V.
(II) It remains to prove that the numberc is unique. Let ɛ be positive. Suppose there are ui∈C(M×N,ℝ) and ci∈ℝ, i=1,2, such that ℒnui=ui+nci, with c1>c2. Choose Θ*(n)∈ℰN(x,y,n) such that
(59)ℒnu2(x,y)>supx¯(n){u2(xn,Θ*(n)[x¯(n)]n)>sup-An(x¯(n),Θ*(n)[x¯(n)])}-ɛ.
For this strategy, we also have that
(60)ℒnu1(x,y)≤supx¯(n){u1(xn,Θ*(n)[x¯(n)]n)≤supx¯(n)-An(x¯(n),Θ*(n)[x¯(n)])}.
So there is x¯*(n)∈SM(x,n), such that
(61)ℒnu1(x,y)<u1(xn*,Θ*(n)[x¯*(n)]n)-An(x¯*(n),Θ*(n)[x¯*(n)])+ɛ.
Therefore, using the hypothesis, we obtain
(62)u1(x,y)+nc1<u1(xn*,Θ*(n)[x¯*(n)]n)-An(x¯*(n),Θ*(n)[x¯*(n)])+ɛ,u2(x,y)+nc2>u2(xn*,Θ*(n)[x¯*(n)]n)-An(x¯*(n)Θ*(n)[x¯*(n)])-ɛ.
Considering the subtraction of the previous inequalities, we obtain following relations:
(63)infM×N(u1-u2)+n(c1-c2)≤u1(x,y)+nc1-u2(x,y)-nc2<u1(xn*,Θ*(m+n)[x¯*(n)]n)-u2(xn*,Θ*(m+n)[x¯*(n)]n)+2ɛ≤supM×N(u1-u2)+2ɛ,
then
(64)n(c1-c2)<supM×N(u1-u2)-infM×N(u1-u2)+2ɛ.
On the other hand, because c1>c2, we have n(c1-c2)→∞ when n→∞, which is a contradiction.Considering the one-step case (see [8]), we can rewrite the Lax operator as
(65)ℒ1g(x,y)=supx1∈Minfy1∈N{g(x1,y1)-V(x,y,x1,y1)}.
If u∈C(M×N,ℝ) is a fixed point with critical value c, then u is a solution for the following discrete-time analog of the Hamilton-Jacobi equation:
(66)supx1∈Minfy1∈N{u(x1,y1)-u(x,y)-V(x,y,x1,y1)}=c.Conversely, ifu is a solution of the previous Hamilton-Jacobi equation, then u is a fixed point of the Lax operator ℒ1 with critical value c. According to semigroup property and relation 2 in Lemma 7, it follows that u is a fixed point of ℒn with critical value c, for all n∈ℤ+.


## 3. Peierls Barrier

Let us now study an infinite horizon problem for playersJM and JN. Let M and N be compact metric spaces, and let V:M×N×M×N→ℝ be a Lipschitz function. For n∈ℤ+, let us consider the function h(n) defined as
(67)h(n)(x,y):=supΘ(n)infx¯(n)An(x¯(n),Θ(n)[x¯(n)]),
where x¯(n)∈SM(x,n) and Θ(n)∈ℰN(x,y,n).Fork∈ℝ, the lower Peierls barrier hk-:M×N→ℝ is
(68)hk-(x,y):=liminfn→∞{h(n)(x,y)+kn}.Proposition 8.
For everyk∈ℝ, one has the following: (1)
ifhk-(x,y)=-∞ for some (x,y)∈M×N, then hk-(z,w)=-∞, for all (z,w)∈M×N;(2)
ifhk-(x,y)=+∞ for some (x,y)∈M×N, then hk-(z,w)=+∞, for all (z,w)∈M×N.Proof.
LetB be positive and consider C>supV-infV+B.(1)
Let us take(z,w)∈M×N and suppose that hk-(x,y)=-∞. Hence, there is nj↑∞ such that
(69)limj→∞{h(nj)(x,y)+knj}=-∞.Therefore, there isJ∈ℤ+ such that if j≥J, then
(70)h(nj)(x,y)+knj<-C.LetΘ(nj)∈ℰN(z,w,nj) be a strategy. We define Θ0(nj)∈ℰN(x,y,nj) as follows: for x¯(nj)={x,x1,…,xnj}∈SM(x,nj),
(71)Θ0(nj)[x¯(nj)]i={y,i=0,Θ(nj)[{z,x1,…,xnj}]i,1≤i≤nj.Therefore,infx¯(nj)Anj(x¯(nj),Θ0(nj)[x¯(nj)])+knj<-C. Hence, there is x¯0(nj)={x,x10,…,xnj0} such that
(72)Anj(x¯0(nj),Θ0(nj)[x¯0(nj)])+knj<-C.If we definez¯0(nj)={z,x10,…,xnj0}∈SM(z,nj), then
(73)Anj(z¯0(nj),Θ(nj)[z¯0(nj)])+knj=V(z,w,x10,Θ(nj)[z¯0(nj)]1)-V(x,y,x10,Θ(nj)[z¯0(nj)]1)+Anj(x¯0(nj),Θ0(nj)[x¯0(nj)])+knj<supV-infV-C<-B,in which it follows thatinfz¯(nj)Anj(z¯(nj),Θ(nj)[z¯(nj)])+knj<-B, for every Θ(nj)∈ℰN(z,w,nj), where j≥J. Then,
(74)limj→∞{h(nj)(z,w)+knj}=-∞;sohk-(z,w)=-∞.(2)
Let us take(z,w)∈M×N and suppose that hk-(x,y)=∞. There is N∈ℤ+ such that if n≥N, then
(75)h(n)(x,y)+kn>C.Therefore, there isΘ0(n)∈ℰN(x,y,n) such that
(76)infx¯(n)An(x¯(n),Θ0(n)[x¯(n)])+kn>C.Takingz¯(n)={z,z1,…,zn}∈SM(z,n), define Θ1(n)∈ℰN(z,w,n) as
(77)Θ1(n)[z¯(n)]i={w,i=0,Θ0(n)[{x,z1,…,zn}]i,1≤i≤n.So, consideringx¯(n)={x,z1,…,zn}∈SM(x,n),
(78)An(z¯(n),Θ1(n)[z¯(n)])+kn=V(z,w,z1,Θ1(n)[z¯(n)]1)-V(x,y,z1,Θ0(n)[x¯(n)]1)+An(x¯(n),Θ0(n)[x¯(n)])+kn>infV-supV+C>B.Since the previous relation is valid for everyz¯(n)∈SM(z,n), it follows that
(79)infx¯(n)An(z¯(n),Θ1(n)[z¯(n)])+kn>B.Hence,(80)hk-(z,w)=limn→∞{h(n)(z,w)+kn}=∞.In order to see thathk-(x,y) has a radical change on its values, for a particular value of k, we prove the following statement.Lemma 9.
There existsk>0 large enough, such that(1)
h-k-(x,y)=-∞.(2)
hk-(x,y)=+∞.Proof.
Consideringk>supV+1, we have V-k≤supV-k<-1. If x¯(n)∈SM(x,n) and Θ(n)∈ℰN(x,y,n), then An(x¯(n),Θ(n)[x¯(n)])-kn<-n, for each n∈ℤ+. Hence,
(81)h-k-(x,y)=-∞.
The other relation can be obtained similarly.It is clear thathk- is monotone in k.Lemma 10.
Letk,k1, and k2 be real numbers such that k1<k<k2, then(1)
ifhk-(x,y)=-∞, then hk1-(x,y)=-∞;(2)
ifhk-(x,y)=+∞, then hk2-(x,y)=+∞;(3)
moreover, ifhk-(x,y)∈ℝ, then
(82)hk1-(x,y)=-∞,hk2-(x,y)=+∞.Corollary 11.
There existsc-∈ℝ, such that
(83)inf{k∈ℝ:hk-=+∞}=sup{k∈ℝ:hk-=-∞}=c-.Proof.
From the previous results, it follows that there are(84)inf{k∈ℝ:hk-=+∞},sup{k∈ℝ:hk-=-∞}∈ℝ.
Given (x,y)∈M×N, choose k1,k2∈ℝ such that hk1-(x,y)=-∞ and hk2-(x,y)=+∞, then k1≤k2. Therefore, sup{k∈ℝ:hk-=-∞}≤k2, so
(85)sup{k∈ℝ:hk-=-∞}≤inf{k∈ℝ:hk-=+∞}.
Suppose thatsup{k∈ℝ:hk-=-∞}<inf{k∈ℝ:hk-=+∞}, then there are k0∈ℝ and ɛ>0 such that hk0-(x,y)∈ℝ and
(86)sup{k∈ℝ:hk-=-∞}<k0-ɛ<k0+ɛ<inf{k∈ℝ:hk-=+∞}.
Lemma 10 shows that hk0-ɛ-=-∞ and hk0+ɛ-=+∞; this is a contradiction. Hence,
(87)sup{k∈ℝ:hk-=-∞}=inf{k∈ℝ:hk-=+∞}.Theorem2 provides us a different characterization for the critical value c.Proof.
Letu be a fixed point of the Lax operator with critical value c. For (x,y)∈M×N and n∈ℤ+,
(88)u(x,y)+nc=ℒnu(x,y)=infΘ(n)supx¯(n){u(xn,Θ(n)[x¯(n)]n)=infΘ(n)sup-An(x¯(n),Θ(n)[x¯(n)])},
where x¯(n)∈SM(x,n) and Θ(n)∈ℰN(x,y,n). Therefore,
(89)infu+nc≤supu-supΘ(n)infx¯(n)An(x¯(n),Θ(n)[x¯(n)]);
and then, for every n∈ℤ+,
(90)h(n)(x,y)+cn≤supu-infu.
So hc-(x,y)<+∞; on that account, c≤c-. Analogously, from (88), we obtain
(91)supu+nc≥infu-supΘ(n)infx¯(n)An(x¯(n),Θ(n)[x¯(n)]);
consequently, for each n∈ℤ+,
(92)h(n)(x,y)+cn≥infu-supu.
Hence, hc-(x,y)>-∞ and in addition c≥c-.We can introduce the upper Peierls barrierhk+:M×N→ℝ defined by
(93)hk+(x,y):=limsupn→∞h(n)(x,y)+kn.
By similar arguments to the ones we made for hk-, we obtain analogous properties for hk+ and the following result.Theorem 12.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, and (x,y)∈M×N, then
(94)c=inf{k∈ℝ:hk+=+∞}=sup{k∈ℝ:hk+=-∞},
and hc+(x,y)∈ℝ, where c is the critical value.On account of lower and upper Peierls barrier properties, we havehk-=hk+ if k≠c.Corollary 13.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, and (x,y)∈M×N, then
(95)supn∈ℤ+|nc+h(n)(x,y)|<+∞,
where c is the critical value.Proof.
There isN∈ℤ+ such that
(96)hc-(x,y)-1<nc+h(n)(x,y)<hc+(x,y)+1,
for n≥N. Let B be the maximum of numbers |hc-(x,y)-1|, |hc+(x,y)+1|, |c+h(1)(x,y)|,|2c+h(2)(x,y)|,…,|(N-1)c+h(N-1)(x,y)|. According to Theorems 2 and 12, we have hc-(x,y),hc+(x,y)∈ℝ, so B∈ℝ, and in addition,
(97)|nc+h(n)(x,y)|≤B,
for all n∈ℤ+.Corollary 14.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, and (x,y)∈M×N, then
(98)-c=limn→∞1nh(n)(x,y),
where c is the critical value.Theorem3 states that c can be written in terms of actions for certain special sequences, using a solution of the Hamilton-Jacobi equation.Proof.
Considern∈ℤ+, (x,y)∈M×N, and u∈C(M×N,ℝ) solutions of the Hamilton-Jacobi equation (66). Because M and N are compact spaces, for each n∈ℤ+, given xn∈M, we can choose
(99)yn*(xn)∈argminyn∈N{u(xn,yn)-u(xn-1*,yn-1*(xn-1*))yn*(xn)∈argminyn∈N-V(xn-1*,yn-1*(xn-1*),xn,yn)},
where (x0*,y0*(x0*))=(x,y). We may now choose
(100)xn*∈argmaxxn∈M{u(xn,yn*(xn))-u(xn-1*,yn-1*(xn-1*))xn*∈argmaxxn∈M-V(xn-1*,yn-1*(xn-1*),xn,yn*(xn))}.
On account of u is the solution of (66), we have
(101)c=u(xn*,yn*(xn*))-u(xn-1*,yn-1*(xn-1*))-V(xn-1*,yn-1*(xn-1*),xn*,yn*(xn*)).
Consequently, for each n∈ℤ+, we have
(102)nc=u(xn*,yn*(xn*))-u(x,y)-An(x¯*(n),y¯*(n)),
where x¯*(n)={xi*}i=0n∈SM(x,n) and y¯*(n)={yi*(xi*)}i=0n∈SN(y,n).
By the compactness ofM and N and because u∈C(M×N,ℝ) we obtain that
(103)infu-supu≤nc+An(x¯*(n),y¯*(n))≤supu-infu,
from which we conclude that
(104)|nc+An(x¯*(n),y¯*(n))|≤supu-infu<+∞,
for all n∈ℤ+.We can obtain another characterization of the critical value in terms of optimal sequences in the previous theorem.Corollary 15.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, and (x,y)∈M×N, then there are sequences {xi*}i=0∞⊂M and {yi*}i=0∞⊂N such that
(105)-c=limn→∞1nAn(x¯*(n),y¯*(n)),
where x¯*(n)={xi*}i=0n∈SM(x,n) and y¯*(n)={yi*}i=0n∈SN(y,n), where c is the critical value.


## 4. Critical Solutions

LetM and N be compact metric spaces, and let V:M×N×M×N→ℝ be a Lipschitz function.Definition 16.
Fork∈ℝ, a function g∈C(M×N,ℝ) is called k-supersolution if
(106)ℒ1g≥g+k.
Analogously, a function g∈C(M×N,ℝ) is called k-subsolution if
(107)ℒ1g≤g+k.
The function g is a k-solution, if g is k-supersolution and k-subsolution.It is evident thatg is a k-solution if and only if g is a fixed point of the Lax operator with critical value k; in this case k=c according to Theorem 1. The c-solutions are called critical solutions.Proposition 17.
IfM and N are compact metric spaces, V:M×N×M×N→ℝ is a Lipschitz function, k∈ℝ, and (x0,y0)∈M×N, then  (1)
g is k-supersolution if and only if there exists x^1∈M such that
(108)g(x^1,y1)-g(x0,y0)-V(x0,y0,x^1,y1)≥k,for ally1∈N;(2)
g is k-subsolution if and only if for every x1∈M, there exists y^1=y^1(x1)∈N such that
(109)g(x1,y^1)-g(x0,y0)-V(x0,y0,x1,y^1)≤k.Proof.
Consider(x0,y0)∈M×N,  (1)
g satisfies (108) if and only if there is x^1∈M such that
(110)infy1∈N{g(x^1,y1)-V(x0,y0,x^1,y1)}≥g(x0,y0)+k,so(111)ℒ1g(x0,y0)=infΘ(1)supx¯(1){g(x1,Θ(1)[x¯(1)]1)-V(x0,y0,x1,Θ(1)[x¯(1)]1)}=supx1∈Minfy1∈N{g(x1,y1)-V(x0,y0,x1,y1)}≥g(x0,y0)+k,wherex¯(1)∈SM(x0,1) and Θ(1)∈ℰN(x0,y0,1);(2)
g satisfies (109) if and only if for every x1∈M, we have
(112)infy1∈N{g(x1,y1)-V(x0,y0,x1,y1)}≤g(x0,y0)+k.Next,(113)ℒ1g(x0,y0)=infΘ(1)supx¯(1){g(x1,Θ(1)[x¯(1)]1)-V(x0,y0,x1,Θ(1)[x¯(1)]1)}=supx1∈Minfy1∈N{g(x1,y1)-V(x0,y0,x1,y1)}≤g(x0,y0)+k,wherex¯(1)∈SM(x0,1) and Θ(1)∈ℰN(x0,y0,1).We have another consequence of the previous result: ifn∈ℤ+, the critical solutions u satisfy the following statements: (1)
for every strategyΘ(n)∈ℰN(x0,y0,n), there exists x¯^(n)∈SM(x0,n) such that
(114)u(xn,Θ(n)[x¯^(n)]n)-u(x0,y0)-An(x¯^(n),Θ(n)[x¯^(n)])≥nc;(2)
there exists a strategyΘ^(n)∈ℰN(x0,y0,n) such that
(115)u(xn,Θ^(n)[x¯(n)]n)-u(x0,y0)-An(x¯(n),Θ^(n)[x¯(n)])≤nc,∀x¯(n)∈SM(x0,n).We have some properties ofk-super and k-subsolutions.Lemma 18.
Forg∈C(M×N,ℝ) and (x0,y0)∈M×N,(1)
ifg is k-supersolution and k′≤k, then g is k′-supersolution;(2)
ifg is k-subsolution and k′≥k, then g is k′-subsolution;(3)
if the setsSU,SL⊂ℝ are defined as
(116)SU(g)={k∈ℝ:gisk-supersolution},SL(g)={k∈ℝ:gisk-subsolution},
then supSU(g)≤infSL(g).Proof.
The first and second items are clear. To prove the third claim, choosea∈SU(g) and b∈SL(g). Then, there is x^1∈M such that
(117)g(x^1,y1)-g(x0,y0)-V(x0,y0,x^1,y1)≥a,
for all y1∈N. Because b∈SL(g), there is y^1=y^1(x^1) such that
(118)g(x^1,y^1)-g(x0,y0)-V(x0,y0,x^1,y^1)≤b.
Therefore, a≤b, and then supSU(g)≤infSL(g).By definition, ifu is a fixed point of the Lax operator ℒn with critical value c, then u is a critical solution. Therefore, c∈SU(u)∩SL(u), and according to Lemma 18, we have a new characterization of the critical value c (see Theorem 4).We are interested in showing that the lower Peierls barrier is a critical solution. To this end, we consider the behavior of extremal sequences for lower Peierls barrier defined as follows.Definition 19.
We define a couple(x¯^(n),Θ^(n))∈SM(x0,n)×ℰN(x0,y0,n) extremal for h(n)(x0,y0), if h(n)(x0,y0)=An(x¯^(n),Θ^(n)[x¯^(n)]) and satisfies the following conditions:(1)
for every strategyΘ(n)∈ℰN(x0,y0,n), there exists x¯~(n)∈SM(x0,n) such that
(119)An(x¯^(n),Θ^(n)[x¯^(n)])≥An(x¯~(n),Θ(n)[x¯~(n)]);(2)
for everyx¯(n)∈SM(x0,n),
(120)An(x¯^(n),Θ^(n)[x¯^(n)])≤An(x¯(n),Θ^(n)[x¯(n)]).The following result tells us that the lower Peierls barrier is a critical solution and therefore a solution of the Hamilton-Jacobi equation.Theorem 20.
-
h
c
- is a critical solution.Proof.
Consider(x0,y0)∈M×N. According to Theorem 2, hc-∈ℝ.
(I) We begin by proving-hc- is c-supersolution. Let us take y1∈N and let Φ^(n-1)∈ℰN(x1,y1,n-1) be extremal for h(n-1)(x1,y1), then
(121)h(n-1)(x1,y1)=infz¯(n-1)An-1(z¯(n-1),Φ^(n-1)[z¯(n-1)]),
where z¯(n-1)∈SM(x1,n-1).
For everyx¯(n)∈SM(x0,n), define Θ^(n)∈ℰN(x0,y0,n) as
(122)Θ^(n)[x¯(n)]i={y0,i=0,Φ^(n-1)[{x1,x2,…,xn}]i-1,1≤i≤n,
then
(123)hc-(x0,y0)≥liminfn→∞{infx¯(n)An(x¯(n),Θ^(n)[x¯(n)])+cn}.
There is x¯^(n)∈SM(x0,n) such that
(124)infx¯(n)An(x¯(n),Θ^(n)[x¯(n)])=An(x¯^(n),Θ^(n)[x¯^(n)]).
Choose a subsequence nj↑∞ such that n1=1 and
(125)liminfn→∞An(x¯^(n),Θ^(n)[x¯^(n)])+nc=limj→∞Anj(x¯^(nj),Θ^(nj)[x¯^(nj)])+njc;
extracting a subsequence if necessary, we can assume that
(126)x¯^(nj)⟶x¯*∈SM(x0,∞),
where SM(x0,∞) denotes the set of infinite sequences in M, with initial condition x0. Therefore,
(127)hc-(x0,y0)≥limj→∞{(nj-1)cV(x0,y0,x1*,y1)+c+[V(x0,y0,x¯^(nj)1,Θ^(nj)[x¯^(nj)]1)-V(x0,y0,x1*,y1)V(x0,y0,x¯^(nj)1,Θ^(nj)[x¯^(nj)]1)]+[V(x¯^(nj)1,Θ^(nj)[x¯^(nj)]1,+x¯^(nj)2,Θ^(nj)[x¯^(nj)]2)-V(x1*,y1,x¯^(nj)2,Θ^(nj)[x¯^(nj)]2)V(x¯^(nj)1,Θ^(nj)[x¯^(nj)]1,]+Anj-1(z¯^(nj-1),Φ^(nj-1)[z¯^(nj-1)])+(nj-1)c},
where z¯^(nj-1)={x1*,x^2,…,x^nj}. Because V is continuous, then
(128)hc-(x0,y0)≥V(x0,y0,x1*,y1)+c+liminfn→∞{infz¯(n-1)An-1(z¯^(n-1),+liminfn→∞infz¯(n-1)An-1Φ^(n-1)[z¯^(n-1)])+(n-1)cinfz¯(n-1)An-1(z¯^(n-1),}=V(x0,y0,x1*,y1)+c+hc-(x1*,y1),
which proves that there is x1*∈M such that
(129)-hc-(x1*,y1)+hc-(x0,y0)-V(x0,y0,x1*,y1)≥c,
for all y1∈N. Hence, -hc- is c-supersolution.
(II) We proceed to show that-hc- is c-subsolution. Let us take x1∈M. For each n∈ℤ+, let Θ^(n)∈ℰN(x0,y0,n) be extremal for h(n)(x0,y0), then
(130)h(n)(x0,y0)=infx¯(n)An(x¯(n),Θ^(n)[x¯(n)]).
Observe that Θ^(n)[x¯(n)]1 depends only on x1, because Θ^(n)∈ℰN(x0,y0,n). Suppose that Θ^(n)[x¯(n)]1→y1*(x1).
Forw¯(n-1)={x1,w2,…,wn}∈SM(x1,n-1), we can define a strategy Φ^(n-1)∈ℰN(x1,y1*(x1),n-1) as follows:
(131)Φ^(n-1)[w¯(n-1)]i={y1*(x1),i=0,Θ^(n)[z¯(n)]i+1,1≤i≤n-1,
where z¯(n)={x0,x1,w2,w3,…,wn}∈SM(x0,n). So
(132)h(n-1)(x1,y1*(x1))≥infw¯(n-1)An-1(w¯(n-1),Φ^(n-1)[w¯(n-1)]).
We can choose w¯^(n-1)={x1,w^2,…,w^n}∈SM(x1,n-1) extremal for
(133)infw¯(n-1)An-1(w¯(n-1),Φ^(n-1)[w¯(n-1)]),
and a subsequence nj↑∞ such that
(134)hc-(x1,y1*(x1))≥limj→∞Anj-1(w¯^(nj-1),Φ^(nj-1)[w¯^(nj-1)])+c(nj-1).
If z¯^(nj)={x0,x1,w^2,w^3,…,w^nj}, then
(135)hc-(x0,y0)=liminfn→∞infx¯(n)An(x¯(n),Θ^(n)[x¯(n)])+nc≤limj→∞{(nj-1)cV(x0,y0,x1,y1*(x1))+c+[V(x0,y0,x1,Θ^(nj)[z¯^(nj)]1)-V(x0,y0,x1,y1*(x1))V(x0,y0,x1,Θ^(nj)[z¯^(nj)]1)]+[V(x1,Θ^(nj)[z¯^(nj)]1,z¯^(nj)2,Θ^(nj)[z¯^(nj)]2)-V(x1,y1*(x1),z¯^(nj)2,Θ^(nj)[z¯^(nj)]2)]+Anj-1(w¯^(nj-1),Φ^(nj-1)[w¯^(nj-1)])+(nj-1)c}.
According to the above relations and the continuity of V, if x1∈M, there is y1*(x1)∈N such that
(136)-hc-(x1,y1*(x1))+hc-(x0,y0)-V(x0,y0,x1,y1*(x1))≤c.
Therefore, -hc- is a c-subsolution.



---

*Source: 769368-2013-07-10.xml*