Optimal Sequential Selection from a Known Distribution with Holding Costs

Abstract

X ₁, X ₂, …, X_N is a sequence of independent random variables from a common continuous known distribution. The variables are observed sequentially, and as in the classical secretary problem, exactly one choice is made. In this case, however, one may either accept, reject without recall, or hold a presented variable with some associated cost. Optimal strategies are obtained for the additive and discounted-cost models. Optimality is seen in terms of the minimized overall cost of the selection procedure with a reward of 1 when the maximal element is selected. If holding is not allowed (with no associated cost) the problem reduces to the classical secretary problem with a known continuous distribution. Based on the holding cost, the optimal strategy involves either acceptance or rejection of the presented observation until it is cost-effective also to consider holding a presented variable. A held observation will eventually be either accepted or traded for a larger observation that may also be traded or accepted.

Key Words:

• Secretary problem
• Optimal stopping