Optimal Search for a Moving Target with the Option to Wait

We investigate the problem in which an agent has to find an object that moves between two locations according to a discrete Markov process (see Pollock, 1970). At every period, the agent has three options: searching left, searching right, and waiting. We assume that waiting is costless whereas searching is costly. Waiting can be useful because it could induce a more favorable probability distribution over the two locations next period. We find an essentially unique (nearly) optimal strategy, and prove that it is characterized by two thresholds (as conjectured by Weber, 1986). We show, moreover, that it can never be optimal to search the location with the lower probability of containing the object. The latter result is far from obvious and is in clear contrast with the example in Ross (1983) for the model without waiting.We also analyze the case of multiple agents. This makes the problem a more strategic one, since now the agents not only compete against time but also against each other in finding the object. We find different kinds of subgame perfect equilibria, possibly containing strategies that are not optimal in the one agent case. We compare the various equilibria in terms of cost-effectiveness.