DISCRETE TIME ZERO-SUM GAMES

DISCRETE TIME ZERO-SUM GAMES

ALEXANDER J. ZASLAVSKI Received 3 September 1998

We consider a class of dynamic discrete-time two-player zero-sum games. We show that for a generic cost function and each initial state, there exists a pair of overtaking equilibria strategies over an infinite horizon. We also establish that for a generic cost functionf, there exists a pair of stationary equilibria strategies(xf,yf)such that each pair of “approximate” equilibria strategies spends almost all of its time in a small neighborhood of(xf,yf).

1. Introduction

The study of variational and optimal control problems defined on infinite intervals has recently been a rapidly growing area of research [4, 6, 9, 10, 15, 16, 17]. These problems arise in engineering [1, 19], in models of economic dynamics [11, 13, 18], in continuum mechanics [5, 10, 12], and in game theory [3, 4, 7].

In this paper, we study the existence and the structure of “approximate” equilibria for dynamic two-player zero-sum games.

Denote by·the Euclidean norm in_R^m. LetX⊂R^m1andY⊂R^m2be nonempty convex compact sets. Denote by _Mthe set of all continuous functionsf :X×X× Y×Y→R¹such that:

•for each(y1,y2)∈Y×Y the function(x1,x2)→f (x1,x2,y1,y2),(x1,x2)∈ X×Xis convex;

•for each(x1,x2)∈X×Xthe function(y1,y2)→f (x1,x2,y1,y2),(y1,y2)∈ Y×Y is concave.

For the set_Mwe define a metricρ:M×M→R¹by ρ(f,g)=supf

x1,x2,y1,y2

−g

x1,x2,y1,y2:x1,x2∈X, y1,y2∈Y

, f,g∈M. (1.1) ClearlyMis a complete metric space.

Copyright © 1999 Hindawi Publishing Corporation Abstract and Applied Analysis 4:1 (1999) 21–48

1991 Mathematics Subject Classification: 49J99, 58F99, 90D05, 90D50 URL: http://aaa.hindawi.com/volume-4/S1085337599000020.html

Givenf ∈Mand an integern≥1, we consider a discrete-time two-player zero-sum game over the interval[0,n]. For this game{{xi}ⁿ_i=0:xi∈X,i=0,...,n}is the set of strategies for the first player,{{yi}ⁿ_i=0:yi∈Y, i=0,...,n}is the set of strategies for the second player, and the cost for the first player associated with the strategies{xi}ⁿ_i=0, {yi}ⁿ_i=0is given by_n−1

i=0f (xi,xi+1,yi,yi+1).

Definition 1.1. Letf ∈M, n≥1 be an integer and letM∈ [0,∞). A pair of sequences { ¯xi}ⁿ_i=0⊂X,{ ¯yi}ⁿ_i=0⊂Y is called(f,M)-good if the following properties hold:

(i) for each sequence{xi}ⁿ_i=0⊂Xsatisfyingx0= ¯x0,xn= ¯xn

M+

n−1

i=0

f

xi,xi+1,y¯i,y¯i+1

≥ n−1

i=0

f

¯

xi,x¯i+1,y¯i,y¯i+1

; (1.2)

(ii) for each sequence{yi}ⁿ_i=0⊂Y satisfyingy0= ¯y0,yn= ¯yn

M+

n−1

i=0

f

¯

xi,x¯i+1,y¯i,y¯i+1

≥

n−1

i=0

f

¯

xi,x¯i+1,yi,yi+1

. (1.3)

If a pair of sequences{xi}ⁿ_i=0⊂X, {yi}ⁿ_i=0⊂Y is(f,0)-good, then it is called(f )- optimal.

Our first main result in this paper deals with the so-called “turnpike property” of

“good” pairs of sequences. To have this property means, roughly speaking, that the

