A contribution to the study of Robbins’ problem
Yvik C. Swan · Open Repository and Bibliography (University of Liège) · 2011
The classical secretary problemsAlthough it would be fruitless to recall all the existing versions of the above problem, it is necessary to inscribe our problem within its context, i.e. that of the the four classical secretary problems.Of these, the first three were solved successively by Lindley (1961), Chow, Moriguti, Robbins and Samuels (1964), and Gilbert and Mosteller (1966).The fourth problem, Robbins' problem, remains to this date unsolved. The no-information best-choice problemConsider a situation where an employer has advertised an opening for a secretary.There are a known number, n, of applicants, and the employer interviews them one at a time.He is very specific about the qualities that are needed for the job so that, after each interview, he can rank the present applicant with respect to all previous applicants with no ties.The applicant 1 Ferguson (1984).n→∞ w n ≈ 0.580164... Hence we see that there is an improvement of roughly 58% from the noinformation to the full-information problem. The no-information expected rank problemWe consider the same situation as in the classical secretary problem, in which an employer interviews n candidates for a job under the restriction that, at each interview, the only information he can work on is the relative A heuristic argument given in Lindley (1961) indicated that, by approximating these recurrence relations by a differential equation, the optimal expected rank should approach a finite limit as n goes to infinity.Chow et al. (1964) were able to make this rigorous and obtained then the limiting form of the expected rank under the optimal policy.For this they showed that the minimum expected rank for the n arrival problem is a strictly in-3 This appellation is due to Lindley (1961).n→∞ E[nX τn ] = 2.In the sequel, we will often refer to this problem, and to the optimal rule τn . Acknowledgments and outline of the mémoireThe following work is the outcome of our efforts on the full-information expected rank problem.The original research which is recalled in the next few pages was conducted in close collaboration with Professor F. T.