K. Hinderer et M. Stieglitz, Isotonicity of minimizers in polychotomous discrete interval search via lattice programming, MATH M O R, 51(1), 2000, pp. 139-173
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.