“good” pairs of sequences are determined mainly by the cost function, and are essen- tially independent of the choice of interval and endpoint conditions, except in regions close to the endpoints. Turnpike properties are well known in mathematical economics and optimal control (see [11, 13, 15, 16, 17, 18, 19] and the references therein).

Consider anyf ∈M. We say that the functionf has theturnpike propertyif there exists a unique pair(xf,yf)∈X×Y for which the following assertion holds.

For each >0 there exist an integern0≥2 and a numberδ >0 such that, for each integern≥2n0and each(f,δ)-good pair of sequences{xi}ⁿ_i=0⊂X,{yi}ⁿ_i=0⊂Y the relationsxi−xf,yi−yf ≤holds for all integersi∈ [n0,n−n0].

In this paper, our goal is to show that the turnpike property holds for a generic f ∈M. We prove the existence of a setF⊂Mwhich is a countable intersection of open everywhere dense sets in_Msuch that eachf ∈Fhas the turnpike property (see Theorem 2.1). Results of this kind for classes of single-player control systems have been established in [15, 16, 17]. Thus, instead of considering the turnpike property for a single function, we investigate it for a space of all such functions equipped with some natural metric, and show that this property holds for most of these functions.

This allows us to establish the turnpike property without restrictive assumptions on the functions.

We also study the existence of equilibria over an infinite horizon for the class of zero- sum games considered in the paper. We employ the following version of the overtaking optimality criterion which was introduced in the economic literature by Gale [8] and von Weizsacker [14] and used in control and game theory [1, 3, 4, 19].

Definition 1.2. Let f ∈M. A pair of sequences { ¯xi}^∞_i=0⊂X, { ¯yi}^∞_i=0 ⊂Y is called (f )-overtaking optimalif the following properties hold:

(i) for each sequence{xi}^∞_i=0⊂Xsatisfyingx0= ¯x0

lim sup

T→∞

_T−1

i=0

f

¯

xi,x¯i+1,y¯i,y¯i+1

−

T−1 i=0

f

xi,xi+1,y¯i,y¯i+1

≤0; (1.4) (ii) for each sequence{yi}^∞_i=0⊂Y satisfyingy0= ¯y0

lim sup

T→∞

_T−1

i=0

f

¯

xi,x¯i+1,yi,yi+1

−

T−1 i=0

f

¯

xi,x¯i+1,y¯i,y¯i+1

≤0. (1.5)

Our second main result (see Theorem 2.2) shows that for a genericf ∈Mand each (x,y)∈X×Y there exists an(f )-overtaking optimal pair of sequences{xi}^∞_i=0⊂X, {yi}^∞_i=0⊂Y such thatx0=x,y0=y.

2. Main results

In this section we present our main results.

Theorem 2.1. There exists a set _F⊂Mwhich is a countable intersection of open everywhere dense sets inMsuch that for eachf ∈Fthe following assertions hold.

(1)There exists a unique pair(xf,yf)∈X×Y for which supy∈Yf

xf,xf,y,y

=f

xf,xf,yf,yf

= inf

x∈Xf

x,x,yf,yf

. (2.1)

(2)For each >0there exist a neighborhoodUoff inM, an integern0≥2, and a numberδ >0such that for eachg∈U, each integern≥2n0, and each(g,δ)-good pair of sequences{xi}ⁿ_i=0⊂X,{yi}ⁿ_i=0⊂Y the relation

xi−xf, yi−yf ≤ (2.2)

holds for all integersi∈ [n0,n−n0]. Moreover, ifx0−xf,y0−yf ≤δ, then (2.2) holds for all integersi∈ [0,n−n0], and ifxn−xf,yn−yf ≤δ, then (2.2) is valid for all integersi∈ [n0,n].

Theorem 2.2. There exists a set F⊂Mwhich is a countable intersection of open everywhere dense sets in_Msuch that for eachf ∈Fthe following assertion holds.

For each x ∈X and each y ∈Y there exists an (f )-overtaking optimal pair of sequences{xi}^∞_i=0⊂X, {yi}^∞_i=0⊂Y such thatx0=x,y0=y.

