Optimal stopping: When to stop looking?

I am reading an interesting book titled “Algorithms to live by” by Brian Christian and Tom Griffiths. It is about applying algorithms found in computer science (or maths) textbooks in real-life problems. I just finished reading the first chapter on the optimal stopping problem and found it quite interesting.

The problem statement

We face the optimal stopping problem a lot in our lives. The secretary problem is one of the best examples of it. The problem statement goes like this: We have to hire a secretary for our office. A few candidates are waiting for an interview. We know the number of candidates in advance. After each interview, we have to decide whether to give them the offer or not. We can’t call back the rejected candidates. For simplicity, let’s assume that there is only one position to fill, and the candidates will always accept the offer if provided one. Once we hire a candidate, we can’t interview the remaining candidates. We can’t reject all of them. The last candidate gets the job position if none of the previous ones were hired. We want to select the best candidate for the job.

There are two ways in which we can fail: We pick someone too early and miss out on the best candidate, or we interview the best candidate and reject them in the hope of finding a better one later in the remaining candidates. We need to “look” (reject the first few candidates) and then “leap” (offer the position to the candidate that is better than what we have seen so far). The problem is to find the right balance between looking and leaping. 

Motivation

The problem appears in many forms in our lives. Here are some examples:

• Searching for an apartment to rent: When we move to a new city, we book temporary accommodation for the first few weeks to look for an apartment to rent. During apartment hunting, we face a variation of the secretary problem when we have to decide in a few days after visiting an apartment. 
• Finding the best parking space: We need to find a parking space that is closer to our destination. But we don’t know if there is a parking space available further down the road. If we see a parking space, we need to decide whether to occupy it or keep moving closer to the destination. Another variant of the secretary problem.
• Dating: We need to decide whether the current partner we are dating is the best match. A classical ‘look’ vs ‘leap’ scenario.
• Selling house/car: Every time someone bids an offer to buy, we need to decide whether to accept the bid or wait for a higher one. 

Solution

Well, good news! This problem (and many variations of it) has been studied a lot in computer science. In the classical secretary problem, the optimal stopping point is 37% (actual number is 1/e). We start interviewing candidates and reject the first 37% of them. After that, if we see a candidate that is better than those 37% (in other words, the best candidate we have seen so far), we hire them. This strategy maximizes the probability of us picking the overall best candidate. Unfortunately, that maximum probability is quite disappointing: 37%. But any other strategy has a lower chance of picking the overall best candidate. If you are interested in the detailed proof, here is the wiki page on the secretary problem.

Variations

Sometimes, the problem assumptions are too strict for a real-life version. For example, in house hunting, we can sometimes go back to a house we rejected. There is a chance that it is no longer available, but nothing is stopping us from trying. But the solution method of the secretary problem is still relevant. If the chance of rejection (the apartment is already occupied) is 50%, the same method will output the stopping threshold at 61% (with a 61% probability of success). 

In the case of dating and house hunting, we don’t know the number of people we will be dating or the number of houses we will get to visit. The secretary problem is still applicable. Here, we use time as a finite resource. If we have a rough estimate of how long the search period will last, we can stay in the “look” phase till 37% of that time period and then switch to the “leap” phase.  

The threshold number and the probability of success change for different variants. We assumed that the candidates would always accept our offer. If we instead assume a 50% chance of acceptance, the probability of success (finding the best candidate) drops down to 25%. If we somehow can quantify the skills of the applicant in a numeric score in a fixed range, we are now in a “full-information” variant, and the chances of success increase to 58%. The threshold number and chances of success change if we assume a time cost for searching.

Takeaway

The natural question is, do we already follow this algorithm (by evolution or intuition)? As per some studies, we tend to stop early when faced with some variant of optimal stopping point. We tend to get bored quickly, and that results in us associating a ‘time cost’ for searching. Sometimes, there is a time cost, and the stopping threshold changes for such scenarios. For the secretary problem, while we haven’t hired a secretary, we are spending our time doing that instead of our regular activity. But if this hiring job is delegated to an HR with only a few hours reserved to interview the candidates, the time cost is negligible. Getting bored is not a valid excuse to stop early. In any case, knowing the optimal stopping number for different variations can be quite helpful.

My favorites

Video: 85 year long study on happiness (Veritasium)

Quote: "Your Thoughts Are Better Spent On Things You Can Change, Not Those You Can't." — Doctor Fate, Black Adam