SIAM Journal on Control and Optimization, Vol.47, No.3, 1178-1190, 2008
The "princess and monster" game on an interval
A minimizing searcher S and a maximizing hider H move at unit speed on a closed interval until the first (capture, or payoff) time T = min{t : S(t) = H(t)} that they meet. This zero-sum princess and monster game or less colorfully search game with mobile hider was proposed by Rufus Isaacs for general networks Q. While the existence and finiteness of the value V = V (Q) has been established for such games, only the circle network has been solved (value and optimal mixed strategies). It seems that the interval network Q = [-1, 1] had not been studied because it was assumed to be trivial, with value 3/2 and "obvious" searcher mixed strategy going equiprobably from one end to the other. We establish that this game is in fact nontrivial by showing that V < 3/2. Using a combination of continuous and discrete mixed strategies for both players, we show that 15/11 <= V <= 13/9. The full solution of this very simple game is still open and appears difficult, though many properties of the optimal strategies are derived here.