Hacker News Reader

Comment by mdesq | Hacker News Reader

... the best way to proceed is to interview (or date) the first 36.8 percent of the candidates. Don't hire (or marry) any of them, but as soon as you meet a candidate who's better than the best of that first group — that's the one you choose! Yes, the Very Best Candidate might show up in that first 36.8 percent — in which case you'll be stuck with second best, but still, if you like favorable odds, this is the best way to go.

Maybe I haven't had enough coffee this morning. Can someone explain how you would get second best in this case? Wouldn't you never meet a candidate better than the best of that first group and exhaust the rest of the candidates?

View on HN

It's good that they finally mentioned it at the end - this is a flavor of the optimal stopping problem (http://en.wikipedia.org/wiki/Optimal_stopping). This is a cute application of that strategy, the problem is that mathematics has very little to do with actual relationships, as much so as the assumptions game theory makes about actual relationships (http://crookedtimber.org/2005/10/13/whats-wrong-with-game-th...). Whats more important than trying to play your luck in a relationship is: working through the grit of an actual relationship.

In reality - if you don't put in the actual work any single relationship takes, then none of them will work out, it doesn't matter how large your "sample size" is.

The article blithely describes the "best" strategy, without defining "best." I believe the strategy is only best in the sense of giving the highest probability of ending up with the best candidate--so the second best candidate is considered as bad as the worst.

It also actually maximizes the expected rank of the chosen candidate.

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.

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)

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).

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

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.

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

Imagine you had 11 candidates like he described, and you interviewed them in random orders. For ease, we will describe them by number, which will also equate to their "goodness" by arbitrary criteria (known to the interviewer only).

One of the worst possible cases would be that you interview them like:

1 2 3 4 5 6 7 8 9 10 11

In this case, you would see them decreasing in "goodness" without ever increasing. You would get to 11 and be stuck with the crappiest whatever possible.

In the average version though, you might get something like:

7 3 4 6 5 8 11 1 10 9 2

Using their strategy, you would check the first 4 candidates (7 3 4 6) and then you would stop when you hit better than max(7 3 4 6) = (3), which in this case would equate to finding (1) at the 8th position.

You are correct that if the best is in the first block it screws everything up. In the specific version you mention, a possible arrangement that triggers could be:

3 9 8 1 5 10 2 6 4 7 11

You would interview the first set with a best of (1). All the rest would then not compare, and you would get (11).

(FYI, the scale used in parent's is 1 is best, 11 is worst. Confused me for a bit.)

[Edit - Ignore me. I guess you can't recall rejected candidates.] In your final example though, because you had now interviewed all the candidates, you could go back and offer jobs to the best candidates. The point of interviewing four and then interviewing until you find a better one is that it should keep you from wasting time interviewing the whole list. If you end up doing that anyway, you know who the best was and can hire them.

Yeah, 36% chance of getting nothing isn't great. I'd expect that for the last third, you might want to settle for someone who is a bit worse than the best of the test group.

This algorithm is only good if you'd rather have nothing than second best.

Yes, that appears to be a mistake. In the 36.8% of cases where the best candidate shows up in that first 36.8%, it would seem the algorithm must keep running until it is forced to select the final candidate, which is essentially a random choice out of all but the very best (assuming ordering has no relation to goodness) -- very different from being "stuck with the second best." However, the rest of the quote -- "but still, if you like favorable odds, this is the best way to go." -- might very well be true.

Presumably the optimal strategy would be to gradually lower your standards the further you go. It's easily proven that the optimal strategy for the second-to-last candidate is to select the candidate if the candidate is above average. So the algorithm as described in the article seems to be missing something.

I think I've got it.

The main thing here to notice is that this is a strategy and not a solution.

If the best options is in the first 1/e * n of group elements of the group you will end up with the last interviewee as the one to choose.

But if you use this strategy many times over max permutations of the group it WILL give you the best output in general.

btw i would like to thank the author for posting this.

No, you're right. You will be stuck with the last one, not the second-best one.

Presuming 'serial dating'. You can actually know several people at once, and get more serious with one once you've evaluated the pool.

That's concurrent, not serial

The parent to your post could be rephrased as:

> That presumes 'serial dating,' but you can actually know several people at once, and get more serious with one once you've evaluated the pool.

I think that's what they were trying to say

It's flat out wrong. You'd end up with the last candidate, not the second best, as you say.

Similarly, isn't there like a 10% chance you're stuck with the 3rd best candidate? Is that still good enough?

The point is, he will not end up even with second best if the best candidate is in the first group. Rather he will end up with the last candidate hitting a dead end just like the example. That's because no one in the second group is better than the best in first group.

Yeah I misread that. That's true, but my point still stands as well. It sounds like using this strategy as it is written yields increasingly poor results as the sample size increases (assuming a total ordering)

Yes, increasingly poor, but converging on 1/e. http://en.wikipedia.org/wiki/Secretary_problem#Deriving_the_...

Reply on news.ycombinator.com