On polychotomous search problems

The paper gives a unified treatment of those stochastic sequential search problems where in each state the searcher may decompose according to a given scheme the current search region in a finite number of parts upon which one obtains the error-free information in which of the parts the object is hidden. Many examples are given to show the generality of the model. The main results are: (a) a rigorous proof of the dynamic programming approach; (b) the reduction of the state space for problems with translation invariant data; (c) a dynamic programming proof for the computationally very attractive property of monotonicity and Lipschitz continuity of optimal search rules for two important special models, one of which has been investigated by Hassin using methods from information theory.