I recently encountered the secretary problem and there are essentiall two problems:
- Maximizing the probability of choosing the best candidate. Gnedin proved in his paper https://projecteuclid.org/download/pdf_1/euclid.aop/1176988613 the following:
There exists no algorithm, which can choose the best candidate with probability better than $\frac{1}{e}$.
- Maximizing the expected value of the candidate. So, basically if we don't get the best candidate, we like to get at least a fairly good candidate, who is not too much worse than the best candidate.
Do you think the following statement will also hold true:
There exists no algorithm, which chooses a candidate whose value ("talent") is better than $\frac{1}{e} \cdot c^{best}$, where as $c^{best} = max\{c_1,...,c_n\}.$
I haven't found any proof for this statement yet. I wonder, whether it can be proved by using the statement for the first problem. If you have any papers or any ideas, which can help me, this would be great!