The secretary problem, also called the best-choice problem or marriage problem, is an optimal stopping problem in which distinctly ranked candidates are presented in an order given
by a random permutation. After each interview,
the interviewer knows only the candidate's relative rank among those already seen
and must either accept that candidate or reject the candidate permanently. The objective
is to maximize the probability of selecting the best
candidate.
Suppose the first
candidates are rejected and the first later candidate better than all of them is
accepted. The probability that this rule selects
the best candidate is
For large , writing
gives the approximation
. This is maximized at
, so the optimal rule asymptotically rejects the
first
candidates and then accepts the next record. Its limiting success probability
is also
(Freeman 1983, Ferguson 1989).
This use of "marriage problem" is distinct from Hall's marriage theorem, which concerns the existence of a matching, and from the stable marriage problem, which concerns stability under two sets of preference rankings.
The submodular secretary problem generalizes irrevocable random-order selection to accepting up to candidates whose joint value is a submodular
function, rather than selecting the single best-ranked candidate (Bateni et
al. 2013).