[pavpanchekha]

This is not true. To maximize the expected rank, reject the first sqrt(n) candidates, and then pick the next one better than that group. Once you have more than 7 candidates, this means that for maximizing expected rank, you want to reject fewer candidates than if you maximize probability of choosing the best.

[mgraczyk]

Can you link me to a proof? I recall working this out and finding that the solutions were the same whether you were maximizing rank or maximize P(best)

[spacehome]

It's pretty easy to see for yourself that the two metrics can't simultaneously be maximized.

Imagine a situation where you've already passed by all of the candidates except for the last two. You meet the second-to-last candidate, and she's at the 99.99% percentile, but there was one single previous candidate that was ranked higher. What do you do?

If you want to maximize the expected value of the rank, you have to pick her, because the odds that the last candidate is better is vanishingly small. If you want to maximize the chance that you pick the maximum rank, you have to pass, because the chance that the second-to-last candidate is the best is zero (since you've already seen one who's better).

[pavpanchekha]

Does http://en.wikipedia.org/wiki/Secretary_problem#Cardinal_payo... work? They have a sketch derivation.

[dbdr]

This is under this hypothesis: "the interviewer does not learn the actual relative rank of each applicant. He learns only whether the applicant has relative rank 1." I think this is rarely a reasonable hypothesis. Kepler certainly could tell how much he liked each woman, not just whether she was the best so far or not.

Under the (reasonable) hypothesis that you get some information about the relative value of each candidate, I believe spacehome is correct and the optimal strategies ARE different.

[mgraczyk]

Thanks! Looks like I worked it out wrong. Intuitively it makes sense that the results would be different.