A Problem in Optimal Search and Stop

Abstract

We are told that an object is hidden in one of m ( m < ∞) boxes and we are given prior probabilities p i 0 that the object is in the i th box. A search of box i costs c i and finds the object with probability α, if the object is in the box. Also, we suppose that a reward R i is earned if the object is found in the i th box. A strategy is any rule for determining when to search, and, if so, which box. The major result is that an optimal strategy either searches a box with maximal value of α i p i / c i or else it never searches such boxes. Also, if rewards are equal, then an optimal strategy either searches a box with maximal α i p i / c i or else it stops.