House-Hunting Without Second Moments

Abstract

In the house-hunting problem, i.i.d. random variables, X ₁, X ₂,… are observed sequentially at a cost of c > 0 per observation. The problem is to choose a stopping rule, N, to maximize E(X _N  − Nc). If the X's have a finite second moment, the optimal stopping rule is N* = min {n ≥ 1: X _n  > V*}, where V* satisfies E(X − V*)⁺ = c. The statement of the problem and its solution requires only the first moment of the X _n to be finite. Is a finite second moment really needed? In 1970, Herbert Robbins showed, assuming only a finite first moment, that the rule N* is optimal within the class of stopping rules, N, such that E(X _N  − Nc)⁻ > −∞, but it is not clear that this restriction of the class of stopping rules is really required. In this article it is shown that this restriction is needed, but that if the expectation is replaced by a generalized expectation, N* is optimal out of all stopping rules assuming only first moments.

Keywords:

• Job search
• Optimal stopping
• Selling an asset

Subject Classifications:

• 60G40
• 90A80

ACKNOWLEDGMENTS

We thank the referee for his comments. The work of Michael Klass was partially supported by NSF grant DMS-0205054.

Notes

Recommended by A. G. Tartakovsky.