This post is split out from my main summary of Algorithms to Live By by Brian Christian and Tom Griffiths. Check out that summary to learn more about the book.
What is an optimal stopping problem?
In an optimal stopping problem, you’re trying to find the best option and have to decide when to end your search and settle for an option. It’s finding the right balance between “looking” and “leaping”.
The classic example is the “secretary” problem, where you are trying to hire a secretary. Other examples of optimal stopping problems include trying to find: a spouse, an apartment, or a parking spot.
The 37% rule
The magic number turns out to be 37%. (Or, more precisely, it’s 1/e, e being the constant 2.718… etc).
That is, if you have 100 candidates, look at the first 37 without hiring any of them, then leap to hire the next candidate you see that is better than the first 37. If you don’t know how many candidates there are, you can apply the 37% number to the fixed time you have instead (e.g. if you have 100 days to look, spend the first 37 looking noncommittally).
This 37% rule only gives you a 37% chance of success. However, your chances of finding the single best candidate don’t decline as the pool grows larger.
Variations on 37%
Real life differs from the classical problem in several ways, which may give rules higher or lower than 37%:
- If candidates reject you at a 50% rate, you need to leap earlier, after interviewing just 25% (your success rate drops to 25% too).
- Being able to recall a past candidate increases your success rate. Assuming past candidates have a 50% chance of rejecting you, you should leap after seeing 61% of candidates (with a 61% success rate).
- If you can compare candidates to an external benchmark, you can recognise a good candidate when you see one (instead of only knowing how good a candidate is relative to others). You should then apply a Threshold Rule, starting out with a high threshold and lowering it as time passes. [Sounds like dating!]
- Costs of search will alter your strategy. For example, if you have holding costs when trying to sell a house, you don’t want the single best offer, you want to maximise your money. In that case, you should just pick a threshold and stick to it.