Secretary Problem - History

History

The secretary problem was apparently introduced in 1949 by Merrill M. Flood, who called it the fiancée problem in a lecture he gave that year. He referred to it several times during the 1950s, for example in a conference talk at Purdue on 9 May 1958, and it eventually became widely known in the folklore although nothing was published at the time. In 1958 he sent a letter to Leonard Gilman, with copies to a dozen friends including S. Karlin and J. Robbins, outlining a proof of the optimum strategy, with an appendix by R. Palermo who proved that all strategies are dominated by a strategy of the form "reject the first p unconditionally, then accept the next candidate". (See Flood (1958).)

The first publication was apparently by Martin Gardner in Scientific American, February 1960. He had heard about it from John H. Fox, Jr., and L. Gerald Marnie, who had independently come up with an equivalent problem in 1958; they called it the "game of Googol". Fox and Marnie did not know the optimum solution; Gardner asked for advice from Leo Moser, who (together with J. R. Pounder) provided a correct analysis for publication in the magazine. Soon afterwards, several mathematicians wrote to Gardner to tell him about the equivalent problem they had heard via the grapevine, all of which can most likely be traced to Flood's original work.

The 1/e-law is due to F. Thomas Bruss (1984)

A 1989 paper by T. S. Ferguson has an extensive bibliography, and points out that a similar (but different) problem had been considered by Arthur Cayley in 1875 and even by Johannes Kepler long before that.