Charles E. M. Pearce - The University of Adelaide, Department of Applied Mathathematics, Adelaide, South Australia 5005, Australia (email)
Abstract: We treat a version of the multiple-choice secretary problem called the multiple-choice duration problem, in which the objective is to maximize the time of possession of relatively best objects. It is shown that, for the $m$--choice duration problem, there exists a sequence $(s_1,s_2,\ldots,s_m)$ of critical numbers such that, whenever there remain $k$ choices yet to be made, then the optimal strategy immediately selects a relatively best object if it appears at or after time $s_k$ ($1\leq k\leq m$). We also exhibit an equivalence between the duration problem and the classical best-choice secretary problem. A simple recursive formula is given for calculating the critical numbers when the number of objects tends to infinity. Extensions are made to models involving an acquisition or replacement cost.
Keywords: Optimal stopping, relative ranks, best-choice problem, dynamic programming, one-step look ahead rule.
Received: October 2011; Revised: May 2012; Published: May 2012.