# Maximum-Value Secretary Problem

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.
-
There were some results from Rothschild and coauthor in the economics literature in the 70s, but they assumed a known distribution. – Nameless Mar 4 '14 at 18:17

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.

-
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 '14 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 '14 at 22:40
@Briguy37 - it depends on whether you know the distribution in advance. – Henry Mar 4 '14 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 '14 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 '14 at 21:26

Let us first analyze the expected value of the candidate chosen by the same stratey, which maximizes the probability of hiring the best candidate. As you mentioned, the strategy is the following: Rejecting the first $n/e$ candidates and memorizing the best candidate $c^{relativeMax}$ amonst them. We then select the first candidate who is better than $c^{relativeMax}$.

Let's call the strategy we just described $S$, the sequence of candidates it receives $\sigma$ and $w_S(\sigma)$ defined as the weight or value of the candidate which strategy $S$ chooses when given $\sigma$. And let $c^*$ represent the best candidate.

Then, we can conclude $$E[w_S(\sigma)] = \sum_{c\in\sigma} P[\text{candidate c is selected}]\cdot w(c) \ge P[c^* \text{is selected}] \cdot w(c^*) \ge \frac{1}{e}\cdot w(c^*).$$

[On page 15, Corollary 2.2 of this thesis, you can see the proof: http://darwin.bth.rwth-aachen.de/opus3/volltexte/2014/5270/pdf/5270.pdf]

So, our the expected value of the chosen candidate of our strategy is at least $1/e$ of the best candidate.

The only point left to prove is, that there is no strategy, which can obtain a candidate with an expected value better than $1/e \cdot w(c^*)$. More formally, we have to show that:

$$\not\exists \text{ Strategy } S: \exists r < e: \forall \sigma: E[w_S(\sigma)]\geq \frac{1}{r}.$$

Once we have shown this, we know we cannot do better than $1/e \cdot w(c^*)$ for the expected payoff and our intial strategy also is not only a strategy for maximizing the probility of the best candiadate, but also a strategy for maximizing the expected value of the selected candidate.

This has also been proven in the thesis I mentioned above (Corollarly 2.4), but it contains a logical mistake assuming, that one instance for $\sigma$ is enough to proove this. For my bachelor thesis, I am working on this proof and once I have completed it, I will attach is to this post.

-