JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS: Vol. 56, No. 2, FEBRUARY 1988

Theories of Pursuit and Evasion' J. MYCIELSKI

2

Communicated by L. D. Berkovitz

Abstract. We give three elementary definitions of a game of pursuit and evasion in a large class of metric spaces. Our definitions are independent of the theory of differential games. We prove that the three definitions yield the same value of the game, and we study this value as a function of the initial positions of the players and their velocities. Several open problems are stated.

Key Words.

Pursuit, evasion, game theory, strategies, payoff functions.

1. Introduction

Our aim is to define and study a function V : M x M x [ O , 1 ] ~ [0, oo], such that V(x, y, v) can be reasonably regarded as the value of a game of pursuit and evasion in a metric space M, where the initial position of the pursuer is x and his maximal velocity is 1 and the initial position of the evader is y and his maximal velocity is v. O f course, all that matters is the case where M is connected by arcs of finite length. Without loss of generality, we can assume that M is endowed with geodesic (i.e., inf arc length) distance. We shall assume that M, with this distance, is complete and locally compact. The intriguing aspect of this subject is that, under those assumptions, V has very natural definitions (Theorems 3.1 and 3.4) and still is not well understood nor practically computable. In Section 5, we shall state some questions which are open already for the case where M is the unit circle

{z: Iz[-< 1}. Our theory is not general enough to subsume all games studied in differential game theory. Some possible generalizations are mentioned in Section 4. This work was supported by an NSF Grant. 2 Professor, Department of Mathematics, University of Colorado, Boulder, Colorado 803090426, USA. 271 0022-3239/88/0200-0271$06.00/0 © !988 Plenum Publishing Corporation

272

JOTA: VOL. 56, NO. 2. FEBRUARY 1988

This paper is a continuation of Refs. 1-3 but is self-contained. The author has benefited from some conversations with G. Choquet, C. RyllNardzewski, and A. Zieba in the 1950's. The proof of Theorem 5.3, which is given here, is due to R. M. Redheffer. Although during the last twenty years the theory of differential games has been developed very much (see Refs. 3-8 and references therein), the author hopes that his elementary approach is still of some interest, especially since his definitions yield two natural sets of strategies, A for the pursuer and B for the evader, which are complete in a sense and such that every pair (a, b) ~ A x B determines a unique pair of trajectories of the pursuer and the evader. This goal is not always achieved in other mathematical treatments of pursuit and evasion.

2. Preliminaries and an Open Problem

M will be a locally compact metric space with distance function d (x, y). We assume moreover that M is convex, i.e., every pair of points in M is contained in a subset of M which is isometric to a segment of the real line. The assumption of convexity does not restrict our theory, since, as explained in Section 1, we can always introduce the geodesic distance and, as is well known, we have the following theorem. Theorem 2.1. For every complete metric space connected by finite arcs, the geodesic distance preserves completeness and yields convexity. We shall also need the following extension of the Bolzano-Weierstrass theorem, Refs. 9 and 10. Theorem 2.2. In a locally compact, complete, and convex metric space, every bounded closed set is compact. We shall also need a consequence of a deep theorem of Martin, Ref. 11 (see also Ref. 12). To formulate it, we need some terminology and notations. For any set A, we consider the space A '° of sequence of elements of A of type co. We introduce in A ~ the PD-topology which is the product topology, A being endowed with the discrete Hausdorff topology (so, a basic neighborhood of a sequence a is the set of sequences which agree with a on a given finite set of indices). Given a function p : A °" -->[0, 1], we define the following zero-sum game of perfect information F(p): Player a picks aoC A; player/3 picks al ~ A; player a picks a2 e A; player 13 picks a3 ~ A, etc. When the infinite sequence a = (ao, a ~ , . . . ) is completed, a pays to/3 the value p(a).

JOTA: VOL. 56, NO. 2, FEBRUARY 1988

273

Theorem 2.3. (Martin). If the function p is Borel-mcasurable relative to the PD-topology, then the game F(p) has a value V c [0, t]. Moreover, either a has a strategy which secures p(a) <- V and, for every e > 0, ¢J has a strategy which secures p(a)>- V - e , or, for every e > 0, a has a strategy which secures p(a)<_ V + e and fl has a strategy which secures p(a)>_ V. We shall not need the full strength of this theorem. An earlier and easier theorem of Davis (Ref. 13), which tells the above in the case where p is the characteristic function of a set of class F~8 or G ~ , would suffice for our purpose. In fact, our functions p will always be of sufficiently low Baire class. Problem2.1. Open Problem. L e t f : X × Y ~ A ~ a n d P C _ A ~ . W e d e f i n e a game G ( f P). Player a chooses x e X, player [3 chooses y ~ Y; both know f and P, but they make their choices without knowing the choice of the opponent. Then, a wins if f ( x , y ) ~ P and fl wins if f ( x , y ) ¢ P . So, G ( f P) is a determined game iff there exists an x ~ X such that f ( { x } x Y) C P or there exists a y e Y such that f ( X x {y}) c~ P = Q. Suppose that G ( f P) is determined for every clopen set P. Must the same be true for all F=-sets P ? For all Borel sets P ? Note that a full positive solution would easily imply the theorem of Martin. Does it help to assume that X and Y are compact metric spaces, f is continuous, and A is finite?

3. General Theory We shall define two games G+(po, qo, v) and G - ( p o , qo, v), where Po, qo ~ M and 0 < v-< 1. Those will be games of pursuit and evasion in a space M satisfying the assumptions of Theorem 2.2. The initial position of the pursuer, called ~r, is Po, and that of the evader, called ~, is qo. The maximal velocity of ~- is 1 and the maximal velocity of -q is v. In G +, ~moves first; and, in G - , ~q moves first. As we shall see in Theorem 3.3, the player who has to make the first move has a slight disadvantage. Definition 3.1. Definition of G*. ~r chooses any point Pl ~ M and then rt chooses any point ql ~ M such that

d( qo, q,) <- vd(po, Pl). Again, ~- chooses any P2 c M and r1 chooses any qz ~ M satisfying d ( ql , q2) <- vd ( pl , P2), etc., for o~ steps. Then, ~- pays to ~ the value T which is defined as follows. If

!imood(p~, %) = O,

274

JOTA: VOL. 56, NO. 2, FEBRUARY 1988

then

T= ~ d(pi, pi~-l); i=0

otherwise, T = oo. It is clear that it is in the interest of ~r to minimize T, the time of his run. Definition 3A was given in Ref. 1. Definition 3.2. Definition of G - .

r/chooses any q~ ~ M and tl such that

d(po, q~) >- tl >- (1/ v)d( qo, q,); then, ~r chooses any p~ ~ M satisfying

d(po, Pl) <- tl. Again, ~1 chooses any q2 ~ M and t2 such that

d(p,, q2) >- t2 >- (1/v)d(q,, q2). Then, ~" chooses any p2 ~ M satisfying

d(pl, p2) <--t2, etc., for ¢0 steps. Then, w pays to ~1 the value T, where oo

T=~

tk. k=l

We interpret tk as the time ~1 decided to use to move from qk-~ to qk (of course, without exceeding the speed limit v). It is clear that it is in the interest of ~/to maximize T, i.e., the time of his run prior to capture. This definition of G - is an inessential modification of one in Ref. 2. Theorem 3.1. Each of the games G + and G - has a value in [0, co]. If V+(po, qo, v) and V-(po, qo, v) are those values and v < 1, then

V+(po, qo, v ) = V (Po, qo, v)<-d(po, qo)/(1-v). Also,

V-(eo, qo, 1 ) ~ V÷(po, qo, 1). Proof. By Theorem 2.3, both G* and G - have values. To show that V - -< V +, we argue as follows. Any strategy ~ - for ~ in G can be transformed into a strategy 5~+ for r/ in G ÷, which secures the same lower b o u n d for T. Let us outline this construction. ~ equipped with ~ - received in G+ more information than

JOTA: VOL. 56, NO. 2, FEBRUARY 1988

275

needed to apply E - , and the only modification that is needed for G + is the following. ~ may be forced to name some intermediate points, instead of those which would be chosen by ~ - . In fact, in G +, ~r may prohibit ~7 from completing a Y.--step. Then, ~/should choose a step moving as close to his E - - g o a l as permitted by the rules of G +. Or else ~ could have given to more time than needed for one E--step. Then, ~ should complete as m a n y E--steps as possible (which need not be a whole number); to do this, ~7 must imagine a polygonal line whose vertices are the choices of ~r, and must imagine additional choices of 7r along this line which partition it into intervals whose lengths are dictated by E - . This concludes the definition of the strategy Y~+ for rt for G +. Now, it is clear that, if E - did secure T_> V - e in G - , then ~+ also secures T>_ V - - e in G +. Hence, V + ~ Vfollows. Now, consider the following trivial strategy for ~r in G+: Pr,+l = q,,

for all n.

It is clear that this strategy secures T ~ d ( po, qo) + vd ( po, qo) + v2 d ( po, q~) + " . . .

Hence, if v < 1, V +~ d ( p o , q0)/(1 - v).

It remains to prove that V +-< V-, for v < 1. We claim that any strategy ~ - for ~r in G - can be transformed into a strategy ~+ in G + which yields almost the same u p p e r bound for T. In fact, let them play G +, and let ~r choose t > 0 and imagine that they play G • and that ~ declared t~ = t and chose q~ = qo. Then, ~r moves according to E - , choosing, say, p~. Now, 71 chooses what 7r imagines to be q2 (and really is q~) and imagines that declares again t2 = t. Since they are playing G +, r/ had to satisfy d ( ql , q2)-< vd ( po, p~) <- vt2.

Thus, ~r can still believe that they are playing G - and continues playing in the same way using Z - . As shown above, v - ~ v + <__d ( p o ,

qo)/(1 - v),

so we can assume that E - secures T <- V - + e < a z Therefore, since t~ = t, t2 = t , . . . , there exists

for ~r, for some e > 0 .

n~l+(V-+e)/t,

and hence n < 0% such that 7r imagines that, in his move p,, he caught 7. But in fact 7/ is one t e m p o ahead and the truth is only that the distance

276

JOTA: VOL, 56, NO. 2, FEBRUARY 1988

between them is <-vt. But now ~- returns to reality and uses the trivial strategy defined above. This completes the definition of the strategy ~+. It is clear from this definition and from the property of the trivial strategy proved earlier that, if ~ - did secure T - V - + e, then Y~+ secures

T< - V-+e+vt/(1-v). Since e and t were arbitrary positive numbers and v < 1, we get V + <- V-. E3 Problem 3.1.

Is it always true that

V~(po, qo, 1 ) = V-(po, qo, 1)7 Notation. For v < 1, we denote V + and V- by V or V(po, qo, v), which is permitted by Theorem 3.1. B(x, r) denotes the closed ball with center x and radius r. Theorem 3.2. (i) (ii) (iii) (iv)

For v < 1, the function V is continuous; moreover:

d(x,y) < - V(x,y, v ) ~ d ( x , y ) / ( 1 - v ) ; ]V(x,y~, v ) - V(x, y2, v)l<-d(y~,y2)/(1-v); [V(x~, y, v ) - V(xz, y, v)[-< d(x~, x2)/(1 - v); if 0 < Vl -- v2 < 1, then

V(x, y, v~) <- v(x, y, v2) <- [ ( 1

- ~)/(1

- v2)]

V(x, y, vi).

Proof. (i) This follows immediately from the definition of G - and Theorem 3.1. (ii) This is a Lipschitz condition. Hence, since M is convex, it suffices to prove that it holds locally, say for d(yl, y2) <- d(x, y2). They play the game G-(x, Y2, v), but let ~r choose some e > 0 and imagine that they are playing G-(x, y~, v) and that the first move o f ~/ was from y~ to Y2 and ti = (1/v)d(y~, Y2). He answers accordingly, ignoring the time move of ,/ (possibly for several moves, if T/ forces him to do so) until he completes his desired answer. He continues in that way chasing an imaginary position of 7/ which is d(yl,y2) distant from the real one. (I have omitted some tedious details.) When, after a finite n u m b e r of moves, he got no further than e from this imagined position of ~/, and hence not further than d(y~, Y2)+ e from the true position of ~/, he switches to any strategy which will not let him lose more than e over the infimum of his possibilities in this position. Hence, by (i), zr has a strategy which secures

T <- V(x, y~, v) + e + [d(y~, Y2) + e]/(1 - v) + e. Since e is an arbitrary positive number, this implies that

V(x, Y2, v) <- V(x, y~, v) + d(y~, y2)/(1 - v).

JOTA: VOL. 56, NO. 2, FEBRUARY 1988

277

By s y m m e t r y we can prove a similar inequality with y~ and Y2 interchanged. So, (ii) follows. (iii) By the definition o f G +, it is clear that

V(x~,y, v)<-d(x~,x2)+

max

y' E B(y, vd ( xbx2) )

V(x2,y', v).

But, by (ii), for y' c B(y, vd(xa, x2)),

V(x2, y', v) <--V(x~, y, v) + vd(xl, x2)/(1 - v). The last inequalities imply that

V(x,, y, v) <- V(x2, y, v) + d(xl, x2)/(1 - v). By symmetry, we can show a similar inequality with xl a n d x2 interchanged. So, (iii) follows. (iv) The first inequality is obvious. To show the second, we consider the game G+(x, y, v2). Let 7r c h o o s e some e > 0, a n d let him imagine that they are playing G-(x, y, v~), i.e., ~- chases an imaginary point q~ which is on some p o l y g o n a l line in M with consecutive vertices y, q~, q2, • • •, but m a y b e b e h i n d %, since its maximal velocity is Vl. Still, o f course,

d(q'~,%)<_

d(p~,pi+~) (v2-v,). \ i=0

As soon as d(p,, q')<_ e, ~r returns to reality and begins to use the trivial strategy. Thus, rr has a strategy which secures

T <- V(x, y, v,) + [ V(x, y, v,)(v2 - v,) + e ] / ( 1 - v2). Since e is an arbitrary positive number, (iv) follows. Problem 3.2.

[_3

Is it always true that

lim V(x, y, v) = V-(x, y, 1)? v1"l

For the games G + and G - , Tfieorem 2.3 can be refined as follows. Theorem 3.3. I f v < 1, ~7 has a strategy for G + which secures T-> V and 7r has a strategy for G - which secures T ~ V. Proof. By T h e o r e m 3.2, for v < 1, V(x, y, v) is continuous. Hence, by T h e o r e m 2.2, ~7 has optimal moves in G +. For the same reasons zr has optimal moves for G - . D

278

JOTA: VOL. 56, NO. 2, FEBRUARY 1988 Notation.

We let

a_b=~a-b, /

O,

ifa>-b, i f a < b.

Now, we will prove a theorem which yields a third definition of V for v < 1. This new definition does not use any game-theoretical concepts. Theorem 3.4. The function V: M × M × [0, 1) ~ [0, ~ ) satisfies and is uniquely determined by the following four conditions [we will write V(p, q) for V(p, q, v)]: (i) V(p, p) = 0; (ii) V(p,q)-- d(p,x)~maxy~B(q.vd(p,x)) V(x,y); (iii) V(p, q)>-d(p, q); (iv) V(p,q) "-t>--minx~B(p.~)V(x,y), whenever d(q,y)<-vt. Proof. First we check that V satisfies ( i ) , . . . , (iv). Both (i) and (iii) are visible. (ii) Consider G+(p, q, v). Suppose that 1r moved from p to x. Then, by the definition of G ÷, the compactness of B(q, vd(p, x)) (Theorem 2.2), and the continuity o f V(x, y) (Theorem 3.2), r / m u s t be able to move from q to y such that

(iv) declared

d(q,y)<-vd(p,x) and V(x,y)>_ V(p,q) -d(p,x). Consider G-(p, q). Suppose that ~1 moved from q

to y and

t>_(1/v)d(q,y). Then, again by Theorems 2.2 and 3.2, ~ must be able to move from p to some x such that

d(p,x)<_t

and

V(x,y)<-V(p,q)- t.

It remains to prove that V is the only function satisfying ( i ) , . . . , (iv). Let V' be another such function. We claim that (i) and (ii) for V' imply 0-< V'-< V. Indeed, (ii) for V' yields a ~trategy for ~7 in G + which secures that V' does not decrease more than d(p, x). By (i) for V' this strategy used repeatedly secures T-> V'. Hence, V>- V'. In a similar way, (iii) and (iv) imply V ' >- V. Indeed, (iv) for V' yields a strategy for 7r in G - which secures that V' will decrease at least by t if T-< V' and will decrease to 0 if t > V'. By (iii) for V', this strategy used repeatedly secures T < -- V'. Hence, V -< V'. E] In the case where M is a closed convex set in R ~ (bounded or not) with the Euclidean distance, Theorem 3.4 yields a well-known consequence.

JOTA: VOL. 56, NO. 2, FEBRUARY 1988

Corollary 3.1.

279

If V is differentiable at (Po, qo), then

IIv glL = 1 ÷ vlfvovll,

at (Po, qo),

where V~ denotes the gradient operator restricted to the subspace of the variable u (the other variable being fixed) and !t" II is the Euclidean norm. Proof. If V is differentiabie at (Po, qo), then, by (i) and (iii), V(po, qo) > 0. Now, the corollary follows from (ii) and (iv) by letting d( p, x) with respect to t converge to zero. For example, (iv) yields -I > -

rain [ V ( x , y ) - V ( p , q ) ] / t

x~B(p,t)

>- rain [ V ( x , y ) - V(p, v)]/t+v[V(p, v ) - V(p, q)]/vt. x~B(p,~)

"

"

Hence, since r/ can declare

t=(1/v)d(q,y), we have - - t >- - t l V p V l l

+ ~)[tVqVli.

The reverse inequality follows in the same way from (ii). However, as we shall see in Section 5, V need not be differentiable even in the interior of M x M and away from the diagonal p = q. Hence, Theorem 3.4 gives more information than Coro!lary 3.1. Corollary 3.t is also valid in many cases where M is not a convex part of R ", but some manifold with boundary. It may be interesting to state the following informal assertion and proof.

Parable 3.1.

The optimal strategy for ~r is suggested by the differential

equation

[, = -v

v/llV

vll,

and the optimal strategy for ~q is given by the differential equation = vv

Reasoning.

v/tlv

vll.

The extrema

rain max( d / dt ) V(p + Ikt, q + qt)[,=o 0 and max min(d/dt) V(p +/~t, q + c~t)I,=o,

JOTA: VOL. 56, NO. 2, FEBRUARY 1988

280

under the conditions

liplI-
IlqlI-< v,

are attained f o r / i and t~ given by the formulas of Parable 3.1. Remark 3.1. Both Corollary 3A and Parable 3.1 are well known in the theory of differential games,.but neither can be made sufficiently general and precise without some rather tedious definitions. See also an example of Zieba (Ref. 14) concerning the necessity of using discontinuous strategies, which shows the informal character of Parable 3.1.

4. Generalizations One generalization of the above theory which does not require much change in the theorems and proofs is to allow several pursuing and evading points (this will be used in Section 5). Another would be to allow convex spaces M~, Mn _ M to which p~ and q, respectively would be confined. Some generalizations are made by Ryll-Nardzewski (Ref. 3). For example, he introduced two metric spaces, one for the pursuer and one for the evader, and an arbitrary closed subset of their product as the set of final (capture) positions. It is natural to introduce such configuration spaces if we want to study pursuit and evasion of several points by several points. He introduces also asymmetric distance functions which may reflect, for example, the difference of cost or velocity between running uphill or downhill. He allows also for many payoff functions different from our time from start to capture. Many games considered in the theory of differential games do not fall under the present scheme and would require some generalizations of this kind. In this paper, we shall not develop any generalization, although many are tempting. We are more interested in the open problems (Problems 2.1, 3.1, 3.2, and 5.1 below). 5. Examples Example 5.1. Two Pursuers Running after One Evader in the Plane. Let one of the pursuers be faster than the evader and the other be at least as fast. M is the Euclidean plane. We imagine three circular discs centered at the initial positions of the pursuers and the evader, which are of radius zero at time zero, but are expanding with the maximal velocities allowed for the corresponding points. Let p be any of the points in the expanding disc of the pursuer. We consider a generalization of the game G - which is

JOTA: VOL. 56, NO. 2, FEBRUARY t988

281

appropriate for this game (see Section 4). Theorem g.L (Zieba). The best strategy for the pursuers and the evader in the above game of type G - is to run full speed toward some such p and, unlike in Theorem 3.3, player ~ does not have to tose any e > 0. The proof is easy. Example 5.2. One Pursuer Running after One Evader on a Closed HalfPlane. Let the pursuer be faster than the evader, i.e., v < 1, and let M be the closed Euclidean half-plane. We imagine again a closed ball in M expanding around the initial positions of each player as in the previous example, and again we define p in the same way. In other words, p is any point in M which is the most distant from qo and has the property

d(qo, p) = vd(po, p). We consider the corresponding game of type G - . Theorem 5.2. (Zieba). Theorem 5.1 is also valid for this game. Again the proof is quite easy. For example, if P0 and qo are both on a straight line perpendicular to the edge of M, the distance of Po to the edge is a, and the distance of qo to the edge is b, then

[[(a2-b2)/(1-v2)]~/2, V(po, qo) = [1 a _ b]/(1 - v),

ifb~av, if b >- av.

It follows that V(po, qo) is not differentiable at (Po, %) if b = av. Remark 5.1. Zieba's definitions of the games were different from our G - and his proofs of theorems 5.1 and 5.2 had to involve somewhat tedious arguments. Example 5.3. One Pursuer Running after One Evader in a Closed Circle. Now, we introduce a game considered long ago by Zieba and also in Refs. 2 and 15, which is the simplest example in which the function V is not explicitly known. Let

M : {:: Izt-< 1) in the complex plane, and let

d(x, y) = Ix - Y l .

282

JOTA: VOL, 56, NO. 2, FEBRUARY 1988

We assume as always that v -< 1 and Po, qo ~ M, and we have the two games F+(po, qo, v) and F - ( p o , qo, v) of types G + and G - , respectively. Let V~ and Vr be their values. O f course, by Theorem 3.1, V~ = Vr for v < 1, so in that case we denote again both values by Vr.. For those games, the e's of Theorem 2.3 (which remain after Theorem 3.3) appear to be essential. By Theorem 3.1, for v < 1, the trivial strategy (which was defined in the p r o o f of Theorem 3.1) yields Vr(Po, qo, v ) = ]Po- q o ] / ( 1 - v), whenever [Po-a]-> ]P0- q0[/(1 - v), where ta[ = 1 and qo belongs to the straight segment poa. Theorem 5.2 yields certain upper estimates of Vr, since it is easy to prove that Vr(Po, qo) -< VN (po, qo), where VN is the value of the game on any closed half-plane N including M (see Ref. 2). For the games F + and F-, both Problems 3.1 and 3.2 are solved by the following theorem. Theorem 5.3.

If Po ~ qo, then

lim Vr(Po, qo, v ) = Vr(Po, qo, 1) = V~(po, qo, 1) =oo. L,'~I

Proof.

We will show first that

Vr(Po, qo, 1) = oe,

for Po ~ qo.

So, we study a game of type G - . I f qo is on the boundary of M, r/ must move to the interior of M and make a small enough step and declare a small enough tl so that 7r Cannot capture him in his first move. If q0 were not on the boundary of M, the argument would be similar. After the answer of 7r, rl imagines a circular disc D of radius 2e, e > 0, such that ql is in the center of a radius of D and e is small enough so that D C_M. Furthermore, imagines a straight line L~ through ql and the center c of D. Then, ~7 looks at which side of L~ is Pl and steps to the other side of L1 in such a way that the segment qlq2 be perpendicular to L1 and tq2-qll = e/2. Also, he declares t2 = e/2, which is legal, since v = 1. If it happened that Pl e L~, the side of the step q2 does not matter. In any case, the answer P2 of 7r cannot be a point of capture, because

]p,--qz]>]qt--q21.

JOTA: V O L 56, NO. 2, FEBRUARY 1988

283

Then again, ~ looks at a time L2 through q2 and c and looks at which side of Lz is P2- And again, he steps to the opposite side and so that qaq3 be perpendicular to L2 and [q3- q2] = e/3, he declares t3 = e/3, etc. To sh6w that this strategy for ~/is always applicable, it suffices to check that t % - c[<2e,

for all n.

But, of course, 1 1 1 \t/2 1 + - + - +9 ' 4 ..+n~ !---~1 < ~ r / , / 6 < 2 e .

]q,-c[=e

On the other hand, this strategy secures E

(!+!+. ) .o

\2 Hence,

~-=OO.

3

VF = co.

By the last part of Theorem 3.1, we have also V~ = oo. It is routine to analyze the above strategy in order to show also that lim Vr(Po, qo, v ) = oo. The above strategy for F- was communicated to the author by R. M. Redheffer. It simplifies an earlier argument of Besicovitch, described by Littlewood in Ref. 15. We list certain questions about those games, some of which were already stated in Ref. 2. Problems 5.1. (i) What is the rate at which Vr(po, qo, v)-~ec as v~l? (ii) Let Po = 0 and v < 1. Does Vr(0, q0, v) increase as ]q0[ increases from 0 to 1 ? (iii) Is Vr(0, qo, v) differentiable in the domain !qot> 1 - v ? By the statement made prior to Remark 5.1, Vr(0, qo, v) is not differentiabte in qo for lqo]= 1 - v. This was overlooked in Ref. 2. (iv) A natural strategy for 1r in F-(0, q0, v) is the following: If you can capture, capture! If not, move to the radius of M on which the evader finds himself and as close to him as permitted by the rules of the game. Is this an optimal strategy for % in other words, does it secure T <- V-(O, q0, v)? It would not always be optimal if Po = 0 was not assumed. (v) Does Theorem 5.3 generalize to arbitrary surfaces? We know only the following theorem.

284

JOTA: VOL. 56, NO. 2, FEBRUARY 1988

Theorem 5.4. (W. F. Taylor and J. Mycielski). Theorem 5.3 is true in any spherical cap and any disc in the hyperbolic plane. The p r o o f is an easy modification of the p r o o f of Theorem 5.3, using the spherical and hyperbolic analogues, cosacosb=cosc

and

coshacoshb=coshc,

of the Pythagorean equation, a2 + b 2 = c 2,

for right triangles.

References i. MYCIELSKI, J., Continuous Games with Perfect Information, Advances in Game Theory, Annals of Mathematical Studies, Vol. 52, pp. 103-112, 1964. 2. MYCIELSKI, J., Pursuit and Evasion in a Circle, American Mathematical Monthly, Vol. 91, pp. 415-416, 1984. 3. RYLL-NARDZEWSKI, C., A Theory of Pursuit and Evasion, Advances in Game Theory, Annals of Mathematical Studies, Vol. 52, pp. 113-126, 1964. 4. HAJEK, O. Pursuit Games, Academic Press, New York, New York, 1975. 5. KUHN, H. W., and SZEG~3, G. P., Editors, Differential Games and Related Topics, North-Holland, Amsterdam, Holland, 1971. 6. ELLIOTT, R. J., and KALTON, N. J., The Existence of Value in Differential Games, Memoirs of the American Mathematical Society, No. 126, pp. iv+67, 1972. 7. ZAREMBA, L. S., Existence of a Value in Games Governed by Generalized Differential Equations, Systems and Control Letters, Vol. 4, pp. 237-241, 1984. 8. ZAREMBA, t. S., Existence of Value in Generalized Pursuit-Evasion Games, SIAM Journal on Control and Optimization, Vol. 22, pp. 896-901, 1984. 9. LELEK, A. and MYCIELSKI, J., On Convex Metric Spaces, IV, Fundamenta Mathematicae, Vol. 61, pp. 171-176, 1967. 10. MYCIELSKI, J., A Generalization of the Bolzano- Weierstrass Theorem, Notices of the American Mathematical Society, Vol. 13, p. 130, 1966. 11. MARTIN, D. m., Borel Determinacy, Annals of Mathematics, Vol. 102, pp. 363-371, 1975. 12. MARTIN, D. A., lnfinite Games, Proceedings of the International Congress of Mathematicians, Helsinki, Finland, pp. 269-273, 1978. 13. DAVTS, M., lnfinite Games with Perfect Information, Advances in Game Theory, Annals of Mathematical Studies, Vol. 52, pp. 85-101, 1964. 14. ZIEBA, A., An Example in Pursuit Theory, Studia Mathematica, Vol. 22, pp. 1-6, 1962. 15. LITTLEW'OOD, J. E., A Mathematician's Miscellany, Methuen & Co. Ltd., London, England, pp. 135-136, 1953.