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

We can now obtain the solution for the OEIG when n = 2. We have to compute ( 3.6 ),

which in this case is equal to

1
m 2 min

( s 1 ( m − s 2 )+ s 2 ( m − s 1 ))

1
m 2 min f

= ( s 1 , s 2 )

where s i = | B ∩ L i | . From Lemma 1 it follows that this minimum is given by

1
m 2

1
m 2 (

f ( s 1 , s 2 )= ms − 2 [ s / 2 ]( s − [ s / 2 ]))

which is the value of the game. A set B 0 which determines the optimal strategy for
player II is defined by

B 0 = { ( i , j ) :1 ≤ j ≤ s − [ s / 2 ] , for i = 1 , 1 ≤ j ≤ [ s / 2 ] , for i = 2 }.

The solution for the OEIG when n ≥ 3 is established by a number of lemmas and

theorems.
Lemma 2. Let s and m be integers such that 0 < s < 2 m. For each set of integers

s 1 , s 2 ,..., s n satisfying

n
i = 1 s i = s ,

0 ≤ s i ≤ m

s 1 ≥ s 2 ≥ ...≥ s n , (3.16)

the inequality

s 2 s n s − [ s / n ]

s 2 + ... + s n ≤ ] , m − m − m − [ s / 2

holds.

Proof. From ( 3.16 ) it follows that

s 2 ≤ [ s / 2 ] and therefore s i ≤ [ s / 2 ] for all i = 2 ,..., n

then

1 1

s i ≤

for all i = 2 ,..., n .

m − m − [ s / 2 ]

Multiplying both members by s i and adding

n
2

−

s i s s 1

s i ≤ ] , m − m − [ s / 2

n
i

assumptions

1 s i =

s and s 1 ≥ s 2 ≥ ...≥ s n imply that s 1 ≥ [ s / n ] ,then

∑

=