Isotonicity of minimizers in polychotomous discrete interval search via lattice programming

We consider several sequential search problems for an object which is hidde n in a discrete interval with an arbitrary prior distribution. The searcher decomposes the momentary search interval into a fixed number of subinterva ls and obtains the information in which of the intervals the object is hidd en. From the well-known lattice programming results of Topkis (1978) we dev elop a unifying method for proving in a transparent way the computationally very useful property of isotonicity of (largest and smallest) minimizers. We obtain rather natural sufficient conditions on the prior distribution an d the cost structure, some of them weakening corresponding ones in Hassin/H enig (1993). We also show how these assumptions can be checked in particula r cases. Some of our auxiliary results on lattices and submodular functions may be of independent interest.