Open Problems on Search Games - Search Theory: A Game Theoretic Perspective - page 74

there until the sweeper that starts from the nearest end point is ε -close. Then

run to the the middle until ε -close, turn, and run back until the end.

It is possible to show that there exists an optimal response in M 1 ∪M 2 against

any mixed strategy that is based on . The conjecture in [ 2 ] is that conversely

against any mixed strategy that is based on

P

M 1 ∪M 2 there exists an optimal

response that is in . If this conjecture is true, then the princess and monster game

on an interval reduces to a standard optimization problem that can be solved numer-
ically by discretization and linear programming. An initial computation of the value
of the game under the assumption of the conjecture was carried out in [ 2 ], but it
contained some inaccuracies that have been corrected in [ 10 ]. The table below gives
the value of the game V n against the number of grid points n of the discretization.
In [ 2 ] it was stated that the value of the game could perhaps be 11

P

8, but this table
demonstrates that the value must be slightly lower: the value V n for n

/

= 1 , 024 in

Tab le 5.1 is within 10 − 3 of the actual value of the game.

n V n

1 1

2 1 . 2667

4 1 . 3303

8 1 . 3547

16 1 . 3647

32 1 . 3689

64 1 . 3709

128 1 . 3719

.

256 1 3724

.

512 1 3726

3727
Tabl e 5. 1 Number of grid points versus value of the game

1 , 024 1 .

Since the solution of the game on an interval is already a hard problem, it may
seem that the solution of the game on an arbitrary graph is impossible. However,
one should observe the following nice confluency property of the princess' strategy
: suppose that p 1 , p 2 ∈ P and that p 1 ( t 0 )= p 2 ( t 0 ) for some t 0 .Then p 1 ( t )= p 2 ( t )

for all t 0 ≥ t (in Chap. 14 , Steve Alpern calls this 'sticky'). Even more so, a mixed

strategy based on )

is the probability that P is in A at time t . Perhaps it is possible to derive the optimal
response of the monster from this property, and verify the conjecture. We conjecture
more generally, that for the game on a tree there exists an optimal princess strategy
that satisfies the confluency property.

P can be described by a probability measure μ t such that μ t ( A

5.3 High-Low Search Games

Dresher's guessing game has recently been solved asymptotically [ 8 ], but there is a
very similar high-low search game that remains unsolved. It was proposed around
the same time as Dresher's game, by Ed Gilbert [ 12 ]. As in Dresher's game, Blue