A competitive search game with a moving target

Résumé

We introduce a discrete-time search game, in which two players compete to find an invisible object first. The object moves according to a time-varying Markov chain on finitely many states. The players are active in turns. At each period, the active player chooses a state. If the object is there then he finds the object and wins. Otherwise the object moves and the game enters the next period. We show that this game admits a value, and for any error-term ε > 0, each player has a pure (subgame-perfect) ε-optimal strategy. Interestingly, a 0-optimal strategy does not always exist. We derive results on the analytic and structural properties of the value and the ε-optimal strategies. We devote special attention to the important time-homogeneous case, where additional results hold.