Effective Search for a Naval Mine with Application to Distributed Failure Detection - Search Theory: A Game Theoretic Perspective - page 118

The optimal strategies of player A and player B for the k -th stage (1 ≤ k ≤ m ),

denoted by a k and b k ,are

1
r k ( α + β )+

r k β + 1

r k ( α + β )+

r k α + n −

a k =

n ,

n

and

n
r k ( α + β )+

r k ( α + β )
r k ( α + β )+

b k =

n ,

,

n

respectively.
If k is very large or α < β n holds, we have

1
n ,

n − 1

a k b k (

, , ) .

1 0

n

On the other hand, if n α < β holds, we have

β
α + β ,

α
α + β

a k b k ( , 0 , 1 ) .

If n r k α and β α hold, we have

n

+ 1 2 n − 1

a k b k (

, , / , / ) .

1 3 2 3

3 n 3 n

8.3.2 Mine-Preparing Probability: Game Termination Case

In this section, we consider that only one transport ship sails and the game termi-
nates if it is broken by a mine. Then, the game Γ ( m ) is determined by an auxiliary

Γ ( game k , m ) ,i.e.,thelast k stages of the game Γ ( m ) :

r 1 α + Γ (

+ Γ (

m − 1 , m ) 1 − n m − 1 , m )

Γ ( m )=

+ Γ ( r 1 ( − β ) 1 m − 1 , m )

and

r m − k + 1 α + Γ (

+ Γ (

k − 1 , m ) 1 − n k − 1 , m )

Γ ( k , m )=

+ Γ (

r m − k + 1 ( − β ) 1 k − 1 , m )

Γ (

for ( k = m − 1 , m − 2 ,..., 2 ) ,where 1 , m ) is the game with payoff matrix

r m α

1 − n

.

r m ( − β ) 1

If the ship does not dispatch a reconnaissance boat when a naval mine is laid, the
ship is sunk and the game terminates with an expected cost r 1 ( − β ) .Thevalueof

the game is represented by