Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-30T15:09:06.491Z Has data issue: false hasContentIssue false
  • English
  • Français

APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM

Published online by Cambridge University Press:  31 March 2011

Chris Dietz ,
Dinard van der Laan  and
Ad Ridder
Chris Dietz
Affiliation:
Vrije University Amsterdam, The Netherlands E-mail: [email protected]; [email protected]; [email protected]
Dinard van der Laan
Affiliation:
Vrije University Amsterdam, The Netherlands E-mail: [email protected]; [email protected]; [email protected]
Ad Ridder
Affiliation:
Vrije University Amsterdam, The Netherlands E-mail: [email protected]; [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A version of the classical secretary problem is studied, in which one is interested in selecting one of the b best out of a group of n differently ranked persons who are presented one by one in a random order. It is assumed that b ≥ 1 is a preassigned number. It is known, already for a long time, that for the optimal policy, one needs to compute b position thresholds (for instance, via backward induction). In this article we study approximate policies that use just a single or a double position threshold, albeit in conjunction with a level rank. We give exact and asymptotic (as n → ∞) results, which show that the double-level policy is an extremely accurate approximation.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 25 , Issue 2 , April 2011 , pp. 157 - 169
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Dynkin, E.B. & Yushkevich, A. (1969). Markov processes: Theorems and problems. New York: Plenum Press.CrossRefGoogle Scholar
2.Ferguson, T.S. (1989). Who solved the secretary problem? Statistical Science 4: 282–296.Google Scholar
3.Frank, A.Q. & Samuels, S.M. (1980). On an optimal stopping problem of Gusein-Zade. Stochastic Processes and Their Applications 10: 299–311.Google Scholar
4.Gilbert, J.P. & Mosteller, F. (1966). Recognizing the maximum of a sequence. Journal of the American Statistical Association 61: 35–73.Google Scholar
5.Gusein-Zade, S.M. (1966). The problem of choice and the optimal stopping rule for a sequence of indpendent trials. Theory of Probability and Its Applications 11: 472–476.Google Scholar
6.Quine, M.P. & Law, J.S. (1996). Exact results for a secretary problem. Journal of Applied Probability 33: 630–639.Google Scholar