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

val r 1 α +

v m − 1 , m 1 − n + v m − 1 , m

v m =

v m − 1 , m

r 1 ( − β ) 1 +

and

val r m − k + 1

v k − 1 , m v k − 1 , m

α + 1 − n +

v k , m =

v k − 1 , m

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

,where v k , m Γ (

for ( k = m − 1 , m − 2 ,..., 2 ) is the value of k , m ) ,and

val r m α

( α + β ( − ))

1 − n r m 1 n

v 1 , m = =

n .

r m ( − β ) 1

r m ( α + β )+

Γ ( , the expected payoffs of player A's mixed strategy a =

For the game k , m )

p , p )

( 1 − against player B's pure strategies are

a , p ( v k − 1 , m )+( p ) E ( Mine )= r m − k + 1 α + 1 − r m − k + 1 ( − β )

a ,¬ p ( v k − 1 , m )+( p )( v k − 1 , m ) . E ( Mine )= 1 − n + 1 − 1 + (8.2)

Then, the intersection of them is

p ( v k − 1 , m )+( p ) p ( v k − 1 , m ) r m − k + 1 α + 1 − r m − k + 1 ( − β )= 1 − n +

p )( v k − 1 , m )

+( − +

1 1

v k − 1 , m + r m − k + 1 β + 1

r m − k + 1 α + n − 1

p =

n =

1 −

n .

(8.3)

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

v k − 1 , m − np from ( 8.2 ), we have

+

Since the value of the game is 1

r m − k + 1 α + n − 1

v k , m = v k − 1 , m −

1 + n + n ·

n .

v k − 1 , m +

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

Then, the value of v k , m

can be approximated by

r m − k + 1

α

v k , m

1 − β

. (8.4)

n −

v m , m ,wehave

Since v m =

r 1

α

v m

1 − β

.

n −

From ( 8.3 )and( 8.4 ), the probability p for the k -th from the last stage is

r m − k + 1 α + n − 1

p = 1 −

n ,

r m − k + 1 g n , s +