Secretary Problem

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

by tosh • 9 years ago

145 62 9 years ago

en.wikipedia.org

mrguyorama• 9 years ago

Interestingly, it seems this has been discussed here before: http://www.thelowlyprogrammer.com/2010/04/introducing-marria...

capocannoniere• 9 years ago

I like this explanation of the Secretary problem (aka optimal stopping problem) by @lpolovets [1]

The basic problem is this: there are N applicants for a secretarial position. The applicants are interviewed in random order, and you must accept or reject a candidate immediately after interviewing them. After you reject someone, there's no way to bring them back. There is only one position available, so as soon as you accept a candidate you are done. What strategy should you pursue in order to maximize the likelihood of hiring the best candidate out of the N applicants?
It turns out that the best strategy is to look at the first N/e applicants (i.e. the first ~37%), reject all of them, then accept the first applicant that is better than all of the initial rejects. It turns out this strategy has a ~37% (1/e) chance of picking the best candidate, regardless of how large N is. This is counterintuitive. It means that even if you have one billion applicants in some random order, you will find the very best one ~37% of the time with this strategy, even though you will (on average) make your choice without meeting the last few hundred million candidates.
I think this has some interesting practical implications. For example, as a VC, one possible strategy that I can pursue is to look for interesting sectors (3D printing, drones, bitcoin, etc.) and try to invest in the very best startup in each of those sectors. The Secretary Problem is a decent approximation of this. I can go on AngelList and see that there are thirty 3D printing startups in LA/NYC/SF, which are the markets I'm interested in. One way to pick the best one of these 30 would be to meet 11 of these startups, pass on all of them, then invest in the next 3D printing startup I meet that's better than all of those. Of course, this would be a jerk move. I'd be wasting the time of a lot of founders if I knew I was planning to pass on their startups no matter what. However, if I happened to pass on a dozen 3D printing startups by chance, and I knew that there were ~30 in total, then if the 14th one was better than the first dozen, I would know there was a pretty good chance it was the best one out of all 30 even though I had yet to see the last 16.

[1] https://www.quora.com/Mathematics/What-are-the-most-interest...

happyopossum• 9 years ago

The secretary problem and investing have one important difference that throws this all out the window - you can meet with multiple startups without rejecting them, and make a decision when you've met them all (or all the ones you want to meet). There's no requirement in the real world to accept/reject immediately post-interview without any possibility of recall.

Of course, this would be a jerk move. I'd be wasting the time of a lot of founders if I knew I was planning to pass on their startups no matter what.

On a macro-level, this isn't a jerk move at all - the other way would have you 'waste' the time of 29 founders instead of 11.

dsr_• 9 years ago

No, the biggest problem is that nobody is perfect at ranking startups, period. And as proven by that "antiportfolio" page of a day or two ago, even generally successful VCs can't do that reliably.

posterboy• 9 years ago

and then theres a 37% chance the best was among the rejects and the algorithm fails.

thefalcon2• 9 years ago

And there's a 26% chance that you'll never even interview the best because you hired someone before you ever saw them. But it's still an optimal solution to the problem, given the constraints.

indubitable• 9 years ago

Incredibly interesting, but I can't resist nitpicking!

The with extrapolating this to real life would be that it's making assumptions that are not realistic. For instance it assumes infinite granularity in candidates. In other words the rating of a candidate can be from 0 to infinity instead of the granularity we really see things in which is going to be closer to 0-4 or very bad/bad/neutral/good/very good.

It also assumes a normal distribution. Something that's perfectly reasonable for an unknown distribution, but in my experience the number of 'very good' candidates tends to be much larger than its equal but opposite 'very bad' end perhaps due to some sort of survivorship bias.

scardine• 9 years ago

I started listening to the audio book version of "Algorithms to Live By: The Computer Science of Human Decisions"[1] by Brian Christian and Tom Griffiths. It starts by talking about the Secretary Problem and the 37% rule and it is very entertaining how much of our daily problems are some variation of a small set of well known problems that have interesting (and often counter-intuitive) mathematically proofed solutions.

Before I get downvoted to hell, let me say THIS IS NOT AN AFFILIATE LINK, I will earn nothing if you click it (I hate spam as much as the next guy but people here tend to be a little trigger happy).

[1] https://www.audible.com/pd/Business/Algorithms-to-Live-By-Au...

dang• 9 years ago

A previous thread: https://news.ycombinator.com/item?id=7337759.

gumby2• 9 years ago

I've always liked this problem mathematically but I'd never used it for actual hiring (though I have happily used it for certain statistical sampling).

