REPORT -NO. M720-1 R 41 UNCLASSIFIED COPY NO. ONE PARAMETER SOLUTION OF A GAME OF PURSUIT BY JESUS GIL DE LAMADRID DIRECTOR OF PROJECT A. H. COPELAND, SR. PROFESSOR OF MATHEMATICS CONTRACT N6 ONR 232-1 PROJECT M720-1 AUGUST, 1953

DISTRIBUTION LIST Office of Naval Research Navy Department Air Branch, Code 461 T/3 Building, Room 2609 Washington 25, D. C.. 1.,0*.....................Copies 1 - 10 Office of Naval Research New York Branch Office 346 Broadway New York 10, New York...0...o*.....**..,..........o o. Copy 11 Director, Office of Naval Research Chicago Branch Office The John Crerar Library Building Tenth Floor, 86 E. Randolph Street Chicago 1, Illinois 0.....*.............o *. C.opy 12 Director, Office of Naval Research San Francisco Branch Office 1000 Geary Street San Francisco 9, Californiao.ooo*o..o...o..ooo....o,..Copy 13 Operations Evaluation Group (Op 374) Office of the Chief of Naval Operations Navy Departiment Washington 25, D. C.. e........o.........ooo......oCopies 14 - 15 Director, Naval Research Laboratory Washington 25, D. Co o...............O...o.oovo0o oo.oo Copy 16 Commander, Operational Development Force USS Adirondack, U. S. Naval Base Norfolk, Virginiai., *......* * *. 0Copy 17 Chief of Staff, U. S. Army Attn: DC/S P & R. 3-D-640 Pentagon Washington 25, D. Co........o....oo o 0 e Copy 18 Naval Research Laboratory Washington 20, D. C,....oooo.,...oooo.............e.0Copy 19 Mr. R. A. Bailey Military Operations Research Division Lockheed Aircraft Corporation Burbank, Califo rnia...,.. 0*............ opy 20

ii Chief, Bureau of Aeronautics Navy Department Washington 25, D. Co Attn: Aer - TD - 41.4.o....................o...o.....Copies 21- 22 Chief, Bureau of Aeronautics Navy Department Washington 25, Do Co Attn: Mer. B. A. Wiener, C....................0opy 23 Chief, Bureau of Ordnance Navy Department Washington, D. C. Attn: Re 9.........000...00000.0000 Copy 24 Chief, Bureau of Ordnance Navy Department Washington, D. C. AttnO Re 2.0 0000..000.o 000.......000 0 OCopy 25 Mr. James V o Burke HQ WADC Wright-Patterson Air Force Base, Ohio Attn: WCEGOo.........0 oo o0o0o o 000.00000.. 0...oCopy 26 Research and Development Board Library Branch Room 3 - E - 1065 The Pentagon Washington 25, D. C.....0............................. Copies 27 - 28 Chief of Staff, Uo SO Air Force Washington, Do Co...Oe,,........................o o o Copy 29 Chief of Staff, Uo S. Army Office of Chief of Ordnance Washington, D. C. o.4.0.000.*..0.000.....00 00..00.Copy 30 Professor J. LaSalle Department of Mathematics University of Notre Dame South Bend, Indianao o o o...o............o.. *ooooooooo.Copy 31 Professor T. Ho Hildebrandt, Chairman Department of Mathematics University of Michigan Ann Arbor, Michigan 0 0 o0o. o... o.. 0.............. Copy 32 Professor Richard Courant New York University New York 3, New York,..C*,................*...Copy 33

iii Professor SO Lefschetz Princeton University Princeton, New Jersey..............................Copy 34 Professor William Prager Brown University Providence 12, Rhode Island..4.......................Copy 35 Dr. Richard Bellman The Rand Corporation 1700 Main Street Santa IMonica, California,.....................Copy 36 Professor Edwin W. Titt Indiana University Bloomington9 Indianaa., -.....................Copy 37 Professor G. E. Uhlenbeck Department of Physics University of Michigan Ann Arbor, Mvlichigan.o * * *.......***.................*opy 38 Dr. Andrew Sobczyk 3007 Villa Street Los Alamos, New hMexico C.......................Copy 39 Library U. So Naval Ordnance Plant Indianapolis 18, Indiana............................*...Copy 40 Cornell Aeronautical Laboratory 4455 Genessee Street Buffalo 5, New York Attn: Mr. Ro Shatz O o * o o. ***........Cpy 41 Professor A. W. Tucker Fine Hall, Box 708 Princeton University Princeton, New Jersey.......................Copy 42 Mr. Harry Goode Willow Run Research Center Willow Run, Michigan,.........................Copy 43 Mr. Leonard Gillman DMathematics Department Purdue University Lafayette, Indiana.............***.*.***........ *....Copy 44 Dr. Seymour Sherman Navy Research Group Dept. 72-25 Lockheed Aircraft Corporation Burbank, California.................................Copy 45

iv The Rand Corporation 1700 Main Street Santa Monica, California Attn: Mr. Frank R. Collbohm..........................Copy 46 Engineering Research Institute University of Michigan Ann Arbor, Michigan............................Copy 47 Dr. Max A. Woodbury Department of Statistics Wharton School Univrrsity of Pannsylvania Philadelphia 4, Pennsylvania..*.*..*..*....**......***Copy 48 Bell Aircraft Corporation P. 0. Box 1 Buffalo 5, New York Attn: Dorothy Zeman.............................Copies 49 - 50 Mathematical Reviews 80 Waterman Street Providence 12, Rhode Island.............Copy 51 Armed Services Technical Information Agency Document Service Center Knott Building Dayton 2, Ohio Attn: DSC-SA..................................Copies 52 - 56 Professor Oskar Morgenstern Princeton University Princeton, New Jersey.......................Copy 57 Dean Walter Bartkey Air Weapons Research Center University of Chicago Chicago, Illinois.................Copy 58 Guided Missiles Library, 22-001 Massachusetts Institute of Tecbnology Cambridge 39, Massachusetts........................... Copies 59 60 Dr. E. D. McAlister Eastman Kodak Company Navy Ordnance Division 121 Lincoln Avenue Rochester 11, New York...........................Copy 61