3. Definitions and notations

Letf ∈M. Define a functionf¯:X×Y→R¹by

f (x,y)¯ =f (x,x,y,y), x∈X, y∈Y. (3.1)

Then there exists a saddle point(xf,yf)∈X×Y forf¯. We have sup

y∈Y

f¯ xf,y

= ¯f xf,yf

= inf

x∈Xf¯ x,yf

. (3.2)

Set

µ(f )= ¯f xf,yf

. (3.3)

Definition 3.1. Let f ∈M. A pair of sequences{xi}^∞_i=0⊂X, {yi}^∞_i=0⊂Y is called (f )-minimal if for each integer n≥2 the pair of sequences {xi}ⁿ_i=0,{yi}ⁿ_i=0 is (f )- optimal.

We show in Section 5 (see Proposition 5.3) that for eachf ∈M, eachx∈X, and eachy∈Y there exists an(f )-minimal pair of sequences {xi}^∞_i=0⊂X,{yi}^∞_i=0⊂Y such thatx0=x,y0=y.

Letf ∈M,n≥1 be an integer, and letξ=(ξ1,ξ2,ξ3,ξ4)∈X×X×Y×Y. Define X(ξ,n)=

{xi}ⁿ_i=0⊂X:x0=ξ1, xn=ξ2

, (3.4)

Y(ξ,n)=

{yi}ⁿ_i=0⊂Y:y0=ξ3, yn=ξ4

, (3.5)

f^(ξ,n)

x0,...,xi,...,xn ,

y0,...,yi,...,yn

= n−1

i=0

f

xi,xi+1,yi,yi+1 , {xi}ⁿ_i=0∈X(ξ,n), {yi}ⁿ_i=0∈Y(ξ,n).

(3.6)

4. Preliminary results

LetM,N be nonempty sets and letf :M×N→R¹. Set f^a(x)=sup

y∈Nf (x,y), x∈M, f^b(y)= inf

x∈Mf (x,y), y∈N, (4.1) v_f^a = inf

x∈M sup

y∈Nf (x,y), v^b_f =sup

y∈N inf

x∈Mf (x,y). (4.2) Clearly

v_f^b ≤v_f^a. (4.3)

We have the following result (see [2, Chapter 6, Section 2, Proposition 1]).

Proposition4.1. Letf :M×N→R¹,x¯∈M,y¯∈N. Then

y∈Nsupf (x,y)¯ =f (x,¯ y)¯ = inf

x∈Mf (x,y)¯ (4.4) if and only if

v^a_f =v^b_f, sup

y∈Nf (x,y)¯ =v^a_f, inf

x∈Mf (x,y)¯ =v_f^b. (4.5)

Letf :M×N→R¹. If(x,¯ y)¯ ∈M×Nsatisfies (4.4) that it is called a saddle point (forf). We have the following result (see [2, Chapter 6, Section 2, Theorem 8]).

Proposition4.2. LetM⊂R^m,N⊂Rⁿbe convex compact sets and letf :M×N→ R¹be a continuous function. Assume that for eachy∈N, the functionx→f (x,y), x∈M is convex and for eachx∈M, the function y→f (x,y), y∈N is concave.

Then there exists a saddle point forf.

Proposition4.3. LetM,N be nonempty sets,f :M×N→R¹and

−∞< v_f^a =v_f^b <+∞, x0∈M, y0∈N, 1,2∈ [0,∞), (4.6)

y∈Nsupf x0,y

≤v^a_f+1, inf

x∈Mf x,y0

≥v^b_f−2. (4.7)

Then

sup

y∈Nf x0,y

−1−2≤f x0,y0

≤ inf

x∈Mf x,y0

+1+2. (4.8)

Proof. By (4.7) and (4.6)

y∈Nsupf x0,y

−1−2

≤v_f^a−2=v^b_f−2≤ inf

x∈Mf x,y0

≤f x0,y0

