The secretary problem is the standard example of an optimal stopping problem with partial information. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game and the best choice problem. It is studied in applied probability, statistics and decision theory. Its solution is often called the 37% rule: a simple rule picks the single best of applicants with probability about , whether there are 100 or 100 million applicants (Wikipedia: Secretary problem). The problem is a standard example of the exploration–exploitation dilemma.
Timeline (as recounted in the Wikipedia article's History section, following Ferguson 1989):
There is a single position and there are applicants, where is known. If seen together, the applicants can be ranked from best to worst with no ties. They are interviewed one at a time in a uniformly random order: each of the orders is equally likely. Right after each interview the applicant is either accepted, which ends the process, or rejected for good. The decision may depend only on the relative ranks of the applicants interviewed so far. The objective is to maximize the probability of selecting the best applicant of the whole group.
An order is a permutation of . The applicant interviewed at time has quality , where larger means better. The relative rank of the applicant interviewed at time is the number of applicants interviewed before time who are worse than them. A stopping rule maps the list of relative ranks observed so far to "accept" or "reject". Its success probability is the fraction of the orders on which the applicant accepted by is the overall best. A rule that never accepts anyone fails. The optimal success probability is
A candidate is an applicant who is better than every applicant interviewed before them. The cutoff rule with cutoff rejects the first applicants and then accepts the first candidate after that point.
The result. The 37% rule is the classical result of optimal stopping. It shows that a fixed fraction of the best possible success probability survives as the number of options grows without bound, and that a simple threshold policy achieves it. The structure of its solution has three parts: optimal rules may be taken to be threshold rules, there is an exact formula in terms of the records of a uniformly random permutation, and a limit turns a harmonic sum into an integral. This structure recurs throughout the best-choice literature, including the prophet-secretary and multi-choice secretary problems.
Formalizing it. The result has been proved since the late 1950s and early 1960s. The remaining work is to formalize the known proof: a model of rank-based stopping rules over uniformly random permutations, the exact success probability of cutoff rules, the optimality of cutoff rules among all rank-based rules, and the asymptotics.
The success probability of a fixed cutoff rule and the calculus limit are elementary. The central step is the optimality of cutoff rules (Milestone 3). A stopping rule may depend arbitrarily on the whole history of relative ranks, and one has to show that no such rule beats the best cutoff rule. Evaluating cutoff rules alone does not prove the goal, because is a supremum over all rank-based rules. A second, smaller difficulty is that the limit statements need control of the harmonic sums along a varying cutoff , not only along a fixed ratio.
Equiv.Perm (Fin n) with uniform weights. successProb n s is the ratio (number of winning permutations) / in .List ℕ → Bool, applied to the list of relative ranks observed so far. Through the length of the list it also knows the current time. It never sees absolute qualities. Randomized rules are not modelled. A randomized rule is a mixture of deterministic ones, so it cannot do better.optimalProb n is the real supremum of successProb n s over all such rules. The values lie in , so the supremum is the usual least upper bound.Fin n). Cutoffs are 1-based, as in the article: cutoffRule r accepts at time exactly when and the current applicant is a candidate.Real.exp (-1).All declarations live in the namespace ClassicalSecretary. Reusable contributions are welcome, in particular facts about records of uniformly random permutations (independence of relative ranks, the probability that position is a record) and a backward-induction principle for finite-horizon stopping problems.
namespace ClassicalSecretary
theorem tendsto_optimalProb :
Tendsto optimalProb atTop (𝓝 (Real.exp (-1))) := by sorry
end ClassicalSecretary
Let be the largest probability, over all stopping rules that use only the relative ranks of the applicants seen so far, of selecting the best of applicants interviewed in a uniformly random order. Then
This is the classical solution of the secretary problem: as the number of applicants grows, the best achievable chance of picking the single best one converges to .
No open leaves. Every sub-goal is proved or awaiting decomposition.