4...

  
      

                   

KI; Elfin" 1 3.1!... I . . 1.331.. 7‘. . .93...“ LrNfl. . ti. 4 . kph-xv. HQfiWNr

..A .3 WI“ P— K

 
 

 

“1.9.1,“...
r1.....

”WWW/1. .Ytt...’

“fr/...:

”whim 4/
wmfivn. .
It.

 

  

    

O. 1
.f .
, 59

£1.39...» .
. .... .AW .
.V :5...

1. v.

I

    
         

         

I,”

 

        
   

 

rub... 3.41113...

15.“.de VI“...
11...er

I

  

ENI

 

Mfr
”rang. z}.
.. huw.w,w...1...wwW WW.

1 11‘ 4a... . War. “arr. 1.»st
Farm.” ruin». W... .pm. WW. ..Wtadcfivwflb
#5. .I. ,.w..r.,am, yd».

 

I

 

    
 

. . .JMW.1W.A.1 -... c
I I t . . ._ . .I.T".'a ’ .Ufllqt‘fl’m

.w.f.. yr r155; 4.1%.“.
I

 

ERffI‘IINGIIERF

 

   

4

        

 

...». . Z .
...",rzkua: n...

 

 

III I

3

 
 

III

N

 

{AELB‘I
I0?
I!

II“:
III
III-I”

II

:I
1; III 7 ..

II

 

e,

‘1'

III
I;
, _ II

1%

 

.1.. l. .. I . I,

 

 

 
 

I... .3 . ; .F. ”maul-1.11. 3‘2... >3 2... ~..£......&.a.:...1 ..x.,...~...:d.fi?».§V, . C ... n . . I ...: . 151i. . Iv.) . ..

 

THcSII LIBRARY
Mfighigan State
University

 

V‘—

’1!

This is to certify that the

thesis entitled

ON Ull‘ll-AL FIELDS FOR ClFFER'LJNTlAL GANLS

presented by

John Walter Wingate
has been accepted towards fulfillment

of the requirements for

H133. degree in Electrical Engineering

Major professor

Date W

0-169

ABSTRACT

ON OPTIMAL FIELDS FOR DIFFERENTIAL GAMES

by John Walter Wingate

The study of differential games is the study of game
theory as applied to processes of the type considered in
Optimal control theory. Almost all differential games
studied have been two-person zero-sum games” This is due
partly to limitations in general game theory and partly to
the type of differential games most often StUdiGd--pUISth-
evasion games“

The process in a differential game is modeled by vector

differential equations

CLICL
CT‘ X

= f (t, x, u, v) all

where the independent variable t is called the time, x the
state, and u and v are called control variables“ These
variables, u and v, are chosen by two opposing players, one
of whom wishes to maximize and the other to minimize a

functional

J = K (t1, Xét ‘ + L (t, Xitl, uit), v(t)ldt (2)

l)'

which depends on a solution to (l) on a time interval

t0 3 t 5 tlo The initial point (to, xttoll is in a region B

in tx-space, while the terminal point (t xttl)) belongs to

l,

John Walter Wingate

a set T_which may be taken to be part of the boundary of

£0 Functions U(t,x) and V(t,x) which give choices of the
control variables u and v to use at each point of the
region §_are called strategies“ Given a pair of strategies
and an initial point in E, the payoff (2) is determineda

In an optimal field one assumes that there exist
strategies U and V optimal in some sense (this sense being
specified for a particular type of optimal fieldl and a
value function w, also defined on E, The value function
is closely related to the payoff functional (2)“ The
optimal strategies in an optimal field are taken to be
piecewise continuous and have piecewise continuous first
partial derivatives“ The value function is assumed to be
continuous and have piecewise continuous first partial
derivatives.

Two types of optimal fields are considered: one of
which requires the value function to satisfy a saddle-point
condition, and the other of which requires the value
function to satisfy a maximin (or, alternatively, a
minimax) condition, The saddle-point condition is the more
stringent requirement” It corresponds to a solution to the
differential game in pure strategies (that is, those chosen
directly by the player, without the assistance of a random
device). The maximin or minimax optimal fields are
applicable to differential games which do not have solutions

of this type.

John Walter Wingate

The results obtained are extensions of optimal field
and Hamilton—Jacobi theory for optimal control problemso
The extension is to fields defined by saddle-point con-
ditions and to fields defined by maximin conditions,
Several useful discontinuity conditions, distinguished by
the behavior of the optimal trajectories in the neighbor-

hood of the discontinuity, are also obtained.

ON OPTIMAL FIELDS FOR DIFFERENTIAL GAMES

By

John Walter Wingate

A THESIS

Submittedwto
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Electrical Engineering

1968

3%

ACKNOWLEDGMENTS

The author wishes to thank the members of the
guidance committee, Dr. R. C. Dubee, Dr. T. Guinn, Dr.
H. G. Hedges, Dr° H. E. Koenig, and Dr. P. K. Wong for
their advice, aid and understanding during the time of
his doctoral candidacy. He wishes to express particular
thanks to Dr. Theodore Guinn for the able direction he
gave in carrying out the research for this thesis.

The author also wishes to thank the National
Science Foundation for fellowship support and the Depart-
ment of Electrical Engineering for assistantship support

while he was a graduate student.

ii

TABLE OF CONTENTS

ACKNOWLEDGMENTS .
LIST OF FIGURES . . . .
Chapter

I. INTRODUCTION . . .

1.1 Game Theory, Optimal Control Theory, and
Differential Games . . . .
Auxiliary Theorems . . . .

1.2

II. DEFINITIONS AND SOLUTION CONCEPTS FOR

DIFFERENTIAL GAMES

2.2
2.3

2.1 Definition of a Differential Game

Solution Concepts . . . .

Examples . . .

O O O 0 0

III. OPTIMAL FIELDS FOR SADDLE POINTS

3.1 Optimal Fields in Control Problems
3.2 Optimal Field for a Saddle Point

IV. MAXIMIN FIELDS

V. TRANSVERSALITY AND DISCONTINUITY CONDITIONS

5.1 Transversality Conditions . .
Manifolds of Discontinuity . .

5.2
VI. CONCLUSIONS . .
6.1 Conclusions . .
6.2 Further Research
BIBLIOGRAPHY V . .

O O 0 0

iii

Page
ii

iv

NH

28

28
AA

50
59

59
67

90
110

110
11“

125

125
126

128

LIST OF FIGURES

Figure Page
2.3.1 . . . . . . . . . . . . . 52
203.2 o o o o o o o o o o o o o 52

2.3.3 . . . . . . . . . . . . . 52

iV'

I. INTRODUCTION

1.1 Game Theory, Optimal Control Theory,
and Differential Games

 

 

The theory of differential games brings together two
originally separate branches of applied mathematics--the
theory of games and optimal control theory. It draws on
ideas and concepts from both of these fields.

Game theory had its origins in the work of von Neumann
who wrote a pioneering article in 1928 [30]. During the
Second World War he wrote, in collaboration with Morgenstern,

the classic book on the subject, Theory of Games and

 

Economic Behavior [31].. Almost all later workers take as
a basis the theory developed by von Neumann and Morgenstern.
A game is a situation in which several persons make
decisions. The essential feature of a game is that these
decisions must be made on the basis of conflicting
interests. (One could consider a game in which the
decision makers have completely parallel interests as a
degenerate case.) A game must have well-defined outcomes
which depend on the decisions made and perhaps on chance
factors. Each of the players (the decision-makers)
evaluates these outcomes according to some criterion. In
general, the players will not agree in their evaluations;

this is the source of conflict. Normally the evaluation

assigns a real number to each outcome of the game. If a
player prefers outcomes with higher numerical values, the
evaluation is called his payoff; if he prefers lower
numerical values, the term used is 3953. Games are
usually presented in terms of payoffs rather than in
terms of costs. The decisions made by the players, and
perhaps chance occurrences, determine the outcome of the
game, and hence the payoffs. No one player controls the
game completely. In general his payoff is as much deter-
mined by the actions of the other players as by his own.
Game theory addresses itself to the problem of prescribing,
in some fashion, rational behavior under those circum-
stances.

Most games are defined by a set of rules. The rules
prescribe the structure of the game, the manner in which it
is played, which player must make a decision at any par-
ticular stage of the game, the information available to
this player--in fact everything but the actual choices
made by the players (and by chance). Games which are

described in this manner are said to be in extensive form.

 

After a long careful development, von Neumann and Morgen-
stern give a precise, axiomatic definition of a game in
extensive form [31, section 10]. In a game in extensive
form, a plan detailing what choice to make, on the basis
of the available information, under every situation which

could arise, is called a strategy. If each player chooses

a strategy, the course and outcome of the game are deter-
mined, except for chance effects. These chance effects
can be eliminated by considering the expected values of
the payoffs instead of the payoffs themselves. An equiva—
lent game can be generated in which each player makes one
choice only, from the set of all strategies available to
him, in complete ignorance of the particular choices of
the other players. He will, however, be aware of the
strategies available to the others (through knowing the
rules of the game, for instance). This equivalent game is

in the normalized form. More precisely, a game for N

 

players in normalized form consists of:

N sets of strategies Si’ i = l, ..., N;

N real-valued payoff functions P , i I l, ..., N,

i

with the domain of each of these functions being

S Q S x ... XS

1 N'

Each player chooses independently a strategy from his

set of strategies. If s are the strategies

1’ s2, ..., sN
chosen, 5 = (81, 52, ..., sN) is the corresponding point in
S, and Pi(s) gives the (expected value of the) payoff to

the 1th player corresponding to the play of the game in which
these strategies are used.

Each of the two formulations has its advantages: the

normalized form is most useful when considering features

common to all games, and the extensive form emphasizes the
peculiarities of individual games.

A satisfactory solution theory does not exist for
general games. One does exist for certain types of two-

person zero-sum games. A zero-sum game is one in which

HMZ

Pi(s) = O for all scS.
=l

An N-person game which is not a zero-sum game can be made

into one by adding another player who has the payoff

PN+l(s) = — Pi(s).

l-“MZ

=1

The set of strategies for this player, S is, of course,

N+1
empty. N-person games are generally studied by dividing
the players into two coalitions and considering the
resulting two—person games for various divisions of this
sort. It can be seen then that the theory of two-person
zero-sum games plays a large part in the theory of games
as a whole.

The basic idea behind the solution to a two-person
zero-sum game is guaranteed payoff. If the first player

chooses a strategy 5 his payoff could be as little as

l

min Pl (81,,52).

$2682

However, by choosing his strategy to be 51, the maximin

strategy, where

min P (sl,S2) = max min Pl (81,82) = E»

1
82832 s as 3 £82

1 l 2
he can guarantee that his payoff will be at least E)
Likewise the second player can guarantee that his payoff
is at least

max min P (s s ) =-min max P (s ,s )='- W.
s as s as 2 l, 2 s as l 1 2

2 2 1 1 82632 1 1
In Chapter II it is shown that u S G. If E = 1.7, the first
player can gain, and the second player can lose, neither
more nor less than t, provided both players use their
maximin strategies. In this case, the solution consists

of the maximin strategies, El, E and the payoff Pl (Ei,§é),

2
called the yalug of the game.

If wg<W} in certain types of two-person zero-sum
games, such as those in which both players have a finite
number of strategies, the sets of strategies can be
extended in such a way that_with respect to the extended
strategies the game has a solution. Usually one considers
the set of probability distributions over the original set
of strategies (called page strategies) as the extended set

of strategies (called mixed strategies); "Every two-person

zero-sum game in which each player has a finite number

of strategies has a solution in mixed strategies. This‘
result was first obtained by von Neumann [30].

Game theory is only one of the two areas which con-
verge in differential games. The other is optimal control
theory.

Optimal control theory is concerned with finding a
maximum or a minimum (usually a minimum) of a functional
such as
t

l

K (t1, x(tl)) + I L (t, x(t), u(t)) dt,

t0

where x(t) and u(t) satisfy the differential equation

9.22.

dt = f (t, x, u).

The points (to, x(t0)) and (t1, x(tl)) are constrained
by boundary conditions and the functions u must belong to
a certain class of functions (such as measurable functions,
or piecewise continuous functions) and must satisfy certain
constraints. Optimal control problems can be translated
into problems in the Calculus of Variations, and optimal
control theory developed by interpreting variational
theory. This has been done, for example, by Hestenes [15]
and Berkovitz [1]. Alternatively, the theory can be
developed more or less independently of Calculus of Vari—

ations as it is usually formulated. This-is the approach

taken by Pontryagin and his colleagues in the Soviet Union
[36]. In recent years Optimal control theory has expanded
rapidly.

From the point of view of game theory an Optimal con-
trol problem is a one player game. If additional players
are added to problems to this type, a differential game
results.

A differential game is a game in extensive form, or
rather a family of such games indexed by points (initial
conditions for the differential equations) in a region E
to tx-space. Instead Of having a single value (if the game
has a solution), the game has a value function whose domain
is this region; that is, the game associated with the point
(t, x) has the value W(t, x). A play of a differential game
evolves as a process continuous in time modeled by a system
of differential equations in which certain parameters,

called the control variables, are chosen by the players.

 

The solution to the system of differential equations is a
curve lying in the region F, and the transition between
points on this curve provides the link between members of
the family of games. The players receive payoffs which
are functionals of the solution to the differential
equations and of the control variables. These functionals
are of the same type as those considered for performance

criteria in Optimal control theory.

For reasons which have been mentioned previously,
almost all differential games studied have been two-person
zero-sum games. The differential games covered in the
succeeding chapters are all two-person zero-sum games.
Accordingly, only one payoff functional is introduced,
and the concepts of maximin points-and equilibrium points
are discussed with respect to this single payoff. This
is not an important restriction since most Of the solution
concepts for general games rely on equilibrium points or
maximin points of the type considered [1“, 26, 29, A3].
The appropriate modifications for more general games
readily suggest themselves.

The study of differential games was initiated by
Isaacs in a series of Rand reports [19]. These_were
later collected with additional material and published as
a book [20]. Differential games were treated in a series
of articles in the Contributions to the Theory_of Games,
volume III by Fleming [7], Scarf [H2], and Berkovitz and
Fleming [5]. Berkovitz, in later articles [2, 3] in 196“
and 1967 entended the class of games covered. His approach
is to show that under certain restrictions on the types
Of discontinuity allowed in the controls that the differ-
ential game has an associated optimal field. In-this
thesis, such optimal fields are considered per s2) and the
necessary conditions Obtained for these fields can be

applied to any differential game which has an associated

optimal field, whether or not it satisfies the discon-
tinuity conditions Of Berkovitz. These Optimal fields are
an extension of the type Of Optimal field considered by
Hestenes for Optimal control problems [16].

Differential games can be approximated by difference
games. Fleming [8, 9] has investigated conditions under
which the solutions to a sequence Of approximating games
converge to the solution of the differential game.
Meschler [27] has used a method based on Fleming's work
to compute the solution to a specific differential game.

Many of the differential games studied have been
pursuit-evasion games, in which one controlled object
pursues another controlled Object taking evasive action.
Most Of the work done in the Soviet Union has dealt with
pursuit games. Kelendzheridze, in an article [21], and
also in a section of the well-known book by Pontryagin
33 31. [36], considered a class of pursuit—evasion games.
His work was followed by further developments by Pontryagin
[37, 38], Petrosyan [82, 33, 3A, 35] and others [23, 24,
25]. A differential pursuit game of prescribed duration
was studied by HO, Bryson and Baron [18] to illustrate
conjugate point conditions and the use of the_matrix
Ricatti equation in differential games. Since in most
cases in pursuit games, the capture will occur on the
boundaries of the attainable sets for the pursuing and

evading Objects, it is useful, as in Optimal control

lO

theory, to study boundary arcs in differential games. This
has been done by Guinn [13]. More general (i.e., those

not necessarily involving differential equations) pursuit
games have been studied by Zieba [A7, 48], Mycielski [28],
Ryll-Nardzewski [40] and Varaiya [A6].

Differential games have also been studied in con—
nection with minimax problems in Optimal control [10, ll,
12, 22], and with Optimal control problems involving
uncertainty [39, Al]. In the latter case it would seem
useful to consider one of the players, "Nature," as being
indifferent to the outcome. In such a two-person nonzero—
sum game the payoff to Nature may be taken to be a con—
stant function--say zero. Optimal control problems of
this type are problems Of guaranteed performance rather
than problems requiring a saddle-point for a solution.
This also appears to be the approach taken by Pontryagin
[37, 38], and Krasovskii, Repin and Tret'yakov [25] to
pursuit problems.

Optimal fields can be defined for such problems
also, even when a saddle-point does not exist. This is
done in Chapter IV of this thesis. As was mentioned
previously, the optimal field theory presented in Chapter
III is closely related to the work of Berkovitz [3] and
is a direct extension of the optimal field theory used by
Hestenes [16]. The optimal fields are studied by them-

selves without direct reference tO a differential game.

11

However, to apply to a differential game the Optimal
strategies for the field must be the Optimal strategies for
a differential game--that is they must be functions with
domain F giving the Optimal control at each point (t, x)
Of E. Also the value function for the field must be the
value function for the game. This game must have the

same integral payoff functional and satisfy the same con-
straints as those used in the Optimal field. Berkovitz
[3] Obtains conditions equivalent to the existence Of an
Optimal field when the Optimal strategies satisfy certain
conditions on the form Of their discontinuities. Other
strategies, however, need not satisfy these conditions.
The discontinuity conditions are not needed, if one starts
with the optimal field rather than with the differential
game.

An excellent overview of differential games is the
survey paper by Simakova appearing in Automation and Remote
Control [HA]. In the article she pays particular attention
to the work of Isaacs [20], the convergence theory of
Fleming [8, 9], and the pursuit games considered by
Pontryagin [37, 38].

The second chapter of this thesis presents a defini-
tion of a differential game with discussions Of the con-
cepts introduced in the definition, and considers the
solution of a differential game in terms of maximin points
and equilibrium points (which are saddle-points in two-

person zero-sum games). In the third chapter, after

12

