Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Background:
The classic secretary problem has the simple solution of rejecting the first 1/e applicants and then selecting anyone who was better than the best in the rejected set. However, in the real world secretaries are not of value 0 if they are not the best, and so choosing the 2nd best is normally far better than choosing the worst. Also, if you stick to the classical approach, there's a 1/e chance that you will receive a random secretary from the set that excludes the best secretary.

Real-World Example:
Say that you've interviewed 98 out of 100 secretaries and have not found any better than secretary #32. You then interview the 99th secretary and find that she is second only to #32.

Analysis:
Under the classical problem, you'd reject #99 as they have a value of 0 (not the best). Thus, you'd take a random secretary in favor of the 98th or 99th best, depending on whether the last secretary is the best or not.

However, the classical solution would not be the best decision in nearly all real-world cases, as you are taking a random applicant instead of one better than at least 97/99 others.

Question:
What is the proper stopping strategy to maximize the expected-value of the secretary you hire?

  1. You have n secretaries.
  2. Each secretary has a linear value assigned after each interview (a secretary ranked 4 is assumed to be twice as valuable as one ranked 2).
  3. The value-distribution of secretaries is unknown.
  4. You must accept or reject each secretary immediately following their interview with no recalls.
  5. You must maximize the expected value of the secretary you hire.
share|improve this question
    
There were some results from Rothschild and coauthor in the economics literature in the 70s, but they assumed a known distribution. –  Nameless Mar 4 at 18:17
add comment

1 Answer 1

http://www.sie.arizona.edu/MURI/papers/pdfs/thrust%20A/Bearden%20Skip%20the%20Sq%20Rt%20of%20n%20Thrusts%20A%20and%20C.pdf

This might be fun for you to look at.

share|improve this answer
    
Thanks for the link. I found that as well when I was searching for how this problem would be handled. In their problem, they assume a uniform value distribution, which is a specific case for the general problem I mentioned. I'm still hoping for a general approach where you can maximize the expected-value for any distribution. –  Briguy37 Mar 3 at 22:33
    
Okay, well this was my quick answer. Maybe I'll take some more time to think about your post while I am not at work. –  Jonathan Aronson Mar 3 at 22:40
    
@Briguy37 - it depends on whether you know the distribution in advance. –  Henry Mar 4 at 7:55
    
@Henry: Please assume for this question that you do not know the value-distribution of secretaries. I've added this to the question. –  Briguy37 Mar 4 at 15:06
    
@Briguy37: That may make it difficult. One approach could be to maximise the expected ranking of the individual selected –  Henry Mar 4 at 21:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.