Optimal sequential file search

This paper analyzes a dynamic problem in decision-making under uncertainty in which the decision-maker must determine whether or not to purchase costly information. The objective is to see whether or not a record is in a sequential computer file whose contents are initially not known. It is possible to gather information about the contents of the file by examining one or more of its positions. Obtaining this information is costly, however. The problem of determining an optimal search and disposition strategy is formulated as a Markov decision process. A finite-step algorithm for computing an optimal policy is presented. Finally, qualitative properties of the optimal search procedure are discussed. One particularly interesting result establishes conditions under which a ‘search-while-uncertainty-persists’ strategy is optimal.