When actually hiring, I care about the time value of opportunity cost. That is, we interview and get hire the first candidate that we feel can do the job well and we all otherwise like, then the benefit of having her on the job ASAP exceeds any possibly value from another candidate that might show up some uncertain time later.

kyleschiller• 9 years ago

When actually hiring, you also have benchmarks that aren't purely relative, and past experience to fall back on.

gumby2• 9 years ago

When actually hiring, you also have benchmarks that aren't purely relative, and past experience to fall back on.

(This problem is framed as hiring the best which I assume means closest to optimal weights on those non-relative benchmarks -- whatever "optimal" means.)

But your comment is interesting, as this problem was originally as "the wife problem": how do "you" -- presuming incorrectly even at the time all mathematicians to be male -- find the optimal wife.

The thing that made your comment funny to me is that in majority of marriage cases (by anyone to anyone) neither party has much, or any past experience to fall back on!

pianowow• 9 years ago

Several mobile strategy games like Clash of Clans present this problem when raiding. You can skip to the next base or raid the current base.

Numberphile did a nice presentation of this problem and a solution here: https://www.youtube.com/watch?v=ZWib5olGbQ0

cperciva• 9 years ago

In addition to having more information -- you can measure (very approximately!) how good candidates are, rather than merely being able to rank them against each other (as in the Secretary Problem) -- the payoffs are different. For actual hiring, having the second-best out of 100 secretaries is still pretty good; while for the purposes of the Secretary Problem having the second-best out of 100 secretaries is just as bad as having the worst secretary.

There is some connection to real world hiring practices, but only if you abstract away enough: The solution to the Secretary Problem basically comes down to

1. Spend some time gathering information which will let you assess how strong future candidates are.

2. Use that information to help you decide whom to hire.

In some cases step 1 is solved by interviewing many candidates in parallel; but in most cases companies adjust their thresholds for what "good enough" is over time based on their observations of incoming candidates. They might very well reject a candidate early on and then regret that decision later once they realize that she was exceptional compared to a disappointingly weak candidate pool.

dbcurtis• 9 years ago

To be fair, that is a restatement of the problem into a much more difficult one. Instead of looking for the best candidate among N, you are looking to maximize net-present-value of the work product produced by a candidate selected from a pool of N presented over time.

So you need not just a discrete better/worse comparison of candidates, but some linear measure of each candidate's productivity, some value for the work product, and an interest rate.

extr4• 9 years ago

I was asked a version of this as an interview question a few months ago. Despite recognizing the form of it immediately and giving some intuition for why it converges to 1/e, the interviewer had nothing else prepared and had expected it to be new to me, so he took me through a brutal one hour of his personal "guided proof" of the answer, including drawing a massive grid on a whiteboard and stepping through iterations. At one point I may have hinted that his method was overcomplicating things and tried to steer the conversation towards other aspects of the problem (ex: the time based formulation), no, let's get back on track with this grid. I didn't get the job, and I was specifically called out for doing poorly on that portion of the interview. I used to think this problem was really cool, now it just pisses me off remembering that situation.

quickthrower24• 9 years ago

On the positive side you dodged a bullet and wasted just a day. Imagine working for someone like that. Time you'll never get back.

awakeasleep• 9 years ago

Oh come on. Seems _highly_ probable he was stuck in an interview with a junior dev that only understood enough to follow the documented answer.

walshemj2• 9 years ago

well you could argue that's £400/500 - (say $600) down the drain as that's an average day rate for a contractor in the UK

dolson• 9 years ago

Maybe you were the first person he interviewed.

silveira• 9 years ago

the first n/e

cbhl• 9 years ago

Companies should really adopt shadow interviewing more. Go into an interview and watch someone experienced do it, so you can learn more about how to make interviews pleasant (even for a candidate that doesn't know what they're doing).

extr4• 9 years ago

It was one of the team members, not a manager or lead, so I would have been inclined to overlook it had it not been alongside 3 other "case interviews" that were tricky whiteboard coding/math problems in disguise. I think I spent a grand total of 20 minutes of my 8 hour day discussing my history and relevant experience.

quickthrower24• 9 years ago

This is the awe inspiring bit:

One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple and selects the single best candidate about 37% of the time, irrespective of whether there are 100 or 100 million applicants.

Another example of how our intuitions are poor at probabilities.

100M! Might give that a Monty Carlo sim. Or even try it on a big DB table at work.

jagthebeetle• 9 years ago

There's probably no lack of toy code, but since I am a skeptic / sceptic, quick nonsense code for pythonistas : https://gist.github.com/anonymous/ef975cdcb26044de9ba93e4e74...

Guess what? Skepticism allayed!

carapace• 9 years ago

