Tools to Manage Search Games on Lattices - Search Theory: A Game Theoretic Perspective - page 43

Theorem 5. In the OEIG with n ≥ 3 and 0 < s < 2 m, if

2 m
3

[ s / 2 ] ≤

is s at isfied, then an optimal strategy for player II is the uniform distribution on the
set B 0 ,whereB 0 is the set defined by ( 3.26 ) and the value of the game is equal to H
defined by ( 3.27 ). If, on the contrary,

2 m
3 ,

[ s / 2 ] > (3.30)

then the value of the game is

min H H

= ,

v

with H defined by ( 3.27 ) and H defined by ( 3.29 ). I f v

=

H then an optimal strategy
for player II is the uniform distribution on the set B 0 ,whereB 0 is the set defined by
( 3.26 ), if v H then an optimal strategy for player II is the uniform distribution on

the set B 0 ,whereB 0 is the set defined by ( 3.28 ).

=

Proof. As we know, the OEIG satisfies hypothesis of Theorem 2 , therefore, an op-
timal strategy for player I is the uniform distribution on X = F and the value of the

game is given by

1
m n min

A ∈F

v = M ( A , B )

which in this case is written as

n
i = 1 s i

1
m n min f

1
m n min

j = i ( m − s j ) .

( s 1 , s 2 ,..., s n )=

2 m
3 is satisfied, then from Corollary 1 it follows that the minimum of f is
equal to K defined by ( 3.23 ), therefore

[ / ] ≤

If s 2

v = H

and an optimal strategy for player II is the uniform distribution on the set B 0 ,where
B 0 is the set defined by ( 3.26 ).
If, on the contrary, ( 3.30 ) is satisfied, then, Theorem 4 proves that the minimum
for f is the minimum of the values K ,definedby( 3.23 ), and K defined by ( 3.24 ).
If this minimum is K , then the value of the OEIG is equal to H defined b y ( 3.27 )
and an optimal strategy for player II is the uniform distribution on the set B 0 ,where
B 0 is the set defined by ( 3.26 ). If this minimum is K , then the value of the OEIG
is equal to H defined b y ( 3.29 ) and an optimal strategy for player II is the uniform
distributionontheset B 0 ,where B 0 is the set defined by ( 3.28 ). This proves the
theorem.