≤sup

y∈Nf x0,y

≤v^a_f+1=v_f^b+1≤ inf

x∈Mf x,y0

+1+2.

(4.9)

This completes the proof.

Proposition4.4. LetM,N be nonempty sets and letf :M×N→R¹. Assume that (4.6) is valid,x0∈M,y0∈N,1,2∈ [0,∞), and

y∈Nsupf x0,y

−2≤f x0,y0

≤ inf

x∈Mf x,y0

+1. (4.10)

Then sup

y∈Nf x0,y

≤v_f^a+1+2, inf

x∈Mf x,y0

≥v^b_f−1−2. (4.11)

Proof. It follows from (4.10), (4.2), (4.6), and (4.3) that v_f^b−2=v^a_f−2≤sup

y∈Nf x0,y

−2≤ inf

x∈Mf x,y0

+1≤v_f^b+1. (4.12)

This implies (4.11). The proposition is thus proved.

5. The existence of a minimal pair of sequences Letf ∈M,xf ∈X,yf ∈Y, and

supy∈Yf¯ xf,y

= ¯f xf,yf

= inf

x∈Xf¯ x,yf

. (5.1)

Proposition5.1. Letn≥2be an integer and

¯

xi=xf, y¯i=yf, i=0,...,n. (5.2) Then the pair of sequences{ ¯xi}ⁿ_i=0,{ ¯yi}ⁿ_i=0is(f )-optimal.

Proof. Assume that{xi}ⁿ_i=0⊂X,{yi}ⁿ_i=0⊂Y, and

x0,xn=xf, y0,yn=yf. (5.3) By (5.1), (5.2), and (5.3)

n−1

i=0

f

xi,xi+1,y¯i,y¯i+1

=

n−1

i=0

f

xi,xi+1,yf,yf

≥nf

n⁻¹

n−1

i=0

xi,n⁻¹ n−1

i=0

xi+1,yf,yf

=nf

n⁻¹

n−1

i=0

xi,n⁻¹

n−1

i=0

xi,yf,yf

≥nf

xf,xf,yf,yf ,

n−1

i=0

f

¯

xi,x¯i+1,yi,yi+1

=

n−1

i=0

f

xf,xf,yi,yi+1

≤nf

xf,xf,n⁻¹

n−1

i=0

yi,n⁻¹

n−1

i=0

yi+1

=nf

xf,xf,n⁻¹

n−1

i=0

yi,n⁻¹

n−1

i=0

yi

≤nf

xf,xf,yf,yf .

(5.4)

This completes the proof of the proposition.

Proposition5.2. Letn≥2be an integer and let x_i^(k)_n

i=0, y_i^(k)_n

i=0

⊂X×Y, k=1,2,... (5.5)

be a sequence of(f )-optimal pairs. Assume that

k→∞lim x^(k)_i =xi, lim

k→∞y_i^(k)=yi, i=0,1,2,...,n. (5.6)

Then the pair of sequences({xi}ⁿ_i=0,{yi}ⁿ_i=0)is(f )-optimal.

Proof. Let

{ui}ⁿ_i=0⊂X, u0=x0, un=xn. (5.7) We show that

n−1

i=0

f

xi,xi+1,yi,yi+1

≤

n−1

i=0

f

ui,ui+1,yi,yi+1

. (5.8)

Assume the contrary. Then there exists >0 such that

n−1

i=0

f

xi,xi+1,yi,yi+1

>ⁿ⁻¹

i=0

f

ui,ui+1,yi,yi+1

+8. (5.9)

There exists a numberδ∈(0,)such that f

z1,z2,ξ1,ξ2

−f

¯

z1,z¯2,ξ¯1,ξ¯2≤(8n)⁻¹ (5.10) for eachz1,z2,z¯1,z¯2∈X, ξ1,ξ2,ξ¯1,ξ¯2∈Ysatisfyingzi− ¯zi,ξi− ¯ξi ≤δ, i=1,2.

