The Problem With The Secretary Problem
Or: On Optimal Stopping Rules
Johannes Kepler, poster child of the Scientific Revolution, widower, but most notably a German, struggled with the pressure of finding a second wife.1 With little trust in divine intervention he considered 11 different women. After much deliberation he decided on the fourth woman, but she was fed up with his indecisiveness and instead went for a man who had long been committed to her. Things didn't work out the fifth woman either. He was once again outcompeted by another suitor. After two years of weighing the pros and cons of each potential wife, things finally worked out with Susanna Reuttinger, who became his second wife.
Johannes faced a conflict that we all face: do we explore or do we pull the trigger? Do we stick with what we have or do we look for something new? Sounds trivial, but many people have crumbled under this pressure.
Johannes wanted to get a good idea of what options were out there and then pick the woman who he thought he was most compatible with. Pretty straightforward right? Well no. As we saw exploring comes with a cost, you might ultimately want to choose an earlier option who at this stage probably wants nothing to do with you.
This tension between looking and committing was later formalised and became known as the Secretary Problem which went viral in the mathematics community in the late 1950s.2 “Secretary Problem” because this tension isn’t limited dating, but also applies to hiring a secretary or other problems like choosing between potential mining sites. However, when you come across the Secretary Problem in pop culture it’s mostly in reference to finding a romantic partner. Hence the Secretary Problem is also known as the Marriage Problem or the Fussy Suitor Problem.
The solution to the Secretary Problem is often touted as the most rational and effective approach to finding a spouse. From what I have seen online, reactions tend to fall into two broad camps. One camp outright rejects the idea of applying mathematics to romance, deeming it unhuman, while the other hears “mathematically optimal solution” and is immediately sold. Neither reaction, however, is critical.
My initial reaction was definitely in the latter camp. But more recently, I took a closer look at the assumptions behind it, and I was surprised by how incompatible many of them are with real-world dating.
That being said let’s dive in.
Ferguson describes the problem in its simplest form as follows:3
There is one secretarial position available.
The number n of applicants is known.
The applicants are interviewed sequentially in random order, each order being equally likely.
It is assumed that you can rank all the applicants from best to worst without ties. The decision to accept or reject an applicant must be based only on the relative ranks of those applicants interviewed so far.
An applicant once rejected cannot later be recalled.
You are very particular and will be satisfied with nothing but the very best. (That is, your payoff is 1 if you choose the best of the n applicants and 0 otherwise.
The optimal solution to the Secretary Problem acknowledges the two tensions from earlier and splits the process of finding a secretary or spouse into an exploration stage and into a trigger pulling stage.
Let’s dive further into why the exploring stage is actually necessary. Let’s say you’ve only dated a two people. You might be able to say that John was a lot better boyfriend than Harry, however, you don’t know how John and Harry ultimately score on the worst-to-best boyfriend scale. You know Harry scores lower than John, but you don’t know by how much. And you also don’t know how high John scores. You might just be viewing him favourably because “anyone is better than Harry.” Maybe John isn’t a good boyfriend either or maybe he is. It’s difficult to tell if you don’t have a lot of experience to go off of. Gathering additional information by dating more people will hopefully get you a more calibrated understanding of what a good and what a bad boyfriend is. That way you hopefully have an easier time at picking good partners and dodging bad ones. Let’s say John ends up being the best boyfriend out of 10, that shows you that he’s probably a solid partner.4 That’s why the first part of the process is to explore. The next step is to actually commit to a partner.
The optimal solution to the Sectary Problem in this most simplest form is to wait until you’ve dated 37% of the potential partners and then commit to the next person who is better than everyone you have previously dated. 37% of the potential partners? Yes, the so-called 37% Rule assumes that you have a set pool of people that you are dating.
While this isn’t necessarily an incorrect assumption, it’s just not the way we tend to think about dating. When we typically think of our dating pool we think of all the possible people we could be dating rather than the total number of people we plan of dating in our lifetime which is a number you will have to know if you if you want to make use of the 37% Rule. That’s tough of course. Who knows how many people they expect to date?
Thankfully some people suggest making this a little easier by defining a time-frame, which coincides better with how most people tend to think about dating. For example, let’s say you’re 20 and want to get married by 30. Then you have 10 years to find a partner to settle down with. According to the 37% Rule, you should spend the time until age 23 years and 8 months exploring your options—learning about the kind of partners available and looking without any intention of committing. And then once you’ve spent 37% of your dating time looking, you commit to the next partner that is better than all previous ones. This sounds a lot more doable than defining some arbitrary number of potential partners, however, the problem isn’t entirely gone, it has merely taken on a new shape. The time-based rule assumes that the number of people you date remains equal over time. Dating 5 people one year and 1 the next year is going to be problematic. So you better make sure that you date approximately the same number of people every year.
As you can see from this first example, following the 37% Rule, the optimal solution to the Secretary Problem, makes some pretty strong assumptions about real-word behaviour.
The Optimal Solution Isn’t that Optimal
What results would you expect from the mathematically optimal way of finding a partner?
Surely the huge restrictions on your dating behaviour and personal autonomy will result in an exceptional payoff. Possibly a guarantee of finding “the one” or at least a very high chance!
However, something that might shock people is the staggering amount of uncertainty associated even with the optimal solution. Coincidentally, the 37% Rule also results in 37% probability of selecting the best potential partner in a defined pool of people. So, more often than not you will fail to select the best potential partner in a defined pool of people, even when using the optimal solution.
Mathematically, that’s impressive. Given the complexity of the problem, a 37% success rate is surprisingly high, especially considering the pool might include 50, 100, or even 10,000 people.
(A quick note: if you plan to date fewer than 20 people, the 37% Rule doesn’t apply, and you’ll need a different stopping rule.)5
However, certainty-seekers are unlikely to be impressed by a 37% chance. Of course, there’s a pretty simple way of increasing your chances: by lowering your standards.
Who is Swimming in Your Pool?
Maybe you decide that you’re actually fine with the top 3 or top 10% of your dating pool. That might sound quite satisfactory at first but that is entirely dependent on the quality of your sample and quality is something the Secretary Problem does not address. The Sectary Problem assumes you think about the people in your pool in terms of rank.
But the problem with a rank-order is that it only tells you something about relative preferences rather than absolute quality.
You can rank 10 methods of torture from most to least preferred. One method will end up at rank 1 but you don’t actually want to be subjected to any of them.
You can rank 10 masseuses at a massage competition. One masseuse will end up at rank 1 but you’d probably be happy with a massage from any of them.
Maybe your dating pool is full of super attractive, kind, honest, and intelligent people then getting the best person is actually not that important, you might be satisfied with option 21 out of 25. But that is unlikely to be the case for most people otherwise the Sectary Problem would have never become this famous.
We Don’t Have Perfect Information
While I think it’s pretty fair to assume that we “can rank all the applicants from best to worst without ties,” I think we should think twice about how valid that chosen rank-order is.
We are ranking these people on imperfect information. In the case of hiring a secretary, a job interview. When it comes to a potential partner, a couple dates. We don’t actually know how these people will turn out. At the end of the day, we’re just trying our best and are trying to predict how these people will fare in the future based on information we have in the present.
This point is easier to illustrate when it comes to hiring secretaries. Let’s consider the following thought experiment. We take a couple days to interview all applicants and at the end we rank them all. And then we do something strange—we hire them all. Fast forward a year and we rank them all again. So, now we have an initial ranking of the applicants based on imperfect information, i.e., the interview. And we have a second ranking of all the applicants—the actual outcome.
The way that people talk about the Secretary Problem assumes that the initial ranking is identical to the second ranking. This is a flawed assumption. When it comes to predicting future real-world outcomes involving human, our accuracy is far from perfect. Realistically, there will be changes between the two rankings. Some people will perform better than expected, others worse, and, naturally, some will perform exactly as expected. If we are so accurate in selecting romantic partners, the Secretary Problem would have never made it this far.
The main conclusion is that the optimal solution might give a 37% chance of selecting the best candidate but that has little use to us if it turns out that the best candidate is unlikely to be the best person.
In other words, since we are relying on imperfect information, the chance that we select the best candidate and they also turn out to be the best person is drastically lower than 37%.
In my estimation the chance of getting the best person is at best a measly 6%.6 Suddenly 37% doesn’t seem so bad.
The Stone Cold Practicalities
So, now that we are acknowledging the imperfection of our information, it’s also good to remember that the information you are collecting in the exploration phase should be compatible with the kind of relationship you are looking for.
If you are looking for a long-term partner, going on 50 first dates isn’t going to cut it. Going on 50 first dates is a great strategy if your aim is to optimise for the best second date. And I can’t imagine a lot of people are longing for the ultimate second date. Getting to know a bunch of people on a superficial level isn’t going to be of much help in finding a long-term partner. You’re way better off with 10 one-year relationships.
This makes the exploration phase difficult for two reasons.
The longer your “encounters” are with potential partners, the less people you can meet. You could theoretically have 365 one-night stands in a year, but only one one-year relationship. The main benefit of the 37% Rule is that it works as long as your dating pool is above 30.7 So, it can be used to work your way through hundreds of potential partners in an attempt to find the “perfect match.” The more people you consider the more likely you’ll find an exceptional partner.8 If you’re “only” considering let’s say 10 partners the chances are lower that it will include a truly exceptional partner.
Oh and the other thing is that you should robotically breakup with your long-term partners at a pre-defined point so you have enough time to explore other options. There are of course several practical problems with this: A) You need to be upfront about this. B) You need to actually be able to go through with it.
If you’re up front with someone that you’re just interested in dating them for data purposes most people will be out the door. Not a lot of people are interested in long-term relationships that end at a pre-defined time point especially if the reason for break-up is to look for other partners. The people that would say yes to this are unlikely to be representative of your general dating pool and will skew your information drastically. If you’re not upfront about it, it’s selfish and deeply unethical because you’re deceiving people. Same actually goes for applicants for the secretary position. It’s unacceptable to invite applicants to an interview that cannot lead to a job. You’re wasting peoples’ time.
Also you have to be able to break up at the pre-defined point. You also cannot get stuck in one of the “exploration relationships.” You fall in love? Sorry boss you have to move on. The entire setup of the relationship prompts both partners to remain emotionally detached because they know it will end. So you have the facade of a long-term relationship. But that’s it. Which is actually pointless because you are again not getting the information that you want to get.
Another thing to consider is that you’ll need some time to process a break-up and find a new person. Most people do not have people queuing up to date them. While we’re on the topic of other people, it goes without saying you could also mindless adhere to all these invasive and unnatural assumptions, select the best potential partner after having seen 37% of your dating pool, and that person rejects you. The 37% Rule only considers your choices, but not the choices of others. That’s not a critique of the 37% Rule, but rather something to keep in mind.
Some Major Technicalities
Sticking with information. How are you going to compare a two-week holiday fling with a two-and-a-half year relationship? How are you supposed to compare a date on the day that you got the long awaited promotion versus a date on the day your boss shouted at you in front of everyone? Or in the hiring context how do you compare an excellent internal candidate to an excellent external candidate? These scenarios are incomparable.
You want consistency in your information so your comparisons are valid. When hiring a secretary this is fairly straightforward. You simply invite all candidates to your office for a one-hour interview, ask them the same questions in the same order, and evaluate their responses.9 Of course, no experience is ever exactly comparable. The time of day will vary. On some days you’ll feel better than on others. As Heraclitus pointed out a while ago: “No man ever steps in the same river twice, for it's not the same river and he's not the same man.” But you can try your best.
The same level of consistency is practically impossible when it comes to romance. Where would you even start? Ensure that your dates or relationships always last the same length of time? Ensure that you have the same conversations in the same order and then systematically evaluate them after? Ensure that you always do the same date activities and in the same order? This may sound pedantic but how are you going to compare a cinema date with a bowling date?
How are you going to overcome memory biases? How are you going to avoid cognitive pitfalls? What should you trust more—how you felt during the date or how you felt after the date? How should you adjust for your own change in preferences over time?10
Very quickly your experiences become incomparable. That’s life.
That’s totally fine—we know it’s impossible to fairly compare all information or achieve complete consistency in our experiences. In fact, trying to do so would likely make life far less enjoyable. However, if you aim to reach the 37% probability of selecting the best candidate from your dating pool, striving for this kind of consistency is paramount.
While the 37% Rule is often hailed as the most rational and effective approach to dating, its underlying assumptions are at odds with reality. And when those assumptions are violated, the conclusion starts to unravel. Although the rule promises a 37% chance of selecting the best candidate, the real-life probability of selecting the best person is likely much closer to 0% than 37%. The enormous trade-offs in autonomy and the need to "robotise" yourself simply aren’t worth it.
That being said, I believe there are valuable lessons to be learned from comparing mathematically optimal dating to how we approach dating in reality—lessons I’ll explore in future essays.
Johannes Kepler: Life and Letters by Carola Baumgardt. Letter to Baron Peter Heinrich von Strahlendorf, October 23, 1613.
The Secretary Problem and Its Extensions: A Review by Freeman.
Who Solved the Secretary Problem? by Thomas S. Ferguson. I refer to the simplest form of the Secretary Problem because there are many extensions with more complex solutions. (In this essay when I refer to the Secretary Problem I always mean the Secretary Problem in its simplest form.) As I’ll outline in this essay, many of the assumptions underlying the Secretary Problem clash with the realities of dating. For this reason, I think the utility of the 37% Rule for dating has been drastically overstated. While it’s likely that some journals articles propose slightly more realistic extensions, I find it highly improbable that there is a solution that is both viable and as simple as the 37% Rule. If calculating the stopping rule required booting up Python, I suspect much of the appeal would disappear. Nonetheless, the Secretary Problem serves as a valuable thought experiment for dating and surely has practical applications in other domains.
I say probably because that depends entirely on the quality of the 10 boyfriends. If you end up with an additional 8 boyfriends from hell, that will not be very informative in terms of assessing John. But if you feel like the 8 boyfriends range from bad to very good, and you realise that John is actually great, that insight can be incredibly helpful.
The 37% Rule only kicks in at a pool size of around 30. This graph is taken from Algorithms to Live By written by Brian Christian and Tom Griffiths.
So, ChatGPT and I ran some Monte Carlo simulations to explore the Secretary Problem in a hiring context. One advantage of this scenario is that we can use existing estimates for the validity of interviews from selection research. According to Sackett and colleagues, unstructured interviews have a criterion validity of 0.19, while structured interviews are notably higher at 0.42. These values are based on Pearson correlation coefficients. Although I used Spearman’s correlation coefficients in my simulations, I expect the difference to minor as they often align closely.
The Secretary Problem makes several unrealistic assumptions about real-world hiring, so I focused on generating plausible estimates rather than overly optimistic ones. Since structured interviews are less common, I used the unstructured interview estimate (ρ = 0.19) for a realistic scenario and the structured interview estimate (ρ = 0.42) for an optimistic scenario.
Here’s how the simulations worked: I ran the Secretary Problem 10,000 times on rank-ordered lists of n candidates and recorded how often the best candidate was selected. As expected, the 37% Rule resulted in the best candidate being chosen 37% of the time. Go 37% Rule!
Next, to simulate imperfect information—in this case, the validity of interviews—I generated another 10,000 rank-orders that were correlated with the original rankings using the given validity estimates (ρ = 0.19 for unstructured interviews and ρ = 0.42 for structured interviews). I then calculated how often the initially selected best candidate (from the 37% Rule) remained the top-ranked candidate in the correlated list, essentially estimating the probability of hiring the actual best person. The results are as follows:
Most realistic estimate: n = 50, ρ = 0.19: 2.76%
Realistic but higher sample size: n = 100, ρ = 0.19: 2.16%
Best-case scenario: n = 50, ρ = 0.42: 5.19%
Best-case scenario with higher sample size: n = 100, ρ = 0.42: 3.57%
On average, this yields a probability of only 3.42%. Suddenly 37% doesn’t seem so bad.
This analysis is specific to hiring contexts, but it’s of course more interesting to consider how this might apply to dating. While no validity estimates for first-date impressions exist, let’s generously assume ρ = 0.5. With this correlation, the probability of identifying the best partner is:
n = 50, ρ = 0.5: 5.93%
n = 100, ρ = 0.5: 4.19%
Even with higher validity, the success rate is small. 6% is very little chance for a lot of effort.
Here is the R code in case someone is interested:
set.seed(123) # For reproducibility
# Number of simulations and candidates
num_simulations <- 10000
n <- 100
threshold <- floor(n * 0.37)
# Function to simulate the Secretary Problem
simulate_secretary <- function(ranks, threshold) {
best_seen <- min(ranks[1:threshold])
for (i in (threshold + 1):n) {
if (ranks[i] < best_seen) {
return(ranks[i] == 1) # Check if selected candidate is the best
}
}
return(ranks[n] == 1) # If no better candidate is found, pick the last one
}
# Function to generate rank-orders with a specific Spearman correlation
generate_correlated_ranks <- function(ranks, rho) {
if (rho == 1) {
return(ranks) # Directly return the original ranks for rho = 1
}
n <- length(ranks)
permuted_ranks <- sample(ranks) # Generate a random permutation of ranks
cor_ranks <- round(rho * ranks + (1 - rho) * permuted_ranks)
return(rank(cor_ranks))
}
# Simulate Secretary Problem and Correlated Ranks
original_ranks_list <- replicate(num_simulations, sample(1:n, n), simplify = FALSE)
# Step 1: Run original Secretary Problem
results <- sapply(original_ranks_list, function(ranks) simulate_secretary(ranks, threshold))
prob_best <- mean(results)
# Step 2: Run correlated simulation with rho = 1
correlated_results <- sapply(original_ranks_list, function(ranks) {
is_best <- simulate_secretary(ranks, threshold)
if (is_best) {
selected_index <- which.min(ranks)
correlated_ranks <- generate_correlated_ranks(ranks, rho = 0.5)
return(correlated_ranks[selected_index] == 1)
}
return(FALSE)
})
prob_correlated_best <- mean(correlated_results)
# Output probabilities
cat("Probability of selecting the best candidate:", prob_best, "\n")
cat("Probability of being the best in correlated ranks:", prob_correlated_best, "\n")
See footnote 5.
The flip side of this is of course also that you’ll probably meet some truly messed up people. The more people you meet the more likely that you’ll encounter a murder especially if you are a woman dating men.
If I had to live the life I dreamed about when I was 16, I would be miserable.