The Value of the Two Cable Ambush Game - Search Theory: A Game Theoretic Perspective - page 136

1 / b
i = 0

1 / b
i = 0 λ i β i = k

1 / b
i = 0 β i = m

i β i = and

so

1 / b
i = 0 β i /

1 / b
i = 0

v ( a , b )= 1 − ( i β i ) .

1 / b

Thus, putting g j =( β j / ∑ i β i ) , a lower bound for v ( a , b ) is 1 − H where

i = 0

max 1 / b

j = 0

H = g j

subject to

1 / b
j = 0 λ j g j =

1 / b
j = 0

jg j = 1 , and g j ≥ 0 ( j = 0 , 1 ,..., 1 / b ) .

This is a linear program with dual

min x + y

subject to

λ i x + iy ≥ 1 , x , y unrestricted ( i = 0 , 1 ,..., 1 / b ) .

∈ Λ + and q ∈ Λ − be such that G Let s ( s , q )= G , where G ( i , j ) and G are given

,∈ Λ −

by ( 9.4 )and( 9.5 ) respectively. It is routine to check that, for i

)= (

s − λ s )( i ( λ q − λ s )+ λ i ( s − q ) − ( s λ q − q λ s ))

0 ≤ G ( s , q ) − G ( s , i

( − )( − )

s λ q λ s λ i λ

q s i s

∈ Λ + , and that, for i

)= ( λ q −

q )( i ( λ q − λ s )+ λ i ( s − q ) − ( s λ q − q λ s ))

0 ≤ G ( s , q ) − G ( i , q .

( s λ − q λ )( s λ − i λ ) q s i s

It is now straightforward to verify by the duality theorem that H = G ( s , q ) by

taking g q = G ( s , q ) − g s =( s − λ s ) / ( s λ q − q λ s ) , g i = 0 otherwise and x = G ( s , q ) −

y =( s − q ) / ( s λ q − q λ s ) .

9.5 A Second Illustrative Example

In the previous section we showed that an optimal Defender strategy gives rise
to a number of chains of intervals and used this fact to obtain a lower bound for
v

( a , b ) . However the type of chains and the number of each type that give this lower