The Secretary Problem with Independent Sampling

José Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, Alexandros Tsigonias-Dimitriadis

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
Number of pages24
JournalManagement Science
DOIs
Publication statusAccepted/In press - 2025

Fingerprint

Dive into the research topics of 'The Secretary Problem with Independent Sampling'. Together they form a unique fingerprint.
  • The secretary problem with independent sampling

    Correa, J., Cristi, A., Feuilloley, L., Oosterwijk, T. & Tsigonias-Dimitriadis, A., 2021, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Marx, D. (ed.). Association for Computing Machinery, p. 2047-2058 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Cite this