UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Attack and defence models Cooper, John Neil 1966

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1966_A8 C63.pdf [ 2.33MB ]
Metadata
JSON: 831-1.0080570.json
JSON-LD: 831-1.0080570-ld.json
RDF/XML (Pretty): 831-1.0080570-rdf.xml
RDF/JSON: 831-1.0080570-rdf.json
Turtle: 831-1.0080570-turtle.txt
N-Triples: 831-1.0080570-rdf-ntriples.txt
Original Record: 831-1.0080570-source.json
Full Text
831-1.0080570-fulltext.txt
Citation
831-1.0080570.ris

Full Text

ATTACK AND DEFENCE MODELS by John N e i l Cooper B.A., University of B r i t i s h Columbia, 1964 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF Masters of Arts in the Department of Mathematics We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1966 In presenting this . thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the Univers i ty of • B r i t i s h ' C o l u m b i a , I agree that the Library shal l make i t f r e e l y avai lable for reference and study* I further agree that per-mission for extensive copying o f - t h i s thesis for scholarly purposes may be granted by the Head of my Department or by his representat ives . I t i s understood that, copying or p u b l i -cat ion of th is thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission,, Department of The U n i v e r s i t y of B r i t i s h Columbia, Vancouver 8 5 Canada ^ t e W &/y  ABSTRACT This thesis deals with Attack and Defence Models involving four di f f e r e n t pay-off•functions In each model, by means of standard min-max and convexity arguments, the optimal attack strategy, optimal defence strategy, and value are calculate ACKNOWLEDGEMENT The author wishes to express his sincere appreciation to Dr. Rodrigo Restrepo f o r introducing t h i s topic to him, and f o r the a i d and guidance given during the preparation of th i s t h e s i s . i i i TABLE OF CONTENTS Page CHAPTER I INTRODUCTION; GAMES•AND OPTIMAL STRATEGIES 1 1.1 D e f i n i t i o n of a Game i n Normal Form 1 1.2 Pure S t r a t e g i e s and Pay-Off 1 1.3 M i x e d S t r a t e g y Spaces 2 1.4 C h o i c e of S t r a t e g i e s 3 CHAPTER I I AN ATTACK AND DEFENCE MODEL WITH A CONVEX 6 CONTINUOUS PAY-OFF FUNCTION 2.1 A Model o f n - C i t i e s w i t h D<A 6 2.2 A Model o f 2 - C i t i e s w i t h A<D 7 2.3 A Model o f n - C i t i e s w i t h A<D 10 CHAPTER I I I AN ATTACK AND DEFENCE MODEL WITH A CONTINUOUS, 15 NON-CONVEX PAY-OFF FUNCTION 3-1 I n t r o d u c t i o n 15 3-2 A Model of n - C i t i e s w i t h A<D 15 3-3 A Model o f n - C i t i e s w i t h D<A 18 CHAPTER IV AN ATTACK AND DEFENCE MODEL WITH A NON- 20 CONTINUOUS PAY-OFF FUNCTION 4.1 I n t r o d u c t i o n 20 4.2 A Model o f n - C i t i e s w i t h ( n - l ) AiEXnA 26 4.3 A Model of 3 - C i t i e s w i t h AsD<2A 28 CHAPTER I INTRODUCTION; GAMES AND OPTIMAL STRATEGIES 1.1 D e f i n i t i o n Of A Game In Normal Form: A game i s defined to be a t r i p l e t (X, Y,K) where X and Y are sets, c a l l e d sets of strategies, for player I and player II respectively, and K Is a re a l valued function on X x Y. The games considered i n t h i s paper are two-person zero-sum, that i s , one player gains only at the expense of the other. The two players may be considered to be diam e t r i c a l l y opposed armies,companies, p o l i t i c a l parties etc For uniformity of description i n the models, the antagonists w i l l be considered to be armies. The attacker gains by overcoming c i t i e s and the defender gains by successfully defending the c i t i e s . 1.2 Pure Strategies and Pay-Off: (a) The attacker. In the games considered here a pure strategy for the attacker i s determined by the manner i n which the t o t a l attack force i s dis t r i b u t e d among the c i t i e s . With a t o t a l attack force of A, di s t r i b u t e d over n - c i t i e s , a pure strategy w i l l be the vector !=(!,>• w i t h 0 a n d £ | ! i = A where each ^ r e p r e s e n t s the allotment from the t o t a l attack force to the i - t h c i t y . The set of pure strategies w i l l then be _ . ' x 0 = { ( 1 J | §i»o ;h%i =A] 1-9 I 2 (b) The defender. A pure strategy for the defender i s determined by the manner i n which the t o t a l defence force i s d i s t r i b u t e d among the c i t i e s . With a t o t a l defence force of d i s t r i b u t e d over n - c i t i e s , a pure strategy w i l l be the vector 7| , . . . ,HTJ with \ >,o a n d j ^ =D where each 7|j_represents the allotment from the t o t a l defence force to the i - t h c i t y . The set of pure defence strategies w i l l then be (c) The Pay-Off. The pay-off to the attacker w i l l be denoted by K(§,7|) and to the defender by -K(^,^), for the two pure strategies In 'the following chapters several choices of pay-off functions w i l l be considered. 1.3 Mixed Strategy Spaces: When K i s a measurable function the mixed strategy spaces X and Y are constructed by Identifying the pure strategies for each player with points i n the simplexes X q and Y Q j and by l e t t i n g the strategy spaces X'and Y consist of a l l p r o b a b i l i t y d i s t r i b u t i o n functions F and G (ca l l e d mixed strategies) over X Q and Y Q respectively. The pure strategies <^,j7|« would then correspond to degenerate d i s t r i b u t i o n functions F^ , G^o for which a l l the p r o b a b i l i t y i s concentrated at the points ^ , T ] e respectively. The pay-off corresponding to the choice of F by the attacker and G by the defender i s then defined to be the expected value K(F,G)=//K(f J)))dF(5)dG() l) For any d i s t r i b u t i o n F(or G ) of X(or Y) the support i s defined to be the complement of the largest open set i n which F(or G) vanishes. A p a r t i c u l a r mixed strategy important to t h i s paper i s one i n which the support consists of a f i n i t e number of pure strategies. If a mixed strategy F has such a support i t i s said to be of f i n i t e type and has the representation F(5)= A j F ^(J) where Ai >y o a n d j j ^ i = 1 For convenience, when there i s no danger of ambiguity, t h i s F w i l l be written i n the form F= &A^^i, and the pure strategies F^ and GTJo w i l l be denoted by t^0 and> 0^ respectively. 1.4 Choice of Strategies; If the attacker announced he was going to use the pure strategy F , the defender would c l e a r l y use the T/ 0 e. y such that K ( £ , * )= m i n K($.,Ti) Y o Under these circumstances the attacker would have been best advised to choose his ^ e such that K ( ^ ) j J = m a x m i n K ( ^ ) = v ^o Y 0 S i m i l a r l y i f the defender announced he was going to use the pure strategy J?0 , the attacker would choose <;„ s x o such that K($.,)f.)= max K ( ^ yj.) X o and the defender would have been best advised to choose J|« such that K ( 5 » , ^ ) = min max K ( ^ , J J)=V Yo X o Now i t i s well known [l] that v * v (l<) and t h i s r e l a t i o n leads to the following considerations: (a) With equality holding, ( l ) reduces to max min K(£,«)= min max K(?,») X^ Y_ Y X J K o o o o which implies that there exists a ij oe X Q and IJo € YQ such that min K ( $ 0 ^ ) = K ( £ , ) | J = i n a x K(§, yjo) Y o X o The value v=K( y 0^) i s c a l l e d the value of the game and the strategies tj. , >j0 are c a l l e d pure optimal strategies of the game. If such optimal strategies exist f or a game there i s no need for either player to keep his strategy a secret. (b) With inequality holding, ( 1 ) reduces to max min K(§,)i)<min max K(E,Ji) X Y n 1 Y X ' o o o o which implies that there are no pure optimal strategies. In t h i s case i t i s es s e n t i a l f o r the players to maintain the secret of t h e i r choice of strategy. I f one player knew his opponents choice he could obviously improve his p o s i t i o n . Both players would then be best advised to use mixed strategies, that i s to randomize over t h e i r pure strategies leaving the choice of a p a r t i c u l a r pure strategy to chance, and thus eliminating the p o s s i b i l i t y of spying. Solving a game consists then of f i n d i n g those strategie F*€ X, G % Y such that min max K(F,G)=K(F*,G*)=max min K(F,G) Y X X Y Such strategies are c a l l e d the optimal strategies of the game and K(F , G ) i s the value of the game. Not a l l games have optimal mixed strategies, but i t w i l l be shown that the games under consideration here do. The following theorems, stated and proved by K a r l i n [ l ] w i l l be used to find.these strategies. Theorem 1 . 4 . 1 Let F ,G be optimal. I f G has a f i n i t e support and^ 0is i n the support of G , then K(F ,^o)=v, * where v i s the value of the game. Likewise l f F has a f i n i t e support and |o Is i n the support of F. , then K(!-0,G )=v. Theorem 1.4.2 Letfc^} be a family of continuous convex functions defined over a compact convex n-dimensional set S. Then sup^cp^Tj ) attains i t s minimum value c at some point of S. Moreover given any &) 0 there exists indices et£ and r e a l numbers/\j such that E ^^.(Tj^c-o" f o r a l l T| i n S where \±>, 0 and^M/=l Thus l f the pay-off function K i s convex in?| f o r each % , and i s j o i n t l y continuous, the optimal strategy f o r the attacker (F ) w i l l be of f i n i t e type and have the form F (§) =,EA.a, where A\ > O iZM =1, and a. i s the pure strategy 1=1 1 1 i=./ 1 (.0, .. .,0,A,0, .. .,0) with A occurring i n the i - t h p o s i t i o n . 6 CHAPTER II AN ATTACK AND DEFENCE MODEL WITH A  CONVEX CONTINUOUS PAY-OFF FUNCTION 2.1 A Model of n-Cities with D*A The f i r s t model considered i s one described by K a r l i n [1] and o r i g i n a l l y resolved by Gross[2j . It i s t h i s model that s h a l l l a t e r be generalized. In t h i s model there are n - c i t i e s of values k, ,...,k where k.5...^k . The attacker I n 1 n has a force of A with which to destroy the c i t i e s and the defender has a force of D with which to defend them. It i s assumed that DsA and that the pay-off to the attacker i n any p a r t i c u l a r c i t y i s proportional to (1) the difference between the attack force and the defence i n that c i t y , provided that the attack force i s larger than the defence force i n that c i t y . (2) the value of that c i t y . Otherwise the pay-off. i s zero. The pay-off function K i s defined by K ( ^ ) = £ k j m a x C c ^ i - r j i ) ] and the solution i s as follows ([1] , chapter 4, page 95) ( l ) choose r such that rA-D Is maximized. This w i l l be the value of the game. 7 (2) The defender has a unique pure optimal s t r a t e g y described by This shows th a t he defends o n l y the r most v a l u a b l e c i t i e s . (3) the a t t a c k e r employs h i s e n t i r e f o r c e i n a s i n g l e city> which he chooses from the r most v a l u a b l e * The c i t y t o concentrate on i s determined by randomization, w i t h p r o b a b i l i t y Aj of a t t a c k i n g the l ^ t h c i t y (i=l>*..,r)> where A ; _ 1 and L= £(l/k,) 1 " k^TT ^ 1 2.2 A Model of 2 - C i t i e s w i t h A<D The model, o u t l i n e d i n s e c t i o n 2.1, w i l l now be extended to encompass the 2 - c i t y case i n which A<D. By studying the r e l a t i v e s i z e s of A and D an upper bound on D i s immediately obvious. I f 2A*D, the defender would d i v i d e D evenly among the 2 - c i t i e s and the net g a i n t o the a t t a c k e r would be zero. Thus i t i s o n l y necessary t o consider the model i n which A<D<2A. A s i m i l a r remark a p p l i e s when there are n - c l t i e s and nA*D* rA-D (j—!>•'«-• «,r ( j = r + l i . . , , n I n t h i s model (1) the pure a t t a c k s t r a t e g y i s to d i v i d e A i n t o 5 agains t the f i r s t c i t y and A-j- aga i n s t the second c i t y where 0*§*A 8 (2) the pure defence s t r a t e g y i s t o d i v i d e D Into )j f o r the f i r s t c i t y and D-7| f o r the second c i t y where 0*ipD (3) the pay-off f u n c t i o n K i s defined by K(f>)j)= maxfo,k1(f->f)J+ max[b,k2(A-D-R|-5)J In p a r t i c u l a r (1) f ^(5.-1') > 7[< $. K(5. ,7|)= 1 k 2(A-I>H|-f 0) , T J ^ D - A + J . \^  0 t otherwise (2) K ( a 1 ^ ) ^ ( A - f ) , ^ A 0 ; if>A K(a 2,7()=V ( I k 2(A - ^B+^) >>pD-A and p l o t t i n g these gives f i g u r e I* Since K I s convex the opt i m a l s t r a t e g i e s could be determined u s i n g Theorem 1.4.2 or d i r e c t l y from the graph as f o l l o w s . As seen from f i g u r e I , the a t t a c k e r w i l l achieve the gre a t e s t .possible g a i n f o r any p a r t i c u l a r i j by c o n c e n t r a t i n g h i s f o r c e on a s i n g l e c i t y * A l s o as seen from f i g u r e I I f the defender chooses the s t r a t e g y 7| , the p o i n t at which K(a1,")^) and K(a 2,?|) i n t e r s e c t * he w i l l be sure of f o r c i n g h i s l o s s below a c e r t a i n l e v e l , no matter what s t r a t e g y the a t t a c k e r uses. I t i s c l e a r t h a t 7| i s the s t r a t e g y t h a t minimizes the l o s s of the defender> assuming t h a t the a t t a c k e r chooses a s t r a t e g y t h a t w i l l maximize h i s g a i n s . Thus ^  I s the opt i m a l defence s t r a t e g y chosen according t o the min - max c r i t e r i o n o u t l i n e d i n s e c t i o n 1.4. Figure I a l s o i n d i c a t e s t h a t )| occurs between , LVA and A. Therefore >| i s the s o l u t i o n of Ki&^jf)^ K ( a 2 > f ) and thus 77 » k 1 + k 2 Using Theorem 1.4.1 the value of the game i s v ^ C A - f ) = i/k^+I/k 2 Having determined the optimal defence s t r a t e g y and the value of the game i t o n l y remains to determine the opt i m a l a t t a c k s t r a t e g y . From Theorem 1.4.2 t h i s s t r a t e g y w i l l be of the form F * (5)=^a 2+(l-/\)a 1 w i t h 0^1 By studying f i g u r e I , and i n p a r t i c u l a r the convex combination of K ( a ^ ) and K(a 2 > 7 f ) marked on i t , i t i s c l e a r t h a t K(F ,7|) must equal v f o r a l l values o f ^ c l o s e t o ^ . I f F gives a value greater than v t o one side of ^ *"then i t w i l l g ive a value l e s s than v t o the other side of T J * . I f t h i s were the case F would no longer be opt i m a l since i t would not assure a ga i n of v t o the a t t a c k e r . Therefore A K ( a 2 , 7 | )+(l«>A)K(a 1 >^ )=v f o r 7j c l o s e tof|* . This i m p l i e s t h a t A[k 2 (A-D+»j )]+(l - A )f k-^A -^J *v which, since v i s a constant, i m p l i e s t h a t A ko-k,+Ak.,r=0 10 and thus \_ k l • &nd - -v k 2 k l + k 2 k 1+k 2 Hence the optimal attack strategy i s F ( 5 ) = k T T k 7 a 2 + 2 a. l'"2 " k l + k 2 1 where (1) k^ i s the p r o b a b i l i t y of attacking c i t y II with f u l l force. (2) kg i s the p r o b a b i l i t y of attacking c i t y I with f u l l force. 2.3 A Model of n^Ci t i e s with A<D The 2-city model, considered i n section 2.2, w i l l now be generalized to the n - c i t y case. In t h i s model (l ) the pure attack strategies are of the form ( Si 5*) w i t n a n d i ? ( Si -A , (2) the pure defence strategies are of the form ( JJ, ,..., rj*) with T\& 0 and 5j Jji =D (3) the pay-off function K i s defined by n. K(I,Tj)=j: m a x f o k ^ i - T j i ) ] 11 Now ( l ) K(^,>|) i s convex i n 7| f o r each | s i n c e - | m a x ^ k ^ f c - ^ / ' ' - ( W ) ^ W ) J ^Jmax[0,k i(c<(^- ) + ( W ) ( | i - ^ ( a ) ) ) ] . (2) K(§,)f) I s j o i n t l y c o n t i n u o u s i n f and and by Theorem 1.4.2 t h e form o f t h e o p t i m a l a t t a c k s t r a t e g y F i s F (S) = 2 A i a . where ,2Ai=l andA^O Assume t h a t A^ ^...^A^ a r e t h e s t r i c t l y p o s i t i v e A^'s a s s o c i a t e d 1 . in w i t h F . The s o l u t i o n t h e n p r o c e e d s as f o l l o w s ( l ) The o p t i m a l defence s t r a t e g y SinceX , , . . . , A . aire assumed t o be t h e s t r i c t l y x i • hn p o s i t i v e A^'s a s s o c i a t e d w i t h F c o n s i d e r what would happen i f y\ . *>/ 0 w i t h k*m. I n t h i s i n s t a n c e t h e o p t i m a l defence s t r a t e g y k l k w ould be d e f e n d i n g a c i t y t h a t I s n o t a t t a c k e d . But t h i s means t h a t t h e d e f e n s i v e f o r c e i s s m a l l e r I n t h o s e c i t i e s t h a t a r e a t t a c k e d , and hence t h a t the a t t a c k e r a c h i e v e s more t h a n t h e de f e n d e r heed l e t him. C l e a r l y t h e n t h e o p t i m a l defence s t r a t e g y w i l l d e f e n d o n l y t h o s e c i t i e s t h a t a r e a t t a c k e d . C o n s e q u e n t l y Now u s i n g Theorem 1.4.1 E % •* v**^ (A- y\tj) ( j - l > ...,m) 12 where v i s independent of ly Therefore * « v and 7) J -A- ~ ~ ~ (j=l,,„. ,>m) i m p l y i n g t h a t >' ' J 0=1 Ik7 '2 l/k* 0=1 / 1 Since the a t t a c k e r wishes t o maximize v, the m t h a t occurs i n the o p t i m a l a t t a c k s t r a t e g y must he such t h a t mA-D xA-D v=» ' s= max A l s o s i n c e v i s maximized when the k. Js are as l a r g e as p o s s i b l e J the a t t a c k e r w i l l a t t a c k the f i r s t m - c i t i e s . Therefore (1) v= max rA-D «. mA-D l i r s n r m T. .2? 1/k i=/ i x=/ 1 ( I — 1 > m), (2) - A- niA-D k, § 1/k, 7|£= 0 (i«m+l, .. .,n) 13 I t remains to v e r i f y t h a t ^ * " i s a v a l i d defence str a t e g y * ( =D and ^ 0 , (i«=l..,ni)) This i s done as f o l l o w s : (1) S )(i =mA-(mA-D)§ (l.A^) =D TU. 5 l A i (2) Since ft =AT- 3 ( i = l , . . .,m) then yjj^^lf j$k and i t i s s u f f i c i e n t t o v e r i f y t h a t ^ O Now A J 1/kj, r- l/km(mA-D) 7/*<0 o : - <0 1 ML E 1/k. i»/ J -o A || l / k ± - l/km(mA-D) < 0 ^ D A ^ A d n / k ^ ^ l l / k ^ *>D/A<m - k m | 1 A ± But a l s o mA-D > y (m-l)(A~D) § 1/k, £ 1/k. which s i m p l i f i e s to D/A>.m-km I' 1 A ± i m p l y i n g t h a t 7 | V o Hence i f i s a v a l i d defence s t r a t e g y . 14 (2) The optimal a t t a c k s t r a t e g y F Determining the optimal a t t a c k s t r a t e g y , as i n the 2 - c i t y case^ c o n s i s t s of determining theA^'s a s s o c i a t e d w i t h F * For p r e c i s e l y the same reasons as used, i n the 2-c i t y case v=\k i(A- i/| I)+...+A J 1 1k m(A-D+7j 1+...+^-l) f o r a l l 7j-(7[,i...>.^) c l o s e to ?}*. Therefore Thus Ark, i s independent of i , and s i n c e S A\ =1, one must have J- l i=i A i „ 1  k i ( l Therefore the op t i m a l a t t a c k s t r a t e g y I s to a t t a c k a s i n g l e c i t y , which i s chosen from the f i r s t m - c i t i e s by a random device according t o the p r o b a b i l i t i e s Ai.'i An, determined above. 15 CHAPTER III AN.ATTACK-AND DEFENCE•MODEL-WITH A • • • CONTINUOUS, NON-CONVEX, PAY-OFF FUNCTION 3-1 Introduction: The following model i s similar to the one described in Chapter 2, but introduces a loss factor for the attacking force. In Chapter 2 the worth of.the attacking force was considered to be so ne g l i g i b l e in comparison to the value of the c i t y , that i f the attacker was overwhelmed i n a c i t y his net gain there was zero, that i s , what he l o s t of his attacking force was of no consequence. In t h i s Chapter a case i n which the attacker places a value on his force, and thereby stands to lose a s i g n i f i c a n t amount each time he attacks a c i t y , i s examined. It i s assumed that the loss that the attacker suffers in a p a r t i c u l a r c i t y i s proportional to (1) a loss constant h (2) the difference between the defence force and the attack force i n that c i t y (3) the attack force i n that c i t y The model also has the r e s t r i c t i o n that k^hA; that i s , the attacker's possible loss in any c i t y that he attacks must be less than or equal to the worth of the c i t y . 3.2 A Model of n-Cities with A<D In t h i s model the strategies are the same as before and a. denotes (0,...0,A,0...0) with A i n the i - t h position, but 16 the pay-off f u n c t i o n i s defined by K ( M ) ~ Jimak(6,k.(§ i-7 i))-max(0,h § i ( ^ §i))J Since' t h i s pay-off f u n c t i o n i s not convex the method of s o l u t i o n used i n Chapter 2 cannot be u t i l i z e d . Theorem 1A.2 does hot. apply and thus the general form of the optimal a t t a c k s t r a t e g y Is unknown. The f o l l o w i n g lemma obviates t h i s d i f f i c u l t y . Lemma ,3.2 .,1 Let A<D and K be the pay-off f u n c t i o n considered above. The a t t a c k s t r a t e g i e s a^,..*^a n are then such t h a t f o r any defence s t r a t e g y TJ max k(£,n)^max K(a, ,r> ) 1**6 1 Proof; Let §' -( f | * ; • • i jf*) D e a n Y a t t a c k s t r a t e g y and consider the form K(^>j|). I t must be k, (f| - )'+...+k. . ->?j. )-(some p o s i t i v e term) i i i i i j j j J since A<i) i m p l i e s that there cannot be n p o s i t i v e terms. I f only n o n - p o s i t i v e terms appear then since nA>D, there must e x i s t some A which i m p l i e s t h a t K ^ J S O ^ a ^ j f ) I f there are p o s i t i v e terms, without l o s s of g e n e r a l i t y assume the order k, < k i (g==L •••«]') and thus e 1 J 17 w h i c h i m p l i e s t h a t max K(j; ,>i )=max K ( a . ,>7) ?eX„ i 1 Q.E.D. T h e r e f o r e a l l h u t t h e s e n s t r a t e g i e s a ^ , . . . , a n can be r e j e c t e d . F o r t h e s e h s t r a t e g i e s t h e p a y - o f f f u n c t i o n i s K ( a 1 , ^ ) -^ ( A - f l . ) , m A -hA(ty "-A) ', } (>A -h'A(fyt -A) , i^?A Each o f t h e s e i s convex because o f t h e r e s t r i c t i o n t h a t . k ^ . . . f r k ^ h A j s i n c e t h e s l o p e o f k i ( A - ^ i ) i s / k ^ M and of -hA(J/i -A) i s hA(^A) ^ ^ h A -A Thus Theorem 1 .4 .2 a p p l i e s t o t h e s e h s t r a t e g i e s and t h e o p t i m a l a t t a c k s t r a t e g y i s of t h e form F*(£)=ib A 4 a , .where Z> Xj =1 ahdA;?0 Now t h a t t h e form o f t h e o p t i m a l a t t a c k s t r a t e g y i s d e t e r m i n e d , t h e method of s o l v i n g t h e game proceeds as i n s e c t i o n 2 . J . The s o l u t i o n t o t h e game i s i d e n t i c a l t o t h a t o f s e c t i o n 2.3 s i n c e D<hA i m p l i e s t h a t v= max rA-D ^  0 1< n h r 1 8 which further implies that 1 k. 1 and thus the loss f a c t o r doesn't enter into the problem. 3-3 A .Model of n-Cities,.with D^A The model considered here i s sim i l a r to that of section 3-2, hut with D£A. Since the solution i s sim i l a r much of the description i s omitted. As i n section 3.2 the main d i f f i c u l t y i s i n determining the form of the optimal attack strategy. An equivalent of Lemma 3.2.1 i s needed therefore, for the case with D^A. The desired lemma follows. Lemma 3.3.-1 Let D^A. The attack strategies a^, ...,a n are then such that for any defence strategy max K(£,w)=max K(a.,w) ?€X { i 1 1 q Proof: Let ^  =(|, ,..., § K) be any attack strategy and consider the form of K(i» ,/|) . It must be k i " I i i ) + - - - + k i (fij - f i j ) _ ( ° o r a p o s i t i v e term) 1 j Since DSA implies that there can be h pos i t i v e terms, and not n non-positive ones unless D=A If only non-positive terms appear there must exist some ^i o*A and then K(5,yl)^0<K(ai pf) 19 O t h e r w i s e , w i t h o u t l o s s o f g e n e r a l i t y assume t h e or d e r k, 45 k. ( g = l . . . j ) and th u s X g 1 1 whi c h i m p l i e s t h a t K ( $ , ? ) * k (J. -fa )+2 i-j k < k, f 2 ?i. - TU 7 max K(^,M)=max K(a.,T?) $eX_ ^ I i 1 I J o Q.E.D. Hence f o r the same re a s o n s as mentioned i n s e c t i o n 3.2 t h e o p t i m a l a t t a c k s t r a t e g y i s o f the form # >L n P (?) =2 A,-a. where 2 A j = l j Ai^O J 2=/ -1 1 i=/ and the s o l u t i o n i s t h e same as i n s e c t i o n 3'2. 20 CHAPTER IV  AN ATTACK AND DEFENCE MODEL WITH A  NON-CONTINUOUS PAY-OFF FUNCTION 4.1 I n t r o d u c t i o n : The f o l l o w i n g model d i f f e r s from p r e v i o u s ones i n t h a t i t has a no n - c o n t i n u o u s p a y - o f f f u n c t i o n . The p a y - o f f f u n c t i o n K i s d e f i n e d by K ( ^ ? ) = | M i ( f i , ) | i ) w i t h V ~ h f i » ? i i T k where once a g a i n i t i s assumed t h a t k,>...£k I n I n s o l v i n g t h i s game t h e f o l l o w i n g lemmas a r e use d ; and i n t h e s e lemmas t h e f o l l o w i n g n o t a t i o n i s u s e d . (1) cA*D<(c+l)A where c i n - 1 (2) b.=(b. ,...,b. ) where b. =< A n. such t h a t Sb. =D and o n l y one b. =D-cA (3) F i s a mixed a t t a c k s t r a t e g y o f f i n i t e t y p e t h a t uses t h e pure s t r a t e g i e s a. w i t h * n p r o b a b i l i t y A. and K(F ,G) = S A;K(a, ,G) i i*i -» l 21 (4) G i s a mixed defence s t r a t e g y of f i n i t e type t h a t uses pure s t r a t e g i e s b^ w i t h p r o b a b i l i t y f± and K(F,G ) = .Z ^K(P,b 1) Lemma .4.1.1 . max K(t, G )=ma: ? 6 X o 3 1 ' max K(a.,G ) Pr o o f : L e t ^ b e any pure a t t a c k s t r a t e g y and l e t T (5)=K(f ,G*) = § ^ i K(§,b ±) The f o l l o w i n g d e f i n i t i o n s are made f o r each 1=1... .m (a) R ={j | b =A} j S,= {o | b =D-cA} V f j l b =0} j Note t h a t i s a one element set f o r each i by the d e f i n i t i o n of b i (o) K*(5,b1)=max{L(5,b1);M(J,b1)] (d) rw-gfiK^) U s i n g these d e f i n i t i o n s i t f o l l o w s t h a t ^ ( e i t h e r 22 and thus s i n c e t h e f ± r s > 0(l=l...m) (2) K (^*D^) i s the maximum of two l i n e a r f u n c t i o n s and i s thus convex. * A * (3) <jp (5^ = jrj / ^ I K ^ 5 , b i ^ i S c o n v e x combination of convex f u n c t i o n s and i s thus convex. Hence, V* .(J) a c h i e v e s i t s maximum a t an extreme p o i n t of the X Q space, say a^, and thus r*Caj)2 f*(jp >ft5) f o r a l l ^ € X 0 Now c o n s i d e r K ( a ^ b ^ ) Case It b^ i s such t h a t j e R^. T h i s i m p l i e s t h a t M ( a j , b 1 ) = -hA+O+0 L ( a J , b 1 ) = -hA-kp (D-cA)< -hA which i m p l i e s t h a t K * ( a J , b i ) = M ( a j , b i ) = K ( a J , b i ) Case 2; b.^ i s such t h a t j e S^. T h i s Implies t h a t M ( a J , b 1 ) = 0-hA+O L(a J,b i)=.O+kj £A-(D-CA)J+0 >-hA which i m p l i e s t h a t K * ( a J , b i ) = L ( a J , b 1 ) = K ( a J , b 1 ) 23 Case 3; b^ i s such t h a t j e T h i s i m p l i e s t h a t M(aj,b 1)=0+0+kjA L(aj,b 1)=0-k p(D-cA)+kjA<kjA which i m p l i e s t h a t K*(a j,b i)=M(a J,b i)=K(a J,b 1) Thus at the extreme p o i n t a^ K * ( a J , b i ) = K ( a j , b 1 ) (i=l...m) which i m p l i e s t h a t ^ ( a j j - f ( a j ) > ^ ( J f c f t f ) f o r a l l J eX Q C o r o l l o r y 4.1.1 max"K(F,G )=max K(a.,G ) FeX i 1 Prooft SinceJdP(p=l and P i s non-negative K(F(a#) =/ K( 5,0*)dF(J) * / max K(J ,G*)'dF(p = K( a j,G*) Lemma 4.1.2 min K(F*,w)=min K(F*,b,) 1 e Y o 1  P r o o f : D e f i n e f ( i f) by ^(y|)=K(P ,vj)=.SAiK( a i,y|) f o r a l l n e Y Q Q.E.D. Q.E.D. 24 Thus i s a piece-wise l i n e a r f u n c t i o n of the 7?^ w i t h d i s c o n t i n u i t i e s o c c u r i n g when the ( n - l ) dimensional simplex Y0={(>|/ > • • • > ^ x . ) / 7i cuts a hyper-plane of the form 7£ ^=A ( i = l . . . n ) . Note a l s o t h a t s i n c e cA4D*(c+l)A w i t h c<n, the simplex Y Q must cut the hyper-cube formed by the hyper-planes ^j_=A ( i = l . . . n ) . See F i g u r e I I . Now these hyper-planes p a r t i t i o n Y Q such t h a t ^ f ( ^ ) i s continuous over each element of the p a r t i t i o n . Thus on any element of the p a r t i t i o n , ^ ()|), because of i t s l i n e a r i t y , must achieve i t s minimum a t a v e r t e x . Hence y (y[) must achieve i t s minimum over Y„ a t one o f these v e r t i c e s , o These v e r t i c e s are formed by the i n t e r s e c t i o n of Y Q w i t h e i t h e r the hyper-planes ^ = A or wit h the c o - o r d i n a t e f a c e s . Thus each of these v e r t i c e s must be one of the f o l l o w i n g type. (1) The i n t e r s e c t i o n of Y wit h a c o - o r d i n a t e f a c e , o o u t s i d e of the hyper-cube. These v e r t i c e s would have the t o t a l f o r c e D c o n c e n t r a t e d i n one c o - o r d i n a t e , and 0 i n the o t h e r s . (2) The i n t e r s e c t i o n of Y Q w i t h the hyper-cube. These v e r t i c e s would have each of t h e - ( h - l ) c o - o r d i n a t e s e i t h e r an A or an 0 and the n-th c o - o r d i n a t e D-cA. C l e a r l y t h e r e i s no ambiquity at t h i s p o i n t of d i s c o n t i n u i t y as t o where the minimum would occur s i n c e /-h5i;5i*A 25 Now the vertices of type ( l ) cannot be possible minimum points as the following shows. If ""j =A+e and ^5 = y then A,(-hA)+A ak 2(A^y)>A /(-hA)+^ Ak 2(A-(y+e)) Thus the minimum must occur at a vertex of type ( 2 ) which are p r e c i s e l y the b^'s ( 1 = 1 . . . m ) Corollory 4 . 1 . 2 min K(F*,G)-=*miri K(F*,b.) GeY i x Proof; Since jdF(?|)=i and G i s non-negative K(F*,G) = /K(F* i)j)dG(7|) > ( min K(F*,^)dG(r|) * K('F*,b3) Q . E . D . Q . E . D . Lemma,,,,4,. 1 . 3 Let (X,Y,K) be a game and X*=fx 1,... Jx n)CX Y*=fy 1, . ..,y n)CY Let v b e t h e value of t h e game (K,X ,Y ) Then i f there are F = 2 A i X . where S A i=l; Aj^O and G • = %L Ay. where .^_< B\ = 1 ] ^ • > 0 such that min K(F*,G)=K(F*,y.)=v; y, e Y* Y <J J and ^ # ' * max K(F,G )=K(x.,G )=vj x. e X X 1 1 then F , G i s the solution and v i s the value of the game (X,Y,K) P r o o f i min max K(F,G)<max K('F,G )=K(x.,G )=v Y X X 1 max min K(F,G)>min K(F*,G)=K(F*,y,)=v X Y Y ? Now these imply t h a t min max K(F,G)<v<max min K(F,G) Y X X Y and since max min K(F,G)<min max K(F,G) X Y Y X then min max K(F,G)=v=max min K(F,G) Y X X Y Hence K(F,G )$v$K(P ,G) f o r a l l F € X and f o r a l l G € implyin g t h a t v i s the value and F , G i s the s o l u t i o n of (X,Y,K) 4.2 A Model of n - C i t i e s w i t h (n-l)A*D<nA I n t h i s model the previous lemmas giv e t h a t (1) (2) The optimal defence s t r a t e g y i s of the form A l s o b..=(D-(ri-l)A;A f ..., A) A, D-(n-l)A) 27 Thus a l l that i s needed to solve t h i s model i s to determine the A^'s and them's and the value of the game. (l ) The optimal attack strategy: Theorem 1.4.1 gives that K('F ,b 1)=v f o r i=l...n Therefore A 1k 1(nA^D)+ /\ 2(-hA) + . . Mn(-hA)=v A 1(-hA)+ +Ahkn(hA-D)=v Let t i n g L=An(kh(nAKD)+hA) and suhtacting the i - t h equation from the n-th gives A j k ^ n A - D H h A ^ L which implies that \ _ A • L ^ i ~ ki(nA-D)+hA .and sincej>jAi =1 then 1= , L ki(nA-D)+hA Thus 1 L = n £-/ ki(nA-D)+hA - 28 and t h e v a l u e o f t h e game i s v = ( - h A ) ( l - A i ) + A ik j_(nA-D) = l>hA (2) The o p t i m a l d e f e n c e s t r a t e g y Theorem 1.4.1 g i v e s t h a t T h e r e f o r e ^ 1 ( k 1 ( n A - D ) ) + £ 2(-hA) + ...+/? n(-hA)=v ^• 1 ( - h A ) + . +^ nk n(nA-D)=v and d e t e r m i n i n g t h e ^ ' s i n a s i m i l a r f a s h i o n t o t h e A^'s g i v e s P i " k^nA-Dj+hA ~ ^ i Thus t h e s o l u t i o n i s c o m p l e t e . ^ • 5 A model o f 3 - Q i t i e s w i t h A*D<2A I n t h i s case Lemmas 4.1.1, 4.1.2, 4.1.3 g i v e t h a t (1) The o p t i m a l a t t a c k s t r a t e g y i s o f t h e fo r m * ,3 3 P ^ j C A ^ w i t h AjZQ (1=1,2,3) a n d ^ S A i = l (2) The o p t i m a l defence s t r a t e g y i s o f t h e form G * w i t h #>0, (1=1. . . 6 ) ; S f t = l and b 1 = (A,D-A,0) . h 2 = (D-A,A,0) b 5 - (0,A,D-A) h 4 = (0,D-A,A) b,- = (D-A,0,A) b 6 = (A,0,D-A) 29 equality must hold for7 7=0^ whenever^ ^  0. Thus f o r each b^ (i= 1 . . . 6 ) either the following equation ( i ) or the inequality ( i ) must hold. (1) K(F*,b i) A1(-hA)+A2k2(2A-D)+A5k5A = V (1*) K(F*,b 1) > V (2) K(F*,b 2) A1k1(2A-D)+A2(-hA)+A3k3A = V (2*) K(F*,b 2) > V C3) A1k1A+A2(-hA)+A3k5(2A-D) = V K(F*,b 3) > V ( » K(F*,b 4) = A1k1A+/\2k2(2A-D)+A5(-hA) = V ( O K(F*,b 4) >_ V (5) K(F*,b-5) •k A 1k 1(2A-D)+A 2k 2A+A 3(-hA) = V (5*) K(F*,b 5) 2 V (6) K(F*,b 6) = A 1(-hA)+^k 2A+A 5k 3(2A-D) = V (6*) K(F*,bg) > V I t can be shown, by tedious methods, that i f fc-t} kp? k^ . then any more than three equations taken at a time are inconsistent. The proof w i l l hot be given here because t h i s r e s u l t can be obtained by c a r e f u l inspection of Lemmas 4.3*2, 4.3«3> 4 . 3 . 4 , 4 . 3 . 5 . 4 . 3 . 1 A c l a s s i f i c a t i o n of the possible optimal defence strategies * G Since the optimal defence strategy G has the above . form, consider the twenty combination of the pure strategies b^...bg taken three at a time. The twenty combinations are 30 c l a s s i f i e d i n t o f o u r types, i n such a manner that the elements of any p a r t i c u l a r type are merely permutations of each other. As an a i d t o the c l a s s i f i c a t i o n consider the three dimensional graph of the s i x pure s t r a t e g i e s b^...bg four c l a s s i f i c a t i o n are defined to be. Type 1: two adjacent strategies with the t h i r d i n the other side v^^V They are: 9 ipeft > 0 Type 2; two i n one side and the t h i r d adjacent to one these two They are: 32 Type 3: two i n one s i d e and the t h i r d non-adjacent t o e i t h e r of these two They a r e : fW4 y 0 > 0 Type 4: each i n a d i f f e r e n t f a c e and no two adj a c e n t They a r e : A j / ^ > 0 We > 0 Of these twenty combinations, the f o l l o w i n g lemmas prove t h a t o n l y f o u r are c o n s i s t e n t w i t h the assumption t h a t k ^ k ^ k ^ . In these lemmas assume t h a t ( l ) ( i ) - ( j ) means tb.e j - t h equation s u b t r a c t e d from the i - t h . S i m i l a r l y f o r the i n e q u a l i t i e s . 33 (2) v i = k i(2A-D) and u. = k. + h x 1 Lemma 4.3.2 (Defence strategies of type 4) I f k^>kg>k^ then i t as. impossible to have equations ( l ) , ( 3 ) , (5) with i n e q u a l i t i e s (2*), ( 4 * ) , (6*) Proof: Assume that ( l ) , ( 3 ) , ( 5 ) , (2*), (4*) (6*) hold. Therefore: (l ) - ( 2 * ) < 0 =>A2(k2(2A-D)+hA) < \ r(k 1(2A-D)+hA) (3)~(4*)< 0^A 5(k 3(2A-D)+hA)5 A 2(k 2(2A-D)+hA) (5)-(6*)< 0^A 1(k 1(2A-D)+hA)< A 5(k^(2A-D)+hA) which i s possible i f and only i f equality holds everywhere. But t h i s reduces to k^=k2=k^ which i s a contradiction. In fact t h i s shows, as asserted e a r l i e r , that any more than equations ( 1 ) , (3) and (5) are inconsistant when;k^>k2>k^. Similar observations can be made i n the subsequent lemmas. Q.E.D. Corollory 4.3.2 I f k^>k2>k^ then i t i s impossible to have equations (2), (4) , (6) with i n e q u a l i t i e s ( 1 * ) , ( 3 * ) , ( 5 * ) . Proof: I d e n t i c a l to the proof of the preceeding lemma. Lemma .4.3-2 (Defence strategies of type 3) G- can have ? 6 only i f k-^kgik^ Proof: Assume that ^^^^>0. Thus equations (1), (2), (5) -Jf -X-and i n e q u a l i t i e s (3 )> (4 ) , ( 6 ) hold. Therefore* (i ) - ( 6 * ) £ 0^ A ^ < Agkg (2)-(3*)* 0* A5k5< ^ i k i (5)-(4*)f 0^ A 2k 2 < A^ also (l ) - ( 2 ) = 0^>A1(v1+hA) = A 2(vg+hA) (2)-(5) = 0 ^A 2 u 2 = A 5 u 3 These l a s t two equations imply then that u 3 (v 2 +hA) _ U 3 ( v 2 + h A ) ^'1 = (u2+u^) (v1+hA) +u^ (v2+hA) S U^V^+hA) A 2 = — - J — ™ up(v..+hA) 3" <f Therefore: A - ^ k ^ ^ k g S A^k.^  <* u 2 (' v i + n A ) k ^ 5 u j (v-j+hA) k 2 < u^ (v-^ -f-hA) ^ <3» k.^2 k 2 > k ^ 0 C o r o l l o r y 4.3-3 I f k ^ k g ^ k ^ then G cannot he any other s t r a t e g y of type 3'. P r o o f : The other f i v e s t r a t e g i e s o f type 3 can he achieved by permutations of the i n d i c e s 1,2,3; where i n the defence s t r a t e g i e s the t h r e e p o s i t i o n s of A, D-A, and 0 are permuted. As an example c o n s i d e r the permutation Then: h± = (A,D-A,0) ) (0,A,D-A) = b^ b 2 = (D-A,A,0) ) (0,E-A,A) = b^ and b 5 = (D-A,0,A) i (A,D-A,0) = b. u,(v 0+hA) u n(v,+hA) 2 " << ^(vg+hA) A , = *3 cL and the c o n d i t i o n s on the A 1 ' s and k^'s become: A 1 k 1 < A^k^< A 2 k 2 and k 2 2 k ? > k x Now t h i s same r e s u l t i s a c h i e v e d by s o l v i n g the case i n which fijfafc* 0 or e q u i v a l e n t l y when ( l ) , ( 3 ) , ( 4 ) , ( 5 * ) , ( 2 * ) , (6*) h o l d . Thus the onl y case which holds when k ^ k g ^ k ^ i s when r i r 2 r 5 Q.E.D. Lemma 4.3.4 (Defence s t r a t e g i e s of type 2) G* can have (1) fi^f^^> Q o r (2) /S2/?yS4 0 o n l y I f k^>kg2kj Proof; Assume t h a t §1J3^>0. Thus equations (l),(5),(6) *Jfr •)£ and i n e q u a l i t i e s (2 ),(3 ),(4 ) h o l d . T h e r e f o r e : (5)-(4*)* 0=J> A g k 2 s A ^ (5)-(2*)i 0* A 2(k 2+h)<A 5(k 5+h) a l s o (l)-(6) = 0=* A 2k 2 = A^k3 (5)-(6) = O ^ A ^ + h A ) =A 3(v 3+hA) These l a s t two equations imply t h a t k g(v 3+hA) k 2(v 3-fhA) 1 8 8 ( k 2 + k 3 J (v-j+hA) +k 2 (v 3+hA) = £ k,(v,+hA) A = 2 <J> k Q(v,+hA) A, = 1 '3 5 T h e r e f o r e : A 2 k 2 £ ' \ k i •*» k 3 (v-j+hA) k 2 £ k 2 (v 3+hA) •< k^' 37 and ' A2(k2+h)<A-5(k-5+h) k^(v-j+hA) (k2+h) < k2(v-j+hA) (k^+h) Therefore i f k^  s kg < k^  or k^  < kx < kg G can have P-^P^P^ > 0 S i m i l a r l y , as i n C o r o l l o r y 4 . 3 - 3 the case when ^ ^ ^ ^ > 0 can he achieved by permuting the i n d i c e s 1 , 2 , 3 . The de s i r e d permutation (m) Thus G* can have ^2^3(^4> 0 Q.E.D. C o r o l l o r y 4 . 3 . 4 I f k^>k2>k3 then G cannot he any other s t r a t e g y of type 2 . Proof: As In C o r o l l o r y 4.3«3 i t i s only necessary t o permute the i n d i c e s 1 , 2 , 3 to determine the other cases. Q.E.D. Lemma 4.3»5 '> (Defence s t r a t e g i e s of type 1) G can have $ 0 o n l y l f k l " k 2 ~ k 3 Proof: Assume that f^/S^^-? 0. Thus equations ( 2 ) , ( 4 ) , (5) * # and i n e q u a l i t i e s (3 )*(1 ) , ( 6 ) h o l d . Therefore: ( 2 ) - ( 3 * ) - c V ^ k ^ X ^ (4) -(l*)£ 04> A1(k1+h)<A5(k5+h) Al s o : ( 4 ) - ( 5 ) = 0=s> \k± = ^ 2 k 2 (5) - ( 2 ) = 0* A 2 u 2 = A,u 3 These l a s t two equations imply t h a t k 2 ( k 3 + h ) k 2 ( k 3 + h ) *1 = (k 2+k 5)(k^+h J +k 1(k 2+h) * r k-^k +h) A 2 = f • k ^ k ^ h ) A 3 = T ~ T h e r e f o r e : A-jk^Ajk.^ <B> ^^(kg+h)^ k^Ck^+h) k^ ^  k 2 and X1 ( k ^ h ) £ (k^+h) *9 k 2 (k^+h) (k-j+h) i _k1 (k 2+h) (k^+h) k 2 < k x T h e r e f o r e i f k 2 > k^ G* can have $2.M^ 0 38 Q.E.D. C o r o l l o r y 4.3.5 I f k 1>k 2>k^ then G cannot he any other s t r a t e g y of type 1. Thus these f o u r lemmas and t h e i r c o r o l l o r i e s prove t h a t i f k l > k 2 > k 3 " t h e r e a r e o n l y f o u r p o s s i b l e o p t i m a l defence s t r a t e g i e s These are the f o u r cases i n which G has 39 (1) ^ 2 ^ 5 > ° (3) ^ - V 0 (*) <V 2 ?5 > 0 I t Is now necessary to determine which, i f any, of these defence s t r a t e g i e s can occur. Looking at the pay-off matrix tha t a r i s e s from the a t t a c k s t r a t e g i e s a^a^a^ and the defence s t r a t e g i e s b^....bgj and adding hA t o each of i t s e n t r i e s gives the f o l l o w i n g m a t r i x H 0 w x Z l Z l W l 0 W2 0 0 w 2 ;z 2 z 2 z, z, w, 0 0 w, 3 3 3 3 H where w^^ = k i (2A-D) + hA and z i = A+hA Using t h i s m a t rix i t i s then p o s s i b l e t o determine which of fehfa'* a r e S r e a t e r t h a n z e r o -4o By Theorem 1.4.1 and assuming A i > 0 (1=1,2,3), the optimal defence s t r a t e g y G must s a t i s f y the equation HG* = v+hA ' This gives the f o l l o w i n g : h = - z 2 z 3 - w 1 ( - Z 2 ) + w 1 ( Z 5 ) /s - ( - z 2 Z 5 ) + w 1 ( w 2 - z ; 5 ) /$ where cf = $2 = - W 3 W 2 + Z 1 W 2 + Z 1 W 3 U h = " w l W 2 + w 2 z r Z l Z 3 u h = - w i V z i z 5 U where w. w. W 1 Z 2 Z 3 " W 1 W 2 Z 3 > 0 Z 3 Z 3 w l z l z l o 0 W 2 = w 2( Z 5z 2-w 2w 5) > 0 z 3 W 3 0 41 K - Z 2 W 3 - W 1 ( W 3 " Z 2 ) U where 6 = ^2 " Z 1 Z 2 ' W 1 W 2 h w 1w 2+z 1z 5-w 2z 5 ^ ^ 4 m ' ^ l z 2 + z j 5 z 2 - w l z 3 /tf where 0 w l 0 w 2 z 2 z 2 = w 1(z 2z 5-w 2w 5) > 0 2 3 0 w^ w l z l w l 0 w 2 z2 = z 1 z 2 z 3 - w 1 w 2 z 5 > 0 Z 3 0 0 42 Thus Jin each o f the f o u r cases t h e numerators of them's must he p o s i t i v e f o r t h e /^'s t o be p o s i t i v e . S e t t i n g t h e s e numerators up i n a t a b l e g i v e s : Case (2) z^Wg+w^O-WjWg > 0; z^z^-w^^ ^ 0 ; wg( Z-^w^)-z-jZ^ (1) z1Zg--w1Wg > 0- z 1z 3Wg(w 1-z 3); ZgZ-^+w-JZg+z^) (4) - z 2 z 5 + w 1 ( Z g + z ; 5 ) ; z 3Wg+w 1(z 5-Wg); z^Zg+w-^Wg-z^) (3) ZgZ3-w1(w-5-Zg).? 0; -ZgZ^+w^z^-Wg) > z-jZg-w^Wg:? 0 On e x a m i n a t i o n o f each of t h e e n t r i e s i t i s e v i d e n t t h a t c e r t a i n o f t h e s e a r e g r e a t e r t h a n z e r o . These i n e q u a l i t i e s have been marked i n t h e t a b l e . A l s o , a l l b u t one o f th e e n t r i e s o f undetermined s i g n appear t w i c e i n t h i s t a b l e , b u t w i t h o p p o s i t e s i g n s . Thus, except f o r one i n s t a n c e , t h e r e must be a t l e a s t once case i n w h i c h each o f t h e e n t r i e s i s p o s i t i v e . Hence, a p a r t from t h e one i n s t a n c e t h e game would be s o l v e d . The s p e c i a l case o c c u r s when t h e undetermined z^Wg+w.^ z^-Wg), t h a t o c c u r s i n t h e 4-th c a s e , I s n e g a t i v e . But t h i s case c o r r e s p o n d s t o t h e case i n w h i c h i t i s advantageous t o b o t h t h e a t t a c k e r and de f e n d e r t o i g n o r e t h e t h i r d c i t y and c o n c e n t r a t e on the f i r s t two. T h i s can be seen as f o l l o w s . The p a y - o f f m a t r i x c o r r e s p o n d i n g t o th e two c i t y case i s -w. 0 wr 43 Solving f o r the defence strategy gives w 1 +w 2 > fin = W l 2 w^+Wg and the value of the game i s "1, "2 Now then i f the attacker attacks the t h i r d c i t y the matrix i s w. 0 0 w„ ..z3 and the attacker achieves w. + w 1 w1+w2 W-j+Wg by concentrating on the t h i r d c i t y * Clearly the attacker would not concentrate on the t h i r d c i t y i f + w W l + W 2 1 W-^ +Wg w 1 Wg w i + w 2 which Implies that Z-^w^+Wg) - w^g SO But t h i s i s the spe c i a l case mentioned above and thus the solution i s complete. 4.3.6" Summary (1) I f z^Cw^Wg^w-jWg* 0, where w i=k i(2A-D)+hA and z^k.jA+hA, t h e t h i r d c i t y i s n e i t h e r a t t a c k e d n o r defended and * 3 l (a) t h e a t t a c k s t r a t e g y i s P = ^ u A i a , where w p w. A =± •, „ IF - , and A o «=' 1 w i + w 2 2 w^ +Wg * 5, (b) the defence strategy i s G = £ #b,- where *1 ~ w^+Wg and /5g = w^ +Wg" w l w 2 (c) the value i s v = — (2) I f z^(w1+Wg)-W^w2> 0, the optimal defence strategy i s one of the following fours Gl = ^ l b l + ^ 2 b 2 + ^ 5 b 5 (2) G* * fa2+fyj* fiifii -• (3) G* - ^ b 1 + ^? 6b 6 where i n each case 6. "s 0 and 2 ^ < =1 r 1 j=' ' X J 4 5 Now consider the a r r a y . Case (2) ^(wg+w^-w^Wg;- z i z 3 " * w i w 3 5 w 2 ^ z 3 ~ w l ^ " z l z 3 (1) z^Zg-W^Wg; z 1z 3+Wg(w 1-z 3); ZgZ^-w-^Zg+Zj) (4) -ZgZ^+w^-Zg+Zj)j z 5w 2+w 1(zj-Wg)5 ZgZ5+w1(Wg-z3) (3) ZgZ^-Wj^Cwj-Zg); -z^Zg+w^z-j-Wg); z^Zg-w^Wg and determine which cases have the e n t r i e s i n the corresponding rows a l l noh-negatlve. Anyone that q u a l i f i e s Is an optimal strategy. Let i t he represented "by C- =£3 A b, • The a. 's are then • c a l c u l a t e d by s o l v i n g the simultaneous equations K ( a 1 , G * ) = K(a 2,G*) = K(a ?,G*) (3) The optimal a t t a c k s t r a t e g y Is of the form F - Z 7 A 4 a . and the A • *s are c a l c u l a t e d by s o l v i n g the i=/ 1 1 1 simultaneous equations of K(F*,b, ) * lt(F*,b , ) = K(P*,b ) x l x 2 3 (4) The value of the game i s v=k(F*,b 1 ) = K( a i,G*) F I G U R E I BIBLIOGRAPHY K a r l i n , S-. M a t h e m a t i c a l Methods and Theory i n Games, Programming, and Economics, V o l . 2, A d d i s o n Wesley (1959) Gross U n p u b l i s h e d 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080570/manifest

Comment

Related Items