a preliminary section introducing optimal fields for
control problems (following Hestenes [16]), optimal fields
for saddle-points~are defined and necessary conditions for
such fields are derived. In the fourth chapter, a similar
procedure is carried out when one of the optimal strategies
is a maximin strategy and the other is a strategy which
minimizes the payoff when this maximin strategy is used.
In the chapter following this one, transversality condi-
tions and several conditions applicable to discontinuities
in the strategies are Obtained. Hestenes [16] does not
consider Optimal fields with discontinuous strategies.
Strategies which are piecewise continuous and have piece-
wise continuous derivatives are considered in Chapters
III, IV and V. This represents an extension of Hestenes'
work. Berkovitz [3] considers games with saddle—points.
Consequently, many of the theorems in Chapter III are
similar to theorems Obtained by him under somewhat dif-
ferent hypotheses. He does not however consider maximin
strategies apart from saddle points. Nor, in connection
with optimal fields, does anyone else. The results in
Chapter IV, are, to the author's knowledge, new, and
similar results have not appeared elsewhere. Some of the
conditions in Chapter V were obtained by Berkovitz; others
are new.

The next section Of this chapter contains several

definitions and theorems on differential equations.

13

1.2 Auxiliary Theorems

 

The definition of a piecewise continuous function Of’
a scalar variable is well—known. Perhaps not-so well-
known is a definition applicable to functions defined on
a region E'Of points x in En. The definition follows that
of Berkovitz [3] and is based on a decomposition Of the

region A.

Definition: A decomposition of a region‘£_is a

finite collection of subregions {Efa)} such that

(i) Uxm = Z
d.

(ii) x(“>{\ 3(8) = ¢ if a # 8

(iii) each EA“) is connected and has a piecewise

smooth boundary.

By a piecewise smooth boundary it is meant that the boundary
consists of the union of the closures of a finite number of
(n-l)-dimensional manifolds each Of which can be described
parametrically by equations of the form (where x is a

point Of one of these manifolds):

x = X(a), a e A, a region in En-l,

where the function x is 0(1) on A.

14

Definition: A real-valued function g defined on g
is piecewise continuous on I if there exists a decomposition
{X(a)} of E such that for each a there is a continuous

function g(a) defined on Eta} for which

3(X) e g(a)(x), XEXfa)-

The function g is piecewise C(m) if the functions g(a) are

C(m) on the xfaj.
If g is a vector function with real-valued components

it is piecewise C(m)

if there is a decomposition of E for
which each component satisfies the above definition. If
g1, g2, . . . gp are several vector or scalar functions
with the domain I; the C(m)—decomposition associated with
(a)},

these functions [I is the "coarsest" decomposition
for which each component of these functions satisfies the
above definition. By "coarsest" it is meant that any other
decomposition contains a decomposition of at least one of
the xi“).

The following Lagrange multiplier rule is Theorem 10.1
Of Chapter 1 of Calculus of Variations and Optimal Control
Theory by M. R. Hestenes [16]. The statement has been
slightly modified.

Consider the minimization of a function f on a set

S of points u in Eq. The set S is defined by the relations

l5

¢a(u)55 O a 1, ..., m'
(1.2.1)

¢a(u) = O a

m' + l, ..., m

Let uO afford a local minimum to f on S. It is assumed
that f and o? <x= l, ..., m, are continuous on a neighbor-
hood Of uO and are differentiable at uO. Further if
¢a(u0) < O for some particular a, this strict inequality
holds on a neighborhood Of uO and thus does not locally
constrain the points u. Therefore at no, the set S is
locally determined by those a for which ¢a(u0) = 0. It is
assumed in the theorem that this holds for a = l,

000"m.

The theorem is stated without proof.

Theorem 1.1

 

Let uO afford a local minimum to f on S, and suppose

that the matrix

a a
it? (uo) (1.2.2),

Bu

has rank m. Then there exist unique multipliers

ll, ..., Am, with AGZO for a = 1, ..., m', such that

Fuk (uo) = O, k = l, ..., q, (1.2.3)

where

16

If ¢a (uO) < O for some 5‘, one could include this
constraint in F by defining the corresponding multiplier *5

to be zero. In this way one Obtains the corollary:

CorOllary

 

Suppose that at uO, ¢d (uo) = O for r 5 m indices 5.
Then if the matrix (1:2.2) has rank r where the index a runs

over those Elfor which ¢d (u0) = O, the conclusions of the

theorem hold, and in addition

la ¢a (uo) = O, a not summed. (1.2.M)

Theorem 1.2

 

Suppose f, cl, ..., cm are real-valued functions on

a region R of points (x,u) = x1, ..., xp, ul, ..., uq). The

functions f, ca, fuk and (“LR are continuous on R, LetfiO

be the set of points satisfying the relations

(I 7
(1:1, ...,m'

¢

(X,u) —

(1.2.5)

d
c (x,u) = 0 a m' + 1, ..., m.

Let d3, 3 = l, ..., r be the indices a for which
ca (x,u) IIO. (These indices need not be the same for each

point (x,u)). It is assumed that the matrix

 

 

a¢a (x,u) d = 03, j = l, ..., r;
(1.2.6)
k=1, ...,q

17

has rank r at each point (x,u) of 50' Let g be a set con-
tained in the projection Of 50 into x-space, and let U be
a piecewise continuous function with domain g for which

(x, U(x))efiO whenever xeé, with the property that
f(x, U(x)) S f(x,u),xe§, (x,u)eRO. (1.2.7)

Then there exists a unique set of multipliers

la(x), X€£, a = l, ..., m, (1.2.8)
such that if one makes the definition

F(x,u,l) = f(x,u) + ia¢“(x,u)
then

Fu(x, U(x), l(x)) = O, xcfi (1.2.9)
Further, for a = 1, ..., m'

Aa(x) Z O, xsg

and (1.2.10)

Aa(x) 0 whenever ¢a(x, U(x)) < 0.

The multipliers A“ are piecewise continuous on g and are
continuous at each point of continuity Of U.

Pagg£.-—The existence and uniqueness of the multi-
pliers la(x) at each point x of g follow from the rank
prOperties of the matrix (1.2.6) and the Lagrange multi-
plier rule, Theorem 1.1, and its corollary. This theorem

also gives the sign properties (1.2.10).

18

The continuity properties of the multipliers remain
to be proved. TO do this let f’be a point of g and let
3‘: U(f). If f is a point of discontinuity Of U, one of

the limiting values can be chosen. Let c ..., er be

1,
the values of a for which

¢°‘ (m) = 0

There is a subset of g containing f‘on which U and hence

¢a (f, U(fl) are continuous. This subset can be restricted

to a set N containing f such that
¢B (X, U(X)) < O, xeN, B # “3’ j = l, ..., r.

This gives

18(x) = 0 ch, 8 ¢ c3, j = 1, ..., r.

Define

a
k a J —~—
AJ - 3k (X,U), J = l, o , r1 k: l, 000, q.

u

Then

I ¢a(x) Ak # 0 d = a d j = l r (1 2 11)
k J l, O ’ r; , 0.0, ) O O

 

.... C1
at the point x, where ¢§ (x) = cuk (x, U(x)).

19

The determinant in (1.2.11) is continuous in x on N. Con-

sequently, N can be diminished so that (1.2.11) holds on N
Setting

fk(x) = fuk(x, U(x)),

one Obtains

Fuk(x, U(x), A(x)) = fk(x) + la(x) ¢§ (x) = o, xeN.
Since
la(x) = 0 when ¢°‘(x, U(x))< o,
= 0 on N.

Fuk(x, U(x), A(x)) - fk(x) + laiCxl¢k (x)
k
Multiplying by Aj gives

k

fk(x) A, + lai(x)¢:1(x) Ak

J = 0, xeN.
k
J

equations can be solved uniquely for the multipliers la (x).

a
Since the matrix [cki(x)A J is nonsingular on N, these

Furthermore, if f k: ofifi and U are of class C(n)on N, the
u
(n)

Adi are also of class C . In particular, it follows
that the multipliers la have the stated continuity proper-
ties.

This theorem is an extension of the theorem given by

Hestenes in [16; Theorem 4.1 of chapter 5], which covered

the case Of x a scalar.

 

F'q
‘HG’

oucv.

1:
AH-
30V“:

89‘.

f".

0n

20

Theorem 1.3

Suppose that the hypotheses of Theorem 1.2 are
modified so that the functions f and fuk, k = 1, ..., q,
are continuous in u and piecewise continuous in x on 3.
Associated with these piecewise continuous functions there
is a decomposition of R and also a decomposition Of the
set E introduced in the previous theorem, {£1}, such that
f and fuk are continuous in x on each set Of these decom-
positions. To denote the functions continuous in x on E;
which agree with f and fuk on Ei’ one may use f(1) and
£311.). '

Then multipliers la exist with the properties stated
in.theorem 1.2 provided that a point f.on the common
lacundary of £1 and £3 one defines F(x,u,1) to be either

Anetta) + x§1)¢°‘<f,u>

(1.2.12)
or: '

r(3)(f,u) + léj)¢a(f,u)

where léi) and 1:3) are the limiting values Of )‘a at If

frcnn~§. and X respectively. The multipliers la are con-

1 ‘3
tirnaous at each point of continuity in x of U, f, and fuk.

21

32223

One may apply Theorem 1.2 directly to the case where
x is replaced by i: , r by r”) and fuk by fife) for each
£1 in the decomposition of g. Since the resulting multi-
(i) are piecewise continuous on Z: they can be

a 1
combined to form piecewise continuous functions on the

pliers A

set g, This method of combination requires the interpre-
tation (1.2.12) at points of discontinuity of f and fuk.
Some of the theorems in Chapters III and IV make
use of existence, embedding and differentiability theorems
for differential equations. The following theorems are
taken without proof from the appendix to Hestenes' Calculus
of Variations and Optimal Control Theory[l6]. The
hypotheses are weaker than are required for the applications
in the later chapters. Similar theorems with stronger
hypotheses can be found in Bliss [6] and any differential
equations text.

The differential equations, in vector form are

x = f(t,x,).), (1.2.13)

where x is a vector in n—dimensional euclidean space En,
i = dx/dt, and A is an element Of a normed linear space.

For example, A may be a control function_

IA
0‘

u: u(t), a 3 t

with the norm ||u|| = sup I u(t)| on a S t S b. However,

the parameter A is not restricted to control functions.

 

('

()

(J

(9'

22

Although the results are independent of the norm

used, it is convenient to consider the norm
, i = 1, ..., n.

With this norm, a 6- neighborhood Of a point (d,B) in

tx-space is

{(t,x) It-a|<6 and Ix-B|<6}

Hypotheses

 

It is assumed that the real—valued functions f1 in

the differential equations (1.2.13) are defined for all
(t,x) in a region E_Of tx-space and A in a subset of a A
of a normed linear space.

Moreover, to each (a,B)e.F, assume there is a
constant 6 and two integrable functions M(t), K(t) such
that

1. the 6-neighborhood Of (a,8) is in F;

2. For each x in the 6—neighborhood 85 of B and

for each AeA, the functions fi(t,x,A) are
measurable in t on the d—neighborhood d6 Of a

and satisfy
| f(t,x,A) | S M(t) (1.2.114).

on as. Thus f(t,x,A) is integrable on

a-d < t < a + 6 for each x in 85 and A in A;

 

L'n'

a.“

(7'

I

23

3. For each x and y in 86 and each A in A, the

inequality

If(t,x,A)-f(t,y,A)I S K(t)] x—y | (1.2.15)

holds on 06;
4. For each x in 85 and A0 in A

d+6

iiTO |f(t.x,A)—f(t,x,10)| dt = 0. (1.2.16)

a-d

Lemma
Let S be a compact subset Of F_which is convex in x.
Then there is a 6-neighborhood 85 Of S in §_and integrable

functions M(t), K(t) such that
|f(t,x,A) | S M(t) (1.2.17a)

|f(t,x,A)—f(t,y,A)I S K(t) | x-y | (1.2.17b)

hold for all points (t,x), (t,y) in S and all AeA.

6
In the following theorem S is a compact subset Of F_convex
in x. M, K and 6 are related to S as described in the

previous lemma.

Theorem 1.4

 

There exists a constant p>O with p<6 such that to
each point (a,B) in S and A in A there exists a unique

solution

24

x(t,a,B,A), a - p s t 5 a + p
of the initial value problem
dx
d

T: f(t,X,A), X01): 8.

The function x(t,d,B,A) is a continuous function of its

arguments on the set

lt-al S. p, ((1,8) 5 S, AEA

Let AO be a fixed element Of A and let

a: x(t), a 5 t s b

be a solution of the differential equations

Q10:
('1‘ >4

= f(t,x,AO). (1.2.18)

This solution must lie in F. The closure S of an e-
neighborhood of the points (t, x(t)) Of the arc 5‘18 in F.
The Lemma and Theorem 1.4 can be applied to this set S.
Using the existence theorem, the function x(t) can be

extended uniquely so as to satisfy (1.2.18) on aep$t$b+p,
where 958 . Define

b+p
G(x,A,AO) = If(t,x(t),A) - f(t,x(t),A ) | dt.

a-p

 

.r‘j

r)

25

One can establish the following embedding theorem.

Theorem 1.5

 

There is a positive number 0 such that through each

point (d,8) satisfying with A
a-psasb+p, IB—x(a)| < o, IA-AOI < o (1.2.19)

there passes a unique solution
y(t9a389)\)) a-p‘tsb+p)

Of the equations

