Optimal Decisions with Applications to Tactical Problems Citation Restrepo, Rodrigo Alvaro (1955) Optimal Decisions with Applications to Tactical Problems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/407X-C664. https://resolver.caltech.edu/CaltechETD:etd-12082003-110540 Abstract The minmax criterion for optimal decisions is applied to a special class of infinite games. The existence of a solution is established, and some optimal strategies are described completely. The games considered include the so-called "silent duels". Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics and Physics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Minor Option: Physics Thesis Availability: Public (worldwide access) Research Advisor(s): Karlin, Samuel Thesis Committee: Unknown, Unknown Defense Date: 1 January 1955 Record Number: CaltechETD:etd-12082003-110540 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-12082003-110540 DOI: 10.7907/407X-C664 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 4851 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 11 Dec 2003 Last Modified: 06 Jul 2023 20:15 Thesis Files Preview PDF (Restrepo_ra_1955.pdf) - Final Version See Usage Policy. 1MB Repository Staff Only: item control page

OPTIMAL DECISIONS WITH APPLICATIONS TO TACTICAL PROBLEMS Thesis by Rodrigo Alvaro Restrepo In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California | 1955 -~4ii- _ACKNOWLEDGEMENTS I wish to thank Professor S. Karlin of the California Institute of Technology for the valuable help that he has given me as my teacher and my advisor. I also wish to thank the California Institute of Technology for the financial assistance given to me during the past three years. Finally, I wish to express my gratitude to Miss Rosemarie Stampfel for the excellent typing of the manuscript. ABSTRACT The minmax criterion for optimal decisions is applied to a special class of infinite games. The existence of a solution is established, and some optimal strategies are described completely. The games considered include the so-called "silent duels", Section 1. 2e 36 he De 6. Te 8. TABLE OF CONTENTS Title ACKNOWLEDGEMENTS ABSTRACT Introduction Definitions of X, Y, ¥. Description of the Optimal Strategies. Some Properties of ¥(x,y). Strategies of the Class 0. Corresponding Strategies. Existence of a Solution. Example. References Page ii 13 31 A zero~gum, twomperson game can be defined formally by means of a triplet (X, Y; ¥) where X and Y are two closed convex sets and ¥ is a real-valued function whose domain is X x Y. The elements xeX (or yeY) are called pure strategies, and ¥ is called the pay-off or utility function. The game is said to have a solution if there exist two positive measures F(x) and a" (F) (defined on X and Y respectively and normalized so that each has total measure 1), such that \reznea) >Vs all yey, [repraceg <v; all xeX, for some number v,. The measures F- and G” are called optima] Strategies, and v is called the value of the game. Each of the games that we consider below can be described intuitively as a contest in which each player is trying to achieve a certain fixed objective, but is allowed to try it only a certain number of times. If at time +t contestant I attempts to achieve his goal, he may succeed, or he may fail. (The probability of success is given by a function P(t) and the probability of failure by 1 - P(t).) If he succeeds, he wins one unit from his oppenent, and the contest is over. If he fails, then the contest continues but the other player is not informed about the unsuccessful attempt. Any attempt made by the other contestant is handled in a similar way, but the probability of -2« success is given by a function Q(t) which need not be the same as P(t). In the problema that we consider the pay-off function corresponds | to the expected gain for the first contestant. He is allowed n attempts, and his opponent is allowed m attempts. A special example consists of a combat between two enemy airplanes. The number of attempts corresponds to the amount of ammunition that they carry, while the functions P and Q correspond to the accuracy of the firing machinery. In this example it is also assumed that a pilot is not aware of the number of times that his enemy has fired and missed, He knows » however, how much ammunition can be carried by each plane, and he also knows the form of the functions P and Q. Then the function ¥Y represents the probability of survivale The type of problem just described is often called a silent duel. A special example has been considered by L. Shapley [1], who took P(t) = Q(t) = +t and allowed one attempt for one player and two attempts for the other. The pay-off function is x + [1 =x] (+, + [i =¥,](-9,)} OSx<9, <9, 51 ¥(x,y) = “y,+ (1 -y,){ x+ [1 =x] (-¥,)} OS¥,<x<¥, 51 vytMax {a tlt-x)@) } osy,<y,<xst Here x represents the time of the attempt by contestant I, and ¥49 Yo represent the attempts by contestant II. A slightly different problem (called a noisy duel) has been considered by D. Blackwell and M.A. Girshick [2]. Despite the similarity of the problems, it appears that the recursive method that they used cannot be applied to the problems that we consider. Finally, it may be a3e pointed out that the games discussed below are related to a large class of action games that have been considered by M. Shiffman [3] and S. Karlin [4]. Their problems include a large class of utility functions but allow only one action by each player. 2. Definitions of X, Ys ¥. 1) Let P(t) and Q(t) be two real-valued functions defined on the interval O<t< 1. We assume that P and Q are continuously differentiable, and that they satisfy the following conditions: P(O) = Q(0) = 0 P(1) = Q(1) =1 Q't(t) > Oo, O<t<1. 2) Iet x= {Fenosx sxsetex st} ’ and r= {¥ePlosy, sy, se syst} : In these definitions, Ee and E* denote the n and m=-dimensional Euclidean spaces. 3) let x eX and ¥ €Y be two vectors such that each component of x ig different from each component of ye A new vector 2 & got is defined by rearranging the numbers X49 000 9 X90 Yy9 coe 9 Vy in -i- increasing ordere Then, for each component Zz. of Zs two functions | r(2,) and s(z, ) are defined as follows P(x, ) if 2 =x, r(2,) = “aly,;) if 2 = Y; and P(x, ) if 2, = x; s(z, ) = ay,) if 2 = Yy° We may point out that this definition can be applied to a single vector xX (or ¥), provided that we know that it is associated with the space X {or Y). In this case we shall say that the other vector has no components. 4) A function ¥(Z) is defined as follows: if % has only one component, then U(z) = r(z,) ° While if Z = (2, Bos woe 9 2)» then w(2) = r(z,) +{1- s(z,)] ¥(Z5s coe 9 z,) e 5) The pay-off function ¥(x,y) is defined as follows: if x and y satisfy the conditions of definition 3), then 2 and ¥(z) are constructed as indicated, and ¥(x,y) is defined by V(xey) ZU(Z) « 5 On the other hand, if some component of x equals some component of ¥» V(Xsy) is defined by ¥(x,y) = uim 4 { 6 Fe,y re) +¥(x-e, yt =)| . £70 , In this definition x +c is the vector whose gth component ia the th minimum of +e and 1; similarly, the i“ component of x, > é is Xs the maximm of x 47 © and O. 3- Description of the Optimal Stratecios. It will be shown below that it is always possible to find optimal strategies of the form % es Rx F (x) = TT Fy (x,) » ti. BR. x a) =TTa,G,). j=1 Furthermore, all these measures are continuous except at x, =1 or y,, = 1. The support of each measure F, (x,) is a non~degenerate interval [a,, 2,,,), and in the interior of this interval F, is made i up of a finite number of absolutely continuous measures with densities Q* (x, ) "sg > )°? Q (x, P(x, * Fy" (x,) = j = 1592, eee 9 rs ° A more detailed description of the optimal strategies will be given in Theorem 1 and in Theorem 44 The location of discontinuities in the densities is established, and some simple equationsbetween h. qj and hy iH are established. = 6 « 4. Some Properties of ¥(x.y)- The definition of ¥ shows that this function is continuous as leng as the relative order of the components of x and y is not changed. Furthermore, it is easy to verify that this function is also skew-symmetric in the two vector variables x and y if the roles of X» Y, X and Y are completely interchanged. Other simple properties of Y are given by the following lemmas. Lemma j: let P = (2,5 eco 9 2,9 34449 eee 9 2 Je Then - W(2z) = ¥(25 oor 9 z,) + mi {1 = s(z, )] ¥(z. 49 eee 9 z,) e Intuitively, the lemma asserts that the total probability of success equals the probability of success in the first + attempts, plus the probability that the contest has not yet ended, multiplied by the probability of success in the remaining k - t attempts. The formal proof, involving a simple induction, is omitted, Lemma 2: let z = (245 eee 9 oe 249 2444? ace 9 Ze Then W(z) = ¥(z,5 eos 9 a 2441? ooo 9 z,.) Proof: By Lemma 1, ¥(z) FU(Z19 ooo 5 244) Ft {1 = a(z, )) V(Zp9 see s BH) 5 and ¥(zs» B44? ooe 9 2, = r(z,) + {1 - a(z, )] Wz. eee 9 Z)e These two equations can be combined, collecting at the same time all the terms that involve Zs Then + tt [1 ~ s(z,)] { r(z,) - 8(2,) Ylzii49 eee » 2) | . The first two terms can be combined by Lemma 1 to give the desired result. Lemme 3: For any fixed y, ¥(x,y) is a monotone increasing function of each component Xy of X as long as this component ranges over an open interval bounded by two successive components of ye Similarly if x is fixed, ¥(x,y) is a monotone decreasing function of each component v5 of y as long as v5 varies between two Xe consecutive components of Proof: If x has one component and y has none, then U(x,y) = P(x). This function ig monotone imreasing because P' > 0, Similarly, if y has one component and x has none, then This function is monotone decreasing because Q' > 0. We can proceed by induction and assume that the lemma is valid when the total number ~ Sa of components in x and y is k= 1. Finally, ¥(zys eee » 2) = r(z,) + [1 - s(z,)] U(Zo9 ove » Bde In this equation the factor 1 =~ s(z,) is non-negative and vanishes only when 2, = 1; furthermore, ¥(z55 cos 2.) depends only on ‘k = 1 components so that the lemma is valid when applied to the last k=-1 components. Thus we only have to show that the result is valid when it is applied to the component 34° If 24 is a component of x the last equation can be written in the form = P(x, ) {1 ~ ¥(2,5 ooo 9 z)] + (25s een 9 2, )e But if 24 1s a component of jy, then =s-~ Qly,) {1 + U(zo5 eee 9 2, J+ F(z, eee 9 z, Je _In the first case we have a monotone increasing function of. 4» and in the second case a monotone decreasing function of ¥y4° (It is easy to verify that |[¥(xsy)| <1 always.) Finally, we may point out that the first function is strictly increasing unless ¥(zos ooo s z,) =1. This requires that y be missing and that XS X32 °° $x = 1. 5 Strategies of the Class 0. The expected value of ¥(x,y) with respect to a measure F(x) is a function R(¥) defined by R(y) = fees aF(x) . -9- The function R(7) depends on F(x), and its explicit form may be difficult to find. However, it can be computed explicitly for a special class of measures which includes a particular pair of optimal strategies, These optimal strategies will be exhibited explicitly later. Any positive measure, with total measure 1, is called a strategy. A strategy F(x) is said to belong to the class 0 if it satisfies the following conditions: 1) F 4s separable, i.e., n i=i where each Ry is a positive measure with total measure 1. 2) The support of the measure F, is a non~degenerate interval la,» 8444]3 also a, >0O and a, = 1. 3) Each measure F (x, ) is continuous, except for F (x,)3 this may be discontinuous only at x, = 1. Notation: The expected value of P(t), taken with respect to F(t), is denoted by Ds Thus os ay A vector D (analogous to x) and a function @ (analogous to ¥) are defined as follows: D = (Dy» ene 9 D) gD.) =D, ~10- Lemma 4: If F(x) belongs to the class 0, then fre aF(x) = f(D) . In this lemma it is assumed that y has no components. Proof: If n= 1, the lemma reduces to the definition of Dy. The rest of the proof is by induction, assuming that the result is valid for all vectors x and strategies F(x) of dimension n - 1. Then, if x= (x, » eee 9 x)» \ ow d¥F(x) = fem + [1 = P(x,)] ¥lxys oo x,)} aF(x) Jemma 53 Let F(x) be a strategy in the class 0, and let y= (y,» «e+ » ¥,,) be any vector in Y, with the restriction that y, lies in the open interval (a,, de Then Bee Fay R(yy» ooo 9 n-1? y,,) ” RY,» oor 9 Yn) Ico = im (1 = D,] im} [1 = Q(y,)] [-aG,,)] ° at . af P(x,) aF (x) + [1 - DI[1 + a(*)] ° Yn In this equation i denotes the vector whose components are the last n - k components of D; the function f(D“) is defined like 6(D). -1li- Proof: Let y be the given vector, and let x be any vector in the support of the measure F(x). Let 2 be defined in the usual | way so that Lemma 2 can be applied, selecting for Zi the component ¥((x,> eee 9 x) 90949 ose 9 y,,)) ~ ¥((x,s oe 9 x) 9(¥4» ooo 9 no)? k + (1 - P(x,)] af [1 = Q(y5)} [-aG,,)]° i=] ° [1 ~ P(x,)] fy + ¥(x ys eee 9 x,)} r But if y, <x, S ayy) ¥( (x, s eoe 9 x) 9(¥4s ooo 9 y,,)) ~ ¥((x)5 ooo 9 x) 9(¥;9 ooo 9 vn 1)? k~ k= on = st [t ~ P(x] af [1 - a7,)] [-a,)] ° i=1 “f 1 + P(x) + [1 = Pla)) Vays ooo» x,)} Her )] Ft [1 = Q(y,)] [-Q(y,)] i=i j=l J m : { 2P¢,) + [t= Pad) [1 + WG ys wee x,)} : In either case, the right hand side is continuous and can be integrated with respect to F(x). Then, Ry,» eee 9 Yn) - RIV 4» eee 9 Ynnt) = Ft -5) Fh ar - )) (ag, - ist * ot In { \: [1 ~ P(x,)] ana} [1 + g(5*)) + A [1 =,} a [1 - a7,)} [2,91 B44 . { { { 2P (x, ) +[1- P(x, )1[1 + ai*)} } anny lew’ - = rt [1 - D,} tt (1 = AGG) ¢ i=] J=1 ett . | * 5 2 i P(x,,) dF (x) + [1 - Db J{1 + sorn| . vy. Lemma 6: let F(x) be in the class 0, Then hraw ar(x) is a continuous function of y, provided that Yin #1. Proof: The result follows from the fact that ¥ is a function with simple discontinuities while F is a continuous measure, except at 1. It is algo possible to verify the result by means of Lemma 5; indeed, a simple calculation shows that the right hand side of the last equation varies continuously as In increases from a ~& to a. + & 6. Corresponding Strategies. Let F(x) and G(y) be two strategies contained in the class O, with Rn F(x) = im F, (x,) ay) = 7 J G75). We shall say that F and G form a pair of corresponding strategies if both of the following conditions hold: 1) If ¥ 4s in the support of G(y) and y,, # 1, then Var) aF(x) = y (1) 2) If x is in the support of F(x) and x, #1, then \res) ac(y) =v (2) The numbers y and V are of course independentof jy and X, respectively. In the following sections we shall show that it is always possible to find two corresponding strategies which are also optimal for the game. In order to determine the conditions under which equation (1) will hold, we adopt the following standard notation: Notation: The support of F, (x, ) is denoted by [a,» 8544) and the support of G,(y,) is denoted by [bs Dials The numbers by» eee 9 be are rearranged into subsets, one subset for each of the intervals [a,, Aasisle The resulting array can be written in the form Soon <b <a a 5 byy <M Ir, <2 gq eee eh < . boo ar, ~ °3 25 a, < a3, “Pag < °°" < Pap S Ont = 1. When y rangea over the support of G(y), its last component y, m ranges over the interval [b, . » 1), and any other component ranges over an interval bounded by two adjacent b's; then it is possible to identify each component by means of the interval over which it ranges: with this notation Yn zy mr 7 and 4, denotes the component of y that rangea over the interval [b,.» bapa yle Whenever two adjacent b's are separated by one of the a's, we may write =b Sy io® In this case Vint and Vio denote the game component of ye ae In the following theorem, a denotes the discrete mass that FG) may have at x, = 1. The number D, is defined as on page 9. Theorem 1: Iet F and G be fixed, and let ¥ be my vector in the support of G(y) with Y, #1. Then jeez) aF(x) Fy if and only if all the following conditions are satisfied: 1) In the interval by; <x, < ere the measure F, (x,) is absolutely continuous, and , t Q (x, ) ; (x,) P(x,) FY (xy) = by, 2 - 15 2) 1+ 2a= D, * or, By yoy = (1 = Q(b, pia jy? dF Veeeoer ys 1 = Ipeeogn ar, =H =>) a, LE 1s oe sno de Proof: The proof is by induction. In the first step we determine necessary and sufficient conditions for R(y¥) to be independent of the last component of y when this component ranges over the interval (b_. » 1). In order to simplify the notation, a n function K 2 F4 eee Yar =1) is defined by _= K {1 =D 3 {1 = @ ], n , s=1 * ya Tor (Yor where the second product is to be taken over all components of y that precede Yor ° Then, by Lemma 5 n R(y) = RY, 4» eve 8 Tap -1) , : n 1 - ‘nar, 8,4 2 \, P(x.) dF (x,) +1e- DB, ° nr. It is clear that R(y) is independent of y ny «Af and only if the n coefficient of x nr is a constant; this constant is denoted by ba - Thus R(y) is independent of Yar if and only if saat Wa rele Hoy) a) 128, (3) n -16- Since ‘ F(x) belongs to the Class 0, F, is the sum of a discrete mass a at 1 and a continuous measure F . In terms of F this equation can be written in the form bar , . IG) = 2 P(x) aF (x) +20 P(1) +1-D , (3a) rn Jnr. and it is possible to integrate by parts since P' is continuous; then 2h nr Bey 2 PU F'(1) = PU y. ) Fan) #2a+1-D, n 1 * -2 F (x,) PY(x ) dx. Jnr n In this equation a and PO ny are bounded below by Pn) and P(b, ). Since all other terms are absolutely continuous, F- n must be absolutely continuous too. Then, in equation (3a) we can write *(x_) = FY(x_) aF nn =F (x, dx, ° A simple differentiation shows that -2P ) Ft ) = as was asserted in the theorem. Now that the form of F (x,) is known, equation (3) becomes 2h. n Qty... ) Gyn +2a+1-D = 2h . mr Var ba n wh -17< It is clear that this equation is satisfied if and only if abyp = 2a +1 -D, (4) as was asserted in Theorem 1. Finally, we notice that if we substitute the result of equation (3) into the expression for R(y) we obtain R(y) = R(y,,9 eco 9 Yor, =1) - Ear. Mae e For convenience, the previous results are summarized as follows: R(y) 4s independent of y _ if and only if the following conditions n are all satisfied: a+] (a) tim, { 2 § " P(x, ) aF (x) +1- 0, = 2h n Yor bn n (b) Ft(x ) =h aa ’ b <x <1, nn nr Q (x,) P(x, ) nr n (c) ah, = 2a+1 =D, wv, arn These conditions are not independent since (b) and (c) together determine (a) and (d). The proof of Theorem 1 continues by induction: a set of functions Ks 3% ooo 9 ¥43) and a set of constants ¥ 443 are defined as follows: a Yar, ~ Bar ° Yisj = My; + Yag4t ‘% j= Osecosry - 13 i = nyn~lyecey 1 Vier, =[1t- D,] Ya+t,1 + “Lr, 1 = lyecegnte In the definition of the second product is to be taken over all or components of y that precede v5 5° The definition of 4 igd is applied only when the corresponding h. has been defined. ij let us assume now that R(y} has been made independent of all components of y that lie beyond Vs ? and that the function so obtained is given by RY) = Ry ys eee 9 ¥yy) — Basar Vayger EU Ay ROY) = RO 44s wee Yar,) Ba Yau =, We shall show that we can continue one step further if and only if the analogues of conditions (a), (b), (c),(d) hold for the indices i and je Two cases are considered, depending on the value of j. Case 1: j # Ty- By assumption RY) = ROvyye eee » ¥43) ~ 2K jt Vaan ° Applying Lemma 5 to the first term on the right, RG) = Ry vee 9 Ky5g) > Basar Vay get it . +1 = Ky Uys) 2 \ P(x,) AF, (x,) + [1 - Dy] [1+ B(5")] ij Furthermore, by definition, Ky ja = [1 - 0G ,)) Ky The last two equations can be combined, collecting the terms that depend on ¥aj° Then, R(y) = RYY44s eos 9 Ys jt) - 2K, oj Yaga aa44 ~ Ky Q0,5) 2 \ P(x,) dF, (x,) + [1 - Df + p(*)) 2 Vag It is clear that R(y) is also independent of ¥,3 if and only if the coefficient of K, j in the last term is a constant; this constant > may be denoted by 2h, j so that att a4 (a) QGyy5)) 2 y P(x, ary (x,) + [1-p,][140(0 N25 a4 = 2h, ij | The argument that was given when we were dealing with the component Yor can be used to show that the last equation is satisfied only if n Q' (x, ) (x; 5 2 ? i a°(x,) PG, ) j (b) Fy (x, ) = by; x, < Ler ° -20- With this value of F,, the integral given in (a) can be evaluated explicitly over the interval (by 5s bay 3 | 2h “2h a+ hy, = OC,5) a} - Wry? +2 besa P(x, ) a8, (x, ) Ero) 601-2 Vy aa | Thus, equation (a) is satisfied if and only if (b) holds and also then 2h a (o) 3% =2 \ itt P(x,) aF, (x,) 15+ Ps 544 trad +e -2 Yay Finally, when equation (a) is combined with the equation that precedes it, we obtain or by definition or Y i,j° Tne induction process can then be continued. We point out that in this case conditions (a) and (d) againare implied by (b) and (c). Case 2. j= Ty and i<n. (We recall that in the present notation Ys ry and Ysit,0 denote the same component of y.) In this case the induction hypothesis is given by condition (d), with indices i +1, 13 explicitly, R(y) is independent of all the components of y that lie beyond Y,, only if | 4 R(y) = R449 eee ys Yar,) - 2s 44,1 Yon 1° By means of Lemma 5, this equation can be written in the form RG) = Rye oe + Yap ag) ~ Maaayy Vast st : | S444 “i 7K, Uy, 2 P(x,) dF, (x, +[1-D, [14000] ¢ i i Var ; 4° Farthernore » The last two equations can be combined, collecting the terms that depend on Vir? Then i Ry) = R44» ooo 9 Yar -t? - Kr, - D; J Y sats | 9441 | ~ Ki, a4, 2 ra. P(x,) AF, (x,) + [1-D,][1 * BOD ) i 2 Yan a It is clear that the last term is independent of Vir if and only if 4 the coefficient of Ky or is a constant; this constant is denoted by i 2h, + Once h is defined, the usual steps show that R(y) is ry ir, independent of Yar if and only if the following conditions are all i satisfied: a+ “i (a) 3,,) 2 y P(x,) dF, (x,) + [1-D,][1+9(D") dry - 2V su | = Mire = 22 = Q! (x, ) st Ts Q (x) P(x,) (b) FU(x,) = h, ar, < % < 9a44 r. (e) Qari, arnt y =(1-d,) [1 + 6) - 2 ¥ sat and or (4) RY) = R(yyy9 vee Yar,-1) - Rr Var, ’ by definition of Yaw, « These equations are not independent; indeed, (b) and (c) imply (a) and (a). The induction argument is now complete, In order to complete the proof of Theorem 1 it is sufficient to show that the second condition that is given in the theorem is equivalent to the set of conditions that have been denoted by (c) above. This equivalence is established as follows: 1) For the indices n, r,s condition (c) coincides with the equation b+ 2asd, + 2h 2) For the indices i, j (with j # r,) the equation yg = Tm Ql) Pasay can be obtained by subtracting the equation (c) (with indices i, j+1) from the corresponding equation with indices i, J. Indeed, (c) may be written in the form - 236 2h 8a44 sty =2 Q0b, 544 } or 2h 2h 2h, . jos +1 + sets za - as +2 P(x,) aF, (x, ) QDs 544 QWs 544? QWOs 5, Ps ja tooeaisa +t allt +s6)) -2 Y, 4, P(xy) aR, (xy) + (1-D,][1+ BAN = 2 YY yay Paget Also (for the indices i, j+ 1), (c) has the form Aya 444 “i O=- Teja +2 \ P(x,) dF, (x,) + (1-0, ](146(5*)]~2 Yaga 45+2 Subtracting, 2h 2h 7 Tis = sey +2 ¥, ..,-2 ¥, Abia)” Wy, 4442 4, jt 2h "ie - Bia ° ijt Simplifying, h ng = Em Oly ag )) By say 3) The equation Mr, = (1-d)a can be derived similarly. First, equation (c) (with indices i+1,0) is written in the form - a4 o- 8i42 2h 2h 2h =e wget hnd d+1,9 | ~Ati.o iF ittel + [1 dM + oO) 2 Va, 2h . j Lag mitt "9 Bet +204, += Dll +O) -2 Vy, 2h _ _it+i,0 == GS + 1 + oF) ~2 Seis ° Next, equation (c) (with indices i, r,) is written in the form 2h, . . Wage =[i-p) [1+ 05) -2 ¥y,, 4). Finally, the last two equations are combined, and the result follows, immediately. Conversely, it is clear that each of these steps can be reversed. Therefore, the two sets of conditions are completely | equivalent. | Some additional remarkg. It may happen that one of the b's coincides with one of the a's so that there is no need to introduce the constant Ray 40° In this case it is easy to show that h ar, 7 UH = DIET = Qa) By ys i = i whenever 8544 b, +151 his equation is derived like the equation bse, =[1- D,] but in the first step condition (c) is written for the indices i +1, 1 Bey 39 ’ instead of i + 1, 0. It is important to notice that hy r is a i = 25 « continuous function of the parameter b, 4151° Indeed, if by +151 > 94449 be, = fi- dD] by ef{t- DIL1 = Qld 4451] Besta ° As b, +151 * 4,449 this expression approaches the value h w Zoe D,} [1 - Q(a, 44] h, i that was derived independently when #1 aces Ps ie SS Theorem 2: let F(x) and G(y) be a pair of corresponding strategies. Then Swe) ar(Z) > x, all ex and Sea aG(y) < Vs all xeX. In this theorem n and m are fixed. Proof: It is sufficient to show that the first inequality holds. The validity of the second one will follow from the fact that ¥ is skew-symmetric if the roles of X» ¥» X and Y are interchanged. Furthermore, it is necessary to consider only those vectors y that have no components smaller than aj. (a, denotes as usual the first point in the support of F,(x,).) Indeed, it follows from Lemma 3 that for every x in the support of F(x), ¥(xsy) is a monotone decreasing function of any component of y that is contained in the interval [0, a]. Hence eas) dF (x) is also monotone decreasing in this interval. Finally, if F(x) has a discrete mass a at 1, all vectors y with Yn = 1 can be neglected; this follows from the fact that U(x,» eee 2 Xnaqrt)o(rqs eee 9 Fngng 0?) 2 2 B(x5» eee 9 Xn? ely; s eco 9 Finny?! ~ E)). Intuitively, the pay~off function WY favors the contestant who anticipates hia opponent. In order to prove the theorem, we shall consider each component of y separately, starting with Yn? We shall show that we cannot increase R(y) if we replace y,, by a component y* ¢ [b,. 91). The notation of Theorem 1 is also used below. . If y,, is already contained in the interval (ee we choose yx =y,,° But if ¥,, is contained in some other interval, say [by 59bs 544] we apply Lemma 5 to R(y). Then, Matt " ° QQ) 4 2 P(x,) AF, (x,) + (1 - DJ[1 + £0") 5 mn Furthermore; since F and G are a pair of corresponding strategies, F satisfies all the conditions derived in Theorem 1; in particular, if j <r,» condition (a) in Theorem 1 (with indices i, J) implies that “a+ Qty) 2 | P(x, ) aF, (x,) + [1 = D,J[1 + p(5*)} - 2V, st = 2h, , ¥ 9 - 27 « for all y € [by5s by5,4]+ Thus, by substitution, RG) = RY4» cee 9 Ynnq? - a [1 ~ DJ rt (1 - Qty] { 2h 5 +2 Vag ay) } . Similarly, if j= rs - ft (1 =D.) Ft [1 = ay) {%42, + 211-1 ¥444 04 0G wt. 9=7 In either case, R(y) is a monotone decreasing function of Yn? and it achieves its minimum value when Vn is at the right end point of the interval. But this end point is also in the next interval, and the argument can be repeated. In this manner we deduce that R(y) can only decrease if we replace Yin by Par 3 we write yx = "ne 3 the remaining components are kept fixed. Finally, we notice that condition (ad) in Theorem 1 is applicable to yx. Thus R(y) bad R(yy: oor 9 Vn=4? y*) = Ry,» cece Ym? - ar at a ° The proof continues by induction. We assume that there exists a vector (vy cee yg Bue ose ye) €Y with the following properties: 1) The first gq components of this vector coincide with the first q components of ye 2) The last m ~ q components coincide with the last m - q components of some vector in the support of G(y). 3) R(y) 2 RG, oaes %q s vot $9 ese 8 ye). - 28 = Then, in order to prove Theorem 2, it is sufficient to show that we cen continue at least one more step, since Ry}; ees 9 yx) equals y (by Theorem 1). For definiteness, let [b,,,,» b,145] denote the interval that contains vat Then, condition (d) in Theorem 1 can be applied to all the starred components, and R(yy> eee 9 ¥q yor? ooo » y*) At this point we mst consider three distinct cases: Case ji: Yq & [bo Deraqle In this case we take Me = Yq° Case 2: y q < Dae In this case we repeat the argument that was given for y,,! Leuma 5 is applied to equation (5), and the result is simplified by means of the appropriate condition (a) from Theorem 1; af y, © [b, ;° b,,,,) the term involving Yq will be of the form Lj+i - Fh tog FF trae {an gt AGN jar | - Fh iv, 21¥ 141) } The definition of the YX 's shows that this is a monotone decreasing function of Yq° Hence, we may t ake va = ba Case 3: Vg > be 44° In this case Yq must be contained in the interval Coys a4 sb, 445)» because Yq < v4. 442 and y* vou & Coa dy r40!6 Since the interval that contains Yq is known, lemma 5 can be applied to equation (5), and the result can be simplified by means of the -29- appropriate condition (a) from Theorem 1. Then R(y,s eon g ¥q? vor? eee 9 yx) k= —_ -2 rt [1-p,] A [i-a(y,)] { Sat + bersil-207,1 | It may happen that the component Ygni is also contained in the interval (b, 5 44? er: J]. Then, the previous steps may be repeated,and then R(yy» eee 9 Yq? ott? eee 9 yx) | $=] t=1 ° { Vague * aa lte 42] {11-091} } The process can be repeated for all the components of y that lie in the interval [by a? ig +2! - It is clear that the result is a monotone dnereasing function of these components, and the value of R(y) can only decrease if all of them are replaced by by +H° In particular we take va = bea which is contained in the interval [b,4» by. a and hence satisfies the induction hypothesis. However, the other components that were in the interval [d,5 44? yy 42! no longer agree with the components of y. But they are now contained in the interval [b> by Pie and by the previous argument, we only decrease R(y) if we replace all of them by b43 in particular we take ¥Q- = be the process can be continued until we obtain a vector of the form (y4s eee 9 Vp~1? yp? eee » vot? ya? eon 9 yx) that satisfies the induction hypothesis. The proof of the Theorem is now complete. Corollary. ‘The equation \wer) are) = x is valid only when y is in the support of G(y). This result follows from the strict monotonicity of the functions that appear in the proof of Theorem 2. Theorem 3: Suppose that F(x) and G(¥) are a pair of corresponding strategies, and that at least one of them is continuous at 1. Then y= v, and F(x) and G(y) are optimal for the game generated by ¥. Proofs For definiteness we assume that G(y) is continuous at 1. Then, by definition of vs \ sea aF(x) = zy for all ¥ in the support of G(y), provided that y_ # 1; furthermore, the vectors with in =1 have Gemeasure zero, and \ Wea aF(x) dG(y) = \ ydaG(y) =y. (6) Similarly, by definition of V, (ran ac(y) =¥ for all vectors x in the support of F(x); this result is valid even if x, = 1 because the left hand side is continuous. Then \ Vea aG(y) aF(x) = \ v aF(x) =v. (7) Equations (6) and (7) imply that y = V, and this number is denoted \ 9a) aF(x) > v, all yeyY and \reaw) aG(y) < vy all xe X. Hence, F(x) and G(y) are optimal. Remark: It is well knowm that if F and G are optimal for a game, then \ ¥(xsy) aF(x) =v for all points y in the support of G(y), provided that y is a point of continuity of the integral. Furthermore, a similar result is valid when F and G are interchanged. In particular, my pair of optimal strategies that belong to the class 0 must be a pair of corresponding strategies; and it is easy to show that at least one of them mst be continuous at 1. This remark may be taken as the converse of Theorem 3. Te Existence of a Solution. The problem of finding a solution for the given game has been reduced to the problem of finding two strategies F(x) and G(y) that satisfy the hypothesis of Theorem 3. The new problem can be simplified considerably if F(x) and G(y) are described by means of the equations derived in Theorem 1. We begin by reviewing the necessary notation, and at the same time we introduce the notation that is needed in order to apply Theorem 1 to G(y). The strategies F and G are of the form om n - #G) = TT F, (xy) G(y) = 1 G,(y,) The support of the measure F, is denoted by [a,,9,,,J, and the support of G, is denoted by [b,. Byay]s furthermore, a, = bi..= 1s and F (x 7 and Gy.) may have discrete masses a and 4 at x, =1 and y =1. Each measure is normalized so that 5 9444 \ Daa a, aF, (x,) = 15 b, ac, (y 5) = 1. (8) The constants D, and By are defined by the equations 9544 PH D, = a, P(x, ) aF, (x, )» E, > b Qy;) aa; (y,)- In order to apply Theorem 1 to Fy, the numbers by» eos y bi, are rearranged into subsets, one subset for each interval la,» a, a . Thus &, 3 by, <P sor’ “ir, <a, 92 5 Pay < Pag < *°° < Par, 3 ee 8# @ @ @ @ @ @¢@ e@hc8ehUhHe Fe F&F Fe & @ a, 5%, <> no ~ °°° Sb <a =1, + ry n+1 In order te apply Theorem 1 te G, the numbers Ayy coe 9 B, are rearranged into subsets, one subset for each interval [b 3? b j ale Thus by Say Saas < "1s, * by Pa S Aan < 829 < °°" < Mag, < Bs eoeee##efee8?e#8?e8e @#¢8¢ 8@ © © @ lh 8 Uf b <a €a € °° €a ms < <b =1. Th m1 m2 in m+1 - 33 = In terms of this notation, the previous resulta may be summarized as follows: the given strategies F(x) and G(y) are optimal if and only if they satisfy all the following conditions: 1) For each i and jy, - Tt OT Ns Bee) ee) Pag SS Paget * For each j and i, -_ P*(t as(t) = Kas Put) aa)” | O54 <t< B54 ° 2) V+2a=D, + 2h 1+ 2A E. + ng 3) by ={[1- Q(b, 54491 Bs a4? J = Oseoesrynts 1 = Vyeeesn 5) a, = b, and a@ = 0. Note: The equation a A= Q is equivalent to the continuity hypothesis of Theorem 3; the equation a, = b, is derived as follows: in order to apply Theorem 1 to F it is necessary that a, < bys in order to apply it to 4G, by < a,» hence a, = bye It should be pointed ont that -34- if a solution is constructed from this system of equations, it is necessary to have each measure normalized in the usual way. Thus, equation (8) should be added to the system. In order to show that the given system has a solution,it is convenient to transform it first into an equivalent system in which the number of unknowns and equations is smaller. The numbers bis ooo 9 bd, are regarded as a fixed set of parameters, and a dis- continuous function f*(x) is defined as follows: f*(x) = aL, b,<x<1 Q*(x) P(x) " f(x) = (1 = Q(o,)} ged, oo Q?(x) P(x) = " etc. In general, as x moves to the left of b 3? the factor [1 - Q(b,)] is excluded. Formally, m f£*(x) = 1- b, )] ia) 9 b . pap 1 = 0059) Be) PG) SP If the numbers Ayo eve 9 a, are also regarded ag parameters, then a discontinuous function g*(y) can be defined by eg) = TT [1 - Pla) Ee , a <x Say The factors that appear above are precisely those that relate two con= secutive h'a (or two consecutive k's) in condition (3). Thus a single hy (or k,) is sufficient to describe each F, (or G55 then the given condition can be elimimted completely if condition (1) is replaced by the simpler equations F(t) = h, f*(t), ay <t< A344 (9) ul = <t<b e Gy (t) Ky g*({t), b, 541 The coefficients h, and k ean be related to the 4 Ja new coefficients hy and k j by means of the following equations: h nr zh hn =k, ir, © Ans j= 4 x = 1-Pp Ka» = 1, cos 9 - 1. se, = Jb, ch Onn re . The equations that appear in condition (4) can be expressed now in terms of the new coefficients; the result can be simplified because the sane factors appear in both sides of the equation; then =[1-d,) by Finally, the normalizing equations and the definitions of Ds and £ j can be expressed in terms of f* and g*. The complete system of equations is as follows: = 36 Definitions of bam By 1 =h, P(t) £*(t) dt +a ay 1 k \. Q(t) g(t) db +4 mM = hy, caf P(t) £*(%) dt, bgi4 E, = i, \ Q(t) g*(t) dt, ° Normalizing Equations: 1 1= £*(t) dt + mf, mora 1 =k \ ge(t) at +8 bs] 9444 1=h, f*(t) dt, i Bait 1=k, \ g*(t) dt, 5 Equations from Theorem | and Theorem 3: 1 1 tern} \ P(t) f(t) ara} a, 1 1 +8 “1 \ Q(t) g(t) asa} mn i= Teeoegn=l j = Loeeo smi i= Tpeee nmi j = 1 eceymmt (10) (11) (12) (13) (14) (15) (16) (17) (18) (19) - 37 - a, =d, (22) a B =O. (23) Theorem 4: The given system of equations has a unique solution, and this solution determines two strategies F(x) and Gy) that are optimal for the game with pay-off (x,y). Furthermore, these are the only optimal strategies that belong to the class 0. In order to prove this theorem it is sufficient to show that there is a unique set of numbers ay 5 Bix coo 9 Ais Bis ooo y Hy bas eons bo kis oon 9 x that satisfy the given system of equations. The strategies F(x) and G(y) are determined by means of equation (9), and then the other assertions of this theorem follow directly from Theorem 1 and Theorem 3. In order to show that the given system of equations has a solution, it will be necessary to prove a series of lemmas. As a preliminary step, we develop a method for computing Ayr coo 9 a, as functions of bi» see 3 bo and ae Since the problem is symmetric, this method will also serve to compute bi» ese 3 bo in terms of ars soe 9 Oe The coefficient h, is eliminated from equations (14) and (18). Then; 1 2(1-a) = J {(1 + a) = (1 = a) P(t)] £¥(t) at (24) a n Algo, equation (20) can be written in the form D +.i-1., L = Tyson 7 1. i a Es ™ The left hand side of this equation can be simplified by means of | | , a, 4+1 Here h,,, is to be determined by equation (14), or (16). It is show below that these equations can be used to compute a Ase In the following lemmas it is assumed that the parameters bys eve sb, satisfy the following restriction: O<b <b, <°°* <b <1. 1 lemma 7: Let ys eee rb, be a fixed set of parameters, and let a be any number such that O<a<i1. Then lin jo - P(t)] r*(t) db = +m, x + 0° x | Proof: let M= 1] tt - ae, )] > 0. Then, for all t, Q Ze) P(t) Furthermore, since P is a continuous finction and P(0) = 0, there exists a number c> 0 such that - 39 « -P P(t 21 for all t $c. Then, if x < cs {8 e gt _ wd 1 \ [1 = P(t)] £*(t) at > \ uw Se at = Mates ~ Tey! . The last expression clearly tends to +o as x 0. Since the integral is finite over the interval [a,c], the lemma is valid for all a. Jemma §: let bys eso 9 b be a fixed set of parameters, and let a be any number such that 0<a< 1. Then, equation (24) has a unique solution a, which is contained in the interval (0,1). Furthermore, this solution a, is a monotone increasing function of a, and it approaches 1 as a approaches 1. Proofs If O<a <1, then [(1 +a) = (1 = a) P(t)) f(x) > [1 - P(t)] £*(t) > 0 for all +t. The right hand side of the equation 1 244-4) = ) [(1 + a) = (41 ~ a) P(t)) £e(t) at a n is then a continuous, strictly decreasing function of as and it achieves the value zero when a= 1. Furthermore, as a, * 05 the right hand side approaches + o (by lemma 7). Thus, for each ay there exists & unique solution. Furthermore, the quantity {(1 +a) = (1 = a) P(t)) 2*(t) - is a monotone increasing function of a, while 2(1- a) isa monotone decreasing function. Hence, as a increases, the solution an must also increase in order to preserve the equality. Finally, when a= 1, the equation becomes The only solution is a Jemma 9: Under the assumption of the previous lemma, it is possible to find a unique set of numbers a, < a5 S coe < a, that satisfy equations (24) and (25). Proof: The number a, has already been determined in Lemma 8. Then h, can be computed directly from equation (14) since the parameters by» eee 9 bd, and q are given. Then, Lemna 7 implies that the equation a i " [1 = P(t)) £#(t) at = i nu ae | has a unique solution ann] computed from equation (16). The process can be continued until all <a,- When 1.1; 18 known, hi, can be the numbers &49 coo y @ are determined. Jemma 10: For each fixed ay, the solution a. of equation (24) is a monotone decreasing function of the parameters b, Q eve » bie (It is a strictly decreasing function of the parameters that lie to the right of a =?) Furthermore, a, approaches Oas b_ approaches 1, Proof: The definition of Q(t) implies that [1 - Q(b5)] is a decreasing function of by. Then, for each t < bys f*(t) is a monotone decreasing function of the parameter bss and for t > bss f*(t) 4s independent of b,. ‘Thus, in the equation 5° 1 241-4) = {(1 +a) = (1 =a) P(t)] f(t) at . a, : the integral decreases as the parameters by g ees 9 db, increase. Then a mist decrease in order to preserve the equality. Furthermore, for +t < bis f(t) < [1 = a(b,)) el, Q (t) P(t) Then, as b, > 1, f*(t) tends to zero uniformly over any interval of the form [c, b,] with c > 0. Therefore, 1 \ [(1 + a) = (1 = a) P(t)) r(t) at Cc also tends to zero. Hence, a, > 0. Proof of Theorem 4: let a and fp be two fixed numbers that satisfy the conditions O<a<is osa<i a A, = Then a set of numbers ats ooo ars » bis ooo 9 bs .4s computed as follows: first, a is computed from equation (24), without any parameters by» ooo 8 bis similarly, b in is computed from the equation 1 2(1 - 8 ) - J. [1 +B) = (1 =A) Q(t)] ex(t) at, (26) m and in this equation g* is defined without any parameters. Next, the numbers a. and b 7 are compared, and the larger one is kept as a parameter; the smaller one is completely neglected. For definite- ness we may assume that a. is the larger one, and define ar = a,¢ The corresponding h* can be computed from equation (14). In the next step a number a _, is computed from equation (25) (without parameters), and a new b, is computed from equation (26) (with the single parameter a*). The two numbers a, and b, are compared, and the larger one is kept as a parameter; the smaller one is completely neglected. For definiteness we may assume that aj is the larger number, and define any = The process continues in this manner ! n-1° at each step a new a, and a new b j are computed, using as parameters the previously starred a's and b's. The two numbers are compared, and the larger one is kept ag a parameter, denoted by at (or bt). “When a¥ (or by) is found, the corresponding h¥ (or kt) is computed by means of the appropriate normalizing equation. In this manner it is possible to construct the numbers OTs coo » Abs bis eos » bE and the corresponding hfs k*. Furthermore, the construction shows that j these numbers satisfy the system of equations (10) through (23) except for equation (22). In order to show that there exist values of a and i) for which equation (22) is also satisfied, one may begin by applying the previous construction with a= 8 = 0. -143- If it happens that ay = bys then all the equations are satisfied. Otherwise, either at < b* or by < at. For definiteness, it may be assumed that bf < at « In this case the same construction is applied with a=0, and §# =1--€, for small & By taking 3 sufficiently close to 1, b,, can be made to approach 1; then a n* bw and b* = b.° It follows from Lemma 10 that in the next step a,” 0. All the b*'s are computed without parameters, and they remain bounded away from zero; but at is computed with the parameter bes so that it mst epproach zero. Since at < ars it follows that in this case at < bt. Thus the inequel ity has been reversed. Finally, since all the af and by are computed as limits of integration for the densities f£* and g*, it is easy to see that af and by are continuous functions of a and £ « Since the direction of the inequalities is reversed when p increases from 0 to 1, there mst exist some positive B with the property that the previous construction gives at = bf. Thus, in this case, the game has a solution with «a = 0, RB > Os If it happens that the given construction (with a = pF 0) leads to the inequality ay < bf » then the system of equations has a solution with A = 0, a> 0. Uniqueness. It is easy to see that the solution of the given system of equations is unique. Indeed, suppose that there are two solutions Bye coos Bs bys eee 9 b, and at, eee 9 ars bt» eee 9 bys these solutions give rise to two pairs of optimal strategies F(x), G(y) and F*(x),G*(7). ‘Then, since F and G* are optimal, it follows that = 44 a \ sa0) aF(x) =v for all y in the support of G*(y) (with y, #1). Then the corollary to the Theorem 2 implies that the support of G*(7) mst be contained in the support of G(y). Since the argument is symmetric, the supports of G and G* must coincide; thus bf = by» for all j. A similar argument shows that af = ass for all i. 8. Example. It is very easy to compute the solution for the completely symmetric problem in which n=m and P(t) = Q(t). In this case, by symmetry » Then, by equation (24), P(a) = P(b,) =4 3 and by equation (25) P(ay) = P(b ak? = =t5 9 k= Toesegnmte The optimal strategies are of the form [1] [2] [3] [4} Le De Me S. = 45 -= REFERENCES Shapley, see Rand Corporation Publications. Blackwell and M.A. Girshick, "Theory of Games and Statistical Decisions", Wyley, 1954. Shiffman, "Games of Timing", Annals of Mathematics Studies, Karlin, “Reduction of Certain Classes of Games to Integral Gene Annals of Mathematics Studies, No. 28 pp. 125-158, 1953).