There exists an integerq≥1 such that

xi−x_i^(q), yi−y_i^(q)≤δ, i=0,...,n. (5.11) Define{u^(q)_i }ⁿ_i=0⊂Xby

u^(q)₀ =x₀^(q), u^(q)n =xn^(q), u^(q)_i =ui, i=1,...,n−1. (5.12) Since the pair of sequences

x_i^(q)_n

i=0, y_i^(q)_n

i=0

is (f )-optimal it follows from (5.12) that

n−1 i=0

f

x_i^(q),x_i+1^(q),y_i^(q),y_i+1^(q)

≤ n−1

i=0

f

u^(q)_i ,u^(q)_i+1,y_i^(q),y^(q)_i+1

. (5.13)

By the definition ofδ(see (5.10)), (5.11), (5.12), and (5.7) fori=0,...,n−1, f

x_i^(q),x_i+1^(q),y_i^(q),y_i+1^(q)

−f

xi,xi+1,yi,yi+1≤(8n)⁻¹, f

u^(q)_i ,u^(q)_i+1,y_i^(q),y_i+1^(q)

−f

ui,ui+1,yi,yi+1≤(8n)⁻¹.

(5.14)

It follows from these relations and (5.9) that n−1

i=0

f

x_i^(q),x_i+1^(q),y_i^(q),y_i+1^(q)

−

n−1

i=0

f

u^(q)_i ,u^(q)_i+1,y_i^(q),y_i+1^(q)

> . (5.15) This is contradictory to (5.13). The obtained contradiction proves that (5.8) is valid.

Analogously we can show that for each {ui}ⁿ_i=0 ⊂Y satisfyingu0 =y0, un =yn,

the following relation holds:

n−1

i=0

f

xi,xi+1,yi,yi+1

≥

n−1

i=0

f

xi,xi+1,ui,ui+1

. (5.16)

This completes the proof of the proposition.

Proposition5.3. Letf ∈Mand letx∈X,y∈Y. Then there exists an(f )-minimal pair of sequences{xi}^∞_i=0⊂X,{yi}^∞_i=0⊂Y such thatx0=x,y0=y.

Proof. By Proposition 4.2, for each integer n≥2 there exists an(f )-optimal pair of sequences{x_i⁽ⁿ⁾}ⁿ_i=0 ⊂X, {y_i⁽ⁿ⁾}ⁿ_i=0⊂Y such thatx₀⁽ⁿ⁾=x, y₀⁽ⁿ⁾=y. There exist a pair of sequences{xi}^∞_i=0⊂X,{yi}^∞_i=0⊂Yand a strictly increasing sequence of natural numbers{nk}^∞_k=1such that for each integeri≥0

x_i^(nk)−→xi, y_i^(nk)−→yi ask−→ ∞. (5.17) It follows from Proposition 5.2 that the pair of sequences {xi}^∞_i=0, {yi}^∞_i=0 is (f )-

minimal. The proposition is proved.

6. Preliminary lemmas for Theorem 2.1 Letf ∈M. There existxf ∈X,yf ∈Y such that

sup

y∈Yf

xf,xf,y,y

=f

xf,xf,yf,yf

= inf

x∈Xf

x,x,yf,yf

. (6.1)

Letr∈(0,1). Definefr:X²×Y²→R¹by fr

x1,x2,y1,y2

=f

x1,x2,y1,y2

+rx1−xf−ry1−yf,

x1,x2∈X, y1,y2∈Y. (6.2) Clearlyfr∈M,

sup

y∈Yfr

xf,xf,y,y

=fr

xf,xf,yf,yf

= inf

x∈Xfr

x,x,yf,yf

. (6.3)

Lemma6.1. Let∈(0,1). Then there exists a numberδ∈(0,)such that for each integer n ≥ 2 and each (fr,δ)-good pair of sequences {xi}ⁿ_i=0 ⊂X, {yi}ⁿ_i=0 ⊂ Y satisfying