DID-
('l‘ N

= f(t,x,A)

containing the arc g for attSb, A=AO, B=x(d).

The function y is continuous in its arguments.

There is a constant C such that

|y(t,a,B,A) - x(t)| 5 C |B-x(a)| + CG(x,A,AO)

on a—pstib+p. Moreover if (a',B',A') is on the set
(1.2.19), this inequality holds if x(t) is replaced by

y(t,a',8',A') and A by 1'. In addition

0
O.
IB-y(d,d',8‘,A‘)| s lB-B' | + | M(s)ds |

a!

 

_(‘f

Lib

(n

51)

26

Linear differential equations

g—fé- = A3‘(t) xJ + v1(t)

01"

O
x = Ax + v

where A; and v1 are integrable on an interval astsb have
unique solutions, on this interval through each point

(a,8) with asmsb and BeEfi. If A1 and v1 are extended so

J
that they are integrable on the real line —w<t<w, by
defining them to be zero outside [a,b] for example, these
solutions exist and are unique on 4w<t<w.
Suppose now that Hypothesis 3 is replaced by:
3a. At each point (t,x) in the 6—neighborhood of (a,B) and
for each AeA, the partial derivatives fiXJ(t,x,A) exist

and satisfy

lfixfitfid) l 5- K(t). (1.2.20)

It is easily seen that this hypothesis implies the original
hypothesis 3 with K(t) replaced by nK(t).
With this hypothesis the following differentiability

theorem can be obtained.

 

(7

'1

(‘1

27

Theorem 1.6

 

Under the additional hypothesis 3a, the solution
y(t,a,B,A) a-p5t§b+p

of the equations x = f(t,x,A) is differentiable with

respect to B1 at each point (t,c,B,A) on the set
a—pst‘b+p, a-psossb+p, IB-x(d)l < o IA-A0|<c (1.2.21)

and is differentiable with respect to a at each point
(t,a,B,A) on this set at which y(t,a,B,A) exists.

Moreover, the determinant

8yi(t,d,B,A) ¢ 0
383

on the interval a-oitib+p.

One may also note that on the set (1.2.21)

y(a,a,B,A) = B and the matrix

3Y(GSE’B’A) = I, the identity.

 

The theorems quoted are Lemma 2.1, Theorem 3.1, Theorem 4.1,

and Theorem 7.1 of [16, appendix].

II. DEFINITIONS AND SOLUTION CONCEPTS FOR

DIFFERENTIAL GAMES

2.1 Definition of a Differential Game

PlayingVSpace

Unless otherwise stated, x is a vector in n-
dimensional euclidean space, EP, u is a vector in EP,
and v is a vector in ES. Two regions are also considered.
The first, 5, is a region in the (1+n+p+q)-dimensional
space of points (t,x,u,v), and the second, Fwis a region
of points (t,x) in E§+l. In later sections other regions
will be defined as they are needed. It is assumed that
the region F_is contained in the projection of 5 into

tx—space. §.is known as the playing space, for it is in

 

this region that the solution curves of the differential
equations introduced below lie, and this region is the
domain Of the value function and the strategy functions.
The scalar t is called time. The vector x.is known
as the state, a quantity which characterizes the process
which is under the competing control Of the two players.
The time derivative of the state is given explicitly by
the_differential equations modeling the process. One of
the players, henceforth called player One has the variable

u at his disposal. Likewise, player Two controls v. The

28

29

vectors u and v are consequently called the control

variables.

 

Differential Equations
The game proceeds in accordance with a system of
differential equations

1
dx 2
376— = fi(t,Xl,X2,...,Xn,ul,u2,o..,up,Vl,V ...,Vq)

i=1,2,...,n (2.1.1a)

where the f1 are real—valued continuous functions with

domain 3. These differential equations may be expressed

in the vector form

p

x = f(t,x,u,v) (2.1.1b)

The history of choices made by the first player over a

time-interval is a vector function u of time t, t Skit .

0 1
Player Two likewise chooses a function v. A solution Of
(2.1.1) together with the functions u and v is called an
arc. Specifically, a differentiably admissible arc is the

entity

5; x(t), u(t), v(t), t05t$tl

where x is a solution Of (2.1.1) with the control
functions u and v, which are required to be piecewise

continuous functions of t.

30

Since the hypotheses to some theorems are more,
restrictive than for others, differentiability conditions
for the functions f1 are not stated here but are intro-

duced as needed.

Initial Condition

 

The initial condition is a point (to,xo) in the
playing space 3. Separate games start from each point in
F; the differential game is a family Of such games indexed
by the initial conditions (t0,x0). The differential
equations link members Of the family and allow it to be
studied as a whole.

A play of the game continues for t 2.t according to

O
the equations (2.1.1)-with the initial condition x(t0)=xO
until termination occurs, that is until the path x inter—

sects the terminal surface for the first time.

Terminal Surface

 

A play Of the game ends when the path first inter—
sects an n-dimensional manifold T_which is part of the
boundary Of F. The surface 2.13 parametrized by a vector

0 in a region K Of E? by
i i
(t,x)eT C-b t=T(o), x =X (o), i=1,...,n, 02$. (2.1.2)

The functions T and x1 are assumed to be continuous, and

T03 and Xéj to be piecewise continuous.

un—v

«PL—

 

-~\

31

The need for a surface to terminate the game is.
related to the concepts Of strategy and solution Of the

game and is considered in the section on solutions.

Payoff
A payoff is defined for each differentiably admissible

are
x: x(t), u(t), v(t), tOStStl

having
(t, x(t)) cg, tOStStl

and
(t1, x(tl)) sT;

i.e. tl=T(o), x(tl)-X(o) for some cog. 4 (2.1.3)

This payoff, the payoff to player One, is the real-valued
functional

t1
J(x_) A K(O) + L(t,x(t), u(t), v(t)) dt (2.1.1)

to

The payoff to player Two is —J(x). Player One, conse—
quently wishes to maximize J, player Two to minimize it.
In the next subsection piecewise continuous strate—

gies U and V which are functions with the domain E are

32

introduced. With such strategies, the arc x‘is given by
u(t) = U(t, x(t)), v(t) = V (t, x(t)); that is the arc is

given by

x: x(t), U(t,x(t)), v(t,x(t)), tOStStl (2.1.5)

Such an arc may not be unique. There may be several arcs
(2.1.5), depending on which limiting values Of U or V are
assigned to U or V at their manifolds of discontinuity.
If there are v such arcs, they can be designated El’ E2’
..., xv, with corresponding payoffs J<§1)’ J(§2), ...,
J(§$). To indicate the dependence of the payoff on the
initial condition and the strategies, the following

notation is useful:

J‘“) (t0.x0; U.V) A Mia)
t1
= K(c)+ L(t,x(t), U(t,x(t)), V(t,x(t)))dt (2.1.6)
to
where

12(15): f(t,x(t), U(t,x(t)), V(t,x(t)), x(to) = x0.

Strategy and Information

 

A strategy, in the sense introduced by von Neumann

 

and Morgenstern [31], is a plan detailing, on the basis
of the information available to a particular player, what

action he is to take under any conceivable situation in

33

the game. If the information given to the player is the
same for several different situations, he will not be able
to distinguish one from another, and a strategy, based on
the information, will prescribe the same course of action
in each of the indistinguishable circumstances.

A differential game in which each player is con-
tinuously informed Of t and x-—the time and state variables--
is said to be a game Of perfect information. This is
usually understood to mean that any further information is
superfluous and does not aid in choosing the control
variables. Isaacs [20, p. 26] states this idea as follows
(Isaacs considers autonomous differential equations;
consequently the state x provides sufficient information):
"The x1 are descriptive in the following sense. If a play
of a differential game is halted before completion, the
values of xl,...,xn at the time of interruption supply all
the data needed to resume the partie. We mean that if a
new partie is commenced starting with these xi, it will be
tantamount to the part of the original that would have
occurred after the interruption." It is also tantamount
to assuming that Bellman's principle of Optimality, or, as
Isaacs calls it, the tenet of transition, holds. In a
-game Of perfect information, for payoffs of the type (2.1.4)
and dynamic systems modeled by (2.1.1) this is indeed so.
In such games it is also assumed that both players know

the equations (2.1.1), the payoff functional (2.1.4) and

34

any constraints which are operating. They are not aware
of their Opponent's choice of control.

Under these circumstances, a strategy could be
defined to be a real-valued vector function with the domain
F. The choice Of the control variable u for player One at
the point (t,x) in F would then be given by u = U(t,x),
where U is a strategy. Player Two, likewise, would choose
v = V(t,x) for a strategy V defined on F, This thesis
treats games Of perfect information with strategies Of
this type.

If less information is available, strategies could
be defined to correspond to this reduced state of knowledge.
For example, if the players are given only the initial con-
dition and not the subsequent state history, a strategy
could reasonably be only a function of time, say u(t),

t 2 to. Some Of the consequences of games of this type are
considered in the examples in section 2.3.

The players are not normally allowed a completely
free choice in the functions chosen for strategies. They
are usually restricted to belong to some particular class
of functions--the class of piecewise continuous functions,
for example--and to be constrained so that the points
(t,x,u,v) lie in a specified subset of R. The set Of

strategies satisfying these conditions is the set of

admissible strategies.

35

Constraints

 

The constraint subset of R_may be defined in several
ways. One is to define it as the set 50 of points in R

satisfying constraints of the form

(1

¢ (t,x,u) 5 0 c = l, 2, ..., r‘ (2.1.7a)
d“ (t,x,u) = o o = r'+l, ..., r (2.1.7b)
we (t,x,v) S o s = 1, 2, ..., s‘ (2.1.7c)
vs (t,x,v) = o s = s'+l, ..., s (2.1.7a)

The ¢d and we, which are C(l) functions of this arguments

on 5, must satisfy, at each point (t,x,u,v) in 30’ the
conditions that the matrices
2&3 , d = cl, d2, ., a“; J = 1, 2, . .p (2.1.8a)
Bu

and

l, 2, 00., q (2.108b)

[?2;] B = 81, B2, ..., sp; k

have ranks n and p respectively, where a d are

1’ "" W

the indices a for which ¢d (t,x,u) = 0, and Bl, ..., 80

are the indices 8 for which wB(t,x,v) = o. It is clear

that this requires tsp and psq.

36

In a true game, the constraints for each player
Operate independently, for otherwise the players would
have to cooperate in selecting strategies, an evident
absurdity in two-person zero-sum games, where the players

are completely Opposed. Constraints Of the form

¢(t,x,u,v) 5 0 (2.1.8)

which are not independent of either u or v (but not both)
are not allowed. While such constraints are not part of
a game as described here, constraints of this type may be.
Of interest in other situations, for example, in dis-
criminatory games, in which one player makes his choice
of control variable while cognizant of the other players
choice.

If the players are to make independent choices, the

set R , whether or not it is determined by constraints of

0
the form (2.2.7), must be of the form

- q p x
5.0 " (5.1 x 1.3.. )n (E. [12) (2.1.9)

where 51 and 52

space respectively. Let F

are prescribed sets in txu- and txv—

1 (32) be the projection of

El (52) into tx—space. Then it is assumed that the play-

ing space, F is a subset of Fij . Point-to—set functions

1 -2

¢ and.W can be defined on E1 and F2 by

37
<I>(t,x) A {ul (t,x,u) €31} (2.1.10a)

V(t,x) A {vl (t,x,v) e52} (2.1.10b)

The domain Of d is Ed and that Of T is F2. Constraints
of the form (2.1.7) can Obviously be restated in the
present form, since 51 is the set of (t,x,u) satisfying
(2.1.7a) and (2.1.7b), and 32 is the set of (t,x,v)
satisfying (2.1.7c) and (2.1.7d). The statement that

(t,x,u,v) is an element of the prescribed set R is equiva-

.0

lent to the statements
u e c (t,x) (2.1.11a)
v e V (t,x) (2.1.11b)

Elements (t,x,u,v) in 50 are called admissible elements,
and a differentiably admissible arc whose elements
(t,x(t), u(t), v(t)) are all admissible and for which
(t,x(t)e§ is called simply an admissible arc.

The set of all p-dimensional vector functions U

(l)

which are piecewise C on F and which satisfy
U(t,x)e<b(t,x) on F is defined to be the set E. of
admissible strategies for player One. The set V_Of
admissible strategies for player Two is similarly defined

as the set of all q—dimensional piecewise C(l) functions V

with domain F satisfying V(t,x)cV(t,x) on E.

38

An assumed property of 3 is that to each element

0
(F}§;55e§_ with (ngdeg there exists a function u(t) with
’

u(t) = 3 continuous on the set

A = { t | E - 5 S t S E, 5 < 0}
or on the set

E = { t | {‘5 t S E + 5, 5 < 0}
such that the arcs

teA V V82
5: x(t), u(t), V(t,x(t)) or (2.1.12)
teB VVEX

with x(t) = E, exist and are admissible.
There is a similar condition on 52. If there is more than
one arc corresponding to a given Vex, each one must be

admissible.

Attainable Set

 

Definition: Let (t0,x0) be a point in tx-space.
The attainable set A+(t0,x0) is the set of points (tl,xl)
such that there exists a differentiably admissible arc

5: x(t), u(t), v(t) tOStStl (2.1.13)

with the properties

39

t -<-t$t

(t, X(t), u(t), V(t)) 6: o 1’

30,

x(to) = x0, x(tl) = x1.

Likewise, the set A-(t0,xo) is the set of points (tl,xl)
such that there exists a differentiably admissible arc

x; x(t), u(t), v(t) t 5 t 5 t (2.1.1“)

1 O

with the properties

(t, x(t), u(t), v(t))efio for 121 5- t — t0,

x(tO) = x x(tl) = x

O’ 1'

— +
The set A(t0,x0) A.A (t0,x0)|J.A (t0,x0) is called the

extended attainable set. The attainable set at time T,

 

A (T; t0,x0) is the intersection of A(t0,x0) with the
plane t = T.

It can be seen that A-(t0,x0) can be defined as

A-(t0,x0) = {(t,x) | (tO,xO) e ANT-35)}.

Let SO be a given set in tx-space. Then the

extended attainable set for S is defined by

O

A (so) A U A(t0,x0).
(t0,x0)eSO

U0

Similarly

A"(so) A g Ai(t0,x0).
0

If the arcs x defining the attainable set all have
v(t) = V(t,x(t)) for some particular Vex, this restriction
is indicated by the notations A(t0,xO,V), A+(t0,xO,V), etc.

A(t U) is similarly defined.

o’xo’
If the arcs x_are also required to satisfy

u(t)

U(t,x(t)) for some Ueg‘

v(t) V(t,x(t)) for some V8!

on [t0,tl] (or [tl,tOJ), the resulting attainable sets can
be distinguished by designating them A*+(t0,x0), A*(t0,x0),
etc. It is clear that each of the attainable sets so
obtained are subsets of the corresponding attainable

obtained without this restriction. For example

A* (so) S A (so)

A*+<so) G A+<so)

A*(r,sO)C-A(r,so).

Ml

Playable Pairs

 

A pair of strategies (U,\f), Ueg, V51, is said to be

a playablegpair if for every (t0,x0)e§, each solution

 

curve of the differential equation
x = f(t,x,U (t,x), V(t,x)), x(to) = x0 (2.1.15)

intersects the terminal surface T_at some finite time t1
and is interior to §_on the interval [t0,tl]. Not every
pair of admissible strategies is necessarily playable.

In order to define a solution to a game, a well-
defined payoff for each pair of admissible strategies is
needed. If the pair of strategies is playable, the payoff
functional (2.1.6) can be used to evaluate the payoff. But
the question of how to treat admissible pairs which are
not playable arises. This can be approached in a number
of ways.

One is the obvious method of defining it directly
for nonplayable pairs. An example will illustrate this
procedure. Suppose that player One, the evader, controls
the motion of a point xE in x-space, and that player Two,
the pursuer, controls the motion of a point xP in the same
space, according to the differential equations:

x =~f (t,x

E E U(t,xE)), U s g

E,

it], = fl, (t,xP, V(t,xP)), v e v.

U2

Termination~—capture——is said to occur when the distance‘

between xE and x drops to a set value r. That is the

P
terminal surface in xPxE-space is the set of points xP,xE
satisfying I xP — xE I = r, assuming that initially the
distance between XP and xE is greater than r. The payoff

is the time at which capture occurs. If for a pair of
strategies (U,V) and a particular starting point
(to, xE , xPO), capture does not occur for any finite
time, the payoff for this pair and this initial condition
can be given the value + w. This does not necessarily mean
that I xP(t) - xE(t) | + r as t + w.

A second approach, one used by Berkovitz [2,3], is
to further restrict the admissible strategies to subsets
91 of g_and 11 of V_which have the property that for
every U a g_, V a V1, the pair (U,V) is playable. Its
major weakness, as Berkovitz states, is that the restricted
sets g1 and X1 are not necessarily unique, and that there
may be no clear way of obtaining them from g and V, On the
other hand, there may be obvious candidates. In the pursuit—
evasion example above, g1 could be set equal to g and Vi
defined to be the set of all V playable against every U
in 2. That is, player Two restricts his attention to
only those V which guarantee termination in a finite time
against every evader strategy. The set V1 may be vacuous.
In other cases it may not be as clear how to choose 21 and

Vi; perhaps one could include them as part of the informa-

tion given to both players.

43

A further way around this difficulty is to require
the game to be formulated, by suitable modification if
necessary, in such a way that (U,V) is a playable pair for
every Ueg_and every Vex. An equivalent statement is that
T_must divide the attainable set A*+(§) into two disjoint
sets B and C such that between any point beB and any point
ceC every continuous path joining them lying entirely in
A*+(§) will intersect T. If one uses the attainable set

resulting from pairs in the restricted sets g» and V of

l —l
the previous paragraph, 2 has this property with respect

to this attainable set. Since T divides the attainable

set into two disjoint sets, it will in general be a surface
and thus require n parameters 01, ..., on in §P+l to

specify it. (Since T.is part of the boundary of §_one may
take these sets to be E_and A*+(E)~§.) In the same pursuit-
evasion example a stop rule could be introduced by adjoin—
ing the surface t = T to the original terminal surface and
requiring that play take place for t S T, where T is some
suitably large number. This assumption—-that every
admissible pair of strategies is playable—-is used here-
after unless explicitly stated otherwise.

The need for playable pairs arises from the inde-
pendence of the players' decisions. There is nothing
corresponding to it in optimal-control problems-—one
player games-—where one can ignore arcs which do not

satisfy the terminal conditions and confine the optimiza—

tion to those arcs which do. In games which are inherently

Mb

discriminatory, the requirement is that the player bene-
fitting from the discrimination has, for each strategy of
the opponent, a strategy playable against it. In this
case the terminal manifold may have dimension <n. It
must however have a nonempty intersection with each
A*+(t,x,U), (t,x)eE, UeU, where (for definiteness) One is

the player discriminated against.

2.2 Solution Concepts

 

Maximin and Minimax Points

 

In this subsection, a discriminatory game starting
from some point (t,x) in E is considered. Player One
picks a strategy U which is communicated to player Two, who,
since he is interested in minimizing the payoff, will

choose a strategy V depending on U such that
J (t,x; U, V(U)) S J (t,x; U, V) V v e v
or

J (t,x; U, V(U))= min J (t,x; U, V) (2.2.1)
VeV

1&1 order to minimize the loss due to the discriminatory
Exituation, player One can choose a strategy U* such that
flflt,x) A.J(t,x; U*, V(U*)) = max J(t,x; U, V(U))

UeU

= max min J(t,x, U, V) (2.2.2)
UEU Vey_

”5

U(t,x) is called the lower value. (If the maximizing

U, U* does not exist, or if V(U) does not exist for each

UeU, fl(t,x) could be defined to be sup inf J(t,x; U, V).
Ueg Vey_

However if one wishes to have a determinate optimal

strategy for player One, one must have at least flfit,x) =

max inf J(t,x; U, V).) The strategy U* is called player
USU Vsy;

One's maximin strategy. By playing it, player One can
guarantee a payoff of at least U(t,x), regardless of what
player Two does.

Player Two likewise has a minimax strategy V* which

guarantees that his loss will be not-more than

W(t,x) = min max J(t,x; U, V) (2.2.3)
Val Ueg

(i.e., his payoff will be at least max min (—J(t,x; U, V)).)
VeV_UeU

W(t,x) is called the upper value. Now [(t,x) ‘W(t,x),
provided (U*, V*) is p1ayab1e--which it is by assumption.
This is so because

max min J(t,x; U, V) = min J(t,x; U*, V) S J(t,x; U*, V*)

UeU_VeV VEV

(2.2.H)

and

46

min max J(t,x; U, V) = max J(t,x: U, V*) 5 J(t,x; U*, V*)

VeVbUeU| UeU

(2.2.5)
The inequalities (2.2.4) and (2.2.5) combine to give

max min J(t,x; U, V) 5 min max J(t,x; U, V) (2.2.6)
Ue_I_J_ Vey_ VeV U
The notation V(U) (U(V)) will be used to denote, as
in (2.2.1), the strategy which minimizes (maximizes) the
payoff when the opponent's strategy U(V) is known. If

inequality holds in (2.2.6), either
U(t,x) < J(t,x; U*, V*)
or
J(t,x; U*, V*) < W(t,x)

or both._ In the first case V* is not optimal against U*,
for player Two can use V(U*) and lose only fl(t,x). But
he runs the risk of losing more than W(t,x) for player
One, in anticipation of the use of V(U*), can decide to

use U(V‘(V*)), and
J(t,x; U(V(U*)), V(U*)) 3 J(t,x; U(V*), V*)=' W(t,x).

This argument is symmetrical in the players, and the
process of outguessing the Opponent can continue for any
nunmer of stages. Any definition of solution would be

somewhat arbitrary in this situation. The best that can

”7

be done, although not wholly satisfactory, is to consider
the solution to consist of the set of maximin strategies
(U*, V*) with the associated payoff. The pair (U*, V*) is

then called a maximin point.

Equilibrium Point

 

If player One plays his maximin strategy U* he may
obtain more than the lower value fl_if his opponent does
not play V(U*). That is he may gain if the opponent
deviates from the strategy optimal with respect to U*.

One may also consider the situation in which a pair
of strategies has the property that deviations by one
player cannot produce any gain provided the opponent does
not change his strategy. That is the pair of strategies

(U, V) has the property, where P is the payoff to player

1

One, P2 the payoff to player Two:
Pl(U,V)EPl(U,V) VUeU
(2.2.7)
P2 (U, V) 5 P2 (U, V) \/ V e V_

The pair (U, V) is known as an equilibrium point.
In a two—person zero—sum differential game, (2.2.7)

becomes

J(t,x; U, V) S J(t,x; U, V) s J(t,x; U, V) (2.2.8)

Examination of (2.2.8) shows that (U, V) is also a

maximin point and that

H8

max min J(t,x; U,V) = min max J(t,x; U,V) a J(t,x; U,V)
USU VEV VEV USU

(2.2.9)

On the other hand, suppose that (U*, V“) is a
maximin point with fl(t,x) - W(t,x). Is (U*, V“) also an

equilibrium point? The answer to this question is yes, for
fl(t,x) 5 J(t,x; U*,V)
J(t,x; U, V*) S W(t,x)

w(t,x) = W(t,x) -» J(t,x; U“, V*) = fl(t,x) a W(t,x).

Combining these relationships gives
J(t,x; U,V*) S J(t,x; U*, V*) S J(t,x; U*, V) (2.2.10)

showing that (U*, V“) is an equilibrium point. Thus in
two-person zero-sum games the existence of an equilibrium
point and the condition that max min J = min max J are
equivalent. The term for a pair (U*, V“) satisfying

(2.2.10) is saddle point. A two-person zero—sum game is

 

said to have a solution if it has a saddle point. At a
saddle point a player cannot gain and may lose by deviating
from his maximin strategy. This is the reason for
identifying the solution of the game with its saddle point.
It can also be seen that if a saddle point exists in the
discriminatory game described at the beginning of this
section the extra information gives no advantage to player

Two.

A9
Saddle Points in Differential
sagas-

No mention has yet been made in this section of the
dynamic character of a differential game. Maximin and
equilibrium strategies have been mentioned with respect
to only one point of the playing space E, If there exists
a pair of strategies, U* s U and V* e V_such that (2.2.10)
holds for all (t,x) in E, all U in U and all V in X, then
(U*, V*) is a saddle point for the differential game.
The corresponding payoff, J(t,x; U*, V*), the common value
of [(t,x) and V(t,x), is the value function W(t,x). w is
a function with domain E.

It was previously mentioned that there may be several

arcs satisfying

i = f(t,x, U(t,x), V(t,x)) x(to) = x (2.2.11)

0

for a given pair (U, V). The saddle point condition must
be restated to encompass such cases. Suppose that for a
given point (t,x)eg there are A arcs corresponding to the-
pair (U, V*), U to the pair (U*, V*) and v to the pair

(U*, V). Then the saddle point condition is that

JCG)(t,x; U, V*) 5 J(B)(t,x; U*, V*) 5 J(Y)(t,x; U*, V)
a = l, ..., A; B = l, ..., p; Y = 1, ..., v. (2.2.12)

Setting U = U* and V 8 V* in (2.2.12) shows that

5O

J(a)(t,x; U*, V*) = J(B)(t,x; U*, V*) (2.2.13)

that-is that J(t,x; U*, V*) has the same value on each of
the 11 arcs. This value is W(t,x). It is clear that-w
is continuous along arcs satisfying (2.2.11) with U = U*
and V = V*. Under suitable restrictions (see Berkovitz
[3]), U can be shown to be continuous and piecewise C(1)
on E. This however, is not the approach taken in the

next chapter, where it is assumed that-a function W exists

with the required continuity properties.

2.3 Examples

 

The following examples can all be solved through
simple geometric analysis. Their purpose is to exhibit
maximin points, saddle points, and the effect of imperfect
information. They are all pursuit-evasion games with the

same differential equations, viz.

for the evader:

2E = ul cos u2,

y = ul sin u2, O 5 ul 5 l (2°3°l)
and for the pursuer:

iP = V1 cos v2 (2.3.2)

51

<

9P ='V sin v 0 v 5 a, a > 1.

l 2 l

The equations are similar, with the pursuer having an
advantage in speed. When u1 = l and v1 = ai= const., this
type of motion is called simple motion by Isaacs, who
originated the first of the four examples [20]. The

symbol 2 will mean (xE, yE, xP, yP).

Example 1

 

The initial time, to, is fixed. The payoff is time
to capture--capture meaning xE(tl) = xP(tl), yE(t1) =
yP(tl)’ when this occurs for the least time t1. There
is no loss in generality in taking t0 = 0. At each time t,
each player knows t and 2 as well as the equations (2.3.1)
and (2.3.2). By considering the rate of change of the
distance between the evader and the pursuer, this problem
can easily be solved. Figure (2.3.1) and the Theorem of

Pythagoras show that
r2(t) = (x (t) — x (t))2-+< (t) — <t))2 <2 3 3)
E P yE VP ' 5 ° °
Differentiation.yields

2r(t) f(t) = 2(xE(t)—xP<t))(XE(t)—iP(t)) +