Nerd sniped. I couldn't help it. What do you think> :-)

    from math import e, floor
    from random import randint


    def secretary_search(candidates):
      """Rejects first n / e candidates and then selects the first better."""
      n_reject = int(floor(len(candidates) / e))
      best = max(candidates[:n_reject])
      for candidate in candidates[n_reject:]:
        if candidate > best:
          return candidate
      return candidates[-1]


    success = 0.0
    size = 100
    trials = 10000
    for _ in range(trials):
      candidates = [randint(1, 1000) for _ in range(size)]
      success += max(candidates) == secretary_search(candidates)

    print success / trials

Bromskloss4• 9 years ago

My version! [0]

- More functional, with iterators and stuff. (It's half-baked, though, so please take it further!)

- Handles small numbers of candidates correctly.

- Agrees with the table on Wikipedia [1], and with the 1/e limit.

- Calculates hiring frequency for all candidates, not just the best one.

- Faster!

[0] https://gist.github.com/anonymous/9d735c5c77bd2e0939c69f5dd4...

[1] https://en.wikipedia.org/wiki/Secretary_problem#Deriving_the...

rhallie113• 9 years ago

I dated a guy once who, after a couple of weeks, asked me to marry him--citing this problem as his reasoning.

I said no.

Butt he's all I ever think about whenever I hear it mentioned, so.

aidenn0• 9 years ago

Definitely a good call; I don't think I'd want to marry someone who thought they could evaluate my value as a future partner in a couple of weeks.

khedoros1• 9 years ago

Did you ask his value for "n", and how he chose that value?

rhallie113• 9 years ago

It was 2, and I honestly have no idea why

thefalcon2• 9 years ago

Was his name Michael? http://mat.tepper.cmu.edu/blog/?p=1392

carsondm• 9 years ago

The questionable self help book 'Algorithms to Live By' could have prompted this. It's recommend in the first chapter

f_allwein2• 9 years ago

Did not know about this, but I read a simplified version of it a long time ago, which said "carefully examine the first choice, reject it, then go for the first choice that is better." Apparently, this would give me an above average option in most cases (did not do the math).

I quite like that and sometimes use it, e.g. to decide which restaurant to have a meal in.

zellyn• 9 years ago

The Power of Two Random Choices: it's a surprisingly decent heuristic

https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2...

f_allwein2• 9 years ago

Oh interesting, thanks for sharing!

kornork• 9 years ago

If the chance you'll pick the best option is 37%, what is the chance you'll pick someone in the top 2, or the top 5?

Another way of asking is, does it raise the odds you'll get someone really good, even if they aren't the best?

Bromskloss4• 9 years ago

I haven't calculated it exactly, but we were playing around with simulation code elsewhere among the comments, and my version [0] calculates the hiring frequency for each candidate, not just the best one, so you could look at the tail of the list called "hires".

[0] https://news.ycombinator.com/item?id=15573921

danesparza2• 9 years ago

I'd really like a real-life example of this.

I can't help but think this is a solution in search of a problem.

jpalomaki• 9 years ago

Case: You are wondering around a new city with few friends. Everybody is hungry and getting annoyed. No mobile devices are available or you do not trust the online recommendations. How do you find a good place to eat?

First you estimate based on the level of hunger, quality of shoes and the restaurant density of the area how many places you can check before you starve to death. This rule tells that you should first walk pass n/2.718 restaurants and then pick the best one you have seen so far.

Retra2• 9 years ago

That's a terrible contrivance. The real solution is to walk into the first place you can afford and enjoy the time with your friends. You don't need the best place to eat, you just need a good enough place to eat and a sense of humor or humility.

Too• 9 years ago

Almost correct but the secretary problem only allows you to accept or permanently reject an option. What you describe allows going back to previously rejected options.

psergeant2• 9 years ago

This would feel much more interesting if there was a cost attached to being forced to hire a terrible candidate.

Bromskloss4• 9 years ago

Isn't the cost that you get a terrible candidate?

psergeant2• 9 years ago

Yes. That isn’t factored into the algorithms though.

dreamcompiler• 9 years ago

I ran into this problem many years ago when writing a memory allocator. Say you keep a list of free blocks. You don't keep them sorted, but you do keep track of how long the list is. You now need to find a block of at least size n but not much larger, and the free list is so long you'd rather not look through the whole thing for each allocation.

There are a bunch of ways to write memory allocators, but with the above constraints, it's the same problem.

gnulinux• 9 years ago

You can use this idea in the clock algorithm to approximate LRU.

imrankhan17• 9 years ago

I did some analysis of this problem in Python here: https://imrankhan17.github.io/pages/Solving%20the%20secretar...

Secretary Problem

Related Stories