Dro W. Lo Barrow, Chief Engineer Sperry Gyroscope Company Great Neck, New York62........ Professor G. P. Wadsworth, Room 2-285 Massachusetts Institute of Technology Cambridge, Massachusetts..................Copy 63 Commanding Officer, 3151st Electronics Station Watson Laboratories, AMC Red Bank, New Jersey Attn: WLEPL' 1000 000@ 0~000 *04*0**0*******4***s44Copy 64 So B. Littauer, Project Director NONR 266(04) Department of Industrial Engineering Engineering Building Columbia University New York 27, New York..,......................Copy 65 Professor Abraham Charnes Carnegie Institute of Technology Pittsburgh, Pennsylvania.........................,.C..Copy 66 Dro Howard Raiffa Department of Mathematical Statistics Columbia University New York 27, New York..............................Copy 67 Dro Bo 0. Koopman Columbia University New York 27, New York.........**.*.***....*..........Copy 68 U. So Department of Commerce National Bureau of Standards Washington 25, D. C. Attn: 11.3/A-5RA.............................Copy 69

Introduction Ro P. Isaacs formulated and solved* the game of pursuit outlined below. In it the probabilities pertaining to the chance outcomes are assigned definite values (a probability of 1/3 to each outcome). The purpose of the present work is to assign to these probabilities values depending on one parameter a, to study the effect of this on the game, and to obtain a solution ('as far as is possible) in terms of a. The problem is not completely solved. Most of the features of the solution which are direct extensions of the case a = 1/3 (the game of RMPI-791), are obtained together with others. There are still others whose treatment requires a deeper analysis. These were foregone for lack of time. I have tried to indicate where the gaps lie, unless they seem quite evident. Following is an outline of the original game. For further details, see RM-791, It is a two-person zero-sum game. One player is called the pursuer, P; the other, the evader, E. Both move in a discrete lineal set. This set may be denoted by the sequence of integers o o., -2 -1, 0, 1 2, o. At each move, if E is at point i, he can make any of three moves, to i + 1, i - 1, or remain stationary. If P is at point i, he can make any of four moves, to i +, to o i - 1, to i + 2, or to i - 2. He may not remain stationary. E is completely informed of P's position, and P's state of information. On the other hand, P's information about E's position is incomplete. After each one of E's moves, there is a signal indicating E's position to within three points (each with probability 1/3). P's information * R. P. Isaacs, A Pursuit Game with Incomplete Information, Project RAND Research Memorandum RM-791, Constant reference will be made to this paper which is my sole direct source, and throughout this report it will be referred to as RM-791, -1

is based entirely on all signals given. The cycle of moves is as follows: 1l E moves. 2. Signal 3. P moves, A description of a signal is as follows: If E is at point n one of the following signals may occurs = (n - 2, n- 1, n) = (n-, n, n + l) 06~ = (n, n +, n + 2) each with probability 1/3. Each signal contains the information that E is at one of the points indicated in it, Capture occurs when P and E are at the same point. The payoff to E is the number of cycles before capture. After several moves P can come and maintain himself within at most two moves of E. When this occurs two configurations can describe the relative positions of E and P. These two configurations (Configuration I and Configuration II) are shown respectively in Figures 1 and 2. Each represents the given configuration and P's knowledge of it, The point marked with a square indicates the position of P. E may be at either of the 2 points marked with probabilities S and 1 - S in Figure 1, T and 1 - T in Figure.2. For example in Configuration I (Figure 1), S is the probability that E is at 3; and 1 - S the probability that E is at 2. Now if E moves, a signal is given. The figures also give the set of all possible signals for each configuration, denoted by the 6's.

Configuration I 3 Cli - I. 23 FIGURE 1 Configuration II -3 -2 -1 0 P 1 2 3 4 5 1- T O,-.... FIGURE 2 CFO ~ CnigrtiMI -3 -~~~~~~~~~~~~~~~~~~~~~3 -P ~ O q 2 a d~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ %~~~~~~~l

4 These two configurations have the property that starting from either, P can move in such a way as to establish one of them, or capture, regardless of what E does. That is, for the rest of the game one of these two configurations will prevail at any time if P so chooses, regardless of E's strategies. Suppose the game has been played up to the time when one of the configurations has been established, and that E is to move next. Consider the following new game. It consists of 3 moves as follows: (1) E moves, (2) A chance move consisting of a signal, (3) P moves, The payoff is the expected number of cycles before capture counting the cycle of the new game, assuming P and E behave optimally for the rest of the game. So for each configuration and each value of S and T correspondingly, we have one of these games. Solving the larger game is equivalent to solving these games for each value of S and T. Isaac's paper presents such a solution of the game. The value for configuration I with probability S is denoted by (S), that for configuration II with probability T is denoted by r(T). The notation used here is that of the above-mentioned paper whenever possible. For values of 6(S) and f (T), and for method of solution refer to RM-791. A Generalization As described above, each one of the signals,, 6 I 2 3 has probability 1/3. It may be desirable to consider the problem in which the relative probability of each signal may vary. For instance, a detecting instrument (like radar), may point to a region around a point of probability higher than the neighboring points. Or vice versa, to a circle of points of high probability around a center of relatively low probability. Therefore consider a case in which a probability a, 0' a * 1 is assigned to' 2 (E in the middle point), and equal probabilities

-2- to 0- and 2'. Then C (S) and (T) can be evaluated in terms of the parameter a. It is sometimes desirable although not done here, to compare pure strategies with the optimal mixed strategy obtainedohere. For that purpose it is convenient to allow P to remain stationary if he so chooses, contrary to the rules of the game in RM-791. It turns out that this does not alter the optimal strategies since one is found in which this choice of P is precluded. Whenever a method of reasoning (or a proof) is a mere repetition of a method (or proof) in RM-791, it will be omitted, or simply sketched. Only when a modification is required or a simplification possible, will details be given. Expressions for the Payoff Functions. Configuration I. The mixed strategies for P are given by the following table: 1 2 1. O 6 2(S)1 - p2(S) p3(s) 1 p(S) 0 1 0T A I TABLE I

6 The subscripts on the left hand side from 1 through 5 indicate each of the signals shown in Figure 1. The numbers 1, 2 on the top indicate P's moving 1 or 2 to the right. Here P has nothing to gain by standing still, so this alternative is precluded. The entries in the boxes indicate the probability of P's moving 1 or 2 points given each signal. P determines these probabilities. It is shown in RM-791 that the mixed strategies for E can be given in terms of the numbers A, B, C; the probabilities of Ets finishing at the end of the game (the little game) at points 2, 3, 4 correspondingly. Then in the same way as is done in RM-791, the payoff function is computed to be: (1) $ = 1 a (A + C)& + (A + ()) 2;~' IA +C /.2 / + P2 (1 a B- aA) (0) + p3 1 a (A+ C)(rC) +(aB+ EC) &(Aa Configuration II The strategies for E are given by the following table: -1 0 1 2 0 - q1 0 1 1 q 0 O I q-L I l-q-l I ~ _ TABLE II The numbers 2, 0 on the left indicate the position of E at the beginning of the game (Figure 2). The numbers -1, 0, 1 indicate one move to the left,

7 standing still, one move to the right respectively. The numbers in the boxes indicate the probabilities assigned to each combination (mixed strategy). The strategies for P are given in the table below: -2 -1 0 1 2 1 ~ X I 1 O I O _O 62 0 0 0 0 0 (r 1 _P 4 P 0 0 0 TABLE III The entries on the left hand indicate the signals in Figure 2. The numbers across the top have an explanation similar to those on Table II. The entries in the boxes have a similar explanation. Notice first of all that r 2 and q are not equivalent any longer since they occur with different probabilities. The same can be said of and Also notice that on top indicates that P is allowed to 5 6 stand still, but only under 4 does it seem advisable to do so. His probability of standing still under a given mixed strategy is denoted by 4. In a manner similar to that employed for $, the payoff function for configuration II is found to be: * As in RM-791.

(2) V = 1 + 6 (0) /(1 - T) f q-lp2 + 12a (1 - P2 - q1) + lq lq3+ a(l P3 _qJ)3 + Tf 2 qlP5 1 5 2 2 + a(lq _p ) +la qP6 +2a (19qlP6)]j( + -a p' f (T) 1 - T) (1 - q_l) + T(1 ql) + 1a ( 1) - T) p4(1 - q) + T(1 p4 - p)(l- qlj Optimal strategies and values of & (S) and fC(T) are obtained by solving the functional equations: (3) &(S) = max min 0 = min max 0 A,B,C P2P3 P2, p3 A,B,C A+B+C=l A+B+C=l C_*S C S (4) J (T) = max min q-l,'q P2'P3,'P4'P P5, P6 min max P2P3' P4' P'4'P5'P6 -' The last part of each equation (max min = min max) represents an assumptiono Solutions of equations (3) and (4), together with strategies which give rise to those solutions represent a solution to the game. The Value of ~ (O) Theorem 1. The value of ~ (o) and the corresponding strategies are given as follows: a > 1/3 9(o) 2 1+ a with strategies;A and B arbitrary in the set of values defined by A + B = 1, 1 - a 2 1 + a, = O, p - 1, p = O, 1+a l+a 23

9 a = 1/3 (ef. RM-791, p. 8) 6(0) = 3/2, with strategies A = 1/2, B = 1/2, C = O, P2 and p3 arbitrary among the values P2 + P3 =1. a < 1/3 & (0) 1, with strategiesA and B arbitrary among the values A + B = 1, l-a 2a 4A v 1 - a P O, P =1. l+a 1+a Remark: The method of proof for the three cases mentioned is essentially the same trial and error procedure. Therefore the proof will only be given for a)>1/3. Furthermore a complete proof is quite lengthy, so it will only be shown that for a> 1/3,,(0) 2 + a Proof: The problem is to evaluate E(S) for S = O. In this case C = 0 and B = 1 - A. Also9(A A) =(0) =&)(B )=(o). Substituting these values in (1) and simplifying we obtain (8) 0 = 1+: (0)oC, where (9) J = 1 + a a + P( 1 ) p P a A and from (3) we have (10) = t() = 1 + (0) max min o0. A P2,p3 We show that max min = 1. This establishes the value of E(O), A p,p3 2 since & (O) = 1 + () 1 -, and then solving for 6(0) we obtain (11) (o) 2 +a Now let a >1/3. This is equivalent to 1 -.a, a and -2a. 1- a, 2 l +a l+a (12) max minm min Pl+aA+p22l++ P/a la Al A p,3 p2,p 2,22/- 22

