The Dating Problem, Revisited.

How many dates should you go on before you settle down?

The classic “secretary” problem has many names and guises but it’s essentially a mathematical decision theory problem that goes like this: imagine you are interviewing a pool of candidates, and you want to find the best one, but you are under time constraints. The interviewees arrive in random order, and you evaluate each one with a “score” — but you have to decide if you want to hire them on the spot, or else pass them up and move to the next person. No backsies! So…what’s your algorithm for nabbing the best person? You can use this to model dating, of course, since you’re just uh, hiring someone to be your life partner.

The mathematicians’ answer to this is, rather magically, N/e, where N is the number of candidates (assuming you know this) and e is Euler’s number. This works out to 37% or so, meaning this is how many of the candidates you should go through to establish your “benchmark” —I call it the “burn-in” period — and once you do, then just pick the next person after that who is better than everyone you’ve seen in the burn-in period. This is called an optimal stopping problem, and the solution says that you can expect to come out with the best candidate 37% of the time. Of course, that’s assuming a uniform distribution for the candidates. I tamper with this assumption in the experiments I detail below.

The problem is that if time is money, then it’s not only the 37% of your time that you spend, but also the time it takes to actually find someone that meets the benchmark. I mean, maybe you got lucky and met the best person in the burn in period, an outlier type, and it will take awhile before you find someone of that caliber again. So let’s work in a cost. Let’s see how long it actually takes to find that person.

The code that I came up with for this problem can be found at the end of this post. Here’s the general setup that I came up with.

  • There are 100 candidates, with scores drawn i.i.d from a Poisson(lambda = 100) distribution. Generally, this means a fairly normal-shaped curve, with max scores ~ 126.
  • We can decide if we want our final candidate to be better than the best of the burn-in period — or if we would settle for someone that is, say, in the 90th percentile of the burn-in candidates.
  • We will “grid-search” through various burn-in periods and compute how long it actually takes before we select the final candidate.
  • For each burn-in period, we do 10000 trials.
  • We compute how our final choice stacks up against the actual “global” max value in the 100 candidates, just to see how far we were from the best person, on average.
  • The cost is computed in total number of interviews before the selection is made. So if your burn-in is 10 people and then it takes another 20 before your algorithm tells you to stop and select, then the cost is 10+20 = 30.

You can see that if you use burn-in of just 1 — meaning you only test 1 person before deciding you can accept candidates — you will end up finishing fast — assuming 1 time unit (e.g. an hour) for each person, you finish in 4.53 hours, but you get someone that is on average 16.69 units below the best candidate.

So if you want to get someone that is within 2 of the best score — you see that it takes on average 61.88 hours — of the 100 that you could budget for this task. However, it’s clear there is some exponential/log law at work here, because with just a burn-in period of 11, you can, with an average of 27.54 hours, get someone who scores above a 120 — and when the max is 126, and the average is 100, that seems like a good enough deal.

What about if you were in a rush, and after the burn-in period was done and saw and scored them, you were ready to accept anyone that came after was better than 00% of the burn-in candidates? Here are the results from my simulation:

What you can see here is that after a burn-in of 6, you get an average score of 115.38, while if you choose a burn-in of 21 candidates, you only get a marginally better score of 117.33, which takes you 30.15 hours. So what that means is, for most purposes, is that you can afford to be picky, because getting a scorer of 120 “costs” as much time as someone that is a 117. It also shows that overall, you don’t really have to spend 37% of your time on the burn-in to maximize your chance of getting the best candidate or even someone that is optimally suboptimal — “the best second choice” — you can get something pretty close to decent fast, but that’s simply because we know something about the distribution — which is the biggest “cheat” in this case — since most of the time you might have no idea that scoring 100 on this test is average. Maybe the test is really hard and no one can really score above 120. I will deal with this situation in a later post — what to do when you have no idea what the underlying distribution is.

Here’s the code for my simulation. Check to see if I did it right, any suggestions appreciated!

Machine Learning Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store