2(yE(t)-yP(t))(§E(t)—VP(t))

Upon rearrangement, this becomes

52

 

 

 

 

(XE: YE)
6
(x y )
P’ P
(XE - xP)
Fig. 2.3.1
B
E

(xP<0),yP<0)>

 

Fig. 2.3.2

0"
(xP(O),yP(O))

 

Fig. 2.3.3

53

5(5) = cos 6(z(t»(xE(t) - iP(t))
+ sine (z(t)) (yE(t) - 9P(t)), (2.3.u)
where
6(Z(t)) = tan-1 [(yE(t) - yP(t))/(xE(t) - xP(t))3.

Player One wishes to delay the time t at which r(tl)

l
is zero as long as possible. Consequently he should strive

to maximize r(t). Player Two's interest is in minimizing
f(t).
Substituting the differential equations (2.3.1) and

(2.3.2) into (2.3.4) shows that One should maximize

u (cos 6(z(t)) cos u + sin 6(z(t)) sin u2) (2.3.5)

1 2

and that Two should minimize

--v1 (cos 6(z(t)) cos v2 + sin 6(z(t)) sin v2) (2.3.6)
The optimum conditions are

u2(t) = v2(t) = e(z(t)) (2.3.7)

ul(t) = 1, Vl(t) = a, (2.3.8)

that is, a direct chase at maximum speed.
The payoff is r(O)/(a—l). If the capture condition

is r(tl) = 2 (where r(0) > i), the optimal strategies

5“

remain the same, but the payoff becomes

(r(O) - 2)/(a—l)

The Optimal strategies:

ul(t,z) l
U(t,z) = = (2.3.9)
u2(t,z) 6(2) '
and
v1(t,z) a
V(t,z) = " = (2.3.10)

  
 

are independent of t. This is to be expected, since the,

differential equations (2.3.1) and 2.3.2) are autonomous.

Example.2

This example differs from Example 1 in that the
terminal surface in tz—space is given by the equation ,

t - T (T>O). and in that the payoff is r(T).

ForT <.r(0)/(a-l), the strategies (2.3.9) and (2.3.10)
which provide a saddle point for r(t) on [0,T] are optimal.
For T > r(t)/(a—i), r(t) a o for r(0)/(a-l) s‘t s T, and
consequently 6(z) is indeterminate. However, even if no
strategies are defined when r(t) = 0, any deviation from

this condition results in its immediate restoration.

55

The payoff for T < r(0)/(a-1) is-r(0) + (1-a)T. For
T 2 r(0)/(a—1) it is zero. ‘

Example 3

This example differs from Example 1 in that the
information includes only t and 2(0). That-is, the players
do not know the state after the play has commenced. In
thiscase themaximin payoff is less than the minimax
payoff, and the game has no saddle point.

Suppose.the pursuer announces his strategy. Then,
regardless of what it is, the evader can choose his~

strategy so that the paths

lv
0

xP(t), yP(t), t

and

V
O

xE(t), yE(t), t —

never intersect. The minimax payoff is + Q,

On the other hand, if the evader announces his
strategy, the pursuer can choose any strategy which brings
him to the point where the evader's path first intersects
his attainable set at the same time as the evader. This
can be done since the pursuer is faster.

‘To minimize his loss, the evader must choose his
announced strategy to delay this encounter as long as

possible. Since for t < T‘= r(O)/(a-l), the evader can

56

reach points which the pursuer cannot and since for t 3 T,

the pursuer can reach any point the evader can, the maximin

payoff is T‘and the-evader's maximin strategy is u1 = l,
u2 = 6(z(0)). The play in this case is the same as in
Example 1.

Example A

 

This example differs from Example 2 in that the same
restriction of information occurs as in Example 3.

The cross-sections of the attainable sets for fixed
times are circles centered on x1(0), yi(0), i = E, P, with
radii of l.-t for the evader, and ast for the pursuer. If
T < r(0)/a the situation in Figure (2.3.2) occurs.

The cross-section P(E) of the attainable set at time
T is the circle of radius aT(lT) centered on the pursuer's
(evader's) initial point. The point A is closer to the
point B than any other point in P; the point B is further
from A than any other point in E. Thus the controls which
bring the pursuer to A, the evader to B, constitute a
saddle point. The value is r(O) + (l-a)T.

For T 3 r(O)/a, the saddle point condition breaks
down. In this case, Figure (2.3.3),the point (xE(0), yE(0))
is within the circle P of radius aT. Suppose the pursuer's
strategy is known_to the evader. The evader can choose his
strategy to take him to the point on the circle E of radius

T furthest from (xP(T), yP(T)). The resulting payoff, r(T)

57

is clearly 2 T, the radius of E. The pursuer's minimax
strategy is any one which makes (xP(T), yP(T)) = xE(0),
yE(O)), for in this case r(T) 5 T, regardless of what the
evader does.

If the evader's strategy is known to the pursuer,

the latter can use the strategy which brings him to the

point within P closest to (xE(T), yE(T)). In this case,

(a) r(T) s r(O) + (1-a)T if r(O) + (l-a) T > O, or

(b) r(T) = 0 if r(O) + (1—a)T $0.

The distance r(O) + (1-a)T is the distance between

the points A and B in the figure, which is drawn for the
case (a). The evader‘s maximin strategy is the one which
brings him to the point B, for with this strategy

r(T) é r(O) + (l—a)T. Case (b) corresponds to the situa—
tion where T is sufficiently large for the circle P to
enclose the circle E. For this situation, any of the

«evader's strategies may be considered a maximin strategy,

saince the payoff is zero, independent of the strategy

tzsed by the evader.

The principle of optimality does not hold for the

tnvo examples with incomplete information, although it does

In11d.partially in Example A for T < r(O)/a. The optimal

fieslds introduced in the next chapter have the principle

0f <3ptimality stated as part of their definition. One may

58

view the principle of optimality as a consequence of the
existence of an optimal field. Since the principle is not,
in general, valid for games of imperfect information, as
these examples illustrate, all games to which these fields

are applied are assumed to be games of perfect information.

III. OPTIMAL FIELDS FOR SADDLE POINTS

3.1 Optimal Fields in Controleroblems

The results in this chapter are extensions of those
stated by Hestenes [16, ch. 6, sec. 10] on optimal fields
for optimal control problems. In this section the defini—
tion of an optimal field for the case of a one-player
game is presented, and the basic theorem—-a version of the.
‘Weierstrass necessary condition--is proved. The terminology
developed in the previous chapter, with the maximizing
player, One, suppressed, is used. Consequently u is not
one of the arguments of L and the f1, and §_and 50.are sets
in txv—space.

The fundamental assumption about an optimal field is
that at each point (t,x) in a region F, there exists a
choice V(t,x) of the control variable v optimal in some

sense. That is solutions of
s. = f(t,x, V(t,x)) (3.1.1)

are optimal paths in tx-space. In what follows L and the
f1 are assumed to be C(l) on 3. Consequently if V is

C(1) on a neighborhood of a point (5,?)5 F , there is a
unique arc x satisfying (3.1.1) on an interval [EL6, E46],

6 > 0, with x(F) = x. This is a consequence of a theorem

59

60

on the existence and uniqueness of solutions to differential

equations, Theorem 1.4.

Definition

An optimal field E is a region F.1n tx-space, a
(1)

vector control function W,C on Faand a function w also

C(l) on F, such that
(i) (t,x, V(t,x))e:_13_0 V (t,x)eF

(ii) The inequality

8
W(a,x(a)).s lit,X(t), V(t)) dt + W (B,X(B)) (3.1.2)

11<>lds for every admissible are

x: x(t), v(t), a 5 t 5 8, (3.1.3)

equality holding in case
V(t) =V(t,x(t)), dst ‘8. (3.1.14)

:qu (3.1.4) holds, 5.15 an extremal or a characteristic arc
(DIE the optimal field E, Surfaces in tx-space defined by
eaquations of the form W(t,x) = constant are called

transversals of the field E. If x_is an extremal of the.

 

field 3, then

6l

I(§) = L(t,X(t),V(t)) dt = W(a,X(a)) - W(B,X(B)).

(3.1.5)

Two extremals x and £_whose initial points are on the

transversal W C and whose endpoints are on the

1

C2 have the property that

transversal w

1(5) = 1(3) = cl - c2 (3.1.6)

The following theorem is taken from [16] and the proof

follows that given by Hestenes.

Theorem 3.1

At each point (t,x)ezg of an optimal field 3 one has
L(t,x,v) + wt(t,x) + wx(t,x) f(t,x,v) 2:0 (3.1.7a)

for all v such that (t,x,v)e§0. Moreover, for v = V(t,x)

equality holds:
L(t,x, V(t,x)) + wt(t,x) + wx(t,x) f(t,x, V(t,x)) = O.
(3.1.8a)

For convenience, E(t,x,v) can be defined as

E(t,x,v) A L(t,x,v) + wt(t,x) + wx(t,x) f(t,x,v)

62
so that (3.1.7) can be re—expressed as
E(t,x,v) a o, (3.1.7b)
and (3.1.8) as

E(t,x, V(t,x)) = O (3.1.8b)

Proof

Let (76,3?) be a point of g and choose Vew('€,3€). Let

E? x(t),v(t)
be a continuous admissible arc in F on either
(1) Ffls t:s:F + 5

or (ii)7c--<Sstst'

with x(E) = x, V(F) = V.

In case (1) consider the function

t+e
g(e) = L(t, x(t), v(t)) dt + W(E'Ha, x(t'+e))

't-
and in case (ii)

’6
h(e) = - L(t, x(t), v(t)) dt + W(t-e, x(t-e)),

t-s

63

where O s e s 6 in both cases. By the inequality (3.1.2),
g(e) has a minimum and h(e) has a maximum at e = 0. It

follows that
case (i) g'(0) 2 0
case (ii) h'(O) 5 O.
For case (i), one has

s'(0) = L(Ejffi) + wt(t,x’) + wx(t‘,§) x ('t‘) z 0.

(5.35) + w (5,36) f(t,x,?) a 0 (3.1.lla)

L(t'jj‘) + wt(t',x‘) + wx(t’,x‘) f(t_,'i','\7) 2 o (3.1.1lb)

Thus in both cases

E(t,x,v) 2 o (3.1.llc).

6A

If v(t) = V(t,x(t)) on the intervals (1) or (ii),
(1)3(6) = W(t,x)
or (ii) h(e) = W(t,x).

That is, g(e) and h(e) are constant on 0 s e s 6.
Consequently, g'(0) = h'(O) = O in this situation and
equality holds in (3.1.11). This proves Theorem 3.1.

The proof is based on the inequality (3.1.2). If
this inequality is reversed, then so are all inequalities
(except those defining intervals) in the proof. This con-

sideration leads to the corollary:

Corollary 1

If the inequality (3.1.2) is replaced by

W(a, X(a)) 2: L(t,X(t), V(t)) dt + W(B,x(8)), (3.1.12)

0.

Theorem 3.1 is unchanged except for (3.1.7), which becomes
L(t,x,v) + Wt(t,x) + Wx(t,x) f(t,x,v):S 0. (3.1.13)

The theorem can be extended to cover cases where L and f

(l) (l) (l)

are C in v, piecewise C in (t,x), V is piecewise C

(l)

on F and W is continuous and piecewise C on E. In this
case if (5,?) is a point of discontinuity of one of these
functions the Lipschitz condition in the existence theorem

(i.e., Hypothesis 3 in the section on differential

65

equations in Chapter I) does not hold, and one cannot prove

that there is a unique solution to the initial value

problem with the initial condition x(F) x. However, with

the proper interpretation at manifolds of discontinuity,

the theorem still holds.

Corollary,2
Let {§‘“)} be a decomposition of §_such that L, f,
V and W are all C(l) on each 2‘“). Then these functions

and their first partial derivatives agree on each F‘a)with
functions L(a), f(a), V(a), W(a), etc. which are continuous
on Ex“) (from the definition of piecewise continuity). If
(5,?) is a point on the boundary of v regions Efali ...,

FFGV), Theorem (3.1) holds at (5,?) if (3.1.7) is replaced

by

L(“)(€,f,v) + w§“)(s,;) + wfi“)(€,x) r(“>(f,§,v) Z 0
(3.1.1u)

d = d3, j = l, ..., v,

and if (3.1.8) is replaced by

L(“)(t,x, V(a)(t,x)) + W(a)(t,x)

+ W(a)(t,x)+-W(a)(T,x)f(a)(t,x, V(“)(t,x)) = 0

j = l, ...,v. (3.1.15)

66

Proof
The function E is continuous on the set G of points
(t,x,v) SUCh that (t,x) is in one of the regions 3‘“)

and (t,x,v)e§0. By Theorem 3.1,
E(t,x,v) 3 O on G

Furthermore the function E(a) = L(a) + wéa) + wfia) f(a)
is continhous on the set (t,x,v) such that (t,x)eF‘a)
and (t,x,v)£B_0 and agrees with E on G. Consider the point

(a)

(E;§) on the boundary of}? and let V‘be such that

(3);,V)efio. Let {(ti’ xi, Vi)} be a sequence of points

in G converging to (F,§,V). Since for each i,

E(a)(ti, xi, vi) 2 0,

lim E(a)(t , xi, vi) 2 0
1+0!) 1

But the continuity of E(“) shows that

lim E(a)(ti, xi, v = E(“)(€,E,V).

i+oo

1)
Thus
E(a)(t,x,V) Z 0.

This expression expanded gives (3.1.14). Likewise

67

E(a)(t V(a)(ti, xi)) = 0 for all i

13 xi,

In the limit this gives

E(a)(t,x, V(o‘)(t,x)) = 0,
an expression equivalent to (3.1.15).

The function E is one form of the Weierstrass E-function.

This can be demonstrated by setting
E(t,x,V,v) = E(t,x,v) - E(t,x, V(t,x)) Z 0,
which can be rewritten as

