The Secretary Problem with Independent Sampling

The secretary problem is probably the most well-studied optimal stopping problem with many applications in economics and management. In the secretary problem, a decision maker faces an unknown sequence of values, revealed successively, and has to make irrevocable take-it-or-leave-it decisions. Her goal is to select the maximum value in the sequence. Although in the classic secretary problem the values of upcoming elements are entirely unknown, in many realistic situations, the decision maker has access to some information, for example, from past data. In this paper, we take a sampling approach and assume that before starting the sequence, each element is sampled independently with probability p. We study both the adversarial and the random arrival models. Our main result is to obtain the best possible algorithms for both settings and all values of p. As p grows to one, the obtained guarantees converge to the optimal guarantees in the full information case. Notably, we establish that the best possible algorithm in the adversarial order setting is a fixed threshold algorithm. In the random order setting, we characterize the best possible algorithm by a sequence of thresholds, dictating at which point in time we should accept a value. Surprisingly, this sequence is independent of p. We complement our theoretical results with numerical experiments on data of people playing the secretary problem repeatedly. Our results help explain some behavioral issues they raised and indicate that people play a strategy similar to our optimal algorithms from the start onwards, albeit slightly suboptimally.