xn,x0=xf, yn,y0=yf, (6.4) the following relations hold:

xi−xf, yi−yf ≤, i=0,...,n. (6.5)

Proof. Choose a number

δ∈

0,8⁻¹r

. (6.6)

Assume that an integer n≥2,{xi}ⁿ_i=0⊂X, {yi}ⁿ_i=0⊂Y is an (fr,δ)-good pair of sequences and (6.4) is valid. Set

ξ1,ξ2=xf, ξ3,ξ4=yf, ξ=

ξ1,ξ2,ξ3,ξ4

. (6.7)

Consider the setsX(ξ,n),Y(ξ,n)and the functions(fr)^(ξ,n),f^(ξ,n)(see (3.4), (3.5), and (3.6)). It follows from (6.1) and Proposition 5.1 that

sup _n−1

i=0

f

xf,xf,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

=nf

xf,xf,yf,yf

=inf _n−1

i=0

f

pi,pi+1,yf,yf

: {pi}ⁿ_i=0∈X(ξ,n)

.

(6.8)

Equation (6.8) and Proposition 4.1 imply that sup

_n−1

i=0

f

xf,xf,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

=inf

sup _n−1

i=0

f

pi,pi+1,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

: {pi}ⁿ_i=0∈X(ξ,n)

,

(6.9) inf

_n−1

i=0

f

pi,pi+1,yf,yf

: {pi}ⁿ_i=0∈X(ξ,n)

=sup

inf _n−1

i=0

f

pi,pi+1,ui,ui+1

: {pi}ⁿ_i=0∈X(ξ,n)

: {ui}ⁿ_i=0∈Y(ξ,n)

. (6.10) It follows from (6.3) and Proposition 5.1 that

sup _n−1

i=0

fr

xf,xf,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

=nfr

xf,xf,yf,yf

=inf _n−1

i=0

fr

pi,pi+1,yf,yf

: {pi}ⁿ_i=0∈X(ξ,n)

.

(6.11)

Equation (6.11) and Proposition 4.1 imply that sup

_n−1

i=0

fr

xf,xf,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

=inf

sup _n−1

i=0

fr

pi,pi+1,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

: {pi}ⁿ_i=0∈X(ξ,n)

,

(6.12) inf

_n−1

i=0

fr

pi,pi+1,yf,yf

: {pi}ⁿ_i=0∈X(ξ,n)

=sup

inf _n−1

i=0

fr

pi,pi+1,ui,ui+1

: {pi}ⁿ_i=0∈X(ξ,n)

: {ui}ⁿ_i=0∈Y(ξ,n)

. (6.13) By (6.4) and (6.7)

{xi}ⁿ_i=0∈X(ξ,n), {yi}ⁿ_i=0∈Y(ξ,n). (6.14) Since({xi}ⁿ_i=0,{yi}ⁿ_i=0)is an(fr,δ)-good pair of sequences, we conclude that

sup _n−1

i=0

fr

xi,xi+1,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

−δ

≤

n−1

i=0

fr

xi,xi+1,yi,yi+1

≤inf _n−1

i=0

fr

pi,pi+1,yi,yi+1

: {pi}ⁿ_i=0∈X(ξ,n)

+δ.

(6.15)

It follows from Proposition 4.4, (6.12), (6.13), and (6.15) that sup

_n−1

i=0

fr

xi,xi+1,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

≤sup _n−1

i=0

fr

xf,xf,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

+2δ,

(6.16)

inf _n−1

i=0

fr

pi,pi+1,yi,yi+1

: {pi}ⁿ_i=0∈X(ξ,n)

≥inf _n−1

i=0

fr

pi,pi+1,yf,yf

: {pi}ⁿ_i=0∈X(ξ,n)

−2δ.

(6.17)

By (6.2), (6.8), (6.11), and (6.16) nf

xf,xf,yf,yf

=nfr

xf,xf,yf,yf

≥sup _n−1

