Optimal choice of the best available applicant in full-information models.

*(English)*Zbl 1192.60067The paper deals with a full-information best-choice problem with uncertain employment [see M. Tamaki, Oper. Res. 39, No. 2, 274–284 (1991; Zbl 0741.90090)] for the related models in no information best choice problem when the aim is to maximize the probability of the required selection. Two models are distinguished according to when the availability is checked.

Two models of the availability checking are considered: before (Model 1) or after (Model 2) an offer is made. For Model 1, the explicit expressions for the optimal stopping rule and the optimal probability for a given \(n\) are obtained. In this model, when \(n\rightarrow \infty \), the optimal probability becomes insensitive to the chance of availability and approaches \(0.580 164\). It is shown that the Planar Poisson Process (PPP) model provides more insight into this phenomenon. For Model 2, the author’s opinion is that by strong dependence of the hole history of the process in a complicated way the optimal stopping rule is impossible to get in closed form. A lower bound on the asymptotically optimal probability has been obtained via the PPP approach.

Similar difficulties appear in the two population secretary problem with classification before or after selection. The details can be found in the papers by M. Sakaguchi [Math. Jap. 35, No. 5, 917–934 (1990; Zbl 0709.62074); and ibid., No. 6, 1077–1088 (1990; Zbl 0735.62077)].

Two models of the availability checking are considered: before (Model 1) or after (Model 2) an offer is made. For Model 1, the explicit expressions for the optimal stopping rule and the optimal probability for a given \(n\) are obtained. In this model, when \(n\rightarrow \infty \), the optimal probability becomes insensitive to the chance of availability and approaches \(0.580 164\). It is shown that the Planar Poisson Process (PPP) model provides more insight into this phenomenon. For Model 2, the author’s opinion is that by strong dependence of the hole history of the process in a complicated way the optimal stopping rule is impossible to get in closed form. A lower bound on the asymptotically optimal probability has been obtained via the PPP approach.

Similar difficulties appear in the two population secretary problem with classification before or after selection. The details can be found in the papers by M. Sakaguchi [Math. Jap. 35, No. 5, 917–934 (1990; Zbl 0709.62074); and ibid., No. 6, 1077–1088 (1990; Zbl 0735.62077)].

Reviewer: Krzysztof Szajowski (Wrocław)

##### MSC:

60G40 | Stopping times; optimal stopping problems; gambling theory |

62L15 | Optimal stopping in statistics |

60F05 | Central limit and other weak theorems |

90B80 | Discrete location and assignment |

90C39 | Dynamic programming |

90C40 | Markov and semi-Markov decision processes |

60G44 | Martingales with continuous parameter |

##### Keywords:

best-choice problem; secretary problem; optimal stopping; planar Poisson process; insensitivity; full-history dependence; Robbins’ problem
PDF
BibTeX
XML
Cite

\textit{M. Tamaki}, J. Appl. Probab. 46, No. 4, 1086--1099 (2009; Zbl 1192.60067)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Berezovskiĭ, B. A. and Gnedin, A. V. (1984). The Problem of Optimal Choice . Nauka, Moscow (in Russian). |

[2] | Bruss, F. T. (2005). What is known about Robbins’ problem? J. Appl. Prob. 42 , 108–120. · Zbl 1081.62059 |

[3] | Bruss, F. T. and Rogers, L. C. G. (1991). Embedding optimal selection problems in a Poisson process. Stoch. Process. Appl. 38 , 267–278. · Zbl 0745.60040 |

[4] | Bruss, F. T. and Swan, Y. C. (2009). A continuous-time approach to Robbins’ problem of minimizing the expected rank. J. Appl. Prob. 46 , 1–18. · Zbl 1200.62093 |

[5] | Das, S. and Tsitsiklis, J. N. (2009). When is it important to know you’ve been rejected? A search problem with probabilistic appearance of offers. To appear in J. Econom. Behavior Organization. |

[6] | Gilbert, J. P. and Mosteller, F. (1966). Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61 , 35–73. JSTOR: |

[7] | Gnedin, A. V. (1996). On the full information best-choice problem. J. Appl. Prob. 33 , 678–687. JSTOR: · Zbl 0871.60038 |

[8] | Gnedin, A. V. (2004). Best choice from the planar Poisson process. Stoch. Process. Appl. 111 , 317–354. · Zbl 1076.60043 |

[9] | Petruccelli, J. D. (1982). Full-information best-choice problems with recall of observations and uncertainty of selection depending on the observation. Adv. Appl. Prob. 14 , 340–358. JSTOR: · Zbl 0486.60038 |

[10] | Porosinski, Z. (1987). The full-information best choice problem with a random number of observations. Stoch. Process. Appl. 24 , 293–307. · Zbl 0623.60059 |

[11] | Sakaguchi, M. (1973). A note on the dowry problem. Rep. Statist. Appl. Res. Un. Japan. Sci. Engrs. 20 , 11–17. · Zbl 0286.60023 |

[12] | Samuels, S. M. (1982). Exact solutions for the full information best choice problem. Mimeo Ser. 82–17, Department of Statistics, Purdue University. |

[13] | Samuels, S. M. (1991). Secretary problems. In Handbook of Sequential Analysis , eds B. K. Gosh and P. K. Sen, Marcel Dekker, New York, pp. 381–405. |

[14] | Samuels, S. M. (2004). Why do these quite different best-choice problems have the same solutions? Adv. Appl. Prob. 36 , 398–416. · Zbl 1071.60028 |

[15] | Smith, M. H. (1975). A secretary problem with uncertain employment. J. Appl. Prob. 12 , 620–624. JSTOR: · Zbl 0313.60033 |

[16] | Tamaki, M. (1991). A secretary problem with uncertain employment and best choice of available candidates. Operat. Res. 39 , 274–284. · Zbl 0741.90090 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.