Optimal search on spatial paths with recall: Theoretical foundations

This is the first of two articles which analyzes the problem of organizing an optimal sequential search among sites located in space. Here it is assumed that the pay-offs or costs at sites are independent random variables with known distributions, and that recall of previously inspected sites is possible. Optimal sequential search is then taken to include optimization with respect to both stopping rules and search paths. In this article, it is shown that such optima always exist, and that under mild regularity conditions, optimal stopping rules on search paths always exhibit the classical reservation price property. In a companion article, a computational procedure for the optimization problem with continuous distributions is developed. It is illustrated for small examples, and optimal search paths are also computed for examples with discrete contributions.