i=0

fr

xi,xi+1,ui,ui+1

: {ui}ⁿ_i=0∈Y(ξ,n)

−2δ

≥ −2δ+

n−1

i=0

fr

xi,xi+1,yf,yf

= −2δ+r n−1

i=0

xi−xf+

n−1

i=0

f

xi,xi+1,yf,yf

≥ −2δ+r

n−1

i=0

xi−xf+nf

xf,xf,yf,yf .

(6.18) By (6.2), (6.8), (6.11), and (6.17)

nf

xf,xf,yf,yf

=nfr

xf,xf,yf,yf

≤inf _n−1

i=0

fr

pi,pi+1,yi,yi+1

: {pi}ⁿ_i=0∈X(ξ,n)

+2δ

≤2δ+

n−1

i=0

fr

xf,xf,yi,yi+1

=2δ−r

n−1

i=0

yi−yf+

n−1

i=0

f

xf,xf,yi,yi+1

≤2δ−r n−1

i=0

yi−yf+nf

xf,xf,yf,yf .

(6.19) Equations (6.6), (6.18), and (6.19) imply that fori=1,...,n−1

xi−xf ≤r⁻¹(2δ) < , yi−yf ≤2δr⁻¹< . (6.20)

This completes the proof of the lemma.

Choose a number

D0≥supfr

x1,x2,y1,y2:x1,x2∈X, y1,y2∈Y

. (6.21)

We can easily prove the following lemma.

Lemma6.2. Letn≥2be an integer, M be a positive number, and let {xi}ⁿ_i=0⊂X, {yi}ⁿ_i=0⊂Ybe an(fr,M)-good pair of sequences. Then the pair of sequences{ ¯xi}ⁿ_i=0⊂ X,{ ¯yi}ⁿ_i=0⊂Y defined by

¯

xi=xi, y¯i=yi, i=1,...,n−1, x¯0,x¯n=xf, y¯0,y¯n=yf (6.22) is(fr,M+8D0)-good.

By using the uniform continuity of the functionfr:X×X×Y×Y we can easily prove the following lemma.

Lemma6.3. Letbe a positive number. There exists a numberδ >0such that for each integer n≥2 and each sequences {xi}ⁿ_i=0,{ ¯xi}ⁿ_i=0 ⊂ X,{yi}ⁿ_i=0,{ ¯yi}ⁿ_i=0 ⊂Y which satisfy

¯xj−xj, ¯yj−yj ≤δ, j=0,n, xj = ¯xj, yj= ¯yj, j=1,...,n−1, (6.23) the following relation holds:

n−1

i=0

fr

xi,xi+1,yi,yi+1

−fr

¯

xi,x¯i+1,y¯i,y¯i+1

≤. (6.24)

Lemma 6.3 implies the following result.

Lemma6.4. Assume that >0. Then there exists a numberδ >0such that for each integern≥2, each(fr,)-good pair of sequences{xi}ⁿ_i=0⊂X,{yi}ⁿ_i=0⊂Y and each pair of sequences{ ¯xi}ⁿ_i=0⊂X,{ ¯yi}ⁿ_i=0⊂Y the following assertion holds.

If (6.23) is valid, then the pair of sequences({ ¯xi}ⁿ_i=0,{ ¯yi}ⁿ_i=0)is(fr,2)-good.

Lemmas 6.4 and 6.1 imply the following.

Lemma6.5. Let∈(0,1). Then there exists a numberδ∈(0,)such that for each integern≥2and each(fr,δ)-good pair of sequences{xi}ⁿ_i=0⊂X,{yi}ⁿ_i=0⊂Ywhich satisfiesxj−xf,yj−yf ≤δ,j =0,n, the following relations hold:xi−xf, yi−yf ≤, i=0,...,n.

Denote by Card(E)the cardinality of a setE.

