A History of the Secretary Problem
From dynamic programming and the (1/e) rule to strategic and algorithmic variants.
This curated timeline highlights foundational, influential, and especially relevant contributions. It is not intended as an exhaustive bibliography or an exact citation ranking.
More than sixty years of optimal stopping
The secretary problem developed from a recreational question into a major model in optimal stopping, applied probability, decision theory, economics, and online algorithms.
In Who Solved the Secretary Problem? (1989), Thomas S. Ferguson separates the problem’s early circulation from its publication and mathematical solution. Merrill Flood had discussed a version by 1950; Martin Gardner brought the problem to a wide audience in his February 1960 Scientific American column, drawing on a formulation attributed to John H. Fox Jr. and L. Gerald Marnie. Ferguson identifies D. V. Lindley’s 1961 paper as the first solution in a scientific journal. Gardner’s popularization and Lindley’s mathematical treatment are therefore distinct milestones in the history of the classical secretary problem.
1960
First printed appearance
The game of googol reaches a wide audience
Martin Gardner
Gardner's February Scientific American column introduced
readers to a best-choice puzzle attributed to John H. Fox Jr. and
L. Gerald Marnie. Ferguson (1989) identifies it as the first
generally recognized printed appearance of the secretary problem;
the question had circulated among mathematicians earlier.
Mathematical Games: A Fifth Collection of Brain-Teasers
View publication
March 1961
Foundation
The first scientific-journal solution
D. V. Lindley
Lindley solved the classical best-choice problem by dynamic
programming and backward induction, in the first scientific-journal
solution identified by Ferguson (1989).
Dynamic Programming and Decision Theory
View publication
June 1961
Early optimal stopping
Sequential selection by dynamic programming
Minoru Sakaguchi
Sakaguchi studied dynamic-programming approaches to sequential sampling,
including stopping with observation costs and other selection settings.
This is a separate early contribution, not the first solution of the
classical secretary problem.
Dynamic Programming of Some Sequential Sampling Design
View publication
1964
Classical model
The relative-rank formulation
Y. S. Chow, S. Moriguti, H. Robbins and S. M. Samuels
A rigorous analysis of optimal selection when only the relative
ranks of the observations are available.
Optimum Selection Based on Relative Rank (the Secretary Problem)
View publication
1966
Landmark
The definitive foundational paper
John P. Gilbert and Frederick Mosteller
This highly influential work unified several best-choice models,
including the classical no-information problem and the
full-information problem.
Recognizing the Maximum of a Sequence
View publication
1979
Multiple choice
Beyond selecting only the maximum
Mitsushi Tamaki
Tamaki studied a multiple-choice objective involving recognition
of both the maximum and the second maximum.
Recognizing Both the Maximum and the Second Maximum of a Sequence
View publication
1983
Survey
The first major synthesis
P. R. Freeman
Freeman organized the rapidly expanding literature and reviewed
the classical problem together with its principal extensions.
The Secretary Problem and Its Extensions: A Review
View publication
1984
Generalization
A unified approach and the 1/e law
F. Thomas Bruss
Bruss developed a unified continuous-time approach for
best-choice problems in which the number of available options
may be unknown.
A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options
View publication
1989
History
Who solved the secretary problem?
Thomas S. Ferguson
Ferguson reconstructed the problem’s complicated origins,
distinguishing its unpublished history, recreational appearances,
and formal mathematical solutions.
Who Solved the Secretary Problem?
View publication
2000
Landmark
The odds theorem
F. Thomas Bruss
The odds theorem gives an elegant rule for maximizing the
probability of stopping on the last success in a sequence of
independent Bernoulli trials.
Sum the Odds to One and Stop
View publication
2005
Algorithms
The algorithmic secretary problem
Robert Kleinberg
The multiple-choice secretary problem connected classical
optimal stopping with online algorithms, approximation guarantees,
and online auctions.
A Multiple-Choice Secretary Problem with Applications to Online Auctions
View publication
2012
Applicant strategy
The applicant’s point of view
Darren B. Glass
Instead of asking when the employer should stop, Glass asks
which interview position an applicant should choose to maximize
the probability of being hired.
The Secretary Problem from the Applicant’s Point of View
View publication
RESEARCH BY THE SITE AUTHOR
Contributions by José A. Islas
These papers develop secretary-type and optimal-stopping problems
involving non-identically distributed observations, approximate
selection, random walks, and strategic interview positioning.
2016
Peer reviewed
A Sharp Lower Bound for Choosing the Maximum of an Independent Sequence
Pieter C. Allaart and José A. Islas
Establishes a sharp distribution-free lower bound for selecting
the maximum from independent observations with possibly different
continuous distributions.
Journal of Applied Probability, 53(4), 1041–1051
2018
Peer reviewed
A Sharp Bound for Winning Within a Proportion of the Maximum of a Sequence
José A. Islas
Studies the problem of stopping at an observation whose value is
at least a fixed proportion of the overall maximum and derives a
sharp lower bound for the optimal success probability.
Boletín de la Sociedad Matemática Mexicana, 25, 737–746
2024
Peer reviewed
Oscillation Criteria for Stopping Near the Top of a Random Walk
José A. Islas
Investigates optimal stopping at one of the two highest values of
a finite Bernoulli random walk and establishes new properties and
bounds for the associated critical constants.
Boletín de la Sociedad Matemática Mexicana, 30, article 43
2026
Preprint
Strategic Interview Positioning under Uncertain Self-Rank
José A. Islas
Introduces a truncated geometric prior for an applicant’s unknown
absolute rank and identifies an explicit phase transition between
the first eligible and final interview positions.
arXiv preprint
2026
Preprint
Convergence of the Critical Probabilities for Stopping Near the Top of a Random Walk
José Ángel Islas
Resolves Allaart's conjecture for a semi-best stopping problem
on a Bernoulli random walk: the critical probabilities converge
to 1/2 as the horizon tends to infinity.
arXiv:2610.26670, submitted 19 October 2026
How the papers were selected
The historical timeline balances three criteria:
- foundational importance,
- sustained influence across later research,
- relevance to the topics developed on this site.
The author section is presented separately to distinguish the creator’s research contributions from the historical selection. For bibliographic details of the works cited across the site, see the References page.
Leer en español