Optimal Stopping Problem

• stub

The optimal stopping problem has to do with stopping early enough to minimise cost while not stopping too early to maximise reward.

For example, when looking for an optimal apartment, one would need to look at enough apartments in order to make an informed decision. Yet at the same time, the act of looking for more departments also means losing valuable opportunities.

It turns out that, to optimise an apartment search, one should spend 37%¹ of their allotted time to explore the different options and calibrate their judgment. Afterwards, stop immediately when seeing something better. (Of course, this number changes changes for the size of the pool because not all numbers can be split by exactly 37%, but the optimal percentage approaches approximately 37% as the pool size grow.) When applying the 37% rule, the chance of selecting the best option is, as it turns out, approximately 37%, some interesting mathematical symmetry.

Notice that it is possible that we reject the best candidate during calibration. In this case, we choose the last candidate, unfortunitely. (or is there better mechanism to choose the second best and so on?)

(there is a prove but #stub)

The 37% rule applies to a wide range of other similar situations such as conducting job interviews, building machine learning models, searching for a restaurant, looking for the best toilet, finding love, picking products, etc. By following this rule, analysis paralysis can be avoided.

In other words, diminishing returns kicks in when one devote more than 37% of the allotted time to explore options.

One category of optimal stopping problem is also known as the secretary problem, examplified by the one presented above. There are, however, many other versions in which one or more of these can be true:

1. rejection, i.e. here is a non-zero probability that you don’t get what you pick
2. recall, i.e. You are allowed to go back and pick an option
3. We have some information about the applicants, like their test scores and their percentile

For any combination of the first two variations, an optimal stopping percentage still exists, though it might not be 37%.

For the third variation, one might want to have a threshold for when to stop (e.g. stop when someone’s above the 94th percentile) set according to the remaining pool size.

There are other variants, but the underlying mathematical principle is very similar. Namely, the cost of continuing outweigh the potential rewards of doing so at some point. In (unrigorous) economics terms, marginal cost increases while expected marginal benefit decreases. Examples includes:

• Selling a house and deciding when to accept an offer
• When to park

References:

1. Christian, Brian, and Tom Griffiths. Algorithms to Live by: The Computer Science of Human Decisions. First U.S. Edition, Henry Holt and Company, 2016.
2. https://www.youtube.com/watch?v=ZWib5olGbQ0
3. https://www.youtube.com/watch?v=XIOoCKO-ybQ