Lemma6.6. LetMbe a positive number and let∈(0,1). Then there exists an integer n0≥4such that for each(fr,M)-good pair of sequences{xi}ⁿ_i=0⁰ ⊂X, {yi}ⁿ_i=0⁰ ⊂Y which satisfies

x0,xn0=xf, y0,yn0=yf, (6.25)

there isj∈ {1,...,n0−1}for which

xj−xf, yj−yf ≤. (6.26)

Proof. Choose a natural number

n0>8+8(r)⁻¹M. (6.27)

Set

ξ1,ξ2=xf, ξ3,ξ4=yf, ξ= {ξi}⁴_i=1. (6.28) Assume that{xi}ⁿ_i=0⁰ ⊂X,{yi}ⁿ_i=0⁰ ⊂Y is an (fr,M)-good pair of sequences and (6.25) holds. It follows from Proposition 4.4 that

sup





n0−1 i=0

fr

xi,xi+1,ui,ui+1

: {ui}ⁿ_i=0⁰ ∈Y ξ,n0







≤inf



sup





n0−1 i=0

fr

pi,pi+1,ui,ui+1

:{ui}ⁿ_i=0⁰ ∈Y ξ,n0





:{pi}ⁿ_i=0⁰ ∈X ξ,n0





+2M, (6.29) inf





n0−1 i=0

fr

pi,pi+1,yi,yi+1

: {pi}ⁿ_i=0⁰ ∈X ξ,n0







≥sup



inf





n0−1 i=0

fr

pi,pi+1,ui,ui+1

:{pi}ⁿ_i=0⁰ ∈X ξ,n0





:{ui}ⁿ_i=0⁰ ∈Y ξ,n0





−2M.

(6.30) By Proposition 5.1, (6.3), and Propositions 4.1, 4.2

inf



sup





n0−1 i=0

fr

pi,pi+1,ui,ui+1

: {ui}ⁿ_i=0⁰ ∈Y ξ,n0





: {pi}ⁿ_i=0⁰ ∈X ξ,n0







=sup



inf





n0−1 i=0

fr

pi,pi+1,ui,ui+1

:{pi}ⁿ_i=0⁰ ∈X ξ,n0





:{ui}ⁿ_i=0⁰ ∈Y ξ,n0







=n0fr

xf,xf,yf,yf .

(6.31)

Equations (6.2), (6.29), (6.30), and (6.31) imply that n0f

xf,xf,yf,yf

=n0fr

xf,xf,yf,yf

≥ −2M+sup





n0−1 i=0

fr

xi,xi+1,ui,ui+1

: {ui}ⁿ_i=0⁰ ∈Y ξ,n0







≥ −2M+

n0−1 i=0

fr

xi,xi+1,yf,yf

= −2M+

n0−1 i=0

f

xi,xi+1,yf,yf +r

n0−1 i=0

xi−xf,

(6.32) n0f

xf,xf,yf,yf

=n0fr

xf,xf,yf,yf

≤2M+inf





n0−1 i=0

fr

pi,pi+1,yi,yi+1

: {pi}ⁿ_i=0⁰ ∈X ξ,n0







≤2M+

n0−1 i=0

fr

xf,xf,yi,yi+1

=2M+

n0−1 i=0

f

xf,xf,yi,yi+1

−r

n0−1 i=0

yi−yf.

(6.33) It follows from (6.1) and Proposition 5.1 that

n0−1 i=0

f

xi,xi+1,yf,yf

≥n0f

xf,xf,yf,yf

≥

n0−1 i=0

f

xf,xf,yi,yi+1

. (6.34)

Together with (6.32) and (6.33) this implies that

n0f

xf,xf,yf,yf

≥ −2M+n0f

xf,xf,yf,yf +r

n0−1 i=0

xi−xf, n0f

xf,xf,yf,yf

≤2M+n0f

xf,xf,yf,yf

−r

n0−1 i=0

yi−yf, r

n0−1 i=0

xi−xf ≤2M, r

n0−1 i=0

yi−yf ≤2M.

(6.35)