L(t,x,v) - L(t,x,V(t,x)) + Wx(t,x)[f(t,x,v)

— f(t,x,V(t,x)1= 0

which corresponds more closely to the usual form of the

Weierstrass condition.

3.2 Optimal Field for a Saddle Point
In this section it is assumed that a differential
game of the type defined in Chapter II has a saddle point,

that there exist optimal strategies UeU_and VeV_which are
(1)

piecewise C on F and that there exists a value function

(1)

W which is continuous and piecewise C on E. Solutions

of

68
x = f(t,x, U(t,x), V(t,x)) (3.2.1)

are then optimal paths in tx-space.

It is assumed that L and f are C(l) on R.

The previous definition of an optimal field can be

extended to cover saddle points.

Definition

 

An optimal field F is a region F‘in tx-space, vector
(1)

 

strategies U and V which are piecewise C on F, and a

function W continuous and piecewise C(l) on 3 such that

(i) (t,x, U(t,x)) 85;
V (t,x) 5 E.

(ii) (t,x, V(t,x))efi2

(iii) The inequality

8
W(a,X(a)) S L(t,X(t), U(t,X(t)), V(t))dt + W(B,X(8))

O.

(3.2.2a)
holds for every admissible arc
x: X(t), U(t,X(t)), V(t), a st 5 B,
equality holding in case
V(t) = V(t,X(t)), a s t s B; (3.2.2b)

and the inequality

69

B
[ L(t,x(t), u(t), V(t,x(t)))dt + W(B,x(B))SW(d,x(d))

a
(3.2.3a)
holds for every admissible arc
x: x(t), u(t), V(t,x(t)), a s;t:§ B,
equality holding in case
MH=UWJWH,a§tSB. Siam

If there is more than one admissible arc
é? x(t), U(t,x(t)), v(t) o Sitflé B

for each v(t), (3.2.2a) holds for each of these arcs.

Likewise (3.2.3a) holds when the arcs
x: x(t), u(t), V(t,x(t)) ditSB

are not unique for a given u(t), a S t S B.

On a manifold of discontinuity of U or V one may or
may not have a definition of these functions differing from
their limiting values from neighboring regions of continuity.
If the optimal paths lie on such a manifold, the optimal
strategies need to be defined there, but if the optimal
paths merely cross the manifold from one region to another
this is not necessary (and indeed superfluous). Optimal
arcs lying on manifolds are considered in the corollary

to Theorem 3.4.

7O

Surfaces W(t,x) = constant arc transversals of the
field E, If (3.2.3) holds, the arc x‘is a characteristic

are or an extremal 9f the optimal field E, If the are
x; x(t), u(t), v(t), a s t S B

is an extremal of the field, then

8
1(5) = L(t,X(t),u(t),V(t))dt = W(a,X(a))—W(8,X(B))

(3.2.5)

Two extremals x and 3 whose initial points are on the
transversal surface W(t,x)=Cl and whose final points are

on W = C have the property that

2

my = 1(3) = cl — 02.

In the problem of Mayer, L(t,x,u,v) E 0, and the value
function W is constant along optimal paths. Such paths,

then lie in transversal surfaces. Along arcs
x: x(t), U(t,x(t)), v(t), a St S 8
W(a,X(a)) s W(B,X(B))
and along arcs,
£3 x(t), U(t), V(t,x(t)), O. S t S 8

W(a,X(a)) 2 W(B,X(B)).

71

Transversal surfaces in this case have the property
of semipermeability used by Isaacs [20]. That is, if
player One uses the strategy U at a point (t,x) no arc
can penetrate the transversal surface containing (t,x) in
the direction of decreasing W, and if player Two uses V,

no arc can penetrate in the direction of increasing W.

Theorem 3.2

At each point (t,x) of an Optimal field E one has

L(t,x,u,V(t,x))+Wt(t,x)+Wx(t,x)f(t,x,u,V(t,x)):S O,
o S L(t,x,U(t,x)y)+Wt(t,x)+Wx(t,x)f(t,x,U(t,x),v) (3.2.6)

for all ue¢(t,x), V8V(t,x). Moreover for u = U(t,x) and

v = V(t,x), equality holds:

L(t,x,U(t,x),V(t,x))+Wt(t,x)

+ Wx(t,x)f(t,x,U(t,X), V(t,x)) = 0‘ (3.2.7)

If (t,x) is a point of discontinuity of U, V, Wt or Wx,
in the expression L i Wt + fo, U, V, Wt and WK must all
be evaluated as limits approaching (t,x) from the same

region of continuity of these functions (U, V, Wt, Wx).'

(In succeeding theorems this may be referred to as "the

usual interpretation at points of discontinuity.")

72

£322£,—-The right-hand inequality in (3.2.6) follows
directly from Theorem 3.1 and the second corollary with
L(t,x,v) = L(t,x, U(t,x), v) and f(t,x,v) = f(t,x, U(t,x),v).
The left-hand inequality is obtained in a similar manner
from Theorem 3.1 and both corollaries. Equation (3.2.7)
again comes from Theorem 3.1. It is also an immediate
consequence of (3.2.6). The remaining part Of the theorem
is a restatement of Corollary 2 to Theorem 3.1.

Define

Pi(t,x) = Wxi(t,x) ,
(3.2.8)

H(t,x,u,v,p) = L(t,x,u,v) + pf(t,x,u,v),

Here p is an n—dimensional row vector.

Theorem 3.2 is equivalent to:

Theorem 3.3
At each point (t,x) in an Optimal field E the
inequalities

H(t,x,u,V(t,x),P(t,x)) 5 H(t,x,U(t,x),V(t,x),P(t,x))

IA

H(t,x,U(t,x),v,P(t,x) (3.2.9)

hold for all ue¢(t,x), and for all ch(t,x). Moreover

U, V, and W satisfy

Wt(t,x) + H(t,x, U(t,x), V(t,x), Wx(t,x)) = 0. (3.2.10)

73

The same interpretation at points of discontinuity
as in Theorem 3.2 is used in (3.2.9) and (3.2.10) for Wt,

wx, P, H, U and V.

Finally the integral

I* = [{P(t,x)dx - H(t,x, U(t,x), V(t,x), P(t,x))dt}

(3.2.11)

is independent Of the path in F, provided that any segment
of the path lying on a manifold of discontinuity is divided
into segments on which P and H take the limiting values of
only one adjacent region.

P322£,—-Expressions (3.2.9) and (3.2.10) are restate-
ments of Theorem 3.2 using the terminology of (3.2.8).
The integral I* is seen to be de when (3.2.10) and (3.2.8)
are used to make substitutions. IdW is clearly independent
Of the path. The restrictions on the evaluation of the
integrand insure its existence. This Theorem corresponds
to Theorem 10.2 in Hestenes [16]. The following theorem

relates limiting values of functions appearing in Theorem

3.3.

Theorem 3.4

Let {3}“)} be a 0(1)

~decomposition of F_based on
U, V and W, and let P be a set of indices a such that the

manifold of discontinuity M.é. (I) BFfa) is not empty.
as?

The superscript d (e.g. Wéa))
FIG} which agree on E(a) with
scripted) functions (e.g. Wt).

(dt, dx) is tangent to M, for

Wéa)(t',f)dt + Wéa)(t','x')dx

74

(1)

