UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Reduction of games using dominant strategies Wiens, Elmer Gerald 1969

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

Item Metadata

Download

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

Full Text

REDUCTION OF GAMES USING DOMINANT STRATEGIES  ELMER GERALD WIENS B.Sc,  University  of B r i t i s h  Columbia, 1 9 6 7  \  A THESIS SUMBITTED IN PARTIAL FULFILMENT; OF THE REQUIREMENTS FOR THE DEGREE OF  MASTER OF SCIENCE  In  t h e Department of MATHEMATICS  We a c c e p t t h i s t h e s i s a s to the required standard  conforming  THE UNIVERSITY OF BRITISH COLUMBIA April, 1 9 6 9  In p r e s e n t i n g  t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r  an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e I further agree that permission  for extensive  f o r s c h o l a r l y p u r p o s e s may b e g r a n t e d by h i s r e p r e s e n t a t i v e s .  copying  It is understood that copying  permission.  Department o f  MATHEMATICS The U n i v e r s i t y o f B r i t i s h C o l u m b i a V a n c o u v e r 8, C a n a d a Date  / I P K X L  t  l  ,  ) 1(, f C  c  and  o f this  that  Study. thesis  b y t h e Head o f my D e p a r t m e n t o r  of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be allowed written  I agree  or publication w i t h o u t my  ABSTRACT  U s i n g the concept o f dominant s t r a t e g i e s  3  r e d u c i n g the s t r a t e g y spaces o f a game i s developed. r e s u l t s a r e used t o reduce some i n f i n i t e  a method f o r These  games o f the C o l o n e l  B l o t t o type t o f i n i t e m a t r i x games which a r e then s o l v e d "by the Snow-Shapley theorem.  iii.  TABLE OF CONTENTS  PAGE CHAPTER 1.  INTRODUCTION  1  1.1  D e f i n i t i o n o f a Game  1  1.2  Min-Max S o l u t i o n s o f Games  2  1.3  Some C l a s s e s o f Games  1.4  Optimal \  CHAPTER 2.  Strategies  '  3  f o r M a t r i x Games  5  \  REDUCTION OF GAMES  7  2.1  Introduction  7  2.2  D e f i n i t i o n o f Dominance  7  2.3  Reduction  8  2.4-  D e f i n i t i o n o f e-Dominance  2.5  Reduction  CHAPTER 3.  o f Games U s i n g Dominance  o f Games U s i n g  12 e-Dominance^  ATTACK AND DEFENSE PROBLEMS  12 '  3.1  Introduction  3.2  A Model o f 2 - C i t i e s Payoff Function  w i t h a Continuous^  A Model o f n - C i t i e s Payoff Function  w i t h a Continuous^  A Model o f 2 - C i t i e s Discontinuities  with a Payoff with  A Model o f n - C i t i e s Discontinuities  with a Payoff with -  3.3 3.4 3.5,  -  18 18  Convex 19 Convex 21 Large 23 Large 34-  iv.  PAGE  CHAPTER 4 . 4.1  Introduction  4.2  Matrix  4.3  A Method  REFERENCES  37  SOME MATRIX GAMES  Games f r o m  37 the Discrete  of Inverting Matrices  2 - C i t y Model  38 40  42  ACKNOWLEDGEMENTS  The Dr.  a u t h o r wishes  t o express h i s thanks t o  R. A. R e s t r e p o f o r h i s i n v a l u a b l e a s s i s t a n c e a n d h e l p f u l  criticisms  i n the preparation The  Columbia fully  financial  thesis.  support o f the U n i v e r s i t y o f B r i t i s h  and t h e N a t i o n a l  acknowledged.  of this  Research  Council.of  Canada i s g r a t e  CHAPTER 1  INTRODUCTION  1.1  D e f i n i t i o n o f a Game: A two-person, zero-sum game i s d e f i n e d b y a t r i p l e t  G = (X,Y,f)  .where  X  and Y  a r e measurable spaces and  a bounded, r e a l v a l u e d measurable f u n c t i o n d e f i n e d on A s s o c i a t e d w i t h t h e spaces S  and  T  where  S  X  and  Y  Y .  The s e t s i n S  (or T )  of  X  (or Y )  of  X  ( o r Y ) belong t o S  X x Y .  a r e two f a m i l i e s o f s e t s  i sa a-field i n X  in  f is  and T i s a a - f i e l d i n  a r e t h e measurable  subsets  where i t i s assumed t h a t t h e i n d i v i d u a l (or T ) .  elements  I n - t h i s p a p e r we w i l l  c o n s i d e r o n l y zero-sum games, t h a t i s games w i t h two i r r e c o n c i l a b l e opponents i n w h i c h one p a r t i c i p a n t wins what t h e o t h e r l o s e s . The space o f s t r a t e g i e s f o r P l a y e r I i s t h e s e t U = i\x '• ia i s  a  measure on  S  and p.(X) = 1} .  The space o f s t r a t e g i e s , f o r P l a y e r I I i s t h e s e t V = {v : v  i s a measure on  For a p a r t i c u l a r c h o i c e o f  u € U  and  T  and v ( Y ) = 1} .  v e V  the payoff to  Player I i s F(UJV) =  ff f ( x , y ) d u d v = f f ( x , y ) d v d u  w h i l e t h e p a y o f f t o P l a y e r I I i s -F(\j.,v) .  P l a y e r I seeks t o  maximize t h e p a y o f f w h i l e P l a y e r I I seeks t o m i n i m i z e t h e p a y o f f .  1.2  Min-max S o l u t i o n s o f Games: I f P l a y e r I uses t h e s t r a t e g y  receive at least the number  inf F(u.v) veV  °  v = sup i n f F ( u , v )  \i e U Q  he i s c e r t a i n t o  i n p a y o f f from P l a y e r I I .  Thus  i s t h e upper l i m i t t o t h e amount  laeU veV P l a y e r I canvwin w i t h c e r t a i n t y independent o f P l a y e r I I ' s c h o i c e of strategy. I f P l a y e r I I uses t h e s t r a t e g y t o l o s e a t most  sup F ( u , v )  v  Q  e V  he i s c e r t a i n  i n p a y o f f t o P l a y e r I . • Thus t h e  ueU number  v = i n f sup F ( u , v ) veV ueU  i s t h e l o w e r l i m i t t o t h e amount  P l a y e r I I c a n r e s t r i c t h i s l o s s w i t h c e r t a i n t y independent o f P l a y e r I's choice of s t r a t e g y .  D e f i n i t i o n 1.2.1  •'  \  I f the r e l a t i o n s h i p  sup i n f F(n,v) = i n f sup F ( u , v ) = v ueU veV veV ueU is valid  then  v  i s c a l l e d t h e v a l u e o f t h e game.  D e f i n i t i o n 1.2.2  A pair of strategies  \\* e U  and  o p t i m a l i f and o n l y i f F ( u , v * ) _< F(ia*,v*) <_ F ( u * , v ) u € U  and  v € V .  v* e V  are  for a l l  5.  D e f i n i t i o n 1.2.3 € > o  be g i v e n .  e-optimal  Let  v  A pair  be t h e v a l u e of strategies  o f t h e game, a n d l e t u* e U  and  v* e V  are  i f and o n l y i f F ( u * , v ) :> v - e  fora l l  v e V  F(n,v*) £ v + e  for a l l  u e U .  and  It  c a n b e shown t h a t t h e v a l i d i t y  of  ;  sup i n f F ( u , v ) = i n f sup F ( u , v ) ueU v e V v e V ueU \  guarantees the existence of §»optimal s t r a t e g i e s . the  Furthermore^  relationship  max m i n F(n,v) = m i n max F(n,v) ueU v e V  is  valid  v e V ueU  i f and o n l y i f t h e r e with  exist  optimal  strategies  u* e U  v = F(u*,v*) .  and  v* e V  1.3  Some C l a s s e s o f Games. Some t y p e s  o f games f r e q u e n t l y c o n s i d e r e d a r e a s  follows: 1.  Finite Matrix  Games.  X = {1,2,. . . ,n} , Y = { l / . . . ,m}  , S = 2 , X  T = 2  n U  =  { M = ( M  1  , .  .  .  ,1^)  e  R  N  :  yx  ±  >  o  ,  #  S  | i  ±  =  1)  Y  V = {v=(v ,. . • ,v ) 1  f(i,d)  € R  n  = a ,  e R ,  ±  m  i  : v.. >_ o , S v  = {l,...,n}  j  e  = 1}  ±  tl,...,m),  A = m E u, j=l  n  F(u-,v) = S i=l A  is  a  1  called  0  =  J  X = Y = [0,1]  1}  uAv  the p a y o f f matrix  Games on t h e U n i t  U = V = set  v  1  la ]  of  t h e game.  Square.  > S = T = Class of Borel  of a l l  cumulative  sets  distribution on  n  For  = u(x)  e U  F(^i,v)  and r  = J  l  p  l  o o  n  , Y c R  S = class  , X  m  of Borel the  T = class  the Borel X  and  of  and sets  sets  R Y  11  x R  are  functions [0,1].  .  m  .  c l o s e d , convex  generated by the t o p o l o g y on  X  generated by the  relative  t o p o l o g y on  Games. Y  .  € V ,  f(x,y)du(x)dv(y)  relative  of Borel  [0,1]  J  Games on Convex S u b s e t s X c R  v = v(y)  of  topological  spaces.  .  open s e t s  in  . open s e t s  Y .  in  5.  S  and  T  the  a r e the c l a s s e s o f B o r e l s e t s (generated by  open sets) o f  X .'. and  Y  respectively  The games c o n s i d e r e d i n t h i s t h e s i s w i l l be o f types 1 and 3 and techniques w i l l be developed t o reduce some games of  1.4  type 3 t o games o f type 1.  Optimal S t r a t e g i e s f o r M a t r i x Games. It- can be shown t h a t f o r any m a t r i x game the r e l a t i o n \  max min F(u^v) = min max F(u,v) = v ueU veV veV iaeU  i s always v a l i d  That i s , m a t r i x games always have o p t i m a l s t r a t e g i e s .  [J,  p.26]. '-Further-  more, the s e t o f o p t i m a l s t r a t e g i e s f o r each p l a y e r i s a c l o s e d convex s e t [3j p . 3 6 ] .  The m a t r i x games t h a t a r i s e i n t h i s  paper  w i l l be s o l v e d by means o f the f o l l o w i n g theorem, due t o R.N. Snow and L.S. Shapley [3> p.45].  n*.  Theorem 1.4.1  If  convex s e t s  and  U*  v a l u e o f the game s i n g u l a r submatrix  v  '  and  V*  v*  a r e extreme p o i n t s o f the  o f o p t i m a l s t r a t e g i e s , and i f the  i s n o t z e r o , then t h e r e e x i s t s a non-  M v =  of  A  such t h a t  •1 T  eM"  e  •1 eM" eM" M"• v eM"  where  e  i s a v e c t o r o f the same dimensions as T  components a r e  1  5  and  e  i s i t s transpose.  M  a l l o f whose  CHAPTER 2  REDUCTION OP THE GAMES  2.1  Introduction.  It the  i s o f t e n p o s s i b l e t o s i m p l i f y a game b y  s p a c e o f - . s t r a t e g i e s o f one o r b o t h p l a y e r s .  game  G  i s defined by the t r i p l e t  w i l l be d e f i n e d by t h e t r i p l e t S c  Y  o f t h e game strategies be  1  will  finite  used  subsets  G . and  o\ c X  I f the subsets  ov  Y  G  1  and a n d <b  are  strategies  o f t h e game a n d o p t i m a l  In p a r t i c u l a r , this are i n f i n i t e  reduction can  s e t s a n d C3\  a n d «D  b e c a u s e t h e n t h e Snow-Shapley theorem c a n be  t o s o l v e t h e game.  I t should  be n o t e d  a g e n e r a l i z a t i o n o f the concept o f  that' t h i s  dominant  reduction  strategies i n  [2, p . 4 o ] .  D e f i n i t i o n o f Dominance. Por  X  where  o f t h e game a n d t h e o p t i m a l  f i n i t e m a t r i x games, D r e s h e r  2.2  (o\,©,f)  a l s o be t h e value  o f t h e game  very u s e f u l i f X  are  is  G  That i s , i f a  ( X , Y , f ) t h e r e d u c e d game  a r e both measurable s e t s .  chosen c o r r e c t l y the value  reducing  and  a game  G  Y respectively,  l e t t7\, a n d 2) Define  be m e a s u r a b l e s u b s e t s  U ^ = {u. e U : \x(a\) = 1 }  of  and  8.  = 1}  Vg> = { v e V': v ( © )  Definition each  .  0 1 i s dominant w i t h  2.2.1  respect  to  i f f for  v € Vj> sup j xeX JD  f(x,d)dv  J  ^  Is  2.2.2  inf  dominant w i t h  to  to  OX  Y  .  i f f f o r each  f(a,d)du . !  de© ej d  i s dominant i f f i t i s dominant w i t h  Reduction  Lemma  respect  respect  f(a,y)du = i n f  yeY ^  2.3  .  #  \  A  4>  f(a,d)dv J  i s dominant i f f i t i s dominant w i t h  Definition H e U  = sup aeoj  o f Games u s i n g  respect  to' X  .  e  such  Dominance.  2.3.1 1.  I f f o r each that  for a l l  t h e n Gl 2.  x  IS  I f f o r each ' for a l l  € X  there  d eg)  exists  f(x,d)  <  d o m i n a n t w . r . t . 5)  •  y e Y  a eOl  dominant w.r.t.  there  f ( a , y ) >_ 0\  .  exists  2)  u = u. f  f(a,d)du  v = ,v  f(a,d)dv  e ^  then  (*)  such <£) i s  that  Proof: From  (*)  we  get  f o r each  such that f o r a l l  it)  v e  f ( x , d ) d v _<  01  0\  <  Clearly  since  v € VQ 2.  Lemma  sup xeX  «£)  |ji e  f(a,d)dydv  <3D  f(a,d)dvdu  sup aeoi  &  f(a,d)dv  >_ sup f(a d)dv ae o\ 3)  .  3  £  = sup f(a d)dv aeo\. * £  .for a l l  J 5  J  , which implies  Similarly  exists  VQ  f(x,d)dv ,J  there  x  01 c  f(x,d)dv sup xeX "SO Therefore  x € X  0\  i s dominant w.r.t. 01  i s dominant w.r.t  £)  .  .  2.3-2 1.  For  any  v e  2.  F o r any  u e  Proof:  That  , sup J f(a,d)dvdp uebV <x 2)  01  &  f ( a , d ) d v d m sup  other  j l  f(a,d)d(adv = i n f  ', i n f  sup  = sup ^ f ( a d ) d v aeoi S)  J  F  (  F  T  - ae oi °<S>  The  i n e q u a l i t y i n the  direction  and  p o i n t s were assumed t o be m e a s u r a b l e s e t s .  A  D  )  ±  f(a,d)dfj  s obvious .  i s true because  u(oj) = 1  . . ,  10.  2.3-1  Corollary 1.  F o r any  2.  F o r any  v e V  f(x,y)dvdu  sup ueU inf veV °  p. € U  = sup xeX  »  f(x,y)d|jdv = i n f '  •  yeY  f(x,y)dv . J  f(x,y)dn . <J  Lemma 2.3-3 (71 i s d o m i n a n t w . r . t T) i f f f o r a l l  1.  f(x,d)dvdu  sup  f { f(a,d)dvd(a .  <£) i s d o m i n a n t w^.r.t. Oi i f f f o r a l l  2.  inf f f(a,y)dudv v e V " on  Proof: Lemma  = sup  = inf veV  J a  The p r o o f f o l l o w s i m m e d i a t e l y  v e V£i  u e Ucn  f f f(a,d)dudv » oi  from  the d e f i n i t i o n and  2.3•2.  Theorem 2 . 3 - 1 w.r.t.  0{  (Ol.Sjf)  If  then  C l i s dominant w.r.t.  the optimal  are also  optimal  strategies  strategies  £)  and  £) i s d o m i n a n t  a n d t h e v a l u e o f t h e game  a n d t h e v a l u e o f t h e game  (X,Y,f) . Proof: v  Let  u*  be t h e v a l u e  preceeding  lemma  e  TJox  and  v * e V£>  o f the reduced  game  be o p t i m a l (Olj&f).-.  •  s t r a t e g i e s and Then b y t h e  11.  f ( x , y ) d v d u < sup [ f (.'x, d)dv*d(j " ueU <&  i n f sup veV ueU  J,J  f(a,d)dv*du  = sup  a S) sup i n f ueU veV  J l  f ( x , y ) d u d v >_ i n f veV  f(a,d)dv*du* = v  f(a,y)du*dv  =inf  f(a,d)du*dv  f(a,d)dp*dv* = v . But by F u b i n i ' s Theorem f(x,y)dydu =  f(x,y)dudv  Thus i n f sup veV ueU  J J  f ( x , y ) d u 4 v <_ v <_ sup i n f ueU veV  f(x,y)dudv  J,J  Theorem 2.3-2 1.  Let  X c R-«n  be a c l o s e d , bounded convex s e t w i t h a  f i n i t e s e t o f extreme p o i n t s f : X x Y -» R  01 .  I f f o r £> c Y  i s a convex f u n c t i o n o f  x  the f u n c t i o n  f o r each  d e £) , then  Ol i s dominant w . r . t . S) .• Proof: Then  Let g  point of  v e  , consider the_function  g(x) =  f(x,d)dv .  i s a convex f u n c t i o n and t a k e s i t s maximum a t an extreme X .  _  12.  i.e. 2.  sup f ( x , d ) d v = max f(a,d)dv xeX «3 aeoi^S J  Let Y c R  111  o f extreme p o i n t s f : X x Y - * R  be a c l o s e d , bounded s e t w i t h a f i n i t e s e t .  I f f o r Gl c X  the function  i s a concave f u n c t i o n o f y  f o r each  a e Ol ,  <£) i s dominant w.r.t. 01 .  then  2.4  S)  f o r a l l v e Vg  D e f i n i t i o n o f e-Dominance  D e f i n i t i o n 2.,4.1  ( j ^ i s c-dominant w . r . t .  <£) i f f f o r a l l v e  sup f ( x , d ) d v < sup f.(a,d)dv + e ae a. & xeX £> J  Definition 2.4.2  2.5  3) i s e-dominant w . r . t .  R e d u c t i o n o f Games u s i n g  oi i f f f o r a l l  e-Dominance.  Lemma 2 . 5 . 1 1.  01 i s e-dominant w . r . t . sup  2.  J£) i s e-dominant w . r . t . inf veV  Proof:  f ( x , d ) d v d u < sup  f(a,y)dudv > i n f  S)  i f f f o r a l l v e V< f(a,d)dvdu + e  (X i f f f o r a l l ia;e U f f f(a,d)dudv - e  F o l l o w s i m m e d i a t e l y f r o m Lemma 2 . 3 . 2 .  u e  13.  Theorem 2 . 5 . 1  If  dominant w.r.t.  01 i s e - d o m i n a n t w . r . t .  01  then  (01,5),f) a r e e - o p t i m a l  Proof:  The p r o o f  the optimal  f o r t h e game  strategies (X,Y,f)  S)  <£) a n d  i s c-  f o r t h e game  .  2.3-1.  i s t h e same a s t h e p r o o f i n Theorem  Lemma 2 . 5 . 2 1.  Let  X c R  be a convex bounded  n  convex, bounded u n i f o r m l y c o n t i n u o u s T h e n we c a n e x t e n d P/X = f  and  P  x  f  to a function  set,  f u n c t i o n and F : X -• R  i s a c o n v e x f u n c t i o n on  f  Proof:  f : X - R  be a  X = c l o s u r e X.  such  that  X . i  f(y)  lim  i f y e X f(x)  i f y e X - X  x-y  xeX  First be lim n p  we show t h a t  sequences i n f(x/) = t then  n > N  X  P C  N' > o  such  3  ^ ' ^ )  <  •  n  = l i m x! = x , n  and  exists  in  an i n t e g e r . N > o  Also, f o ra l l  e > o  {x^}  limf ( x ) = S , n  I f we d e n o t e t h e m e t r i c  there 6  Let,. { x }  there  R  by  n  such  that  exists  that i f n > N '  n  with  lim x n  t / S .  6 > o  |f(x )  I f we l e t  i s w e l l defined.'  with  with  f o ra l l then  F  - S|  < e  e = ^~|S-t|  then  p(x ,x^) < 6  but  n  and  fora l l  |f(x£) - t | < e" .•  6 > o  there  exists  x  n  and  14.  This  contradicts  Hence  S = t  and  Now, in  X  the f a c t P  let  such t h a t  Then i f  that  i s well x,y e X  lim x n  f  i s uniformly  continuous.  defined. and  = x  and  (x^l  and  lim y n  (y ) n  be  sequences  = y .  o _< a <_ 1  a P ( x ) + (1 - a ) P ( y ) = a l i m f ( x ) + ( l - a ) l i m f ( y ) n n = lim [af(x ) n  + (1 - a )  n  _> l i m f ( « x n  n  f(y )] n  + (1 - a ) y )  = F ( a x + (1 - a ) y ) .  i.e.  P 2.  i s c o n v e x on Let  Y c R  111  concave, bounded, Then we P/Y  = f  F  and c l e a r l y  P/X  f  = f  be a convex, bounded  uniformly continuous  can extend and  X  to a function  F : Y -* R on  a  finite  bounded,  Let  • X c R  n  b e a c o n v e x , .bounded  s e t o f extreme p o i n t s  &  , f  f : Y -• R and  be  a  Y = closure  such that  ~  set such that  : X - R  uniformly continuous function.  definition.  Y .  Lemma 2.5.3 1.  set,  function  i s a concave f u n c t i o n  by  Then  be a convex,  X  has  Y.  15.  sup xeX  Proof: fact  f (x)  = sup_ lira, f ( x ) . ae oi x - a xeX  The p r o o f  that  follows  and t h e  a convex f u n c t i o n on a c l o s e d convex s e t w i t h  number o f e x t r e m e p o i n t s 2.  Let  a finite  i m m e d i a t e l y f r o m Lemma 2.5.2  Y c R  111  t a k e s i t s maximum a t a n e x t r e m e  finite point.  be a convex, bounded s e t such t h a t  s e t o f extreme p o i n t s  bounded, u n i f o r m l y  a  <£) ,  Y  has  f : Y -• R.be.a c o n c a v e ,  continuous function.  Then  inf f(y) = i n f l i m f(y) . yeY S e S y^a yeY N  N  i  ) Theorem 2.5.2 1.  Let  a finite set.  is  f : X x Y - * R  continuous f u n c t i o n o f there  Let  e O l , d e £)  p  x  exists a finite  e - d o m i n a n t w . r . t . 5)  i s a bounded, f o r each  has  finite  convex,  d e <£) , t h e n  0l = c i ( e ) c X  set  be a  X  for  s u c h t h a t 01  .  be t h e m e t r i c  and  s e t such that  G\ , a n d l e t <£) c Y  s e t o f extreme p o i n t s  e > o  Proof: a  be a convex, bounded  n  If. t h e f u n c t i o n  uniformly all  X c R  e > o  on  there  R  n  .  exists  By Lemma 2.5-2 f o r 5 = 6(a,d,e) > o  each  such  that lim x-»a xeX  Since  f(x,d)  ^) i s f i n i t e  <_ f ( a , d )  this  + c  implies  when  that  a e X  and  f o r a e Ol  p(a,a) < 6 .  there  exists  16.  a  = a(a,e) € X  d e i)  such that f o r a l l  lim f(x,d) x-a  <_ f ( a , d ) + € .  X€X  Then  for a l l v e lim  f(x,d)dv  <  f(a,d)dv  + c  XGX  0[ = {a = a ( a , e ) : a e Oi}  Let  •  h o u n d e d c o n t i n u o u s f u n c t i o n on v e V#  01  Theorem 1.  f(x,d)dv 0  and b y Lemma  = sup [ l i m „f(x,d)dv] ae 6i x-*a '<© xeX  £>  i s dominant  w . r . t . £)  is a  convex  2.5.3, f o r a l l  convex  Let  X =  n U  X.  + s  .\  where f o r e a c h  l e t £) c Y  f : X X Y - * R  i  '  1  set such that c l o s u r e  points,  <_ sup f(a,d)dv a e o i <8  2.5-3  1=1  of  X  f(x,d)dv  x  sup xeX  i.e.  But  X^  be a f i n i t e  , .  has a f i n i t e set.  i n each r e g i o n  X^  there  exists a finite  set  f o r each Ol c X  i s a bounded,  1  number o f  extreme  I f the f u n c t i o n  i s a bounded, convex, u n i f o r m l y  x  X.  continuous function  d e <$ , t h e n f o r a l l  such t h a t  CH  2.5»2, i n e a c h r e g i o n  X^  is  e >> o  e-dominant  w.r.t. Proof: finite  Prom Theorem set 0 \ ^  s u c h t h a t 0\ ^  i s e-dominant  there  w.r.t  «©  exists a in  X^ .  17.  i.e.  f o r a l l v e V<£) sup xeX  Letting  01=  ±  "  f ( x , d ) d v < sup  f(a ,d)dv + e . J  aeo).  n u (\. i=l  we  get  1  sup f ( x , d ) d v < sup xeX » ~ ae 0 | J  \  £>  f(a,d)dv + e .  CHAPTER 3  ATTACK AND DEFENSE PROBLEMS  3.1  Introduction In  t h i s Chapter, t h e r e s u l t s o f Chapter 2 a r e used t o  reduce some i n f i n i t e games t o f i n i t e m a t r i x games. of  The s o l u t i o n s  these m a t r i x games a r e then found w i t h the use o f the Snow-  Shapley theorem.  The games c o n s i d e r e d a r e a l l o f the C o l o n e l  B l o t t o type and hence the t e r m i n o l o g y of a t t a c k and defense problems  i s used throughout t h i s In  each model,  u n i t s and a t t a c k e d by  n  A  Chapter.  c i t i e s a r e to be defended by  units.  D  The outcome o f a b a t t l e a t one  c i t y does n o t a f f e c t the outcome o f a b a t t l e a t another  city.  The a t t a c k i n g p l a y e r seeks t o d i s t r i b u t e h i s f o r c e s among the n  cities  so as to maximize the expected p a y o f f , w h i l e the  defending p l a y e r seeks to d i s t r i b u t e h i s f o r c e s among the n c i t i e s so as t o minimize the expected l o s s . by i t s sets f  X  and  Y  Each game i s d e f i n e d  o f pure s t r a t e g i e s and i t s p a y o f f f u n c t i o n  where n  X = {x = (x ,x ,. 1  2  . . ,x ) : x n  ±  >_ o ,  Z  x  ±  = A}  n  Y = {y = ( y - ^ y g , . . . *y ) : y n  ±  >. o , _s y = D} n  19.  n S f,(x.,y.) i=l  f(x,y) =  1  f (x ,y ) i  i  1  and  1  i s the payoff a t c i t y  i  force consists of  x^  i  i f the a t t a c k i n g  units.  The methods w i l l be a p p l i e d t o two t y p e s o f models:  f i r s t , models  w i t h a c o n t i n u o u s p a y o f f whose s o l u t i o n s have been o b t a i n e d b e f o r e by o t h e r methods;  s e c o n d l y , t o some games w i t h d i s c o n t i n u o u s  payoffs, previously  3.2  unsolved.  A Model o f 2 C i t i e s w i t h a C o n t i n u o u s .  Convex P a y o f f F u n c t i o n  The f i r s t game c o n s i d e r e d i s d e f i n e d by X = { ( x , l - x ) | o <_ x £ 1} Y = {(y,l-y)|  o < y < 1}  f(x,y) = f - ^ x ^ ) + f ( i - x , l - y ) 2  . ' f^Cx-y) f (x,y) = i ( o f (l-x,l-y) = 2  Adding  and  f  2  1  2  i f x > y i f x < y  \ ( l - x -(1-y)) 2  o  ' we g e t  fMx-y) f(x,y) = \ U (y-x)  where  i f x > y i f x £ y  i f 1-x >_ 1-y i f 1-x  < 1-y  20.  Graph o f  f(x,y)  for fixed  y  X-,.(1-7)  * x [0,1],  Prom t h e graph i t i s c l e a r t h a t f o r each  y in  f'(x,y)  i s a convex f u n c t i o n o f x .  Therefore,  by Theorem 2 . 3 . 2 t h e  s e t o f extreme p o i n t s o f X ,  Gl = [ ( o , l ) , ( l , o ) ] , i s dominant.  \  \  But  f(o,y) = X y  and  2  functions of y . of  f ( l , y ) = X- (l-y)  By T heorem 2 . 3 * 2 t h e s e t o f extreme p o i n t s  Y , £) = { ( o , l ) , ( l , o ) }  U s i n g Theorem 2 . 3 . 1 , game w i t h  are both l i n e a r  L  , i s dominant w i t h r e s p e c t t o 0£ .  we have reduced o u r i n f i n i t e game•to t h e  matrix 'f(o,o)  f(o,l)  f(l,0)  f(l,l)  0  B = -  . l x  0  The Snow-Shapley theorem g i v e s us t h e v a l u e o f t h e game as X  v =  l  X  2  The o p t i m a l s t r a t e g y f o r . t h e a t t a c k i n g p l a y e r i s l  X  X  a* = (^ ^  , T~+k~~^  +  X  ability  +  .  ? where he a t t a c k s o n l y c i t y 2 w i t h p r o b -  l  ^  and a t t a c k s o n l y c i t y 1 w i t h  probability  The o p t i m a l s t r a t e g y f o r t h e d e f e n d i n g p l a y e r i s  21. \p -  ( T T T  X-. ~> \" "A' )  -  A.-j^+A.2  ility  -r—-x—  with  probab-  2  X^  Xp  2  where he d e f e n d s o n l y c i t y  and defends o n l y c i t y  1 with p r o b a b i l i t y  1 2  3-3  X,  -r ±l"*" 2  A Model o f n - C i t i e s w i t h a Continuous, This  Convex  Payoff.  game i s d e f i n e d b y •n  X = {x = ( x ^ . . . , x ) | x n  Y = {y = ( y , . - . , y ) | y 1  n X  f(x,y) =  and  It x  f o r each  ^ j  t (x ,y ) ±  ±  i s apparent  that  f(x,y)  X ,  01=  f (x ,y ) i  i  i  = X max(o,x -y ) j L  1  i s a convex f u n c t i o n i n  [ a ^ = ( ^2. '12 ' ' ' &  i s a linear  ,a  s  j  ±  our i n f i n i t e  i n ^  a  i j ~ °  i s dominant.  function of  - ( ^ . . . . . ^ K j .  respect to  a  y  f o r each  t h e s e t o f extreme p o i n t s o f  d j = D  We h a v e r e d u c e d  = D}  ±  .  T h e r e f o r e b y Theorem 2 . 3 - 2 ,  dominant w i t h  y  i f i = j , i = 1 , . . . ..n}  a. . = A  f ( a ^ , y ) = X^(A-y^)  is  n s  > o ,  = A}  ±  T h e r e f o r e b y Theorem 2 . 3 - 2 t h e s e t o f  y e Y .  £ .  1  V x  >_ o ,  with  ±  A >_ D .  extreme. p o i n t s o f i  n  i  o  i f i / i  i  But a^ e Y  :  i f . i = j , i = 1 , . - . ,n} ,  07 . game t o t h e game w i t h  matrix  f  i  X (A-D)  X-jA  1  XA  X (A-D) X A  2  B =  X-jA  2  X A  2  2  [f(a ,d )]. i  j  X  X A  n-1  A  X (A-D)  n  n  T h i s m a t r i x game i s e q u i v a l e n t t o t h e game s o l v e d i n D r e s h e r p. 54].  \  I f we assume t h a t k '1  - i=l  (l)  , l - p = £-2  X-^ > X  >•••> X  > o  and l e t  The o p t i m a l s t r a t e g y f o r t h e a t t a c k i n g p l a y e r i s where  n  a  i  1 =XTSA^  for  i < t ,  = o  for  i > t .  The o p t i m a l s t r a t e g y f o r t h e d e f e n d i n g 0  (p^..'.  , P  n  t - p  =  <  X  " ITS •  t  k<n  v  for - i < t , for  O  The v a l u e o f t h e game i s A  player i s  where  )  «>i - ?  (3)  n  then  a* = (a^,...,a )  (2)  g  A  k  i > t .  [2,  23-  3.4  A Model o f 2 - C i t i e s w i t h a P a y o f f w i t h L a r g e  Discontinuities.  The r e m a i n i n g models c o n s i d e r e d i n t h i s c h a p t e r a r e i n some ways s i m i l a r t o t h e game s o l v e d b y Cooper and R e s t r e p o [ l ] . However, because o f t h e l a r g e d i s c o n t i n u i t i e s i n t h e p a y o f f , t h e o p t i m a l s t r a t e g i e s and t h e v a l u e o f t h e game c o n s i d e r e d here a r e v e r y s e n s i t i v e t o changes i n t h e r e l a t i v e s i z e s o f t h e a t t a c k i n g force  A  and t h e d e f e n d i n g f o r c e D . The 2 - c i t y model was 3 4 - 3 s o l v e d f o r t h e cases where <_ D < 2A and where -^A <_ D < —k  i n w h i c h t h e i n f i n i t e games c o u l d be reduced games.  The>n-city  matrix  model was o n l y s o l v e d f o r t h e case where  (• ~-")A _< D < nA .  Because o f t h e l a r g e d i s c o n t i n u i t i e s i n t h e  2  p a y o f f , we were u n a b l e o t h e r models.  to f i n i t e  t o f i n d f i n i t e dominant s u b s e t s f o r t h e  However, i t i s f e l t t h a t s i m i l a r t e c h n i q u e s can  be used t o extend t h e r e s u l t s o b t a i n e d . The  2 - c i t y model i s d e f i n e d by  X = {(x,A-x) : x e [o,A]} Y = {(y,D-y) : y e [o,D]} f ( x , y ) = f ( x y ) + f (A-x,D-y) 1  3  2  where y y  i f A-x > D-y. f ( A - x , D - y ) =• j-h(A-x) i f A-x < D-y 2  with  X, > X  24.  If  o < A < D < 2A  we g e t X -h(A-x)  i f x > y  X  if  x < A-D+y  if  A-D+y £ x _< y  1  f(x,y) =  - hx  2  -hA  C a s e 1;  3/2 A <_ D < 2A It  will  can be reduced  be shown t h a t i n t h i s  to the f i n i t e  case  game w i t h p a y o f f  the i n f i n i t e matrix:  -hA  X  corresponding  t o t h e dominant  01 = {(o,A), £  To  establish  l  (A,o))  = {(D-A,A),  this  sets  (A,D-A)}  result,  consider  f-hk  if  x < D-A  f(x D-A) = 3  X -h(A-x)  i f x > D-A  -hA  if  x >_ A-(D-A)  if  x < A-(D-A)  v.  1  (1) f(x,A)  = ^X -hx 2  From  ( l )i t i s clear  that since  A-(D-A) <_ D-A  game  (i)  f o r x e [o,D-A]  f ( x , D - A ) = f(o,D-A) f ( x , A ) <_ f ( o , A )  (ii)  f o r x e (D-A,A]  f(x,D-A) < f(A,D-A) f(x,A) = f(A,A) .  By Lemma 2.3-1, CR  i s dominant w.r.t.  oD -  Now c o n s i d e r : • hA f(o,y) = V. 2 X  if  y <_ D-A  if  y > D-A  if  y >_ A  (2) r hA  f(A,y)= -  i f yy < A .  From (2) i t i s c l e a r t h a t (i)  f o r y e [o,A]  f ( o , y ) >. f(o,D-A) f ( A , y ) > f(A,D-A)  (ii)  f o r y e [A,D]  f(o,y) > f(o,A) f(A,y) > f(A,A)  By Lemma 2.3-1/ 01 i s dominant w.r.t.  ...  JD •  T h e r e f o r e , we need o n l y c o n s i d e r t h e game w i t h m a t r i x f(o,D-A)  f(o,A)  -hA  f(A,D-A)  f(A,A)  X 1  B =  f o r which  X, 2 -hA  26.  B  -1  =  \ \ 1  2  I - (hA)  hA  2  :  hA  Then, b y t h e Snow-Shapley theorem, (l)  The v a l u e o f t h e game i s X\ v = X + \ 1  1  (2)  (hAr  2  2  + 2hA  The o p t i m a l s t r a t e g y f o r t h e a t t a c k i n g p l a y e r i s a* = ( X + hA, X 1  (3)  2  + hA) • y  ^  j  ^  •  The o p t i m a l s t r a t e g y f o r t h e d e f e n d i n g . p l a y e r i s = ( X + hA, X 2  Case 2:  *  1  + hA) •  H  +  x  ^  g  h  A  4/3A < D < 3/2A I t w i l l be shown t h a t i n t h i s case t h e i n f i n i t e game can  be reduced t o t h e f i n i t e game w i t h p a y o f f m a t r i x -hA  X,  X -h[A-(D-A) ]  -hA  X -h(D-A)+  X -h(D-A)  •hA  X -h[A-(D-A) ]  +  1  1  1  +  Q  i  c o r r e s p o n d i n g t o t h e e-dominant s e t s .  -hA  01=  { ( o , A ) , ( ( D - A ) ,A-(D-A) ),  £) =  C(D-A,A),(A-(D-A),2(D-A)"),(A,D-A))  where  +  (D-A)  +  = (D-A) + 6  strategies  i n the sets  Consider  +  f o r small  To e s t a b l i s h d o m i n a n c e for  ( A - ( D - A ) , (D-A) ),  01 a n d  6 > o .  2D .  -hA  if  x < D-A  X -h(A-x)  i f  x > D-A if  x < A-2(D-A)  -hA  if  A-2(D-A) < x < A-(D-A)  X -h(A-x)  x > A-(D-A)  fX -hx 2  f(x,A-(D-A) =  1  Graph o f  ,  we c o n s i d e r now. t h e p a y o f f s  1  f(x,A)  :  Xg-hx  if  x < A-(D-A)  -hA  if  x > A-(D-A)  =  f(x,D-A)  D-A  0 -hA  (A,o)}.  first  f(x,D-A) =  (1)  +  A-2("D-A)  A-(D-A)  x A  28.  Graph o f  f(x.A-(D-A))  A-2(D-A)  0  Graph o f  — D-A i —  A-'(D-A)  A  f(x,A)  D-A  Let  X X  x  2  = {(x,A-x)|o < x < = {(x,A-x)|D-A  X = X (i)  1  U X  g  u X^  -hA  D-A}  < x < A-(D-A)}  X^ = {(x,A-x)|A-(D-A) Then  x  A- (D-A)  L-2(b-A)  < x<  A]  and:  x e [o,D-A] f(x,D-A) <  f(o,D-A)  f(x,A-(D-A)) <_ f ( o , A - ( D - A ) ) f(x,A) 1 f(o,A) . That i s , i n t h e r e g i o n w. r t . £  .  X  ±  , 013. = {(o,A)}  i s dominant  29.  (ii)  For  x e (D-A,A-(D-A)),  f(x.A) for  0\  2  +  =  there exists (D-A) + 6 +  For  x e  such t h a t i f  then the s e t  = {((D-A) ,A-(D-A) ),  ((A-(D-A) ,(D-A) )}  +  e-dominant w.r.t. (iii)  6 > o  and  By Theorem 2 . 5 . 2 ,  are a l l l i n e a r functions.  e > o  (D-A)  f ( x , D - A ) , f(x,A-(D-A))  S)  +  i n the r e g i o n  is  +  .  [A-(D-A),A]  f(x,D-A) <. f(A,D-A) f(x,A-(D-A)) < f(A,A-(D-A)) .  f (X,A) - P(A,A) By Lemma 2 . 3 . 1 , 01 i n the r e g i o n  «= {(A,o)}  .  U s i n g Theorem 2 . 5 . 2 * we e-dominant w.r.t. Now  i s dominant w.r.t. «9  S)  .  see t h a t  01 = Ol^ UOlg UOi^  is  '  consider:  f  -hA  i f  y <  D-A  X i f y > D-A \,-h(A-(D-A) ) if 2  +  f((D-A) ,y)  if  +  X -h(D-A)  +  if  X -h(D-A)  +  if  2  y < (D-A) (D-A)  +  < y < 2(D-A)  +  y > 2(D-A) (2)  r  1  f(A-(D-A) ,y) = +  -hA  if  X -h(A-(D-A) ) +  2  if  y < A-(D-A)  +  A-(D-A)" " < y < A-6 1  y > A-6  f(A,y) =  Graph o f  1-hA  if  y < A  if  y > A  f(o,y)  A-(D-A) • hA  2(D-A)  D-A  0  A"  Graph o f f((D-A) ,y) +  X -h(D-A)  +  2  X  -h(A-(D-A) ) +  A-(D-A) h D-A  Graph o f  r-  2(D-A)  T3  A~  *  f(A-(D-A) y) +  ;  X -h(D-A)+ 1  \ - h ( A - ( D - A )+ )\ I +  2  A  D-A Graph o f  A-(D-A) 1 2(D-A) 1 . r  j -  A  f(A,y) 1 1 1 1  1  1 1  A-(D-A) l  D-A  t  i t  2(D-A)  A  'D ' i -hA  31.  ( 2 ) and the graphs we see t h a t  From  (1)  F o r y e [o,D-A] f(o,y) = f(o,D-A) f((D-A) ,y)  = f((D-A) ,D-A)  +  +  f(A-(D-A) ,y)  = f(A-(,D-A) ,D-A)  +  +  f ( A , y ) = f(A,D-A) (ii)  F o r y e (D-A,A) f(o,y) = f(o,A-(D-A)) f((D-A) ,y) > f((D-A) ,A-(D-A)) +  +  f(A-(D-A) ,y) > f(A-(D-A) ,A-(D-A)) +  +  dT(A,y) = f ( A , A - ( D - A ) ) (iii)  For y e  [A,D]  f(a,y) = f(a,A)  T h e r e f o r e by Lemma t o G\ .  f o r a l l a e 01  2 . 3 . 1 *  2)  i s dominant w i t h r e s p e c t  The i n f i n i t e game has been reduced  t o t h e game w i t h  matrix f(o,D-A)  f(o,A-(D-A))  f(o,A)  f((D-A) ,D-A)  f((D-A) ,A-(D-A))  f((D-A) ,A)  f(A-(D-A) ,D-A) .  f(A-(D-A) ,A-(D-A))  f(A-(D-A) ,A)  f (AJD-A)  f(A,A-(D-A»  f(A,A)  +  +  +  B = +  +  +  32.  -hA  X  X -h(D-A)  X -h(D-A)  -hA  X -h[A-(D-A) ]  +  1  h  X  Then l e t t i n g  +  2  +  2  -hA  l  , v = Xj^ + hA , a = h [ A - ( D - A ) ]  + hk  B  2  -hA  +  as  X  \ -h[A-(D-A) ] 1  B =  2  +  C = [ b . . + hA]  s  w h i c h has t h e same o p t i m a l  strategies  y  o C =  u  v-a  o  U-b  v-b  o  u-a  v  V  o  A c c o r d i n g t o t h e Snow-Shapley  theorem i t i s s u f f i c i e n t t o c o n s i d e r  f o r t h e d e t e r m i n a t i o n o f t h e o p t i m a l s t r a t e g i e s o n l y square m a t r i c e s o f d i m e n s i o n l e s s t h a n o r equal t o 3 . matrix  ~"  M =  o  U  H  v-a  o  u-b  V  V  o  C o n s i d e r i n g the .  Then  M"  1  =  -v(u-b)  UV  |Ji(|Ji-b)  v(u-b)  ~uv  u(v-a)  v(v-a)  Hv  -u(v-a)  Prom t h e Snow-Shapley v =  theorem  uv(u-b) + u v ( v - a )  1 uv(.u-b )+uv(v-a)  "  33-  where  p = u.(u.-b) + iav + v ( v - a ) a* = (v(v-a),  .  iav, o , u ( u - b ) )  • ^  u(u-b) + uv - v(n-b) 1 P  u(v-a) + v(ii-b) - \iv v ( v - a ) + IJV - n(v-a) Then a*C = (v,v,v)  03* = v +  But  p.-v = X ~ ^ i — °  (u-v)C(u-b)(v-b) - ( V a ) ( v - a ) 3  s  i  n  c  2l ^2  e  2  (u-b)(v-b) - ( u - a ) ( v - a ) =  5  (\ -h(D-A) +hA)(X -h(D-A) +hA) +  +  2  1  - (\ +h(D-A) )(X +h(D-A)' ) > o +  2  since  -h(D-A)  + hA >_ h ( D - A )  +  +  f  1  i f D < | A .  That i s , . (1)  The v a l u e o f t h e game w i t h m a t r i x v  =  ^ ( u + v - (a+b)) P  _  B is  M  (2)  The e - o p t i m a l s t r a t e g y f o r t h e a t t a c k i n g p l a y e r i s a .  (3)  The e-optimal s t r a t e g y f o r t h e defending, p l a y e r i s p*.  34.  Case 3 :  5/4A < D < 4 / 3 A I n t h i s case we were u n a b l e t o f i n d f i n i t e  subsets.  dominant  ' Based on Case 1 and 2, t h e i n t u i t i v e most l i k e l y  sets  are 01=  {(o,A), ( ( D - A ) , A-(D-A) ), (A-2(D-A) , 2(D-A) ), +  +  +  +  (2(D-A) , A-2(D-A) ), (A-(D-A) , +  +  +  {(o,D), (D-A,A), (2-(D-A),A-2(D-A)), (A,D-A), \  (D-A) )} +  (A-2(D-A),2(D-A)),  (D,o)} .  \  We n o t e t h a t t h e f i r s t components o f p o i n t s i n 01 and. £) p a r t i t i o n the i n t e r v a l s  [0,A] and  However, e i t h e r f o r some subinterval of  [o,D] i n t o  d e 2) , f ( x , d )  [o,A] o r f o r some  on a s u b i n t e r v a l o f  [0,D] .  subintervale.  i s n o t convex on a  a e (ft , f ( a , y )  i s n o t concave  T h e r e f o r e t h e r e s u l t s o f Chapter 2  do n o t a p p l y f o r t h e c h o i c e o f 01 and 2) .  3'5  A Model o f n - C i t i e s w i t h a P a y o f f w i t h L a r g e D i s c o n t i n u i t i e s . T h i s game i s a g e n e r a l i z a t i o n o f t h e game c o n s i d e r e d i n  Section 3 - 4 .  ,The game i s d e f i n e d b y  X = {x = ( x , x , . . . , x ) | x x  2  n  i  n >_ o , .S x  Y = {y = ( y , y , . . . , y ) l y ^ > o , 1  f(x,y) =  2  n  1 f.(x.,y ) i=l • 1  where  n ^  y  ±  = A}  ±  = D}  35.  fx. x  \ L  i f  x  ±  > y, :  H  i ( i ^ i )  f  1 2 - ***- n * x  X  The o n l y model c o n s i d e r e d here i s the case where (  2 r  " )A 1  2  <_ D < nA .  I t w i l l be shown that o p t i m a l s t r a t e g i e s f o r  t h i s game can be o b t a i n e d by f i n d i n g o p t i m a l s t r a t e g i e s f o r t h e reduced  game  where  (Gi,&,f)  CR = ((A,o,...,o),(o,A,o,...,o),...,(6,...,o,A)}  = {a ,...,a } Q  £>= l((^-(n-l)A,A,... A),...,(A,...,A,D-(n-l)A)'} = 9  {d^...^}  To prove t h i s l e t X  Q  = (x € X | x  X. = {x e X -I x. Then  But  X = X  n u X. ° i=l  i  < D-(n-l)A. , f o r a l l i } > D - ( n - l ) A >. x  s i n c e i f x.  n  1  1  > D-(n-l)A  1.  Por  x e X  2.  Por  x €*X, , f ( x d . ) = -hA  Q  , f(x,d) = -hA a  i  f(x,d ) = \  ±  then  fora l l  J £.1} . x, 1  > |A .•  d e S) .  i f J ^ i  o i  fora l l  - h  n^ X j 0=1  f ( a , d ) = Xj ±  i.e.  fora l l x € X  i  JL  , f(x,d) £ f(a ,,d)  d € £> . By Lemma 2 . 3 . 1  01  i s dominant w.r.t. 5) .  j  n  for a l l  36.  For t h e p r o o f t h a t  i s dominant w . r . t .  01 see Cooper and  R e s t r e p o [ 1 , Lemma 2 . 1 ] . Now l e t  w  = hA + \  i  '%  Then  j  and  i  i f i = j  o  i f i / j  f ( a . , d . ) = -hA + P. x  i  and t h e f i n i t e game  x  (<Ji,$),f) has t h e  same o p t i m a l s t r a t e g i e s as t h e m a t r i x game w i t h p a y o f f See  Karlin  1.  P. . .  [3, p.28]. \  The"value o f t h e game i s v = -hA + [ £ - f - ] " i=l i  X  W  2.  The o p t i m a l s t r a t e g y f o r t h e a t t a c k i n g p l a y e r i s a* = ( a  3.  ...,a ) n  with  a ±  = ±  {} ^y I i=l~ I  The o p t i m a l s t r a t e g y f o r t h e d e f e n d i n g  = ( ,...,p ) w i t h Pl  n  p. = ±.  1  player i s  -L}-i .  CHAPTER 4  SOME MATRIX GAMES  4.1  Introduction As s t a t e d p r e v i o u s l y t h e 2 - c i t y game model  considered  i n S e c t i o n 3.s4 c o u l d o n l y be s o l v e d f o r two p a r t i c u l a r  cases.  I f we c o n s i d e r t h e i r dominant s e t s , we n o t e t h a t f o r a p o i n t i n a dominant s e t , one component i s always an i n t e g r a l m u l t i p l e o f D-A .  P o r t h i s r e a s o n we a r e l e d t o c o n s i d e r t h e same game  model b u t f o r m u l a t e d  as a d i s c r e t e game w i t h  X = {(x,A-x) : x  an i n t e g e r ,  o <_ x _< A}  Y = {(y,D-y) : y  an i n t e g e r ,  o <_ y £ D} , D = A + l .  By d e f i n i t i o n s o f f i n i t e m a t r i x games.  X  and Y , a l l t h e s e games a r e  As may be expected t h e s i z e o f t h e p a y o f f  m a t r i x f o r t h i s model i n c r e a s e d as game was o n l y s o l v e d f o r A ± 8 ,  A  i n c r e a s e d and t h e r e f o r e t h e  D <_ 9 .  the p a y o f f m a t r i x i s s t r a i g h t f o r w a r d .  The c o m p u t a t i o n o f  I n each c a s e , b y c h o i c e  o f s u i t a b l e n o t a t i o n and by means o f s t a n d a r d  dominance arguments  the r e s u l t i n g games c a n be reduced t o one o f t h e games c o n s i d e r e d below.  38.  4.2  M a t r i x Games from t h e D i s c r e t e I n t h e f o l l o w i n g games,  game, P  2-City  v  Model  w i l l be t h e v a l u e o f t h e  a * w i l l be t h e o p t i m a l mixed s t r a t e g y f o r P l a y e r I , and i  w i l l be t h e o p t i m a l mixed s t r a t e g y f o r P l a y e r I I .  games were s o l v e d by u s i n g t h e Snow-Shapley  A l l the  theorem.  Game No. 1: M  M =  M,v > o  v  .o  T h i s game has a l r e a d y been s o l v e d i n S e c t i o n 3 . 2 . v = u+v a* = \ ( >^ , u ) m-v -i_ V v  p*  Game  =  No."2:  M =  J  v  ) _L_  o  M  pi  v-b  o  u-a  V  V  o  o <; a" < u o < b < v  T h i s game has been s o l v e d i n S e c t i o n 3 . 4 . Let  d = uv(u-a) + fjv(v-b) p = u(u-a) + MV + v ( v - b ) v = d/p a* = ( v ( v - b ) , u v , u ( u - a ) ) l / p  ,  then  39.  3  = (-v(u-a) + uv + u(u-a) ,v(u-a) - uv + u ( v - b ) , v ( v - b ) + pv - p.(v-b))l/p  Game No.  3:  M =  o  P  p  P  v-d  o  p.-a  p-a  o  v-b  v-b  0  p-c  o  V  V  V  o  -v(u-a) [p+v-(b+c)] v(p-a)(p+v-b-c) v(p-c)(v-d) dM" =  uv(v-b), -uv(p+v-b-c)  <  a,c  <  P  b,d  <  V  Pv(p-a)  p(p-a)(p-c)  pv(v-d)  p ( p - c ) (v-d)  1  pv(p-c)  v(p-c)(v-d)  -pv(p+v-a-d)  p(v-b)(p+v-a-d) -p(p-c)( v-d) i  pv(v-b)  v(v-b)(v-d)  where Let  -p(v-b)(p+v-a-d)  d = p v [ ( p - a ) ( p - c ) + ( p - a ) ( v - b ) + (v-b)(v-d)3 . p = p(p-a)(p-c) + pv(p-a) + pv(v-b) + v(v-b)(v-d) , e = (1,1,1,I)  Then  pv(p-a)  7  v = d/p a* = ( v ( v - b ) ( v - d ) , p v ( v - b ) : , . p v ( u - a ) p ( p - a ) ( p - c ) ) l / p J  p* = dM e/p _1  4o.  Game No. 4:  o  M =  - u-a u-a  u-a  O  u-c  u-c  v-b  v-b  O  u- e  V  V  V  O  v-f  O  v-d  v-d  v-b V  The i n v e r s e m a t r i x o f M and  f 3 * were t o o c o m p l i c a t e d  o <_ a,c,e < u o < b,d,f < v  M- 1  was c a l c u l a t e d , b u t b o t h  t o i n c l u d e here.  However, i f we  let d = mv[(u-a)(|i-c)(u-e) + ( | i - a ) ( ( i - c ) ( v - b ) + ( u - a ) ( v - b ) ( v - d ) + (v-b)(v-d)(v-f)] p =  u(u-a)(u-c)(u-e)+^v[(^-a)(p-c)+(u-a)(v-b)+(v-b)(v-d)] + v(v-b)(v-d)(v-f)  then  v = d/p a* =  (v(v-b)(v-d)(v-f),uv(v-b)(v-d),uv(u-a)(v-b), uv(u-a)(u-c),u(u-a)(u-c)(u-e))  4.3  .  A Method o f I n v e r t i n g M a t r i c e s . When u s i n g t h e Snow-Shapley theorem t o s o l v e a game w i t h  payoff matrix computed.  M , t h e i n v e r s e o f square s u b m a t r i c e s o f M must be  The s t r a t e g i e s g i v e n by t h e theorem f o r a p a r t i c u l a r  s u b m a t r i x must t h e n be checked t o see i f t h e y a r e o p t i m a l .  If  41.  t h e y a r e n o t o p t i m a l , the' s u b m a t r i x i s d i s c a r d e d and the" p r o c e s s i s ' repeated. way  The f o l l o w i n g method was  found t o be a  f o r f i n d i n g the i n v e r s e of a matrix. Let  M  be a square m a t r i x ,  the same dimension  as  M .  I  be the u n i t m a t r i x o f  C o n s i d e r the t a b l o i d  F i r s t we a p p l y row o p e r a t i o n s t o the t a b l o i d t a b l o i d , say  B|c|l  .  r e s u l t i n g i n the t a b l o i d  IJM  l|M|l . yielding  Then we a p p l y column o p e r a t i o n s t o B|D|E  o p e r a t i o n s u n t i l the m a t r i x  .  D  D = BME  which i m p l i e s  the C|l  We a p p l y row and column  i s i n such a form t h a t i t s  i n v e r s e can e a s i l y be found by the s t a n d a r d t e c h n i q u e s . then  convenient  M"  1  = ED B -1  .  But  42.  REFERENCES  [ij  J . N. Cooper and R. A. R e s t r e p o , "Some Problems o f A t t a c k and Defense", SIAM Review, V o l . 9, No. 4 , ( O c t o b e r 1967),  [2]  pp.  680-691.  M. D r e s h e r , Games o f S t r a t e g y :  Theory and A p p l i c a t i o n s ,  P r e n t i c e - H a l l , Englewood C l i f f s , New J e r s e y , 1 9 6 1 . [3]  S. K a r l i n , M a t h e m a t i c a l Models i n t h e Theory o f Games, Programming and Economics, Addi.son-Wesley, R e a d i n g , Massachusetts, 1 9 5 9 .  

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-0080493/manifest

Comment

Related Items