Hacker News Reader

Comment by eterm | Hacker News Reader

It's known to wikipedia as the "Secretary Problem":

https://en.wikipedia.org/wiki/Secretary_problem

The optimum is actually based on 1/e rather than 1/3 but 1/3 is a good enough practical approximation.

In the secretary problem, you're trying to maximize the probability of selecting the absolutely best candidate. In other words you assume that you “win” if you select the best candidate and “lose” otherwise (even if you end up picking the second best who is almost as good!), and you're trying to maximize the probability of winning. (The optimal solution says you can win with probability 1/e ≈ 37%, meaning that ≈63% of the time you lose!)

This has always seemed the most unsatisfying assumption in the problem to me, with application to no real-life case that I can think of. The Wikipedia article has some stuff on relaxing this assumption, in its section titled “Cardinal payoff variant” (it seems that the optimal at least under one set of assumptions is √n rather than n/e, though those assumptions also seem unrealistic): https://en.wikipedia.org/w/index.php?title=Secretary_problem...

I would add that (having simulated this problem in code myself), the reason you have bad outcomes is that you run out of candidates and take a bad one because you have no choice. In real life, at some point you would grab a decent candidate even if s/he were not as good as a prior passed candidate. It is also true that even under the original assumptions, there is a wide range of thresholds around 1/e that yield a similar outcome.

I think most people learning CS101 will at some point attempt to merge-sort a stack of physical papers alphabetically, and give up half way through. Everyone should have this experience: it teaches a lot about the importance of assumptions about the problem. Not to say that the math isn't important, but you have to think critically, because spherical cows are pretty rare.

It also assumes that the sequence is random and that there is no a priori information about the quality of the candidates.

A similar problem occurs in dating today, when people tend to dismiss the current option in the hope or expectation of finding someone better later, intuitively treating it as a secretary problem. But too many people fail to take full advantage of the knowledge they have of themselves and the type of partner they can attract, of the dating market and of the world in general, and end up bitter and disappointed and victims of their own poor choices.

Reply on news.ycombinator.com