An elementary approach to optimal discrete-time search strategies. Issue 4 (2nd October 2017)

• Record Type: Journal Article
• Authors: Cheng, Raymond
• Is Part Of: Sequential analysis. Volume 36:Issue 4(2017)
• Page Start: 541
• Page End: 552
• Publication Date: 2017-10-02
• Subjects: Backward induction -- reservation wage -- sequential search -- stopping time; 60G40 -- 91B44 -- 92B99; Sequential analysis -- Periodicals; 519.54
• DOI: 10.1080/07474946.2017.1394721
• Languages: English
• ISSNs: 0747-4946

Abstract

ABSTRACT: Optimal strategies are known for the finite and infinite horizon discrete-time search with constant unit cost and without recall. These strategies were obtained in the theory of optimal stopping, based on the martingale convergence theorem and other tools from probability theory. We present here an elementary approach to these problems, relying only on routine calculation of expected values. In the finite horizon case, the solution utilizes a simple form of backward induction, in conjunction with a nonlinear dynamical system, to compute the parameters of the optimal strategy. An elementary proof is also given that a simple threshold search is optimal among all strategies with finite expected total cost.