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?
- You have n secretaries.
- 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).
- The value-distribution of secretaries is unknown.
- You must accept or reject each secretary immediately following their interview with no recalls.
- You must maximize the expected value of the secretary you hire.
Best Answer
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.