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

where

g n , s = α (

n − s )

1 +

s β .

n −

Since the k -th from the last stage corresponds to the ( m − k + 1 ) -th (from the first)

stage, the player A's optimal strategy for the k -th stage (1 ≤ k ≤ m )is

1

r k α + n − 1 r k α + n − 1

a k −

n ,

.

+ +

r k g n , s r k g n , s n

On the other hand, the expected payoffs of player B's mixed strategy b =( q , 1 − q )

against player A's pure strategies are

v k − 1 , m )+( v k − 1 , m ) E ( Recon , b )= q ( r m − k + 1 α + 1 − q )( 1 − n +

v k − 1 , m ) . E ( ¬ Recon , b )= qr m − k + 1 ( − β )+( 1 − q )( 1 + (8.5)

Since we obtain

n n

r m − k + 1 g n , s

q =

n v k − 1 , m +

( α + β )+ +

r m − k + 1 n

from ( 8.4 )and( 8.5 ), similar to a k , the player B's optimal strategy b k =( q , 1 − q ) for

≤ ≤

the k -th stage (1 k m )is

n
r k g n , s +

n
r k g n , s +

b k

n ,

1 − .

n

For simplicity, we assume g n , s α + s β . Then, the approximation can be derived

as follows. 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

s

β
α +

α
α +

a k b k (

β ,

, 0 , 1 ) .

s s β

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

sn 1

2

+ 1 2 n − 1 1 + s

a k b k

n ,

,

s ,

.

( 2 + s ) ( 2 + s ) n + 2 + s