Chapter 1: 1. Optimal Stopping: When to Stop Looking
Key concepts: 1. Optimal Stopping: When to Stop Looking
1. Optimal Stopping: When to Stop Looking
The Secretary Problem Framework
- Universal dilemma of when to stop searching and commit
- Goal: hire the single best candidate from a sequential, random-order interview process
- Key constraints: only relative comparisons, no recall of passed candidates, immediate decision ends search
- Origins are murky, popularized by Martin Gardner in 1960 with roots in 19th-century suitor puzzles
The Optimal Strategy: Look-Then-Leap Rule
- Two-phase approach: initial 'look' phase to gather information, then 'leap' phase to commit
- Mathematically optimal to switch after reviewing 37% of candidates (the 37% Solution)
- Yields a constant 37% chance of success, regardless of pool size
- Strategy balances exploration (setting a benchmark) and exploitation (acting before best is lost)
Real-World Applications & Complications
- Applied to romance: calculating when to start seriously committing to a partner
- Real life introduces rejection (candidate says no) and recall (returning to a past option)
- With 50% rejection chance, optimal look phase shrinks to 25% of search
- With recall allowed, look phase extends to 61% with fallback to best past option
Full Information & The Threshold Rule
- When objective data is available (e.g., percentile scores), strategy shifts
- Use a sliding percentile threshold: hire anyone above a predetermined score
- More efficient than the Look-Then-Leap Rule under full information
- Applies to scenarios where candidates can be quantitatively ranked
Optimal Stopping in Life Decisions
- Selling a house: maximize profit by weighing each offer against cost of waiting
- Set a single price threshold in advance and never revisit rejected offers
- Parking spot search: occupancy rate dictates when to start seriously looking
- Cities can optimize parking via pricing based on optimal stopping principles
The Decision to Quit & Problematic Scenarios
- Burglar problem: simple formula for when to stop (attempts = success chance / failure chance)
- Some scenarios (e.g., 'triple or nothing' gamble) have no safe stopping point and should be avoided
- Highlights that not all sequential decision problems have a mathematically sound optimal stop
Human Behavior vs. Mathematical Optima
- Research shows humans consistently stop searching earlier than math advises
- This may be rational due to endogenous costs: time, effort, boredom, and opportunity cost
- Pure mathematical models ignore psychological and real-world search costs
- Optimal stopping theory provides a framework, not a strict prescription, for irreversible choices
Full Information and the Threshold Rule
- Objective data like percentile scores eliminates the need for a calibration phase in decision-making
- A Threshold Rule is used: hire immediately if an applicant exceeds a specific percentile threshold
- The threshold depends on how many candidates remain—higher standards with more options, lower with fewer
- This approach boosts success rates to 58%, showing clear metrics make decisions more efficient
Selling with Costs: The House Selling Problem
- Unlike the secretary problem, selling involves known dollar values and real costs like mortgage payments
- Goal is to maximize total profit by balancing better future offers against immediate waiting costs
- Optimal stopping price depends only on cost per offer and known offer range—set threshold in advance
- Never recall a past offer—if it was below threshold initially, it remains below due to sunk costs
Parking as Optimal Stopping
- Core variable is occupancy rate—percentage of spots filled—which creates cruising when too high
- Look-Then-Leap Rule applies: pass all spots beyond critical distance, then take first one after
- Critical distance shrinks dramatically as occupancy decreases (quarter-mile at 99% vs. half-block at 85%)
- Adaptive pricing to target ~85% occupancy simplifies the stopping problem and reduces societal costs
Quitting and the Burglar Problem
- Mathematical framing of 'quit while you're ahead' using sequential risk-reward decisions
- Optimal number of attempts is roughly chance of success divided by chance of failure
- Some scenarios like 'triple or nothing' have no optimal stopping rule—mathematically advise playing forever
- Highlights that some risk scenarios are best avoided entirely rather than optimized
Human Psychology and Optimal Stopping
- People consistently stop too early in laboratory secretary problems, leaping sooner than optimal
- This impatience may be rational when considering endogenous time costs like boredom and mental toll
- Early stopping aligns with rationally adjusted models that account for human factors
- Optimal stopping mirrors the nature of time itself—one-way sequence of irreversible decisions
The House Selling Problem (Known Distribution)
- Calculate a single, rational threshold upfront based on known offer distribution and constant search costs.
- Hold this threshold firmly; do not lower it out of impatience as time passes.
- Never revisit a rejected offer; the optimal strategy is forward-looking only.
The Parking Problem (Spatial Search)
- Strategy is determined by the occupancy rate (density of available options).
- Higher vacancy rates allow for greater choosiness and searching closer to the destination.
- The optimal strategy balances the risk of passing a good spot against the cost of circling back from farther away.
Sequential Risk and the Quit Formula
- Applies to scenarios with repeated attempts and a chance of catastrophic failure (total loss).
- A simple heuristic: quit after (probability of success) / (probability of failure) attempts.
- This rule balances the diminishing chance of eventual success against the accumulating risk of ruin.
Unwinnable Games (e.g., Triple or Nothing)
- Some scenarios have no mathematically optimal stopping point for long-term gain.
- Indefinite play is mathematically destined for ruin due to the risk structure.
- The rational strategy is complete avoidance, not attempting to find a stopping rule.
Human Behavior vs. Mathematical Optima
- People tend to stop searching earlier than pure mathematical models prescribe.
- This is often due to real but unquantified costs like time, effort, and psychological fatigue (boredom).
- Such early stopping is not necessarily irrational but highlights the need to balance formal models with experiential costs.
