Optimal Stopping
Optimal stopping is a mathematical framework for deciding when to stop evaluating options in a sequential search, balancing the trade-off between exploring new opportunities and committing to a current one. The 37% Rule, derived from the secretary problem, advises looking at the first 37% of options to set a threshold, then selecting the next best option that exceeds it.
THE IDEA
Optimal Stopping
Optimal stopping problems involve deciding the right moment to take a particular action, based on sequentially observed random variables, to maximize an expected payoff. The classic secretary problem asks: given a known number of applicants interviewed one by one, how to maximize the probability of hiring the best? For a large pool, reject approximately the first n/e applicants (about 37%) and then choose the next one who is better than all previous ones. The success probability approaches 1/e (~37%).
The 37% Rule
For a pool of n applicants, the probability of success using the 37% Rule converges to 1/e as n grows. Stopping problems also arise in dating, house sales, parking and gambling, but those settings can require different models and stopping rules. The key assumptions are: no recall of past applicants, only relative ranks matter, and the order is random.
Variants and Extensions
- Full-information problem: If you know the actual value of each applicant (absolute ratings), the optimal strategy involves a sequence of decreasing thresholds, not a fixed percentage. Early in the search, you can be picky; later, you lower your standards.
- Rejection and recall: If past applicants can be revisited later, the strategy changes; you may look longer before starting to offer.
- Maximizing expected rank: Instead of just the best, you may care about the average rank. This results in a different threshold rule.
Applications
- Looking for love: The book compares Kepler’s search for a second wife with the 37% Rule, describing 11 candidates and a decision after the first 4. This is an analogy to the stopping problem, not evidence that he deliberately followed its strategy.
- Selling a house: Set a reservation price based on the trade-off between waiting for a better offer and incurring carrying costs. The first offer above that threshold is accepted.
- Parking: On a street with uncertain spots, the optimal strategy is to start looking seriously for a spot only when you are close to your destination, based on the probability of finding a spot.
- Quitting while ahead: In a sequence of gambles with risk of total loss, stop when accumulated gains exceed a calculated threshold.
Satisficing
Herbert Simon introduced satisficing as a behavioral alternative to optimization: set a threshold of 'good enough' and stop at the first option that meets it. This mirrors optimal stopping solutions and describes actual human decision-making.
When to use it
Recruiting: examine whether a sequential hiring process meets the assumptions behind the 37% Rule before using its threshold.
Comparing personal searches with stopping models: identify whether the pool size, recall options and objective are defined well enough for the analogy to help.
Shopping: When considering sequential price offers (e.g., bidding on a house), set a reservation price based on expected future offers.
Parking: Optimal strategy for cruising for a parking spot to minimize time and distance walked.
FROM THEORY TO EVERYDAY LIFE
In practice
Kepler's Search for a Second Wife
The book compares Kepler’s search for a second wife with the 37% Rule to illustrate learning about a pool of candidates before committing. Its numerical analogy treats the first four as a sample (about 37% of 11). Applying that model requires assumptions about order and recall; the historical story does not establish those assumptions.
Selling a House
When selling a house, offers arrive sequentially. The optimal strategy is to set a reservation price based on the expected distribution of offers and the cost of waiting. For example, if the market is stable and the cost of carrying the house is 2% of the price per month, the reservation price should be set such that the expected benefit of waiting one more month equals the cost.
Parking Spot Search
Driving to a destination, you encounter empty parking spots with a certain probability. The optimal strategy is to first drive past a certain number of spots (or a distance) without stopping, then take the first available spot after that point. The exact number depends on the probability of a spot being free and the distance to your destination.
A MOMENT TO REFLECT
Put it to work.
Think of a major decision in your life (e.g., choosing a job, partner, or apartment). How does the 37% Rule apply to that search process?
In what situations might it be better to stop earlier or later than the 37% Rule suggests? Consider factors like time pressure, risk tolerance, and the cost of continuing.
How does the concept of satisficing relate to optimal stopping? Can you identify a time when you settled for 'good enough' instead of holding out for the best?
Often confused with
References
- Optimal Stopping and Applications — Thomas S. Ferguson (2008)
- Who Solved the Secretary Problem? — Thomas S. Ferguson (1989)
- Recognizing the Maximum of a Sequence — John P. Gilbert and Frederick Mosteller (1966)
- Optimal Selection Based on Relative Rank — Y. S. Chow, S. Moriguti, H. Robbins, and S. M. Samuels (1964)
- Dynamic Programming and Decision Theory — D. V. Lindley (1961)
- The High Cost of Free Parking — Donald Shoup (2005)
- A Behavioral Model of Rational Choice — Herbert A. Simon (1955)
CONTINUE THE CONVERSATION
Source texts
- Algorithms to Live By The Computer Science of Human Decisions (Brian Christian, Tom Griffiths)