The Secretary Problem Site
  • Home
  • Classical Problem
  • Simulations
  • Backward Induction
  • Variants
  • Resources
  • Timeline
  • References
  • About
  • Español

Secretary Problem Research Timeline

Explore the history of the secretary problem and optimal stopping, from Sakaguchi and Lindley to classical results and modern research.

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

Journal arXiv
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

Journal arXiv
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

Journal arXiv
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

arXiv
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

arXiv

How the papers were selected

The historical timeline balances three criteria:

  1. foundational importance,
  2. sustained influence across later research,
  3. 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

© 2026 José Ángel Islas Anguiano

Secretary problems and optimal stopping

Facultad de Ciencias Naturales y Exactas (FACINE), Universidad Autónoma de Sinaloa (UAS)