ON A GENERALIZATION OF THE SECRETARY PROBLEM WITH UNCERTAIN SELECTION

スポンサーリンク

概要

• 論文の詳細を見る

• 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 q_j, 1 <__- j <__- n (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 {q_j; 1 <__- j <__- n} satisfies q_<m+1> = q_<m+2> = ・・・ = q_n, 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 q_2 >__- q_3, 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 q_2 < q_3. We also present some numerical results for the 3-problem which demonstrate the complexity of the optimal policy. Our results give some affirmative evidences to the conjecture that the optimal policy remains a threshold rule so far as the sequence {q_j; 1 <__- j <__- n} satisfies the monotone condition q_1 >__- q_2 >__- ・・・ >__- q_n, 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.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Ohno Katsuhisa

  Nagoya Institute of Technology

• Ohno K

  Nagoya Institute Of Technology

• Tamaki Mitsushi

  Aichi University

関連論文

• STOCHASTIC PROPERTIES OF FORK/JOIN MULTI-STAGE PRODUCTION SYSTEMS WITH GENERAL BLOCKING
• AN INTEGRATED ANALYTICAL/SIMULATION APPROACH FOR ECONOMIC DESIGN OF AN AGV SYSTEM
• 3B3 Complexity of a dynamic lot-scheduling problem formulated by a 0-1 pure integer programming(Technical session 3B : Combinatorics 2)
• ON A GENERALIZATION OF THE SECRETARY PROBLEM WITH UNCERTAIN SELECTION
• ANALYSIS AND OPTIMIZATION OF A U-SHAPED PRODUCTION LINE
• A Continuous Time Duration Problem With an Unknown Number of Options
• SOME RESULTS ON A BAYESIAN SEQUENTIAL SCHEDULING ON TWO IDENTICAL PARALLEL PROCESSORS
• A SECRETARY PROBLEM WITH UNCERTAIN EMPLOYMENT WHEN THE NUMBER OF OFFERS IS RESTRICTED

スポンサーリンク