10 where on the right hand side, A is chose to lie in the interval!,- a A ~ 12a But in this interval the coefficient of P2 is c 0 and l+a l+a that of p3 is 2 0. So the values P2 = 1, p3 = 0 are minimizing values and the expression on the right of (12) becomes equal to -1 a. 2 On the other hand: (13) maQx min9 maxL aLaA+ l__A- 1 aAj A P2,P3 A 2 2 + (setting P2 1= p3 = 0) or max min O C i-a A 0C, a 2 A P2,p3 This completes the proof. The Value of (T) In the proof of the following theorem it will be assumed that 1) 4 (T) - T C (1) 2 0. The negation of this assumption leads to a contradiction. For a proof of this see the appendix. 2) f (T) ='(1l - T) = (min (T, 1 - T)). Since min(T, 1 - T) ~,i the value of the function need only to be given for T, j. This assumption is evident from its interpretation in terms of configuration. Theorem 2. The value of M (T) for T t i, and a set of optimal strategies are given as follows. For a 2. 1/3: (14) (T) 2 + T L (1) (1- a)2 and optimal strategies are 1+ - a 2(1 + a) p2 =O, p P6= O, p5= 1 2+ -. (1),p4 P'4 =q0,q1 1= ~ a 2 1 l+a

For a c 1/3: (15) v (T) = + T ~(1) ( 1- a). and optimal strategies are 1- a 2(1 + a) P2 = 1 P3, P p' POI P 5 + a l 1 P6 q -1 q 1 4 3 l+a 2a 1+ a Only part of the proof of this theorem will be given here. We will only refer to the case a! 1/3, since the other case follows exactly the same method. The proof again consists in showing the two inequalities (16) + T) T 1 +T (1) aL 1- a 2(1 + a) (17) la(T)2 1 +T (1) la) 1- a 2(1 + a) The proof of (16) is almost a step by step repetition of the proof of the corresponding inequality for a = 1/3 given in RS-791, Theorem 2, P. 12. Therefore it will not be given here. The proof of (17) goes as follows: Substituting the values q-1 = ql = 2a, we obtain: (18) (T) = max min q_1,ql P2,P3,P4P'4P5,P 6 2 () (a a9P6+ ( 2T) ~ (1) (1 a) (2- aa 4 + )( (T) -T E(1)) p' + 1 + a & (O) + T ~(1) a Now a -!2 1 0 for a 1/3 so that the coefficients of P2 and P6 are nonpositive, and therefore the minimizing values of p2 and p6 are p2 = 6 1.

12 Again, the coefficient of p4 is nonnegative since T' j. Also the coefficient of p'4 is nonnegative since f(T) _-T E (1) was assumed to be nonnegative. This fact will be shown in the details in the appendix. Therefore the minimizing values of p4 and p'4 are p4 = p'4 O. Thus we have: (19) (T) (1- T) E()(a L a) + T c (0) (a 2a) 2 2 + 1 +La (-T__2.a + 1 +- ~' (O) + T (1) (1- a) 2 2(l + a) (o)( 1 - la) + (o ) a + 1 + 2 a ) (l2a)2'T (:) + (1 =. 1 + a ~ (0) + T (1) -.a) 2(1+ a) 2(1 + a) + T (1) a) - - a 2( + a) which was to be shown. Here as in the previous proof the values pertaining to optimal strategies seem to come out of the air. Therefore for the sake of completeness, I would like at this moment to indicate a procedure for computing them.* This is merely an outline, and no proofs are given. The procedure is to assume that the optimal values of q-1 and ql are interior to the interval of definition of these variables. Therefore for these values we have d = d = - 0. This gives two relations binding 89ql q1 P2',P' P4' p' P2' P3, p 4, Pt4, P5 P6. Fromthese -elations we can find those variables among P2' P3, p4, P'4' P5, P6 achieving their optimal values at points interior to their intervals of definition. By setting the partial derivatives of O with respect to these variables equal to zero, we compute ql and q-1 From all relations involved, the values of P2, p3, P4 P'4' P5, P6 can be obtained. * Suggested by R.a M. Thrall.

13 Lemma 1. (1) _ 4 +a- - +.a Proof. Setting P2 = P3 = 0 in (1) and noting that for S = 1, C can range over the whole interval 0 c C _ 1 we have (20) ~(1) _ max 1 + L (A + C) A,B,C.A+0 A+B+rC= C 1 + (aA + 1+ a C) (0) 2 Now it can be verified from Theorem 1 that & (0) _ 2 for all a, and 1+ a from Theorem 2 that A (T)' 2 + L2 a (1) for all a and T. Substituting these estimates in (20): (21) & (1)' max 1 +ia (A + C) L2+ 6(1 (j1 C 1 A+C=l + (aA + + C) 2 l 2 1+a. The maximum occurs at A = O, C = 1. So: 2 2 (22) c(l) 1+ (1 - a) + ( ) (1) +1 a2 (23) (1. a.)(3.- a) E (1) g 3- a, (24) Q. E. D. 1+a na 2. 2 + a) 4f - a) 2(1 - a)J ( a) 1 8(1- y

14 2 Proof: Combining the two inequalities: 2 - a * 1, (1 a)a 1i, the 2 l+a following relation is obtained: (1 - a)2 (2 a) 1. 2 From this 2(1 + a) 5(1 a)3 (3+ a) (1 a)2 (1 a)2 (2 -a) 8(1 + a) 8(1 + a) 2(1+ a ) 3 2 3 (1 - a) + a) ( - a) 1-.(., and finally: 2(1 + a) 8(1 + a) 8(1 + a) 1. + a 4(1 - a) 2(1 + a) 1 (1 - a)3 a(1 a) - 8(1 + a) Theorem 3. The value of ~ (1) and corresponding strategies are given as follows: A = B = 0, C -= 1, = p = O, (25) &(1) = 1 + E(o) Remark: The proof of this theorem for a 2 1/3 is a paraphrase of the corresponding proof in RM-791, with lemma 1 here used in place of lemma 4 there. However most of the proof for the case a - 1/3, although following a similar pattern, is essentially different. This proof will be given here. Proof: (for a 4 1/3) We set ~ (0) = 1 in 0. 1 -a i) ~ (l)2 1+ - =1+-(03 1-a Substitute the values A = B = 0, C = 1 in (1), and the following results: (26) _ (1) ~ min L1 + a 2a_(1) + l (~) + P3 (l a(1) 2 2[ )+r2a 2 2j A (1))3

15 min l+ aa1 -a + 1+a + 1 p3(. i + ~(1))] I- a 2 2 2 I 3 - a p2,p since (1) = ~ (0) = &(0) The minimizing value of p3 is either 0 or 1 according as the quantity -_ 1 + E(1) is positive or negative (p3 is 1 -a 3 arbitrary if the parenthesis is 0). If- 1 + &(1) 4 0 then &(1) 1 and the minimizing 1 -a value of p3 = 1. Then (27) E (1)2 1 + iL _ i + a. >(1) > 1 1 - a 2 2 1-a a contradiction. Therefore 6 (1) 2 1 or - 1 + C (1) > 0 and i. -a i-a p3 = 0 is always a minimizing value. Then.J 1 E (1) 2 1 + 1 = + (0) 1-a ii) (1) _ 1+ 1i. 1 -a Set p2 = P3 = O in (1), to obtain (28) ~ (1) max [l+-1 a(A + C) C +(aA + aC( + I J ALBC 2 A+ 0 2 1max ( 2 (A+ C+ 1 (A+ C) + C-J = max (C, A) A+C 1 We propose to evaluate maxp (C, A). The set A + C l 1 can be represented as in Figure 3, byr the area enclosed by the line A + C = 1 and the coordinate C-axis, and A-axis. Consider the following two subsets:

16 (1) Those points for which C < A, lying above the line A = C, indicated by the horizontal lines. (2) the complementary set for which A ~ C, below and including the line A = C, indicated by the verticals. / o, C et (C, A) lie on set (1). Then C 4 A. Using the value of Theorem 2 we have 2 a A + C 2(l + a) la a 2 o- ~r3 (29) + A + C) L 1+ -( + C + 2T(1) ) =1+ (A +C) ( 1+ 2 1 a)+ 2 4(+ e 3 ( C It is evident from (29) that the coefficient of C is greater than that of A. Therefore a maximum cannot occur on set (1), since for any pair (Co, Ao) such that CO + Ao' 1 and Co c Ao, we can (properly) increase the value of p (Co, Ao) by increasing slightly Co and decreasing Ao, without violating the above inequalities. We conclude then that any maximizing pair (C, A) of ~ must lie on set (2). In this set A i, C and s

17 (30) (C, A) = 1+ (A + C) ( a (1) a1A a) +2aai+A C 2(1 + a) =1+ 1 + (1 4(1+ ) + _ a) + + a + AC =1 + kA + k2C y Here again the argument must be divided into two parts according as a) kl > k2 or b) k k2 a) Assume kl k2. Then from this follows (31) >(1) () or 4(1 + a) 2 (32) 2 () > 2(1 + a) (1 -a)3 But then the maximizing pair of (C, A) is ( and then: (33)I <5(1) 5 _1 + ___ + a = 1+ _31 a +i (1) Ela3 4(1l-a)'S+a) from which finally results: 1+ 3+a 1. (1 - a), 1 8(1 + a) but this by lemma 2, contradicts (32). So we conclude kl! k2, from which it follows that the maximizing pair is (1, 0) and (35) maxA (C A) = 2+ 1 and (1) 1+ p( 1- a ) 1a 1 a a

18 With 7(O) and S (1) evaluated, all the unknown values in the expression for i(T) are obtained, and therefore the function a (T) is known. Furthermore, with this function known too, all the unknown symbols in the expression for $ in (1) may be replaced to obtain a function of A, B, C, P2, P3, linear in any of these variables. A summary of these values follows. Summary of Result Obtained and General Remarks. All values and strategies obtained to this point are collected in Table IV. For all functional values, the values of a are split into two overlapping sets a e 1/3, a ~ 1/3, and this is the way that the computations were performed except for the case of &(O), where the case a = 1/3 is treated separately. This is not shown in Table IV, but a glance at Theorem 1 will show that there is some arbitrariness in the choice of strategies, even though the value of E(O) = 3/2 conforms to the two general formulas given; 1 and 2 1-a +1 a It is also opportune to observe that the point of view of the proof of Theorem 1 is to start with the function 0 with. S = O and to set out to find in a direct way the optimal value of this function and all the sets of values of A, B, C, P2, p3 that provide this optimal value. In this sense theorem 1 completely solves the problem. This approach is in contrast with that of Theorems 2 and 3. There specific strategies are shown to yield the optimal value of the payoff function, without a claim that those are all the optimal strategies (they are probably not). Also in the last two theorems, no indication is given of how these strategies are obtained. As a matter of fact the strategies presented are generalizations (with the parameter a worked into them) of strategies given in corresponding theorems in RM-791.

TABLE IV Summary of Results Obtained Value and Strategies Symbol a 1/3 a 1/3 Value Strategies Value Strategies 1 I A + B=l 2 A+B= l 1-a 1 +a 2a 1-a 1 -a 2a l~t~a A~i1+a 1+ a SA 1+ 0 O P3-1 2 1, p3 0 A B=0 C0=1 A=B=O 0=1 2 -a 3+a (f -a p+ a p2 3 0 22 1-a 1+a pL=', P3= p3=p'4=0 ___ p2=O, p3=l,2p4 + 110P P4 4 + p 1+ a) ~ 1+a i-a 4~~I= -(2 - a -- a) 22(1+ p =1+P (-a)(3+a) ~ T)111- ~.il- e> g 12(1 +'~: -a)..5 1 a 66- 2 p min (T, l-T~~~~~~~~~ - ( + ) in (T 1-Tff q qmia rn (T, 1- 5 2(1+a) 2a ql= =1q + a

20 As already stated, &(1) = 1 + c(O), for all a. From this and from an inspection of Table IV or Theorem 2, for that matter, the following general expression for P (T) is obtained. (36) ((T) = &(0) + (1)l-a)2 min (T, 1 - T) 2(1 + a) = (0)o) + (1+ A (0)) 2(1-) min (T, 1 - T 2(1 + a) for all a. We can now give an expression for 0 in terms of all the known functional values. This we obtain by substituting the value of (T) given in (36), in (1). We obtain (37) $ = + 1 + a (0)(A + C) + (1) 1 a) min (A, C) 2 +(a. +a +)( + 2 - a (o) C + P2 1 - a B - aA (0) L- P a- B - a 1(o3 + p3 - a (0) (A + C) -. (6(1) min (A, C) 2' 4(l + a) + (aB+ 1-a C C6((C )] This expression can be condensed by using what will be referred to -in the rest-of the paper as the,/ -notation, as follows: (38) = 1 + 1(A + C) + 2 min(A, C) + 3C + p2( X B - XA) P 3 " 2 3 4 + p3 X(A + C) - \2min (A, C) + ( 5B+ X 6c) &( + C )J where the values of the's are given by Table V. The expressions of (37) and (38) are valid for all values of a. This makes them extremely useful in the treatment of & (S) below, since the necessary computations do not depend, as they have until now, on whether a is greater than or less than 1/3.

21 TABLE V Values of the ts' Value Symbol Formula a 1/3 a ~1>| 1 4E; (o 1a | 1/ a, -.-.,..._-2 ( 1 | a) 3(a) (2 a) a) )2 a)' -a) 4+a)2 1!-a (-a a2() aa 4 | a g(0, 1 + -a 2 22 a

22 The last few paragraphs represent an effort to remove the split that exists at a = 1/3 in the treatment of 9 (T), and associated values. Some general expressions were obtained, but still the proofs and computations had to be separated into two cases, However I cannot help feeling that it must be possible to bring forth some more general considerations which will bring the two cases together, but this is all I can say at the moment, Notice that the split beginswith the values and strategies of E(O), which exerts such an influence on the remaining computations, that the split in values of 6(T) and &E(l) are entirely accountable in terms of the difference in& (O) Not so regarding strategies. In the case of E(1) there is no split as can be seen from Table IV. The same table shows however that strategies vary from the case of a c 1/3 to a 21/3 for Configuration II in spite of the fact that the expression of o (T) in terms of C(O) is the same in both cases. One final remark before we plunge into the computation of 6 (S)o It was pointed out at the outset that P will be allowed to stand still, at variance with RM-791. This is represented by p' in Configuration II, From Theorem 3, it turns out that there is an optimal strategy for which p' = 0, which constitutes some evidence that Isaacs' prescription that P stand still constitutes no essential restriction. Notice, however, that Theorem 3 does not show that p' = 0 for all optimal strategies, Determination oP g(S). In this section I have extended (as far as has been possible) the computations appearing in RM-791 for (S) to the general case treated here. Very few things are proved, since proofs for them do not exdst to the best of my knowledge. It is merely shown that if the computations for a = 1/3 are

repeated for an arbitrary a the given results are obtained. Therefore, the formal approach of the previous sections will be abandoned. A few computations and several remarks will be given instead of lemmas and theorems. The fact that a = 1/3 is an exception will become still more evident since it turns out that & (S) is not composed of linear pieces for the general case as it is for a = 1/3. We first transform $ from\ (38) into a more suitable form for the purpose of computation. We first substitute the value of B as 1 - A - C and obtain: (39) = 1 + l(A + C)-+A min (A, C)+3C + P2 ( - C) -(3+ +2 P2 3 3 4 + P4 \3 (A + C) - 2 min (A, C), A 5(l- A) Then: (40) (S) = max (C) where (41),4 (C)= 1+( + X3)+ max 9 ( A, C) 0 A i 1-C and (42) (A, C) = A + 2 in (A, C) P+2 P P2 3 C[( - (X3 + X4)A + p3 X(AC] P2,p3 and finally (43) (A, C) = -3(A + C) - 2min(A, C) + L 5(1- A) 5 2 (B+C

24 The first step is computing/( (C). This is done following the same steps described in Isaacs' paper. Consider the number C1 = A2 + 3It can be shown >2 + 1 6 (1) that this number is Z i by substituting the values of the I's from the second column of Table V, and the formula E (1) = 1 + ~ (0), and noticing that. (o) 1 ik Then for C in the interval C1 C 1 the value of/( (C) is given by: (44) (C) = + 1 + 2 4 +3 + i4 2 and the strategies are: A= - C,P l~-CP3 = O, P2 = 1, The proof of this will only be sketched, since it again represents a repetition of the proof for a = 1/3, and since it rests on a principle which has been used over and over in this report. By setting P2 = 1, p3 = 0 in (42), we see that the maximum for this particular set of values of P2 and p3 occurs at A = 1 - C and the value obtained in (42) is (45) ( + - ) - C) This is obtained using the fact that C? i which is equivalent to 1 - C i C. So we see that max ('A, C)- Z this values On the other hand substituting A = 1 - C in (42) and (43), we see in (43) the eA) becomes &(l), Then for C in the above interval, (1- C1-0).) O, and the minimizing p3 in (42) is O. On the other hand, the coefficient of p < 0 and p2 = 1 is the minimizing value, and so the value

25 obtained is (45), which then must be equal to max 6(A,C). Substituting this value in (41) we obtain the value (44). To perform the evaluation of,9(C) in the next interval, applying the method described by Isaacs, it is necessary to make the following assumptions: 1) A (C) is increasing everywhere and therefore i(S) =As(S). 2) For every value F in the interval Cl_ F s 1, there is a pair of values A and C such that F =., A C, and i-A (C) _1+ ( ) C + 3(A C). It might be possible to prove the validity of these assumptions by a more detailed analysis of A4 (C), but I know of no way of doing it. They are not shown to my satisfaction in RM-791. However, by using them we can show that there is a 1-1 correspondence between the values of F and those of C defined in assumption 2) and that while F describes the interval C1S F ~ l, C describes an interval C2 - C ~ C1 and it is possible to compute C2. Also the A discussed in assumption 2) can be computed as a function of C. In what remains of this section, it will be assumed that a 2 1/3. The whole argument that follows is valid for an arbitrary a, except for the assumption that expression (51) e 0. This inequality is valid for atl/3, but not for an arbitrary a, and the main conclusion depends on this assumption. So the assumption that a > 1/3 may be replaces by the assumption that the expression (51) ~ 0. Consider a pair of values A, C for which Cl l1. Then by assumption 1), X (A, C) assumes the form:

26 (46) X(A, C) = - 3(+ C) -.2min (A, C) +'1 HA) + X6-f5) oi Consider a fixed value of C and an arbitrary value of A satisfying the inequality (47) C1 S1A _ l If for that value, A (A, C) > 0, then it is clear from (42) that the minimizing value of p3 is 0, and then 6 (A, C) is an increasing function of A. This is clear if P2 = 0 (minimizing value), since then (A, C) = I A + m 2 min (A, C) an increasing function of A. If the minimizing P2 is 1, then & (A, C)= (1 - 3- 4)A + min (A C) min (A, C), an increasing function of A. On the other hand, if X (A, C) L 0 for the prescribed values, then the minimizing p3 is 1 and the terms- involving A are: (48) (X1+ - 3- (1 + l+X2+ 24 ))A - P2 (X3 + 4) A +(X26 \5 (X3 + X 2 2 2 or (49) p2(X3 +- 4)A + 1 X3X(l.+\1+\2 \4) A irst term is a decreasing unction of A It is my Plainly the first term is a decreasing function of A. It is my purpose to shor that the last two terms form a decreasing function of A, and therefore a (A, C) is decreasing0

27 Taking the derivative with respect to A of these two terms we get... 02 (SO) 1 X - A5 (1 + 1 + 2 ( 6 - X5) ( > 3 \4 2 (1 _ A)2':( \1-3)-15 (1 + 1 + A 4 + ((1 A-)( >3 )~ This is so because C A 1 The right hand member becomes (51),+ +6 X 3X+ X) -4 \A3 \(+ ~+'3 It can be shown (See appendix) that (51) is,L 0. Then, this shows that (49) is a decreasing function of A, and so is ~ (A, C)o To summarize if ) (A, C) _, 0, (A, C) is increasing with A, and if X(A, C) c 0, 2 (A, C) is decreasing with A. It follows that if X(A, C) vanishes at ail for values of A, for which A A C, C -S5 C 1, (assuming C fixed), then any such value maximizes 9 (A, C) and ((C) = 1 + (X1 + )3)C + 4 (A, C), for that value of A. Our next task is determining for what values of C, the corresponding values of A exist, and to compute them. We start by setting (46) equal to zero. To simplify the computations let us introduce the following notations: (52) a) 1 = 1+ X 1+ X2- X ) qte2 \3 X4 b2 C) L( 6 - d) = Then wit this notation, (46) equated to zero becomes

28 (53) 3, (A + C) - 2A+ ( A)++ 2 5J - 2 2 Also the fact that A ~ C is used~ Multiplying and regrouping we get (54) - 4A+( A+). L A. )C+ A) ( (1-A) 4 1 3 + 5 2 3 5 1 - C2 0, +< 2'3 1 -A This is clearly a quadratic equation in both A and C. At this point a change of variables will simplify matters. We replace the variables A, C by - C C, So let (55) F = C 1 - A With this substitution (54) becomes (56) - L 4(F ) + ( 1 3 C 5 )2 A 3)F +,. 5 1 C + 2 ~ 3CF2 0o which is evidently linear in Co Accordingly, we can solve for C: (57) C = - F 42 <F 3 (( +'4 3 + 5 22 3)F 4 + 5 1 Finally we introduce a notation to replace the - notation and the < -notation. It will be referred to -notation~ (58) a) q1 = 4 ), 2+ 3 b) < 2 2 ( 3( X 6 X5) (A3 \4 A2)

29 c) 31 X+ 562-X3 A(A+ 6,Xi ) ( 1X+ > 2 5( 3 4 2 3 d) q + ='2 + X + X5(1+ + >2 A) 4 Then (57) becomes (59)..1 F C =. - 2F F + ), 3F+N4 This gives C as a function of F in the interval C1 > F' 1. From (55) we obtain A as a function of F, thus: (60) A - 1 t F + 3F + It would be desirable at this point to show that A' C. This is impossible, since it can be shown that there are values of a for which this is not so. To see thisnotice that the a's are algebraic expressions in a. So for a fixed F, A, C are continuous functions of a. Now for a = 1, by substituting from Table V and from (58) we get: (61) C = O, A = 1, A > Co And although we exclude a = 1, there must be values of a close enough to 1 for which A > C holds. So we only deal with those values of a for which A s C. What those values are however, I have not been able to determine.

30 The next task is to show that as F describes the interval C1 <6 F 5 lS C describes some interval, For this call. the function to the right of (59) L(F). We first show & > 0, and then evaluate L at the end points. We first dF consider the function 2F2 + 23F + 94 = F( 2F + 23) + IL 4' If 2F + 3 o, then the function 2 + X + + 5 + X 1 + 2) It is easy to see from Table V that this expression is positive for values of a lo Again if (2 + r 3 ( O then the function I r2F + (3 +?4o If 2 i 0 then this in turn is r y 3 + ~~. Again by substituting in the values of r3 and 4 we can see that F2+ + 4. Finally if (2 0, then 7?F2. Y 3t+ 42 Y 2 +;t3 + +4= 2 + X (I + 1+ +3) > 0 for a f 1. Summarizing then,? 2F2 + F + > 0 for all F and all a; 1. Therefore L(F) is well defined, and therefore the corresoonding values of C and A are also well defined. We now show > 0. (62) h - t dF? 2 + + 2 The denominator is positive as we have shown. If <( 2 O0 then the numerator is.>,, and we saw 4 to be positive. On the other hand if 2 0'.,.. numera, or 2' 4' 2~ o. (6 i t 4 2 X 2 + \3+ > 5(1+ 13 ) evident that to show that2 0,.it suffies to show that)+ 2 I-'.- evident that to show that \ 4 2 >i; it suffices to show that

31 (64) >3 6(3+ X 4)a L- a a&(0) 3 3 4 2 2>LIa 2 2] (o) =0 for a C 1. Therefore d L > 0. Let dF (65) C2 = L(C1) 2- 3 2C 1 + 3 Cl + 4 Let us examine L(1) more closely: (66) L(1) = 2(2+ n3+?4 We have already seen that the denominator of (66) equals X 2 + 6(1 + >1 + 2) From Table V we see that 1 + 1 + 3 = & (1)o So: (67) L(1) - 2 + 6 1 2 + X 6 E Thus we see that as F describes the interval C1_ F < 1, C describes the intervalC2 C C _. Cl, and the maximizing values of A are given by (60), It remains to compute-/t (C) and this will give us the value of &(S) in this interval, since we are assuming that C (S) =/t(S). We evaluate/( (C) by turning back to (41) and (42). There are two cases to distinguish: (a) A> (1 - C) and (b) A. 3 (1 - C) In the first 3+ X 4,+ case we see from (42) that the minimizing value of p2 = 1, and (68) (C) = (F) = 1+ 3 + 1C(F) + (a1 + (92 - 3 -c)A(F) where A(F) and CG(F) are given by (60) and (59) respectively.

In the second case,4(C) is given (69) (C) = _/L(F) = 1 +( 1 + 2)A(F) + ( 1+ 3)C(F) Both cases (a) and (b) occur for suitable values of a. A precise determination of these values has not been possible. It is even possible for the same value of a to have both cases)depending on the value of F.'thus (68) and (69) give the value of - (F) in the interval Cl F 1 or what is the same, < (C) in the interval C2 c C _ C1. We have thus succeeded in evaluating A( (C) and therefore 6(S) in the interval [C2, 1 To summarize, 4 (S) in the closed interval from C2 to 1 is obtained by setting ~ (S) =A (S) and is given in the interval CC2, C1 in case (a) by (68), and in case (b) by (69).

33 Supplement: Some Proposed 2-dimensional Extensions of Isaacs' Game. The following is a brief account of several extension to the plane of the pursuit game of PR-791, proposed in Project M720-1. It represents partly my own work, but mostly that of persons whose names are attached to the specific games. The brief attention given to these games was mostly of a descriptive non-quantitive nature. The first attempts, proposed by R. M. Thrall, consisted in subdividing the plane by a system of congruent regular polygons, and having E move from one polygon to an adjacent or remain stationary, and P move from one polygon to an adjacent polygon, to one adjacent to an adjacent polygon, or remain stationary. A signal would consist of a polygon and those adjacent to it, with a set of numbers indicating the conditional probability that E be at each one of them, given that E is at one of them. Of these the case of triangles, squares and hexagons were considered specifically. The square and hexagonal variations were abandoned almost immediately because they appeared to be hopelessly complicated. The game with triangles was considered in slightly more detail. It is to be played on an infinite arrangement, a portion of which appears in Figure 4. Here E and P are to move across the sides of the triangles, E across one side, P across two at most. This is somewhat unrealistic. For example, notice that triangle 38 in Figure 4 is "next" to 39. Yet, neither E nor P can get from 38 to 39. This perhaps could be remedied by prescribing that the players may also move through vertices as well as across sides. This however has not been considered. Again, from Figure 4, assuming E is at 38, the set of signals may be represented in Figure 5 below:

tp 69IA 16 1 6168 se ~8 Le 9 goli ~b~B 1 ~ 1 ~ 2 as Is 09 6 O L LL 9L 9 L t pL (i I alI IL OL 69 1 99 L9 9 99 9 9 fL9 3 9 19 09 69 I8G LQ 99 9 9 I 9 as 1 9 G O 610 GOf~ L*P tp tp tp, rl tp a to I tp otp 6 2 99. L2~ 99 go tp 9. IC 1 2 ale 1 63~ Oa1 la 93 1 z bpa 2 3 2 13 OZI 61 8 Li 91 1 21 C3~ ~21 11 01 6 8 L ~ ~ 919 9

35 7;, E * 32X Figure 6 If we are to search for a closed set of configurations, we find, contrary to the one-dimensional game, that there is no one such set which is evidently better than any other. In fact there are many closed sets of configurations, and no way of telling beforehand which one is beset, But the union of closed sets is closed, therefore there is a maximal closed set of configurations. It is with this set'that we must work. An example of a closed set of configurations ( which is not maximal) is given in Figure 6.

36 p Figure 6 has an explanation similar to that of Figures 1 and 2. The arrow indicates the position of P; S, 1 - S, T, T1, I T - T' indicate the probability of E being at the corresponding triangles. The following game was suggested by Wo Hoffman of Project M720-1, as perhaps a simpler generalization. It is actually a one-dimensional arrangement in two dimensionso The board consists of an infinite rectangular lattice, a portion of which is illustrated in Figure 7. f ~ o o o o o o 0 o o o o d 4 0o o o o o o o o o o o C o o o o0 0 0 0 o 0 0 0 b 0 0 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 0 0 0 0 I 2 3 4 5 6 7 8 9 0 II FIG. 7

37 Here two points can be defined to be adJacent if they belong to a square, with sides parallel to the edges of the figure, whose four sides contain (altogether) only four points. Then, with this definition of adjacent we can give the usual rules for the movement of P and E from point to point. The signal given for this game is such that it indicates both the position of E and the direction of movement. From Figure 7, it can 1be seen that E can get to any point from four different directions (along four lines). Each direction indicates a set of three signals. So there are twelve possible signals, although once the direction is determined, only three of them are possible. The signals may best be described as follows: Given E to be at some point, and the line along which it moves to it. The points on this line (one of which is the point at which E is) form a lineal set of the kind used in the main portion of this report and in RM-791. Then the choice of signals is that prescribed on that line by the one-dimensional gameo If E remains stationary, the direction is assumed to be that of the previous move. To make the game completely unambiguous, an initial direction may be determined by a chance device. An example,will serve to illustrate and clarify this. In Figure 7, suppose E has arrived at point (d, 6) from (c,5). Then the possible signals are: c1: b, 4), (co, 5), (d, 6)j: [(c, 5, (d, 6), (e, 7)] r.3 id, 6) ( ), (, 7), f). If on the other hand, E had arrived at (d, 6) from (e, 6), then the signals would have been

'1': L(b, 6), (c, 6), (d, 6)j 62' C( C 6) 2 (do 6), (e? 60 63: d3, 6), (e, 6), (f, 6, It would appear that this scheme allows E a great deal of mobility. It turns out that this mobility lasts only as long as P is not close enough for capture. As soon as E changes direction it reveals the position from which such a change occurred (the intersection of the line of the previous signal with that of the present one); and that two of the three choices for the present signal reveal his position unambiguously. This property will probably make a solution simpler. It may even be possible to give the solution in terms of solutions to one-dimensional games. This possibility has not been. investigated. Regarding closed sets of configurations, it turns out, as should be expected, that configurations I and II of the one-dimensional game, form a closed set here too. But there are others, and something like a maximal set may be necessary.

Appendix 39 Proof of the anequality I (T) - &(1) T; 0. This proof is done as a supplement to the proof of theorem 2. So it will only be done for a c 1/3. Also according to previous remarks. it can be assumed that T 4 Lx Suppose Z (T) - g (1) T 4 0. Then, going back to the proof of Theorem 2, and to (18) we see that in that case, the minimizing value of p4' is 1. Then we have: (70) % (T). l + - (o) + ( - L a) (T), (71) w > 1 2(1 + a) This gives a lower bound for' (T), and (16) obtained in the first part of the proof of Theorem 2 gives an upper bound, Turning now to (1) we find, using (16) that: (72) (1) 5 max fl+ 1- (A+ C)Li + (1 a) 1 min(AC) + (aA + 1+2 a C) l a). + a a)2 + g, (l) L ( (a) 2 + + 3a 2 + (1 + a) 2(1 - a) Finally: (73) 2

It is quite clear that (74) 1 1 - a 1 1 < 1 l ( 4(l+a) 1 (+ ) - 2( +' ) ~~2 = 1-a _ (1 + a) Therefore (75) T C~ (1)' 1of 1 er o a 3 1-~ a )/ (1 + a) a contradiction. This establishes (76) g(T) - T j (1) 0o. Q. e. d. A similar proof holds for a 1/3. Proof of the inequality 1+ 6( 3+ i - - - \(1+ x + 3) X o >~+ >~~6 X+ 4 2 3 5 1 ) This inequality which involves (51), arose in connection with the evaluation of ~ (S) in the interval C2 5 C: C1. The proof is valid only for a a 1/3. Values of a can be found close enough to O for which the inequality runs in the opposite direction. By substituting the values of the X's from Table V into (51) and simplifying, the inequality becomes L. (77) 2 (o) (1 - E)3 ().a - o. 2 2 4(1 — aa Now let a 2 1/3. The left hand side becomes ia- -(3 -IIa - a 1- ILam-a 0 wi2 p[rove(1 a)li2a which proves the inequality.