On a generalization of the secretary problem with uncertain selection

On a generalization of the secretary problem with uncertain selection

0.00 Avg rating0 Votes
Article ID: iaor2001730
Country: Japan
Volume: 43
Issue: 1
Start Page Number: 219
End Page Number: 243
Publication Date: Mar 2000
Journal: Journal of the Operations Research Society of Japan
Authors: ,
Keywords: programming: dynamic, programming: markov decision
Abstract:

The secretary problem with uncertain selection, considered by Smith, is generalized to allow for the rejection probability to be rank-dependent. That is, if an offer of employment is given to the j-th best applicant, she rejects it with probability qj, 1 ≤ jn (n is the number of applicants to appear). The optimality equations can be derived with the objective of maximizing the probability of selecting the best applicant. Since giving general guidelines of the optimal policy is difficult, we focus our attention on the simplified problem, called the m-problem, where the probability sequence {qj; 1 ≤ jn} satisfies qm+1 = qm = ... = qn, 0 ≤ m ≤ n − 1. The value m plays a role that regulates the difficulty of the problem (the 0-problem is the Smith problem). We solve the 1- and 2-problems explicitly in both the finite and the asymptotic cases. The optimal policy of the 1-problem is shown to be a threshold rule, i.e., it passes over some portion of the applicants and then makes an offer to relatively best applicants successively. As for the 2-problem, it can be shown that the optimal policy becomes a threshold rule if q2q3, while as n gets large there appears a time interval such that the optimal policy makes an offer alternately to relatively best applicants that appear on that interval if q2 < q3. We also present some numerical results for the 3-problem which demonstrate the complexity of the optimal policy. Our results give some affirmative evidence to the conjecture that the optimal policy remains a threshold rule so far as the sequence {qj; 1≤j≤n} satisfies the monotone condition q1q2≥ ··· ≥ qn, which reflects the real world in the sense that the better the applicant is, the most likely it seems that she refuses an offer with the larger probability.

Reviews

Required fields are marked *. Your email address will not be published.