denotes the functions C on
the corresponding (unsuper-

Then if (t’,3?)eM_ and

each car and Bar

= wé8)('t‘,x‘)dt + WJEB)(F,x-)dx.

(3.2.12)

Also
(What) - P(B)(F,Y)de

= [H(“)(t,§,u(°‘)(t,x), V(“)('t',x), P(“)(t,§))

— H(B)(€,§,U(B)(t,x), V(B)(t,x,) P(B)(t,§,))Jdt
(3.2.13)
Proof.--(3.2.13) follows from (3.2.8), (3.2.10),

and (3.2.12). TO show (3.2.12), a C(l) curve lying in

dI
U

given parametrically by t t(s), x x(s), with t(O)

x(0) = i; can be defined. Let §_be a neighborhood of

( ) on E and C(l)on
A (3(1)

(75.x).
3(a), it is (3(1) on yflanj.

defined on A which has W(t,x) = W(a)(t,x) on FIG}.
(.(1)

J

Since W is piecewise C
function W can be
On the

curve a further function can be defined

w(s) Afi(t(s>, x(s)> = w(°‘)(t(s), mm.

for which one Obtains

75
mm) = Wt(F,x)t'(O) + fix(t‘,i')x'(0) = wé“)(t,§')t'(0)

+ w(°‘)(t‘,x)x'(0).

Another equation is Obtained in the same manner:
w.(0) = wé5)(t‘,x)t'(0) + w§5)(t,§)xv(0).

The curve is arbitrary. It follows that (t'(0), x'(0))ds
may be any vector tangent to M. This, together with the
two expressions for w‘(0), established (3.2.12).

The corollary which follows considers the case where
an optimal path starting or terminating at (E,x) lies in
the manifold M, In this situation Optimal strategies
defined on the manifold are not necessarily the same as

(a) (a).

one Of the limiting strategies U or V

Corollary

Let Optimal strategies U and V defined on the manifold
M prescribe optimal paths lying in M_and let (3,?) be a

point of M, Then
L(t,x‘, U(t,x),v) + wéO‘NE'JE) + w(°‘)(t',i‘)
+ w(°‘)(t',sz) + W(O‘)(t‘,‘x) f(t,x,u(t,x‘),v) ->- o (3.2.l4a)

'whenever (F,§,V)e§2 and (l, f(t,x, U(t,x),v)) is tangent

’60 £3

76

L(t‘,3€,u,V('t‘,x))+wé°‘)(t’,f)+wf{°‘)(E,i‘)f(t',x',u,V(t‘,i‘)) s o

(3.2.14b)

whenever (F,x,u)eRl and (l,f(t,x,u,V(t,x))) is tangent to

M,and
L(t,x,ufi'j) W(t,x) )+wé°‘) (t,x)

+ wt(°‘)(t,§)r(t,;,U(t,x), V(t,x)) = o. (3.2.14c)

Proof.--Let

i: x(t), U(t,x(t)), v(t), tO st stl

be an admissible arc with (t,x(t)) lying in M where either

(t0,x(t0)) = (5,?) or (tl,x(tl)) = (t,x). This are can be

described parametrically with parameter s t - €,‘becoming

£3 x(s), U(t(s), x(s)), v(s) s0 3 3

Either S0 or s1 is zero. The function w defined in the
proof of Theorem 3.4 is differentiable along the are A.

With g(e) given by (where s0 = 0):

e
g(e) = J L(t(s),x(s), U(t(s),x(s)), v(s))ds + w(€),
O

or with h(e) given by (where s1 = O):

77

O
h(e) = - [ L(t(s),x(s), U(t(s),x(s)), v(s))ds + w(—e),
-e

the arguments used in the proof of Theorem 3.1 establish
the first and third of the above expressions. The second
is Obtained through the use Of the first corollary to that

theorem. In carrying out these arguments the substitution
w‘(0) = wé“)(t,§)t'(0) + w§3)(t,x)xi(0)

Obtained in the proof of Theorem 3.4 is used, where in the

present case
t'(0) = l, x'(O) = f(t‘,x‘, U(t‘,x‘), v(F)).

The tangency restrictions arise from the correspond-
ing conditions in Theorem 3.4.

The following theorem is true (as can be seen from
the proof) for any pair of admissible strategies U and V

and function W which satisfies

t1

W(t0,x(t0)) = J L(t,x(t)),u(t),v(t))dt + W(tl,x(tl))

to

for any admissible arc

1‘5 x(t), u(t), v(t) t0 5 t 5 t1

with u(t) = U(t.X(t)), v(t) = V(t,X(t)).

the type of field defined in this section or the type

defined in Chapter IV.

Theorem 3.5
On each region A in g on which U and V are 0(1), an
extremal 5: x(t), u(t), v(t), a 5 t 5 B of the field,

together with the functions
pi(t) = Pi(t,x(t)) (3.2.15)

satisfies the equations

x = H (t,x, u(t), v(t), )
p p (3.2.16)
5 = —(Hx(t,x,u(t),v(t),p)+Hu(t,x,u(t),v(t),p) Ux(t,x)
+Hv(t,x,u(t),V(t),p)Vx(t,x)).
Moreover

fi(t.x(t),u(t),v(t),p(t)>=Ht(t,x(t) ,u(t),v<t) ,p(t))

+Hu(t,x(t),u(t),v(t),p(t)Ut(t,x(t)
+Hv(t,x(t),u(t),V(t),p(t))Vt(t,X(t)) (3.2.17),

.along the extremal A.

Proof.-- x(t) satisfies x = Hp along I since x is

(tifferentiably admissible.

 

79

Consider the differential equation

p --(Hx + Hqu + vax)
where the right hand side is evaluated along the extremal

in This equation can be rewritten as

p = - (Lx+Lqu+Lvi) - p(fx+qux+vax), - (3.2.18)
which is a system of linear differential equatibns.

Furthermore (Lx +L U + Lvi) and (fx + qux + fVVx) are

IAN

u
continuous on d 5 t B. It follows that for any (I,U)
with a s T s B, there is a unique p(t) satisfying
(3.2.18) on a 5 t 5 B. This p(t) may be denoted
p(t,r,w) to indicate its dependence on the initial con—
dition.

Consider now the arc M. It can be imbedded by

Theorem 1.5 in set of arcs

x(t,T,£) for which X(t,T, X(T)) = x(t).

Let x‘= x(E} for some a 5 E‘5 8. Then

8
W(t,x) = L(t,x(tfc‘j),U(t,x(t,‘t’,x‘)),V(t,x(t,'t‘,x‘)))dt
f‘
+ W(B,X(B,€,3{)) (3.2.19)

‘and

 

lg‘" "
+ WE(B’X(B,E,3{-)) x'f( 83.63;)

B ._ _
= J_ {(HX+Hqu+HVVx)-p(fx+qux+vax)} X;(t. .X)dt

+ WX(B,X(B,-,;))X§(B:€3;)° (3.2.20)

Consider now the particular p satisfying (2.3.18) which has
the initial condition p(B) = P(B, x(B)). Also to be noted

is that Z(t,t) A x§(t,E,x(E)) satisfies

é= fx(t,x(t),u(t),v(t))Z with 2(t‘,'t‘) = I.
Thus (3.2.20) becomes

8
P(€,§) = - J 3% p(t,B,P(B,X(B)))x§(t,f,§) dt
t‘

+ P(c,x(s))x;(e,t,x),

or
P(E)?) = p(t',B,P(s,x(e)))x;<'€,t‘,‘£)

-p(B,B,P(8,X(B))) x;(s,'t','i)+P(e,x(s))x;(8,€,3<')

(3.2.21)
But x;('€‘,?,3?) = I and p(B,B,P(B,X(B))) = P(B,X(B)), so

that (3.2.21) reduces to

 

81
Pas-,3?) = p(?,8.P(B,X(B))) (3.2.22)

F‘is an arbitrary point on the interval a 5 t 5 B with
§‘= x(F). Not only does

P(t,x(t)) = p(E‘,8,P(s,x(e)))

 

Eff

hold along the extremal x, but also i
‘ a

P(t,x(t)) = p(‘t‘.€,P(E‘.x(€))), 3
which is an identity. Consequently since p(t;F,P(E,x(F))) ,

satisfies p '(Hx+Hqu+Hvi)’ the function P(t,x(t))
does also. This establishes (3.2.15) and (3.2.16).

Having demonstrated this, it is easy to show that

d -
EEH - Ht + HuUt + Hth°
d _ d
fiH'd’FGJ'pf) .-
= Lt + LuUt + vat + (Lx + Lqu + vax) x

+ p f + p(ft + qut + fVVt + (fX +qux + vax)x)

H + HuU + (LX + Lqu + Lvi)f

t + HVV

t t

— (LX + Lqu + vax + p(fX + quX + fVVX))f

+ p(fx + qux + vaXH‘

Ht + HuUt + HVVt.

82

All Of the above functions are evaluated along the extremal
E: that is that H, L, f and their derivatives have as
arguments t, x(t), U(t,x(t)), V(t,x(t)), and (in H) p(t).
U, V and their derivatives are functions of (t,x(t)). The
proof here is similar to one used by Berkovitz [3].

Under the assumption that W is C(Z) on the region 9
this theorem can be proved using necessary conditions from
Calculus of Variations. This is the approach used by
Hestenes [16].

Theorem 3.3 states that
H(t,x,u, V(t,x), P(t,x))

considered a function of u has a maximum at u = U(t,x) and

that
H(t,x, U(t,x), v, P(t,x))

considered as a function of v has a minimum at v = V(t,x).
If U(t,x) is interior to ¢(t,x) and v interior to V(t,x),

then

Hu (t,x, U(t,x) V(t,x), P(t,x)) = O

and

HV (t,x, U(t,x), V(t,x), P(t,x)) = O

This result may be combined with Theorems 3.3 and 3.5 to

give

83

Theorem 3.6

 

Suppose that on the region glof Theorem 3.5 that
0(t,x) and V(t,x) are Open, or alternatively that U(t,x)
and V(t,x) are interior points of ¢(t,x) and V(t,x)
respectively. Then on Q U, V, and W satisfy the Hamilton-

Jacobi equations .
Wt(t,x) + H(t,x, U(t,x), V(t,x), Wx(t,x)) = 0

0 (3.2.23).

 

Hu(t,x, U(t,x), V(t,x), Wx(t,x))

I
O

Hv(t,x, U(t,x), V(t,x), wx(t,x))

An extremal of the field
x: x(t), u(t), v(t), d 5 t 5 8

satisfies with p(t) = P(t,x(t)) the canonical Euler

equations

i>=-H H=0,H=o (3.2.214)

together with

H = Ht (3.2.25)

on the region Q.

Suppose that M and M. are given by the constraint

1 2
conditions (2.2.7) stated in the last chapter. For con-

‘venience one can make the definition

84

fi(t,x,u,v,p,u v) = H(t,x,u,v,p) + ua¢a(t,x,u) +

 

vaB(t,x,v). (3.2.26)
Theorem 3.7
Let 31 and 52 be as stated immediately above. Then ET“
|
there exist multipliers ua(t,x) and v8(t,x), piecewise

8

continuous on §_(piecewise C(l) if 6a and w are of class F

0(2))such that on E_ E

 

ua(t,x) 5 O a = l, . r'

vB(t,x) 3 O B = l, . s'

ua(t,x)¢a(t,x, U(t,x)) = O a = 1, ..., r, and not
summed,

v6(t,x)¢6(t,x, V(t,x)) = O B = 1, ..., s, and not
summed,

fih(t,x,U(t,x),V(t,x),P(t x), U(t,x),v(t,x)) = 0

(3.2.27)
ޤ(t,x,U(t,x),V(t,x),P(t,x),u(t,x),v(t,x)) = O

The usual interpretation is made at points of discontinuity.

Let

x5 x(t), u(t), v(t), a 5 t S b

   

85

be an extremal, such that there is a decomposition

(ti-1’

of the interval [a,b] with (t,x(t)) in a region on WhiCh U
(l)

and V are C on each of the intervals comprising the
decomposition. (This excludes arcs with subarcs lying on
manifolds of discontinuity of U or V.)

Then 5 satisfies, with

p(t) = P(t,x(t))
u(t) = u(t,x(t))
and v(t) = v(t,X(t)),

the canonical Euler equations

 

 

x(t) = fi5(t,x(t),u<t),v(t),p(t),u(t),v(t))‘}

6(t) = -fig(t,x(t),u(t),v(t),p(t),u(t),v(t))

_ = O
Hu(t.x(t),u(t),v(t),p(t),u(t),v(t)) (3.2.28)
fi,(t.x(t),u(t),v(t),p(t),u<t),v(t)) = o
¢a(t,X(t),u(t)) 5 O a = 1, ... r‘

¢a(t,X(t),u(t)) = 0 o = r'+1, ..., r
(E(t,x(t),u(t)) S o e = 1, s'

WB(t,x(t),u(t)) = O B - s'+l, , s ,J

86

together with

3;} fi(t,x(t),u(t),v(t),p(t),11(t),\)(t)) = fit(t,x(t),u(t).

v(t). p(t),u(t),v(t)) (3.2.29)

I ._ ".- TI]?
2
I

on each of the intervals (ti-1’ ti)’ 1 = l, ..., N. ;

At the points t i = O, ..., N, these expressions

1’
hold in the sense of left— and right—hand limits.

 

 

*- .3. -.I
Q

Proof.-vThe existence of the multipliers V8 with
the stated properties follows from Theorem 1.3 with
H(t,x,U(t,x),v,P(t,x)) the function minimized by

v'= V(t,x). The second equation in (3.2.27) is established

by
H§(t,x,U(t,x),v(t,x),P(t,x),u(t,x),v(t,x))

= Hv(t,x,U(t,x),V(t,x),P(t,x)) + 08w5(t,x,V(t,x)) = O.

The same theorem establishes the existence of the multi-
‘pliers ha. The nonpositive sign of these multipliers is
a result of maximizing, rather than minimizing H with

respect to u.

The properties Of the extremal x, except for

p = ~Hx

and.

87

are a result of (3.2.27) and the fact that §_is an extremal
satisfying the constraints. Let t-be a point of the

interval (t t1), and set ? = x(t). Then U and

i-l’
V are C(l) on a neighborhood N of (5,?) by hypothesis.

Let ad, j = l, ..., M be the indices a for which

- ...—1 ; «153'

Then

 

“J
¢ (t,x, U(t,x)) 5 O on N,

(It will be identically zero if r' < d s r), and

3

[5:3 (F,'£,U(t‘,3?)) + 5:3(F,?,U(F,?))Ut(‘t‘,?)]dt

+ £¢:J(E.Y.U(t,x‘)) + 5:3(t,x,U(t,i))Ux(t,x)1dx s o

1, since (3,?) is

This holds for each (dt, dx) in E§+
interior to the neighborhood N. As a consequence (3.2.20)

cannot hold unless

(XJ__ __ 0‘.__ __ __
¢t (t,x,U(t x)) + ¢uJ(t,x,U(t,x))Ut(t,x) = o
a ._ a. _H_ _|_ _,_
¢XJ(E,?,U(F,X)) + ¢uJ(t,x,U(t,x))Ux(t,x) = O.

Fronlthese equations and from

ua(E,?) = O for those a for which

   

88
t‘j’, U(t,x)) < o,
it follows that
tact-,3?) Myanmar» + ¢§(t,'f,U(f,x))ut(t,x)] = o

(3.2.3la)

and

(3.2.3lb)

The first equation in (3.2.27) can be rewritten to give,

at (5,?) ,

Hu(t',?,U('t_,?) ”(t,x) ,P(E’,?)) = — u

Multiplying by Ut('t',x) and by Ux('t',?) gives

_ _ a = d
Hu Ut - ua¢ Ut ua¢t

and (3.2.32)
Hu Ux u01¢ Ux uu¢x

where each function is evaluated at (t,?). The second

equation in each line of (3.2.32) comes from (3.2.31).

In the same fashion one obtains

 

 

w... .

89

v t
8 (3.2.33)
Hvi = VB wx
at (E,?).
Equations (3.2.32) and (3.2.33) may be used to F?

substitute in (3.2.15) and (3.2.16) to yield at (t,x):

...-fl“\\"‘ll?’ ’3- .‘34' 1

 

o = - - a - B = _
p Hx “a 0X VB wx _ Hx
. = a B - _ a
H Ht + ua ¢ + u8 ¢ - Ht'

Since

I I
O

on

l’1.‘1

ua(t,X)¢a(t,X,U(t,X))‘+v8w8t,X,V(t,X))

Ei= H on E, and along the arc x
H=H.

Thus
H = Ht'

Since the point (5,?) is an arbitrary point Of any one
of the intervals (ti-l’tl) i=1. ---, N, the expressions
(3.2.28) and (3.2.20) hold on each of those intervals.

Further if {T } is any sequence of points in (ti-1’ ti)

3
with limit t1 (ti 1), they hold at each of these points,

and hence hold in the sense of left- (right-) hand limits

 

IV. MAXIMIN FIELDS

The previous chapter handled Optimal fields for a
pair of strategies (U,V) forming a saddle point. In the
present chapter, it is not assumed that the pair (U,V) is
a saddle point, but that U is a maximin strategy and that
Vis the opponent's minimizing strategy against U. The
theorems stated in this chapter correspond closely to the
theorems obtained in section 3.2. The type of Optimal

field used here is called a maximin field.

Definition

A Maximin Field §_is a region M in tx—space,
(1)

vector strategies U and V piecewise C on gland a func-

tion W continuous and piecewise C(l) on F such that
(i) (t,x, U(t,x))eMl V (t,x)eF
(ii) (t,x, V(t,x))eM2 V (t,x) cl:

(iii) The inequality

8
W(a,x(a)) 5[ L(t,x(t),U(t,x(t)),v(t)) dt

0.

+ W(B,x(8)) (4.1.1)

holds for every admissible arc

9O

 

91
5: x(t), U(t,x(t)), v(t) o S t S 8 (4.1.2)
equality holding in case
v(t) = V(t,x(t)). (4.1.3)

This is equivalent to Et-

8 .
W(a,x(a)) = min {I L(t,x(t),U(t,x(t)),v(t))dt g
v a

W

 

+ w(e,x(e)} (4.1.4)

where the minimum is taken over those v for which (4.1.2)
is admissible.

If fi’is any admissible strategy, then

W(d,x(d)) 3 min {JL(t,x(t),U(t,x(t)),v(t))dt

+ W(B,x(8))} (4.1.5)

the minimum (which is assumed to be attained for at least

one v) being taken over admissible arcs

£3 x(t), U(t,x(t)), v(t) d S t S 8. (4.1.6)

<

If v(t), o - t 5

8, minimized (4.1.5), then it can be shown
by contraposition that the same V restricted to d' 5 t 5 B,
'where a 3 d' S 8, minimizes (4.1.5) with d‘ replacing a.

If there is more than one arc (4.1.2) or (4.1.6)

satisfying

   

 

92

x = f(t,x,U(t,x),v) or x = f(t,x,U(t,x),v) (4.1.7)

the inequalities (4.1.1) and (4.1.5) are satisfied for

each such arc. An admissible arc satisfying
x = f(t,x,U(t,x),V(t,x))

is an extremal of the field. This type of optimal field
corresponds to a differential game in which U is player
One's maximin strategy, for if (B,x(8))e:T_and if on T,
w(T(o),X(o)) is defined to be K(o), (4.1.4) and (4.1.5)
simply state that U is the maximin strategy. Furthermore,
if U is player One's maximin strategy and V is the cor-

responding minimizing strategy for player Two, by setting

U(t,x) t < 8 (t,x) e EULP.’
at,“ = (4.1.8)
U(t,X) t ->- B

one can show that not only (4.1.4) but also (4.1.5) must

hold, with W(d,x(d)) given by

t1

W(a,x(d)) = I L(t,x(t),U(t,x(t)),V(t,x(t))dt
a

+ W(tl,x(tl)) (4.1.9)

in which the arc

5F x(t), U(t,x(t)), V(t,x(t)) d 5 t 5 t (4.1.10)

 

93

with (tl,x(tl)) = (T(O),X(O))€ T and W(tl,x(tl)) = K(o),
is admissible. Equation (4.1.9) defines W(a,x(u)) as

J(a,x(a); U,V). Since V is minimizing
J(d,x(d); U, V) s J(d,x(d), U, V)

for any VET, Suppose that V does not differ from V on the
set Of (t,x) in F_which have t 218 for some 8 > a. Let x
be an arc corresponding to the pair (U,V) starting at

t = u, terminating at (t1,x(tl))eT_and let
v(t) = V(t,x(t)) d S t < 8

Then (if B 5 t1)

8
W(d,x(a)) 5 J(d,x(d); U,V) = I L(t,x(t),U(t,x(t)),(V(t»dt
d

t
1
+ I L(t,x(t),U(t,x(t)),V(t,x(t)))dt
8

+ W(tl,x(tl)),

so that

IA

8
W(a,x(a)) J L(t,x(t),U(t,x(t)),v(t))dt + W(B,X(B)).

d
(4.1.11)

This is (4.1.4). To show (4.1.5) one starts with

 

 

94

W(d,x(d)) = J(d,x(d): U,V) 2 min J(d,x(d); U,V) (4.1.12)
VeV

where U is given by (4.1.8). This holds since U is the

maximin strategy. Then

min J(d,x(d); U,V)
VET

B
= min {I L(t,x(t),U(t,x(t)), V(t,x(t)))dt
VEV

t
l
+ J L(t,x(t),U(t,x(t)), V(t,x(t)))dt
B

+ W(tl,x(tl))}

where the arc
35: x(t), U(t,x(t)), V(t,x(t)) 0!. S t 5 t1

intersects T at t = t1, and B 3 t1. Then

min J(d,x(d): U,V)
V82

8
= min {[ L(t,x(t),U(t,x(t)), VL(t,x(t)))dt
V EV
1.—
t1 _
+ min { L(t,x(t),U(t,x(t)), V2(t,x(t)))dt

V28!

8

+ W(tl,x(tl))}}

8
= min {J L(t,x(t),U(t,x(t)), Vl(t,x(t)))dt

+ w(8,x(8)}, (4.1.13)

 

up."
1
\

 

—l

95

since the second minimum is given by V2 = V. Now

8
\rAin { I L(t,x(t),U(t,x(t)),V‘l(t,x(t)))dt + W(B,x(B))}

.5 I‘. Z RA‘I!‘
')

B
2 min { I L(t,x(t),U(t,x(t)),v(t))dt + W(B,x(B))}.

(4.1.14)

 

P- 1 L. '3;

the minimum being taken over admissible arcs (4.1.6).
Combining (4.1.12), (4.1.13), and (4.1.14) establishes
(4.1.5). The inequality in (4.1.14) arises from consider—
ing v‘s which do not satisfy v(t) = V(t,x(t)) for any

VeT, since v is only required to be piecewise continuous

and V‘is piecewise C(l). One may also note that

min, min and min could be replaced by inf , Tnf,

VET; VleT_ V2eT VET VleT
Tnf without changing the validity of the argument.
VZET

In an analogous fashion a minimax field could be defined
in which.V is player Two‘s minimax strategy. While the
theorems in this section are stated for maximin fields,
they hold also for minimax fields if the obvious changes
03.g. in inequalities) are made.

The fact that the inequalities defining an optimal

field.can be obtained from the assumption that the players

ijl.a differential game have optimal strategies (as has

 

96

just been demonstrated for a maximin field) motivates the
study of such fields in connection with differential

games. However, the continuity prOperties of the function
W have not been Obtained. It would be necessary to show
this if one wanted to demonstrate that the field corre-
sponds to the solution of the differential game. Berkovitz
[3] assumes that a differential game has a saddle point

and shows that if the decomposition of T corresponding to
the Optimal strategies U and V is Of a certain type, called
a "regular decomposition," the payoff J(t,x; U,V) has the
continuity properties required Of W.

As before let E be defined by
E(t,x,u,v) = L(t,x,u,v) + Wt(t,x) + Wx(t,x)f(t,x,u,v).

Theorem 4.1

 

The functions U, V, and W satisfy on T

E(t,x(t),U(t,x), V) Z E(t,x,U(t,x),V(t,x)) = 0

(4.1.15)
where ve‘i’(t,x), and
E(t,x(t),U(t,x(t)),V(t,x(t))) =
= uein,X) {8W18fx) E(t,x’u,V)} .(4.1.16)

 

 

97

If {3(a)} is a C(l)-decomposition of T corresponding to
U, V and W, (4.1.15) and (4.1.16) hold on each T1”), and

(4.1.15) holds on the manifolds separating regions of the

 

decomposition if interpreted with U, V, W and WK as

t
limits from one of the adjacent regions. If (5,?)88 E(a)
is a point on one Of these manifolds such that for all
Ub¢(€,?), (F,?,U) is a point of continuity of

inf E(a)(t,x,u,v), (4.1.16) also holds at (3,?) in the

same limiting sense. The expression

 

E(a)(t,x,U(a)(t,x),V(a)(t,x))

= max {TIE E(a)(t,x,u,v)}
He¢(t,x) (t,x,u)-+(t,x,u) ch(t,x)

(4.1.17)

(a), ue¢(t,x), holds regardless of the

where (t,x)e T
continuity Of inf E(a).

Proof.—«The equations

E(t,x,U(t,x),V(t,x)) = min E(t,x,U(t,x),v) = O
veT(t,x)
are consequences of Theorem 3.1 and its second corollary,
for with U fixed, T, W and V form an Optimal field of

the type considered in section 3.1. This establishes

(4.1.15).

 

 

98

It remains to show that (4.1.16) holds. Let (€,f)

be a point of continuity of U, V, W and WK, and let U

t
be any admissible strategy. Arcs to be considered are

admissible arcs of the form
£3 x(t), u(t), v(t) F — 6 5 t 5 E, 6>O (4.1.18)

with x(6) = f, u(t) = U(t,x(t)). From the definition of

the field

”I

W(t-e,x(t-e)) 3 min {I L(t,x(t),u(t),v(t))dt
v

"I

-E

+ W(?,?)} ' (4.1.19)

for each a such that O 5 e 5 6. If V(t), €‘- 6 S t - F,
is the v which minimizes the expression in (4.1.19), for

e = 6 the same V minimizes (4.1.19) for e on [0,6]. Then

t
W(tse,x(t;e)) ZJ L(t,x(t),u(t),V(t))dt + W(t,x).
t—e

But

t
J L(t,x(t),u(t),V(t))dt =
515 J

dI

 

[E(t,x(t),u(t),V(t))
—e

“I

— wt(t,x(t)) - wx(t,x(t))f(t,x(t),u(t),V(t))ldt

t
= [_ E(t,x(t),u(t),V(t))dt + w<€;e,x(t;e)) - w<€,§)
t—e

   

Since 99

[Wt(t,x(t))+Wx(t,x(t))f(t,x(t),u(t),v(t))]dt= dW
t-

[N

Thus —
25(2) A E(t,x(t),u(t),'\'r(t))dt s 0.

t-e

The function E has a maximum on [0, 6] at e = 0, since

gCO) a 0. Since g is differentiable
o zg‘(0) = E(t',?,'u',?), (4.1.20)
where

H’= liM. u(t), V = lim' V(t).
t+t— t+t—

Since U'is any strategy in T, 5 may be any point in ¢(€,?).

Then, from (4.1.20)

inf _ _ E(E,§,E,V) 5 O for any Ut¢(€,?).
vsV(t,x)
Since inf _ _ E(t-,?,U(t—,?),V) = o by (4.1.15),
vsV(t,x)

equation (4.1.16) holds. Suppose that (6,?) is a point on
on a manifold of discontinuity which is part of the

boundary of the subregion TI“), and that EE¢(E,?). Since

inf E(“)(t,x,u,v) S 0 on 3(a)
V

Ti?!)- ____ { inf E(a)(t,x,u,v)} 5 0, (4.1.21)
(t,x.u)+(t,x,u) veW(t,x)

 

 

100

A180
E(O‘)(t,x,U(°‘)(t,x),v(0‘)(t,x)) = 0 on Fm)
implies
E(“)(t,i‘,u(°‘)(t,x),v(“)(t,x‘)) = o (14.1.22)

This equation combines with (4.1.21) to give (4.1.17). If

(F,?,E) is a point of continuity of inf E(a)(t,x,u,v),
V

1im_____ inf E(a)(t,x,u,v)
(t,x,u)9(t,x,u) veV(t,x)

= inf E(“)(t,x,‘d,V),
veT(t,?)

and this may be used to substitute in (4.1.17). In (F,?,H)

is a point of continuity of inf E(a)(t,x,u,v) for each

V
ue¢(t,x),
E(O‘) (t,x,U(°‘) (t,x) ,V(°‘) (t,x))
= max { inf E(a)(€,?,u,v)}

u€¢(t,?) veT(f;?)

This cannot be concluded in general, since inf E(a)(t,x,u,v)
v

Inay not be continuous. It is however, upper semicontinuous,

which yields

 

101

inf E(O‘) (t,x,u,v) Z
V€W(t,x)

TIE { inf E(a)(t,x,u,v)}
(t,x,u)+(F,?,fi) veW(t,x)

The next theorem is Theorem 3.3 restated for the
present type Of field. The definitions of H and P are
the same as before--although the U, V and W used in them
are different, W now being a maximin value function, U,
player One‘s maximin strategy, and V the strategy optimal

against U.

Theorem 4.2
At each point (t,x) in a maximin field T, the

statements
H(t,x,U(t,x),V(t,x),P(t,x)) 5- H(t,x,U(t,x),v,P(t,x)),
veT(t,x), (4.1.23)

H(t,x,U(t,x),V(t,x),P(t,x))

= max inf H(t,x,u,v,P(t,x))
ue¢(t,x) veW(t,x) (4.1.24)

hold” Moreover, U, V and W satisfy

Wt(t,x) + H(t,x,U(t,x),V(t,x), Wx(t,x)) = 0. (4.1.25)

'The usual limiting sense is given to (4.1.23) and (4.1.25)

gm; manifolds of discontinuity. Equation (4.1.24) must be

jJTterpreted with the same caution about limiting values of

 

102

inf H(t,x,u,v,P(t,x)) as with inf E(t,x,u,v) in
V v

(4.1.16).

Finally, the integral
1* = {P(t,x)dx - H(t,x,U(t,x),V(t,x),P(t,x))dt}

is independent of the path in T,
Proof.--The proof is similar to that given for
Theorem 3.3. It amounts to a restatement of Theorem 4.1

in different notation.

Theorem 4.3

Theorem 3.4 holds for maximin fields without restate—
ment.

T32g£,--The inequalities defining the type of field

are not used in the statement of Theorem 3.4 or in its
proof. Theorem 3.4 holds for any continuous, piecewise
C(l) function W on a region T, regardless of its origin.
In the present context the statement about H and P (3.2.13)
is a consequence of (3.2.8) (defining H and P), (4.1.25)
and (3.2.12).

To hold for a maximin field, the corollary to

Theorem 3.4 must be reformulated.

Thegrem 4.4

 

(1)

Let {3(a)} be a C —decomposition of T based on

U, V and W, and let P be a set of indices a such that

 

103

the manifold M_= () BTfa) is not empty. If there exist a
def,

maximin strategy U and a strategy V Optimal against U which
prescribe optimal paths lying in M, then at each point

(5,?) of}M

E(a)(E,?,U(T§,?),v) 2 E(“)(t,x',U('€,x'),V('t‘,x)) = 0 (4.4.26)

whenever VEV(E,?), (l,f(t,?,U(E,?),v)) is tangent to M

and def. Further,

E(“)(t,x‘,U(t‘,x"),V(t,i)) = max in; E(O‘)('t',x‘,u,v).
u ve¢(t,?)

(4.4.27)

The :maximum is not necessarily taken over all u in
¢(E,?), but is taken over a subset of ¢CF,?). For each

u in this subset there must exist an admissible arc

52(t),U(t,§E(t)),V(t) aSt st

Ix)

(4.4.28)
£(t‘)=‘x', U(E,?)=u (t,?(t))e AZ“;

where Dag, which minimizes

E
[ L(t,x(t), U(t,x(t)), v(t))dt + W(F,?)
a

among admissible arcs

104

£3 x(t), U(t,x(t)), v(t), on S t S F

with (4.1.29)

x(F) ='?.

The arcs (4.1.29) need not lie in TTET, although (4.1.28)
is required to do so.

TTQQT,-—Since V is the strategy minimizing against U,
the sections of the corollary to Theorem 3.4 which apply to
minimization yield (4.1.26) immediately. The tangency
restriction allows one to state (4.1.26) with U(F,?) and
V(E,?) rather than U(a)(€,?) and V(a)(€,?).

(a)

If, for def, one defined W and Wx on M‘to be W

t
and Wx(a), one can obtain (4.1.27) with the same argument
as used in the proof of Theorem 4.1 provided that the
stated restrictions are satisfied. These allow the use
of E(a), w (a) and wx(“) for E, w

t t
The comments preceding Theorem 3.5 indicate that the

and WX in the argument.

following theorem is true.

Theorem 4.5

Theorem 3.5 holds without alteration for a maximin

field.

Proof.--Theorem 3.5 is independent of the type of

optimal field; indeed, it depends only on the existence of

(l)

a pair of strategies C on a region TC T, and a function

W satisfying

 

 

105

t1

W(t0,x(t0)) = L(t,x(t),U(t,x(t)),V(t,x(t)))dt

+ W(tl,x(tl))

for admissible arcs I defined by the strategies U and V
lying in T.

One would wish to have results analogous to Theorems
3.6 and 3.7. However, in a maximin field, the strategy U
is not optimal-—does not maximize-~against the strategy V.
Since U does not maximize, one would not expect conditions
such as Hu = O or a multiplier rule to hold. Furthermore,
while a global extremum is a local extremum, a global
saddle point is a local saddle, a global maxmin is not
necessarily a local maxmin. Nevertheless some partial
results can be obtained. If U is considered fixed, the
maximin field is an Optimal (minimizing) field in which V
is the optimal strategy. This property may be used to
obtain the following theorems. The proofs are omitted,

since they are similar to the proofs of Theorems 3.6 and

3.7.

Theorem 4.6
Suppose that on the region g‘of Theorem 3.5 that

W(t,x) is Open, or alternatively that V(t,x) is an interior

point of V(t,x). Then on T, U, V and W satisfy

 

 

106

Wt(t,x) + H(t,x, U(t,x), V(t,x), Wx(t,x)) = 0

Hv(t,x, U(t,x), V(t,x), Wx(t,x)) = 0.
An extremal of the field

3.: x(t), u(t), v(t) a s t s 5

(4.1.30)

satisfies, with p(t) = P(t,x(t)) the canonical Euler

equations

X
II
{It
'0 0
II
I
21‘.
>4
+
SE
C.
C.‘
>4
:1:
II
0

on the region Q,

Theorem 4.7

 

(4.1.31)

(4.1.32)

Suppose that T2 is given by the constraint conditions

(2.2.7c and d), i.e., by

¢B(t,X,V) 5 O B l, ..., s'

(pB(t,x,v) = o s

s'+l,..., s.

Then there exist multipliers 08(t,x), piecewise continuous

(l) B

on T (piecewise C if the 0

that on T

are of class 0(2)) such

 

107

08(t,x) Z 0
08(t,x)wB(t,x,V(t,x)) = O B = l, ..., s, not summed,

Hv(t,x,U(t,x),V(t,x),P(t,x)) + 68(t,x)w§(t,x,V(t,x)) = 0.

(4.1.33)

The usual interpretation is made at points of discontinuity.

Let
E: x(t), u(t), v(t) a 5 t 5 b

be an extremal, such that there is a decomposition

(co-(ti<ooo< tN = b

of the interval [a,b] with (t,x(t)) in a region of con-
tinuity of U and V on each of the intervals comprising
the decomposition (thus excluding arcs which have subarcs
lying on manifolds of discontinuity Of U or V). Then T

satisfies, with

pi(t) = P1(t,x(t))

08(t) v8(t,x(t))

the canonical Euler equations

 

108

x(t) = Hp(t,x(t),u(t),v(t),p(t)) (4.1.34a)
r(t) = —(Hx(t,x(t),u(t),V(t),p(t))
+ Hu(t,x(t),u(t),v(t),p(t)) Ux(t,x(t))
+ v(t) wx(t,x(t),v(t))) (4.1.34b)
Hv(t,x(t),u(t),v(t),p(t)) + v(t)1.bv(t,x(t),v(t)))= 0
(4.1.34c)
w8(t,x(t),v(t)) s o s = 1, , s'
(4.1.34d)
wB(t,x(t),v(t)) = o 5 = s'+l, , 5

together with
5%-H(t,x(t),u(t),v(t),p(t))==Ht(tsx(t),u(t):V(t)ap(t))

+ Hu(t,x(t),u(t),v(t),p(t)) Ut(t,x(t))

+ v(t) wt(t,x(t),v(t)) (4.1.35)
on each of the intervals (ti-1’ t1) 1 = l, ..., N. At
the points ti’ 1 = O, ..., N, these expressions hold in

the sense of left- and right-hand limits.

In this last theorem HVVx and HVV were replaced by

t
vwx and th, as was done in Theorem 3.7. A similar

109

replacement for Hqu and HuUt could not be made since U
does not maximize against V.

One could also consider the situation in which V
is player Two's minimax strategy, and not the strategy
minimizing against the maximin strategy U. Provided that
on T_a function W continuous and piecewise C(l) is
defined which satisfies (on T)

t

W(to,x(t0))= I l L(t,x(t),U(t,x(t)),V(t,x(t)))dt

to

+ W(tl,x(tl))
for admissible arcs
x_: x(t), U(t,x(t)), V(t,x(t)) tO 5- t 5 t1,

Theorems 3.4 and 3.5 apply in this case also. This is so

because these theorems do not depend on the Optimality

of U or V.

 

V. TRANSVERSALITY AND DISCONTINUITY

CONDITIONS

5.1 Transversality Conditions

 

 

I"?
Let I
£5 x(t), u(t), V(t) t0 5 t 5 t1 i
i.
(t,x(t))e;T, to S t 5 t1 (5.1.1) i
’ L

(tl,x(tl)) = (1(0), m» 611;,

be an extremal arc. The transversalipy conditions are

 

obtained by requiring that

W(t,.xuln = K(o) (5.1.2)

Theorem 5.1

 

Let T' be that subset of T which contains the
terminal points of all extremal arcs (3.4.1) which are not
tangent to T_at (tl,x(tl)). Let {5(a)} be a C(l)_
decomposition based on K, T, and X, and let E'be a point

(on)

of one of the T for which

(t (t(o), X(O))E:T',

l’xl)

such that there exists a neighborhood N of (tl,xl) such that

UandVare 0(1) onNflT= N'.

110

   

111

Then the transversality conditions
Wt(tl,xl) 110(6) + Wx(tl,xl) xo(6’) = KO(6‘) (5.1.3)
KO(6") + H(tl,xl,U(tl,xl),V(tl,xl)-P(tl,xl)) TOG)
- P(tl,xl) x0(6‘) = 0 (5.1.4)

hold, where Wt, WX,

values as (t,x)eN'+(tl,xl).

H, P, U and V are given their limiting

Proof.——Equation (5.1.4) follows from (5.1.3), the
definitions of H and P, (3.2.8), and the Hamilton—

Jacobi Equation
Wt(t,x) + H(t,x,U(t,x),V(t,x),Wx(t,x)) = O

(l)

The functions U and V have C extensions to the neighbor-

hood N.

Consider the differential equations
x = f(t,x, U(t,x), V(t,x)) (5.1.5)

There is a constant p > 0 such that there is a unique

solution x lying in N, Of (5.1.5) through the point

0,

(tl,xl) on the interval [6,8], a = tlv-p, B = t1 + p.

Furthermore, there exist constants p', n > 0 such that

through each point (1,5) satisfying

a—D'STSB+9', IE—x0(r)|<w

 

 

 

112

there is a unique solution
x(t,1,£) a - p' < t < B + 0‘ (5.1.6)

of (5.1.5), containing xO

On N' each of these solutions is an extremal arc.

for d s t s B, E = XO(T).

By hypothesis, each one intersects T} and is not tangent

““‘I

to it. Let t(T,€), x(T,€) be the point of intersection Of
(3.4.6) with 1'.

W(I,€) must satisfy, by (5.1.2)

 

t(T,€)
w<:,g) = I L(t,x(t,T.£),U(t,x(t,I,€)LV(t,x(t,IfiD»dt+K(o)

T

where t(r,§)= T(o), x(T,€) = X(o), or equivalently

G(0,T,€) A -X(T(o),T,€) + X(O) = 0. (5.1.7)

G is C(l) in o, T and 6, because of the properties of
the solution (5.1.6), T and X. If ‘GiOJ(3,tl,xl) # 0,
(1)

(5.1.7) determines o as a C function of (I,§) in a
neighborhood of (tl,xl), which may be taken to be N

without loss of generality. The nontangency assumption
assures that the determinant is nonzero, since then the

matrix

1 TO(E)

f(tl,xl,U(tl,xl), V(tl,xl)) x (E)

O'

   

113

has rank n+1. By elementary transformations this becomes

1 O

f(tl,xl,U(tl,xl), V(tl,xl)) M
where
M = XO(3) - f(tl,xl,U(tl,xl), V(tl,xl)) TG(3)
has rank m. But since

§%xx(t,T,E) = f(t,x(t,T,€),U(t,x(t,r,g),V(t,x(t,T,g)))

3G
53- (o,tl,xl) = Xo(o) -f(tl,xl,U(tl,xl),V(tl,xl))TU(O)=M
and the determinant lGij Then
0 # 0.
{T(G(T,€)

W(T,§) = J L(t,x(t,T,€),U(t,x(t,T,£),V(t,x(t,T,€)»dt
T

+ K(o (T,€)).

(l) (l) (d)

W(T,£)is C on Nn T since T and K are C on K ,

(
O and x are C(l) on N, L is C‘l)

(l)

in (t,x,u,v) and U and V

on N.

are C

 

 

114
Let
W(T,€) = W(T(o(1,€)), X(0(T,€))) = K(0(T,€))

and let (?QE) be a point on the extremal x0. Then

8" = amt), 11(6) —

t1, X(E) = x and

1

dw (Tr-.3)

wT(?,§)dT + w€(?,€)d€

(Wt(t1,xl)TO(5“)+Wx(tl,xl)XO(3) ) (oT('-E‘,‘g‘)dr

+

055.3%)

Ko(3) (OT(?,§)dT + O€(?,§)d€).
Since dT and d5 are arbitrary
wt(tl,xl)TO('o‘) + Wx(tl,xl) x0(o) = K06")

as was to be proved.
The proof of this theorem is based on the proof used
by Berkovitz [3] for a related result applied to transition

surfaces (of. the following section).

5.2 Manifolds of Discontinuity

 

A careful application Of Theorems 3.2 and 3.4 can
yield additional conditions at certain types of manifolds
of discontinuity. Three main types are considered:

transition surfaces, dispersal manifolds, and universal

manifolds. This terminology is due to Isaacs [20].

 

 

115

Let M_be an n-dimensional manifold of discontinuity
of U or of V (or of both), (where U and V are optimal
strategies in the case that the game has a saddle point,
U is a maximin strategy with V optimal against it, or V
is a minimax strategy with U optimal against it). If,

for each point (5,?)sM, there is an extremal
T: x(t), u(t), v(t) d 5 t 5 8 (5.2.1)

with x(5) = ?, d < 5'< B, and x(t)¢M for t # 5, M_is

called a transition surface.

Theorem 5.2
(1)

Let {T}a)} be a‘C —decomposition of T based on U,

V and W for a game with a saddle point, and suppose that

 

M = 5:3)[) T(B)(1;T.is a transition surface which is a
manifold of discontinuity of at most one Of the strategies
U and V. If at (5,?)eM, the arc (5.2.1) intersecting M
at (5,?) is not tangent to Mlas t + 5'— 0 and t 4 5‘+ 0,

w (“(5,2) = wt(B)(t,x) and wx<“)(t‘,§) = wx(8)(t,3£). That

t
(l)

is, W is C at (5,?).

Proof.-—From Theorem 3.4, for any vector (dt, dx)

tangent to M‘at (5,?)
(wt (0‘) (t,x)-wt (B) (t,x) )dt+(Wx (0‘) (F.f)-WX(B) (t,x) )dx=0 ,

which indicates either that

wt (0‘) ('t,3?)=wt “5 ) (15,3?) and wXIO‘) (t,x)=wx(8) (t,x)

 

 

116

or that

(a) _ w (e)

(a) (8)
(wt t ’ wx —‘wx )

(t,x) = 5,x)

is a nonzero vector orthogonal to M_at (5,?). Let (u,v)
be any vector orthogonal to M_at (t,x). Then, since M‘is

a transition surface

and

.1 + vf(5,?,U(5,?) ,V(B ) (t,x))

have the same sign, where, for definiteness, V is taken to
be the strategy having the discontinuity. Further, by the
nontangency assumption, this sign must be either strictly
positive or strictly negative.

By Theorem 3.2

L(5,?,U(5,?) ,V(°‘) (t,x))

( ) —-—
- wt °‘ (t,x)

+
2':
A
Q
V
A
“I
U
>“I
V
H)
A
“I
>"I
U
C‘.‘
A
ffl
NI
V
U
<
Q
V
A
“I
U
“I
v

s L(5,?,U(5,?) ,v‘“ (t,x))

+ wXIO‘)(t,x)mtjmwj),v(8)(t',36)).

Likewise,

 

117

-thB) (t,x) = L(5,?,U(5,?) ,v( 8 ) (t,x))
+ w (B)(5,x)f(5,?,U(5,?),V(B)(5,?))
_ L(5,?,U(5,?) ,v(°‘) (t,x))
+ wXIB)(t,i‘,)f(t,x,U(t,x‘),v(“)(t,x‘)).

Consequently, on the one hand
(a) —- (8) '— (8) ._
Wt (5,x) - Wt (5,x) 2 (Wx (5,x)

" Wx(a)(€,f))f(-fi-,Y,U(E,f) ,V(B)(€.a-XT))
and on the other hand
w,(°‘)(t',x) — thBNt‘m 5- (wx(3)(f.x)
_. wX (0‘) (5,?) )f(_,?,U(5,?) ,V(°‘) (t,x) ).
By rearranging
(wt(°‘)(t‘,x') — wt(8)(t,sz)) + (wx(0‘)(t‘,3£)
— WX(B)(5,?))f(5,?,U(5,?),V(a)(5,?)) .<- ,o
(wt(°‘)(t',x') - th8>(5,2)) + (wx(°‘)('t".i)

_ WX(B)(5,?))f(5,?,U(5,?),V(B)(5,?)) 2 0

(5.2.2)

 

118

t(B)’ wx(9) - wx(B)) evaluated at (5,?)

is a nonzero vector orthogonal to M_at (5,?), both of

But, if (wt(“) — w

these quantities must be either strictly positive or

strictly negative, which is impossible. Therefore

Wt(a)(t,x) Wt(8)(t,x)

and

Wx(a)(t,x) WX(B)(t,x).

This theorem and the method Of proof are due to

Berkovitz [3].

Corollary

 

Theorem 5.2 holds for a transition surface M

(i) in a maximin field, if the maximin strategy is
continuous across M
(ii) in a minimax field, if the minimax strategy is
continuous across M
(iii) in an optimal field for a control problem, if
L and f are continuous in (t,x).
TTQQT,--This is true since the proof Of the theorem
requires varying only the discontinuous strategy, which is
either a minimizing strategy or a maximizing strategy.

The proof (given for a minimizing strategy) is actually

the proof for an optimal control problem with

 

119

f(t,x,v) L(t,x,U(t,x),v)

and
5(t,x,v) = f(t,x,U(t,x),v),

and holds if L and 5 are continuous in (t,x) at (5,?).

The next theorem concerns manifolds such that each
point (5,?) on one of these manifolds is the initial point
for several extremal arcs, each Of which proceeds, for
t > 5 into a different subregion of .F.‘_- Manifolds of this
type are called dispersal manifolds. The theorem also
holds for points on manifolds to which several extremal
arcs converge. That is the extremals are distinct for
t < 5, but all have the point (5,?) in common.

As before {2(a)} is a C(l)—decomposition of kaased
on U, V and W for an optimal field in which U and V provide

a saddle point.

Theorem 5.3
Let M.= Tfiajf) TEij) T_be a dispersal manifold.

Then at (5,?)eM

 

(a) -:- (a) —-— (d) —»—
(Wt (t,x) - Wt (t,x)) + (Wx (t,x)

_ WX(B)(5,?))f(5,?,U(OL)(5,?),V(a)(5,?))

3 0 (S 0) (5.2.3)

 

 

120

and

(wt(°‘)<t,x) - wt(8)(’c‘.3€)) + (wx(°‘)(t',3c')
- wx(3>(t‘,3€>)f(‘t‘.‘f,U(B)(t,x).v(8)(€,‘i))

5- 0 (->- 0). (5.2.4)

that is, that these expressions have opposite signs.

Furthermore

(14,996,?) - wt(8)(‘t',i’)) + (wx‘“)(€,x‘)

IV
0

.. wx(8)(t,s))r(t,i’,u(°‘)(t,x),v(5)(t,x‘))

(5.2.5)

and

(wt(°‘)('€,3€) - wt(8)(‘€,3€>) + (wx(°‘)(‘t',i)

— WX(B)(5,?))f(5,?,U(B)(5,?),V(°‘)(5,?)) s 0

(5.2.6)

If M_is a surface (n—dimensional manifold), if the players
choose between U(a) and U(B), V(a) and V(B), and if

(5.2.3) to (5.2.6) are all strict inequalities, one of the
(a)

players can choose which extremal arc--the one entering T

or the one entering T(B)—-is taken.

 

121

If the dispersal manifold M =flfifiyfl T for some set
of indices P, (5.2.3) to (5.2.6) apgig to each pair a, 8,
der and 88?.

T399T,--Let (u,u) be a vectOr orthogonal to Mlat
(5,?). Then the statement that there exist distinct arcs

. (Y) (Y) '— S S
éy' xy(t),U (t,xy(t)),V (t,xy(t)) t t t

1’
Y = “as:
with

(t,xy(t))€T(Y) for t < t 3 t1 (5.2.7)
is equivalent to

u + yf(t‘,x,U(°‘)(t',i‘),v(°‘)(t’,x)) 2 0 (-<- 0) (5.2.8)
and

u + tut—5,11“)(t,x),v(8)(t,x)) 5- o (->- 0) (5.2.9)

that is, the two expressions have Opposite signs.

By Theorem 3.4 (Wt(a)(5,?) - Wt(8)(5,?), Wx(a)(5,?)
- WX(B)(5,?)) is either zero or a nonzero vector orthogonal
to M.at (5,?). If it is zero, the relationships (5.2.3),
(5.2.4). (5.2.5) and (5.2.6) are satisfied trivially. If

it is not zero, then (5.2.8) and (5.2.9) hold with

'C
I

(wt(“)(t,x) — wt(8)(t,x)) and

v = (wx(“)(t,f) — wx(3)(t,x)),

 

 

122

yielding (5.2.3) and (5.2.4). As a matter of notational

convenience, set

f(U,V) = f(5,?,U(5,?),V(5,?))
L(U,V) = L(5,?,U(5,?),V(5,?))
(wt,wx) = (wt(5,§),wx(E,§)). 55'

From Theorem 3.2 one obtains

IV
”1..—m. [Mn 2.

L(U(“),V(B)) + wt(“) + wx(“)f(U(“),V(B)) 0 (5.2.10)

L(U(B),V(a)) + w (a) + wx(a)f(U(B),V(a)

t ) S 0 (5.2.11)

and

IA

L(U(OI),V(B)) + W (B) + wx(8)f(U(a),V(B))

t 0 (5.2.12)

IV

L(U(B),V(°‘)) . w (a) + wx(s)f(U(s),V(c>)

t 0 (5.2.13)

Subtracting (5.2.12) from (5.2.10) yields (5.2.5) and
subtracting (5.2.13) from (5.2.11) yields (5.2.6).

Suppose that (5.2.3) to (5.2.6) are all strict
inequalities, so that none of the arce corresponding to
(U(G),V(G))’ (U(a),V(8)), (U(B),V(a)) and (U(B),V(B)) with
initial condition (5,?) are tangent to M at (5,?), and
suppose for definiteness that (3.4.10) > 0. Then both of
the arcs corresponding to (U(a),V(a)) and (U(a),V(B))

(on)

enter T In the same manner, both arcs corresponding to

123

(U(B),V(a)) and (U(B),V(B)) enter TIE). Clearly player

(a) (B) If

One can choose to enter either T_ or T, .

(3.4.10) < 0, then player Two has the choice.

If M = (1 Thin T, the preceding arguments apply to

as?
each pair a, 8, car, 86?.

Corollapy

 

If two or more arcs converge to (5,?)eM instead of
diverging from (5,?), then (5.2.3) to (5.2.6) hold in this
case also. If M = n T-z-aTnT, these inequalities hold
pairwise for a, BeFIEP

TTQQT.--The only change required is that the arcs
(3.4.16) must be defined on some interval t0 5 t 5 5‘

rather than t-5 t 5 t The statement that one player

1'
can choose the arc which is taken is inapplicable to
this case.

Manifolds of the type in the preceding corollary are
called universal surfaces (curves, etc.) by Isaacs EEO].
The corollary to Theorem 3.4 applies to such manifolds.

If M = () Fm T, and I), V are strategies which equal
U, V onaM: the following theorem holds.
Theorem 5.4

Let M_be a universal manifold as just described.

Then at (5,?)eM, for each as?

124
L(5,?,8(5,?),V(a)(5,?)) + wt(“)(t‘,x)
+ wx(°‘)(t,'£)r(t',x,fi(t,x),V‘“)(5,x)) s 0 (5.2.14)

L(5,?,U(a)(5,?),'\7(5,?)) + wt(°‘)(t',x)

+ Wx(a)(5,?)f(5,?,U(a)(5,?),V(5,?)) 2 0 (5.2.15)

The inequality (5.2.14) holds if the field is a minimax
field and (5.2.15) holds if it is a maximin field.

Proof.--These inequalities are immediate consequences
of Theorems 3.2 and 4.1. For example (5.2.15) follows from
(a) (T5,?)

L(5,?’,U(a)(5,?),v) + wt

+ Wx(a)(5,?)f(5,?,U(a)(5,?),v) z 0

in either Theorem 3.2 or 4.1.

The situations covered in the above theorems do not
exhaust the types of behavior exhibited by optimal
trajectories in the neighborhood of discontinuities.
However, most of them can be treated with a careful appli-
cation Of these theorems. For example, if the optimal
trajectories on one side of a surface were parallel to the
surface, and on the other side departed from the surface in
a direction not tangent to it, Theorem 5.3 could be

applied with (5.2.3) (or (5.2.4)) an equality.

VI. CONCLUSION

6.1 Conclusions

Because of the close relationship between differential
games and optimal fields with independent controls,
optimal fields can profitably be studied in connection
with differential games.

In Chapter III Optimal fields with a saddle point were
investigated. The necessary conditions Obtained included
Hamilton-Jacobi equations, Euler equations, and a saddle
point in the Hamiltonian function corresponding to the
saddle point in the Optimal field. Also a multiplier rule
was derived for constraints on the controls given by
systems Of equalities and inequalities. None Of these
results is particularly surprising; they are an extension
of the corresponding results in optimal control theory.

In the fourth chapter a maximin field was introduced.
Maximin fields are a type of Optimal field not previously
treated. In a maximin field one of the players has a
strategy which maximizes a functional among a collection
of functionals minimized by his Opponent. While the
second player has a minimizing strategy optimal against
the first player's maximin strategy, the maximin strategy
is not necessarily Optimal against this minimizing strategy.

It is optimal when the collection of minimal problems is

125

126

considered. Because of this, the results obtained for
maximin fields are not as strong as those for saddle point
Optimal fields. In particular, a multiplier rule which
applies to the constraints on only one player was obtained.
In Chapter Vca transversality condition for extremal
arcs terminating On the surface T was derived. The
behavior Of extremal arcs in the vicinity Of manifolds of
discontinuity was used to derive further conditions at these

manifolds.

6.2 Further Research

 

Further research in optimal fields for differential
games could profitably concentrate on strengthening the
results Obtained for maximin fields. In particular, if
one can be Obtained, a multiplier rule applicable to both
players is a result which would be most useful.

The value function for a differential game is not
necessarily continuous on the playing space T, It may be
piecewise continuous, in which case one could consider
optimal fields defined on each region of continuity.

One would like to obtain conditions relating these optimal
fields on the manifolds of discontinuity of the value
function.

In differential games in general, rather than in the
optimal fields associated with them, a direction Of research
useful in applications would be into games of imperfect

information. To be successful, this would most likely

127

require some sort of mixed strategy. Mixed strategies
would lead to the consideration of stochastic differential
equations, a difficult subject in itself. Some start in
this direction has been made by Ho [17].

The extension to general N-person differential games
will have to be deferred until the theory of general
games is at a more settled state. Perhaps something
could be done in this line for optimal rendezvous and
collision avoidance problems, which are two-person non-

zero-sum games.

BIBLIOGRAPHY

128

BIBLIOGRAPHY

L. D. Berkovitz, "Variational methods in problems of
control and programming," Journal Of Mathematical
Analysis and Applications, V. 3 (1961), pp. 145-169.

L. D. Berkovitz, "A variational approach to differential
games," in M. Dresher, L. S. Shapley and A. W. Tucker,
eds., Advances in Game Theory, Annals of Mathematics
Study 52, Princeton University Press, Princeton, N. J.,
1964, pp. 127-174.

 

L. D. Berkovitz, "Necessary conditions for Optimal
strategies in a class of differential games and control
problems," SIAM Journal on Control, V. 5 (1967), pp. 1—24.

L. D. Berkovitz, "A differential game without pure
strategy solutions on an Open set," in M. Dresher,
L. S. Shapley and A. W. Tucker, eds., Advances in Game
Theory, Annals of Mathematics Study 52, Princeton
University Press, Princeton, N. J., 1964, pp. 175-194.

 

L. D. Berkovitz and W. H. Fleming, "On differential
games with integral payoff," in M. Dresher, A. W.~
Tucker and P. Wolfe, eds., Contributions to the Theory
of Games, III, Annals of Mathematics Study 39, Princeton
University Press, Princeton, N. J., 1957.

 

G. A. Bliss, Lectures on the Calculus of Variations,
University of Chicago Press, Chicago, Ill., 1946.

W. H. Fleming, "A note on differential games of pre-
scribed duration," in M. Dresher, A. W. Tucker, and P.
Wolfe, eds., Contributions to the Theory of Games, III,
Annals Of Mathematics StudyI39, Princeton University
Press, Princeton, N. J., 1957.

 

W. H. Fleming, "The convergence problem for differential
games," Journal of Mathematical Analysis and Applica-
tions, V. 3 (1961), pp. 102-116.

W. H. Fleming, "The convergence problem for differential
games, II," in M. Dresher, L. S. Shapley and A. W.
Tucker, eds., Advances in Game Theory, Annals of Mathe—
matics Study 52, Princeton University Press, Princteon,
N. J., 1964.

129

10.

ll.

12.

13.

l4.

l5.

l6.

l7.

l8.

19.

20.

21.

130

IA. Yu. Gadzhiev, "Application of game theory to certain
jproblems in optimal control." Avtomatika i telemekhanika,
'V. 23 Nos. 8 and 9 (Journal translated as Automation and
Remote Control.)

‘V. B. Gindes, Optimal processes for two controlled
systems," Proc. 3rd Siberian Conference on Mathematics
and Mechanics, Tomsk, USSR, 1964, pp. 260—261.

V. B. Gindes, "Optimal control in linear systems under
conflict," SIAM Journal on Control, V. 5
(1967), pp. 163—169.

T. Guinn, "Boundary arcs for a class of differential
games," to appear in Journal of Optimization Theory and
Applications.

J. C. Harsanyi, "A general solution for noncooperative
games based on risk-dominance," in M. Dresher, L. S.
Shapley and A. W. Tucker, eds., Advances in Game Theory,
Annals of Mathematics Study 52, Princeton University
Press, Princeton, N. J., 1964.

M. R. Hestenes, "A general problem in the calculus of
variations with applications to paths of least time,"
RAND Corporation Research Memorandum RM—lOO, February,
1949.

M. R. Hestenes, Calculus of Variations and Optimal
Control Theory, John Wiley and Sons, Inc., New York,
1966.

Y. C. HO, "Optimal terminal maneuver and evasion
strategy," SIAM Journal on Control, V. 4 (1966),
pp. 421-428.

Y. C. Ho, A. E. Bryson, Jr., and S. Baron, "Differential
Games and Optimal Pursuit-Evasion Strategies," IEEE
Transactions on Automatic Control, V. AC-lO (1966),

pp. 385-389.

R. Isaacs, Rand Reports RM-1391 (November, 1954),
RM-1399 (November, 1954), RM—l4ll (December, 1954),
RM-l486 (March, 1955).

R. Isaacs, Differential Games, John Wiley and Sons, Inc.,
New York, 1965.

D. L. Kelendzheridze, Theory of an Optimal pursuit
strategy," Soviet Math. Doklady, V. 2 (1961), pp. 654—
6566 (translation of Doklady Akad. Nauk SSR, V. 138
(19 1)).

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

131

Yu. A. Kochetkov, "Application Of Pontryagin‘s method
to investigation of minimax automatic control problems,"
Tekhnicheskaya Kibernetika, NO. 5 (1965) (journal
translated as Engineering Cybernetics).

N. N. Krasovskii, "The pursuit problem in the case of
identical players," PMM, V. 3 (1966), NO. 2.

N. N. Krasovskii and V. E. Tret'yakov, "The pursuit
problem in the case of constraints on the impulses of
the control forces," Differentsial'nye uravneniya, V. 2
(1966), NO. 5.

N. N. Krasovskii, Yu. M. Rupin and V. E. Tret‘yakov,
"On certain game situations in the theory of controlled
systems," Tekhnicheskaya kibernetika, NO. 4 (1964)
(translated in Engineering Cybernetics V. 4 (1964),

pp. l-ll).

R. D. Luce and H. Raiffa, Games and Decisions, John
Wiley and Sons, Inc., New York, 1957.

 

P. A. Meschler, "On a goal-keeping differential game,"
IEEE Transactions on Automatic Control, V. AC-l2
(1967), pp. 15‘2lo

J. Mycielski, "Continuous games of perfect information,"
in M. Dresher, L. S. Shapley and A. W. Tucker, eds.,
Advances in Game Theory, Annals of Mathematics Study 52,
Princeton University Press, Princeton, N. J., 1964.

 

J. F. Nash, "Non-cooperative games," Annals of Mathe-
matics, V. 54 (1951), pp. 286-295.

J. von Neumann, "Zur Theorie der Gesellschaftsspiele."
Mathematische Annalean-lOO (1928), pp. 295-320.

J. von Neumann and O. Morgenstern, Theory Of Games and
Economic Behavior, Princeton University Press, Princeton,
N. J., 1944.

 

 

L. A. Petrosyan, "On a family of differential survival
games in Rn," Dokl. Akad. Nauk SSSR, V. 161 (1965),
NO. l.

L. A. Petrosyan, "Differential survival games with
several participants," Dokl. Akad. Nauk SSSR, V. 161
(1965), No. 2.

L. A. Petrosyan, "Reduction of one pursuit game to
solution of the Cauchy problem for a first-order
partial differential equation," Dokl. Akad, Nauk Arm.
SSR, V. 40 (1965), No. 4.

35.

36.

37.

38.

39.

40.

41.

42.

43.

44.

45.

46.

132

L. A. Petrosyan, One Class of Pursuit Games,
Candidate's Dissertation, LGU, 1965.

 

L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze
and E. F. Mishchenko, The Mathematical Theory of
Optimal Processes, Interscience, New York, 1962.

 

 

L. S. Pontryagin, "On certain differential games,"
Dokl. Akad. Nauk SSR, V. 156 (1964), NO. 4, pp. 738-
741.

L. S. Pontryagin, "On some differential games," SIAM
Journal on Control, V. 3 (1965), pp. 49-52.

R. K. Ragade and I. G. Sarma, "A game theoretical
approach to optimal control in the presence of
uncertainty," IEEE Transactions on Automatic Control
V. AC—l2 (1967), pp. 395-401.

C. Ryll—Nardzewski, "A theory of pursuit and evasion,"
in M. Dresher, L. S. Shapley and A. W. Tucker, eds.,
Advances in Game Theory, Annals of Mathematics Study
52éuPrinceton University Press, Princeton, N. J.,

19 .

 

I. G. Sarma and R. K. Ragade, "Some considerations in
formulating optimal control problems as differential

games," International Journal Of Control V. 4 (1966),
pp. 265—279.

H. Scarf, "On differential games with survival payoff,"
Contributions to the Theory of Games, III, Annals of
Mathematics Study 39, Princeton UniverEity Press,
Princeton, N. J., 1957.

 

L. S. Shapley, "A value for N—person games," in H. W.
Kuhn and A. W. Tucker, eds., Contributions tO the Theory

 

of Games, II, Annals of Mathematics Study 28,
Princeton University Press, Princeton, N. J., 1953.

E. N. Simakova, "Differential Games," Avtomatika i
Telemekhanika, V. 27 (1966), No. 11, pp. 161—178,
(translated in Automation and Remote Control, V. 27,
pp. 1980—1998).

D. D. Sworder, Optimal Adaptive Control Systems,
Academic Press, Inc., New York, 1966.

 

P. P. Variaya, "On the existence of solutions to a
differential game," SIAM Journal on Control, V. 5

(1967), pp. 153-162.

133

47. A. Zieba, "An example in pursuit theory," Studia Math.
V. 22 (1962), pp. 1-60

48. A.Zi§ba, "Fundamental equations of the theory of
pursuit," Trans. of the Second Prague Conference in

Math. Statistics, 1959.

     

143 30 8

03

IIIIIIIIILIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIEs