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 one after the other, and has to make irrevocable take-it-or-leave-it decisions. Her goal is to select the maximum value in the sequence. While in the classic secretary problem, the values of upcoming elements are entirely unknown, in many realistic situations, the decision-maker still has access to some information, for example, in the form of past data. In this talk, I will take a sampling approach to the problem and assume that before starting the sequence, each element is independently sampled with probability p. This leads to what we call the random order and adversarial order secretary problems with p-sampling. In the former, the sequence is presented in random order, while in the latter, the order is adversarial. Our main result is to obtain the best possible algorithms for both problems and all values of p. As p grows to 1, the obtained guarantees converge to the optimal guarantees in the full information case, that is, when the values are i.i.d. random variables from a known distribution. Notably, we establish that the best possible algorithm in the adversarial order setting is a simple 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 start accepting a value. Surprisingly, this sequence is independent of p.
I will then complement our theoretical results with practical insights obtained from numerical experiments on real life data obtained from Goldstein et al. (2020), who conducted a large-scale behavioral experiment in which people repeatedly played the secretary problem. The results help explain some behavioral issues they raised and indicate that people play in line with a strategy similar to our optimal algorithms from the first game onwards, albeit slightly suboptimally.
This is joint work with José Correa, Andrés Cristi, Laurent Feuilloley, and Alexandros Tsigonias-Dimitriadis.
