Skip to content

Podcast

1. Optimal Stopping- When to Stop Looking

Algorithms to Live By: The Computer Science of Human Decisions

Source ↗ ← All highlights
  • The 37 Percent Rule For One-Shot Searches
    • The secretary problem yields a universal 37% rule for no-information searches where options arrive sequentially and cannot be recalled.
    • Look at the first 37% of applicants without choosing, then pick the next person who beats that best-so-far, giving ~37% chance of picking the absolute best. Transcript: Host / Narrator (Algorithms to Live By episode) The 37% rule derives from optimal stopping’s most famous puzzle, which has come to be known as the secretary problem. Its setup is much like the apartment hunter’s dilemma that we considered earlier. Imagine you’re interviewing a set of applicants for a position as a secretary, and your goal is to maximize the chance of hiring the single best applicant in the pool. While you have no idea how to assign scores to individual applicants, you can easily judge which one you prefer. A mathematician might say you have access only to the ordinal numbers, the relative ranks of the applicants compared to each other, but not to the cardinal numbers, their ratings on Some kind of general scale. You interview the applicants in random order, one at a time. You can decide to offer the job to an applicant at any point, and they are guaranteed to accept, terminating the search. But if you pass over an applicant, deciding not to hire them, they are gone forever. The secretary problem is widely considered to have made its first appearance in print, sans explicit mention of secretaries, in the February 1960 issue of Scientific American, as One of several puzzles posed in Martin Gardner’s beloved column on recreational mathematics. But the origins of the problem are surprisingly mysterious. Our own initial search yielded little but speculation before turning into unexpectedly physical detective work, a road trip down to the archive of Gardner’s papers at Stanford, To haul out boxes of his mid-century correspondence. Reading paper correspondence is a bit like eavesdropping on someone who’s on the phone. You’re only hearing one side of the exchange and must infer the other. In our case, we only had the replies to what was apparently Gardner’s own search for the problem’s origins 50 summers ago. The more we read, the more tangled and unclear the story became. Harvard mathematician Frederick Mosteller recalled hearing about the problem in 1955 from his colleague Andrew Gleason, who had heard about it from somebody else. Leo Moser wrote from the University of Alberta to say that he wrote about the problem in, quote, some notes by R.E. Gaskell of Boeing, who himself credited a colleague. Roger Pinkham of Rutgers wrote that he first heard of the problem in 1955 from Duke University mathematician J. Schoenfeld, quote, and I believe he said that he had heard the problem from someone at Michigan. Someone at Michigan was almost certainly someone named Merrill Flood. Though he is largely unheard of outside mathematics, Flood’s influence on computer science is almost impossible to avoid. He’s credited with popularizing the traveling salesman problem, which we discuss in more detail in Chapter 8, devising the prisoner’s dilemma, which we discuss in Chapter 11, and Even with possibly coining the term software. It’s Flood who made the first known discovery of the 37% rule in 1958, and he claims to have been considering the problem since 1949, but he himself points back to several other mathematicians. Suffice it to say that wherever it came from, the secretary problem proved to be a near-perfect mathematical puzzle. Simple to explain, devilish to solve, succinct in its answer, and intriguing in its implications. As a result, it moved like wildfire through the mathematical circles of the 1950s, spreading by word of mouth, and thanks to Gardner’s column in 1960, came to grip the imagination of The public at large. By the 1980s, the problem and its variations had produced so much analysis that it had come to be discussed in papers as a subfield unto itself. As for secretaries, it’s charming to watch each culture put its own anthropological spin on formal systems. We think of Chess, for instance, as medieval European in its imagery, but in fact its origins are in 8th century India. It was heavy-handedly Europeanized in the 15th century, as its shahs became kings, its viziers turned to queens, and its elephants became bishops. Likewise, optimal stopping problems had a number of incarnations, each reflecting the predominating concerns of its time. In the 19th century, such problems were typified by Baroque lotteries and by women choosing male suitors. In the early 20th century, by holidaying motorists searching for hotels and by male suitors choosing women. And in the paper-pushing male-dominated mid-20th century, by male bosses choosing female assistants. The first explicit mention of it by name as the secretary problem appears to be in a 1964 paper, and somewhere along the way, the name stuck. Whence 37% In your search for a secretary, there are two ways you can fail, stopping early and stopping late. When you stop too early, you leave the best applicant undiscovered. When you stop too late, you hold out for a better applicant doesn’t exist. The optimal strategy will clearly require finding the right balance between the two, walking the tightrope between looking too much and not enough. If your aim is finding the very best applicant, settling for nothing less, it’s clear that as you go through the interview process, you shouldn’t even consider hiring somebody who Isn’t the best you’ve seen so far. However, simply being the best yet isn’t enough for an offer. The very first applicant, for example, will of course be the best yet by definition. More generally, it stands to reason that the rate at which we encounter best yet applicants will go down as we proceed in our interviews. For instance, the second applicant has a 50-50 chance of being the best we’ve yet seen. But the fifth applicant only has a 1-5 chance of being the best so far. The sixth has a 1-6 chance, and so on. As a result, best-yet applicants will become steadily more impressive as the search continues. By definition, again, they’re better than all those who came before. But they will also become more and more infrequent. Okay, so we know that taking the first best-yet applicant we encounter, a.k the first applicant, period, is rash. There are a hundred applicants, it also seems hasty to make an offer to the next one who’s best yet, just because she was better than the first. So how do we proceed? Intuitively, there are a few potential strategies. For instance, making an offer the third time an applicant trumps everyone seen so far, or maybe the fourth time. Or perhaps taking the next best-yet applicant to come along after a long drought, a long streak of poor applicants. But as it happens, neither of these relatively sensible strategies comes out on top. Instead, the optimal solution takes the form of what we’ll call the look-then rule. You set a predetermined amount of time for looking, that is, exploring your options, gathering data, in which you categorically don’t choose anyone, no matter how impressive. After that point, you enter the leap phase, prepared to instantly commit to anyone who outshines the best applicant you saw in the look phase. We can see how the look then leap rule emerges by considering how the secretary problem plays out in the smallest applicant pools. With just one applicant, the problem is easy to solve. Hire her. With two applicants, you have a 50-50 chance of success, no matter what you do. You can hire the first applicant, who will turn out to be the best half the time, or dismiss the first and by default hire the second, who is also best half the time. Add a third applicant, and all of a sudden, things get interesting. The odds if we hire at random are one-third, or 33%. With two applicants, we could do no better than chance. With three, can (Time 0:01:58)
  • Why Best-So-Far Applicants Become Rarer Over Time
    • Stopping too early misses the best candidate; stopping too late waits for someone who may never appear, so optimal stopping balances these risks.
    • As you interview more people, the probability a given applicant is the “best so far” falls: the 2nd has a 1/2 chance, the 5th a 1/5 chance, the 6th a 1/6 chance.
    • Therefore “best-so-far” applicants grow rarer but more impressive as the search continues, which is central to deriving the 37% rule.
    • The strategy relies on ignoring non-best-so-far candidates and only considering those who outperform everyone previously seen.
    • This changing frequency of best-so-far events creates the tradeoff that defines the optimal stopping point. Transcript: Host / Narrator (Algorithms to Live By episode) Whence 37% In your search for a secretary, there are two ways you can fail, stopping early and stopping late. When you stop too early, you leave the best applicant undiscovered. When you stop too late, you hold out for a better applicant doesn’t exist. The optimal strategy will clearly require finding the right balance between the two, walking the tightrope between looking too much and not enough. If your aim is finding the very best applicant, settling for nothing less, it’s clear that as you go through the interview process, you shouldn’t even consider hiring somebody who Isn’t the best you’ve seen so far. However, simply being the best yet isn’t enough for an offer. The very first applicant, for example, will of course be the best yet by definition. More generally, it stands to reason that the rate at which we encounter best yet applicants will go down as we proceed in our interviews. For instance, the second applicant has a 50-50 chance of being the best we’ve yet seen. (Time 0:06:08)
  • The Look-Then-Leap 37% Rule
    • The optimal strategy is the look-then-leap rule: spend a predetermined portion of your search only observing and never choosing.
    • After the look phase, immediately accept the first applicant who is better than anyone seen during the look phase.
    • As the applicant pool grows, the breakpoint converges to 37% of the pool — look at the first 37% and then leap for the next best-yet.
    • Following the 37% rule gives you about a 37% chance of selecting the overall best applicant, a surprising symmetry of the problem.
    • The rule emerges from analyzing small pools (2–5 applicants) and generalizes as n increases. Transcript: Host / Narrator (Algorithms to Live By episode) You can hire the first applicant, who will turn out to be the best half the time, or dismiss the first and by default hire the second, who is also best half the time. Add a third applicant, and all of a sudden, things get interesting. The odds if we hire at random are one-third, or 33%. With two applicants, we could do no better than chance. With three, can we? It turns out we can, and it all comes down to what we do with the second interviewee. When we see the first applicant, we have no information. She’ll always appear to be the best yet. When we see the third applicant, we have no agency. We have to make an offer to the final applicant since we’ve dismissed the others. But when we see the second applicant, we have a little bit of both. We know whether she’s better or worse than the first. And we have the freedom to either hire or dismiss her. What happens when we just hire her if she’s better than the first applicant and dismiss her if she’s not? This turns out to be the best possible strategy when facing three applicants. Using this approach, it’s possible, surprisingly, to do just as well in the three-applicant problem as with two, choosing the best applicant exactly half the time. Enumerating these scenarios for four applicants tells us that we should still begin to leap as soon as the second applicant. With five applicants in the pool, we shouldn’t leap before the third. As the applicant pool grows, the exact place to draw the line between looking and leaping settles to 37% of the pool, yielding the 37% rule. (Time 0:08:35)
  • Why The 37% Rule Still Gives You A 37% Chance
    • The optimal stopping strategy settles to sampling the first 37% of options, then choosing the next one better than all you’ve seen.
    • Following that rule yields about a 37% probability of selecting the single best option, regardless of pool size.
    • That 37% success rate holds for small and huge pools alike — 100 applicants or a million, the chance stays ~37%.
    • The failure rate is therefore ~63% even when you act optimally, which is counterintuitive but mathematically inevitable.
    • The larger the pool, the more valuable it is to know and use the optimal algorithm rather than guessing at random. Transcript: Host / Narrator (Algorithms to Live By episode) A 63% failure rate when following the best possible strategy is a sobering fact. Even when we act optimally in the secretary problem, we will still fail most of the time. That is, we won’t end up with a single best applicant in the pool. This is bad news for those of us who would frame romance as a search for the one. But here’s the silver lining. Intuition would suggest that our chances of picking the single best applicant should steadily decrease as the applicant pool grows. If we were hiring at random, for instance, then in a pool of 100 applicants, we’d have a 1% chance of success. And in a pool of a million applicants, we’d have a 0.0001% chance. Yet remarkably, the math of the secretary problem doesn’t change. If you’re stopping optimally, your chance of finding the single best applicant in a pool of 100 is 37%. And in a pool of a million, believe it or not, your chance is still 37%. Thus, the bigger the applicant pool gets, the more valuable knowing the optimal algorithm becomes. It’s true that you’re unlikely to find the needle the majority of the time, but optimal stopping is your best defense against the haystack, no matter how large. (Time 0:10:29)
  • A Mathematician’s Dating Leap And Rejection
    • Michael Trick applied the 37% rule to dating and switched from looking to committing at age 26.1 based on an 18–40 search window.
    • He proposed when he met someone better than his sample, but she rejected him, showing model limits. Transcript: Host / Narrator (Algorithms to Live By episode) It hit me that the problem has been studied. It is the secretary problem. I had a position to fill and a series of applicants, and my goal was to pick the best applicant for the position. So he ran the numbers. He didn’t know how many women he could expect to meet in his lifetime. But there’s a certain flexibility in the 37% rule. It can be applied to either the number of applicants or the time over which one is searching. Assuming that his search would run from ages 18 to 40, the 37% rule gave age 26.1 years as the point at which to switch from looking to leaving. A number that, as it happened, was exactly Trix’s age at the time. So when he found a woman who was a better match than all those he had dated so far, he knew exactly what to do. He leapt. I didn’t know she was perfect. The assumptions of the model didn’t allow me to determine that. But there was no doubt that she met the qualifications for this step of the algorithm. So I proposed, he writes, and she turned me down. (Time 0:12:10)
  • Propose Early When Rejection Is Possible
    • If proposals can be rejected sometimes, start making offers earlier: after about 25% of search rather than 37%.
    • Keep proposing to every best-yet person until someone accepts to maximize chance of ending with the best who will accept. Transcript: Host / Narrator (Algorithms to Live By episode) The possibility of rejection, for instance, has a straightforward mathematical solution. Propose early and often. You have, say, a 50-50 chance of being rejected. Then the same kind of mathematical analysis that yielded the 37% rule says you should start making offers after just a quarter of your search. It turned down, keep making offers to every best-yet person you see until somebody accepts. With such a strategy, your chance of overall success, that is, proposing and being accepted by the best applicant in the pool, will also be 25%. Not such terrible odds, perhaps, for a scenario that combines the obstacle of rejection with the general difficulty of establishing one’s standards in the first place. Kepler, for his part, decried the restlessness and doubtfulness that pushed him to keep on searching. Was there no other way for my uneasy heart to be content with its fate, he bemoaned in a letter to a confidant, than by realizing the impossibility of the fulfillment of so many other desires? Here again, optimal stopping theory provides some measure of consolation. Rather than being signs of moral or psychological degeneracy, restlessness and doubtfulness actually turn out to be part of the best strategy for scenarios where second chances Are possible. If you can recall previous applicants, the optimal algorithm puts a twist on the familiar look-and rule, a longer noncommittal period, and a fallback plan. For example, assume an immediate proposal is a sure thing, but belated proposals are rejected half the time. Then the math says you should keep looking noncommittally until you’ve seen 61% of applicants, and then only if someone in the remaining 39% of the pool proves to be the best yet. If you’re still single after considering all the possibilities, as Kepler was, then go back to the best one that got away. (Time 0:14:59)
  • Full Information Changes The Strategy Dramatically
    • With full information (objective scores/percentiles) the optimal rule becomes a threshold that depends on how many applicants remain, not an initial look phase.
    • This variant raises success probability to about 58% because you can compare to known percentiles rather than only ranks. Transcript: Host / Narrator (Algorithms to Live By episode) Full information. The first variants we considered, rejection and recall, altered the classical secretary problem’s assumptions that timely proposals are always accepted and tardy proposals never. For these variants, the best approach remained the same as in the original. Look noncommittally for a time, then be ready to leap. But there’s an even more fundamental assumption of the secretary problem that we might call into question. Namely, in the secretary problem, we know nothing about the applicants other than how they compare to one another. We don’t have an objective or pre-existing sense of what makes for a good or bad applicant. Moreover, when we compare two of them, we know which of the two is better, but not by how much. It’s this fact that gives rise to the unavoidable look phase, in which we risk passing up a superb early applicant while we calibrate our expectations and standards. Mathematicians refer to this genre of optimal stopping problems as no-information games. This setup is arguably a far cry from most searches for an apartment, a partner, or even a secretary. Imagine instead that we had some kind of objective criterion. If every secretary, for instance, had taken a typing exam scored by percentile in the fashion of the SAT or GRE or LSAT. That is, every applicant’s score will tell us where they fall among all the typists who took the test. A 51st percentile typist is just above average. A 75th percentile typist is better than three test takers out of four, and so on. Suppose that our applicant pool is representative of the population at large and isn’t skewed or self-selected in any way. Furthermore, suppose we decide that typing speed is the only thing that matters about our applicants. Then we have what mathematicians call full information, and everything changes. No buildup of experience is needed to set a standard, as the seminal 1966 paper on the problem put it. And a profitable choice can sometimes be made immediately. In other words, if a 95th percentile applicant happens to be the first one to evaluate, we know it instantly and can confidently hire her on spot. That is, of course, assuming we don’t think there’s a 96th percentile applicant in the pool. And there’s the rub. If our goal is, again, to get the single best person for the job, we still need to weigh the likelihood that there’s a stronger applicant out there. However, the fact that we have full information gives us everything we need to calculate those odds directly. The chance that our next applicant is in the 96th percentile or higher will always be 1 in 20, for instance. Thus, the decision of whether to stop comes down entirely to how many applicants we have left to see. Full information means that we don’t need to look before we leap. We can instead use the threshold rule, where we immediately accept an applicant if she is above a certain percentile. We don’t need to look at an initial group of applicants to set this threshold, but we do, however, need to be keenly aware of how much looking remains available. The math shows that when there are a lot of applicants left in the pool, you should pass up even a very good applicant in the hopes of finding someone still better than that. But as your options dwindle, you should be prepared to hire anyone who’s simply better than average. It’s a familiar, if not exactly inspiring message. In the face of slim pickings, lower your standards. It also makes clear the converse. With more fish in the sea, raise them. In both cases, crucially, the math tells you exactly by how much. The easiest way to understand the numbers for this scenario is to start at the end and think backward. If you’re down to the last applicant, of course, you’re necessarily forced to choose her. But when looking at the next to last applicant, the question becomes, is she above the 50th percentile? If yes, then hire her. If not, it’s worth rolling the dice on the last applicant instead, since her odds of being above the 50th percentile are 50-50 by definition. Likewise, you should choose the third to last applicant if she’s above the 69th percentile, the fourth to-last applicant if she’s above the 78th, and so on. Being more choosy, the more applicants are left. No matter what, never hire someone who’s below average unless you’re totally out of options. And since you’re still interested only in finding the very best person in the applicant pool, never hire someone who isn’t the best you’ve seen so far. The chance of ending up with a single best applicant in this full information version of the secretary problem comes to 58 percent. (Time 0:17:21)
  • Raise Standards When Options Are Plentiful
    • With full information (you can measure applicants exactly) the decision to hire depends solely on how many applicants remain.
    • When many candidates remain, pass up even very good applicants in hopes of a better one; as options dwindle, lower your threshold.
    • Never hire someone below average unless you’re out of options, and never hire anyone who isn’t the best you’ve seen so far.
    • Specific thresholds work backward from the end: last applicant must be taken; second-to-last accepted if above 50th percentile; third-to-last if above 69th; fourth-to-last if above 78th, etc.
    • This full-information strategy raises your success rate to about 58%, better than the 37% from the no-information 37% rule. Transcript: Host / Narrator (Algorithms to Live By episode) But as your options dwindle, you should be prepared to hire anyone who’s simply better than average. It’s a familiar, if not exactly inspiring message. In the face of slim pickings, lower your standards. It also makes clear the converse. With more fish in the sea, raise them. In both cases, crucially, the math tells you exactly by how much. The easiest way to understand the numbers for this scenario is to start at the end and think backward. If you’re down to the last applicant, of course, you’re necessarily forced to choose her. But when looking at the next to last applicant, the question becomes, is she above the 50th percentile? If yes, then hire her. If not, it’s worth rolling the dice on the last applicant instead, since her odds of being above the 50th percentile are 50-50 by definition. Likewise, you should choose the third to last applicant if she’s above the 69th percentile, the fourth to-last applicant if she’s above the 78th, and so on. Being more choosy, the more applicants are left. No matter what, never hire someone who’s below average unless you’re totally out of options. And since you’re still interested only in finding the very best person in the applicant pool, never hire someone who isn’t the best you’ve seen so far. The chance of ending up with a single best applicant in this full information version of the secretary problem comes to 58 percent. Still far from a guarantee, but considerably better than the 37 percent success rate offered by the 37 percent rule in the no information game. (Time 0:20:30)
  • Set A Price Threshold When Selling A House
    • When offers have known dollar values and waiting costs money, set a monetary threshold before listing and accept the first offer above it.
    • Threshold depends only on cost of waiting versus expected offer range, so hold firm and don’t lower it later. Transcript: Host / Narrator (Algorithms to Live By episode) If we don’t have to worry about the offers or our savings running out, then we can think purely in terms of what we can expect to gain or lose by waiting for a better deal. If we decline the current offer, will the chance of a better one, multiplied by how much better we expect it to be, more than compensate for the cost of the wait? As it turns out, the math here is quite clean, giving us an explicit function for stopping price as a function of the cost of waiting for an offer. This particular mathematical result doesn’t care whether you’re selling a mansion worth millions or a ramshackle shed. The only thing it cares about is the difference between the highest and lowest offers you’re likely to receive. By plugging in some concrete figures, we can see how this algorithm offers us a considerable amount of explicit guidance. For instance, let’s say the range of offers we’re expecting runs from $400,000 to $500,000. First, if the cost of waiting is trivial, we’re able to be almost infinitely choosy. If the cost of getting another offer is only $1, we’ll maximize our earnings by waiting for someone willing to offer us $499,552 and not a dime less. If waiting costs $2,000 an offer, we should hold out for an even $480,000. In a slow market, where waiting costs $10,000 an offer, we should take anything over $455,279. Finally, if waiting costs half or more of our expected range of offers, in this case $50,000, then there’s no advantage whatsoever to holding out. We’ll do best by taking the very first offer that comes along and calling it done. Beggars can’t be choosers. The critical thing to note in this problem is that our threshold depends only on the cost of search. Since the chances of the next offer being a good one and the cost of finding, never change, our stopping price has no reason to ever get lower as the search goes on, regardless of our luck. (Time 0:25:35)
  • Parking Strategy Depends On Occupancy Rate
    • Urban parking is an optimal stopping problem where the switch-from-search distance depends on occupancy rates; higher occupancy forces earlier acceptance.
    • With 99% occupancy start looking ~70 spots away; at 85% occupancy wait until half a block. Transcript: Host / Narrator (Algorithms to Live By episode) Another domain where optimal stopping problems abound, and where looking back is also generally ill-advised, is the car. Motorists feature in some of the earliest literature on the secretary problem, and the framework of constant forward motion makes almost every car trip decision into a stopping problem. The search for a restaurant, the search for a bathroom, and most acutely for urban drivers, the search for a parking space. Who better to talk to about the ins and outs of parking than the man described by the Los Angeles Times as the parking rock star, UCLA Distinguished Professor of Urban Planning Donald Shoup. We drove down from Northern California to visit him, reassuring Shoup that we’d be leaving plenty of time for unexpected traffic. As for planning on unexpected traffic, I think you should plan on expected traffic, he replied. Shoup is perhaps best known for his book The High Cost of Free Parking, and he has done much to advance the discussion and understanding of what really happens when someone drives to Their destination. We should pity the poor driver. The ideal parking space, as Shoup models it, is one that optimizes a precise balance between the sticker price of the space, the time and inconvenience walking, the time taken seeking The space, which varies wildly with destination, time of day, etc., and the gas burned in doing so. The equation changes with the number of passengers in the car who can split the monetary cost of a space, but not the search time or the walk. At the same time, the driver needs to consider that the area with the most parking supply may also be the area with the most demand. Parking has a game-theoretic component as you try to outsmart the other drivers on the road while they in turn are trying to outsmart you. That said, many of the challenges of parking boil down to a single number, the occupancy rate. This is the proportion of all parking spots that are currently occupied. If the occupancy rate is low, it’s easy to find a good parking spot. If it’s high, finding anywhere at all to park is a challenge. Shoup argues that many of the headaches of parking are consequences of cities adopting policies that result in extremely high occupancy rates. If the cost of parking in a particular location is too low, or horrors, nothing at all, then there is a high incentive to park there rather than to park a little farther away and walk. So everybody tries to park there, but most of them find the spaces are already full, and people end up wasting time and burning fossil fuel as they cruise for a spot. Shoop’s solution involves installing digital parking meters that are capable of adaptive prices that rise with demand. This has now been implemented in downtown San Francisco. The prices are set with a target occupancy rate in mind, and Shoop argues that this rate should be somewhere around 85%, a radical drop from the nearly 100% packed curbs of most major Cities. As he notes, when occupancy goes from 90% to 95%, it accommodates only 5% more cars, but doubles the length of everyone’s search. The key impact that occupancy rate has parking strategy becomes clear once we recognize that parking is an optimal stopping problem. As you drive along the street, every time you see the occasional empty spot, you have to make a decision. Should you take the spot or go a little closer to your destination and try your luck? Assume you’re on an infinitely long road with parking spots evenly spaced, and your goal is to minimize the distance you end up walking to your destination. Then the solution is the look-then rule. The optimally stopping driver should pass up all vacant spots occurring more than a certain distance from the destination, and then take the first space that appears thereafter. And the distance at which to switch from looking to leaping depends on the proportion of spots that are likely to be filled, the occupancy rate. If this infinite street has a big city occupancy rate of 99%, with just 1% of spots vacant, then you should take the first spot you see starting at almost 70 spots, more than a quarter mile, From your destination. But if Shoup has his way and occupancy rates drop to just 85%, you don’t need to start seriously looking until you’re half a block away. Most of us don’t drive on perfectly straight, infinitely long roads. So as with other optimal stopping problems, researchers have considered a variety of tweaks to this basic scenario. For instance, they have studied the optimal parking strategy for cases where the driver can make U-turns. Where fewer parking spaces are available, closer one gets to the destination, and where the driver is in competition against rival drivers also heading to the same destination. But whatever the exact parameters of the problem, more vacant spots are always going to make life easier. (Time 0:29:28)
  • An Oligarch Who Studied Optimal Stopping
    • Boris Berezovsky knew optimal stopping theory yet his political choices led to exile and later apparent suicide after legal battles.
    • His life illustrates that math can’t fully account for politics, rejection, and unpredictable risks. Transcript: Host / Narrator (Algorithms to Live By episode) But that’s when Berezovsky’s luck turned. Shortly after Putin’s election, Berezovsky publicly objected to proposed constitutional reforms that would expand the power of the president. His continued public criticism of Putin led to the deterioration of their relationship. In October 2000, when Putin was asked about Berezovsky’s criticisms, he replied, The state has a cudgel in its hands that you used to hit just once, but on the head. We haven’t used this cudgel yet. The day we get really angry, we won’t hesitate. Berezovsky left Russia permanently the next month, taking up exile in England, where he continued to criticize Putin’s regime. How did Berezovsky decide it was time to leave Russia? Is there a way, perhaps, to think mathematically about the advice to quit while you’re ahead? Berezovsky, in particular, might have considered this very question himself, since the topic he had worked on all the years ago as a mathematician was none other than optimal stopping. He authored the first and so far the only book entirely devoted to the secretary problem. The problem of quitting while you’re ahead has been analyzed under several different guises, but perhaps the most appropriate to Berezovsky’s case, with apologies to Russian oligarchs, Is known as the burglar problem. In this problem, a burglar has the opportunity to carry out a sequence of robberies. Each robbery provides some reward, and there’s a chance of getting away with it each time. But if the burglar is caught, he gets arrested and loses all his accumulated gains. What algorithm should he follow to maximize his expected take? The fact that this problem has a solution is bad news for Heisman’s replays. When the team is trying to lure the old burglar out of retirement for one less job, the Kenny thief need only crunch the numbers. Moreover, the results are pretty intuitive. The number of robberies you should carry out is roughly equal to the chance you get away divided by the chance you get caught. If you’re a skilled burglar and have a 90% chance of pulling off each robbery and a 10% chance of losing it all, then retire after 90 divided by 10 or 9 robberies. A ham-fisted amateur with a 50-50 chance of success? The first time you have nothing to lose, but don’t push your luck more than once. Despite his expertise in optimal stopping, Berezovsky’s story ends sadly. He died in March 2013, found by a bodyguard in the locked bathroom of his house in Berkshire, with a ligature around his neck. The official conclusion of a post-mortem examination was that he had committed suicide, hanging himself after losing much of his wealth through a series of high-profile legal cases Involving his enemies in Russia. Perhaps he should have stopped sooner, amassing just a few tens of millions of dollars, say, and not getting to politics. But alas, that was not his style. (Time 0:35:44)
  • Quit When Risk Ratio Says Stop
    • The burglar problem shows optimal quitting: expected optimal number of risky tries ≈ probability of success divided by probability of failure.
    • Example: with 90% success and 10% capture risk, retire after ~9 robberies to maximize expected take. Transcript: Host / Narrator (Algorithms to Live By episode) The problem of quitting while you’re ahead has been analyzed under several different guises, but perhaps the most appropriate to Berezovsky’s case, with apologies to Russian oligarchs, Is known as the burglar problem. In this problem, a burglar has the opportunity to carry out a sequence of robberies. Each robbery provides some reward, and there’s a chance of getting away with it each time. But if the burglar is caught, he gets arrested and loses all his accumulated gains. What algorithm should he follow to maximize his expected take? The fact that this problem has a solution is bad news for Heisman’s replays. When the team is trying to lure the old burglar out of retirement for one less job, the Kenny thief need only crunch the numbers. Moreover, the results are pretty intuitive. The number of robberies you should carry out is roughly equal to the chance you get away divided by the chance you get caught. If you’re a skilled burglar and have a 90% chance of pulling off each robbery and a 10% chance of losing it all, then retire after 90 divided by 10 or 9 robberies. A ham-fisted amateur with a 50-50 chance of success? The first time you have nothing to lose, but don’t push your luck more than once. (Time 0:36:50)
  • Some Games Have No Rational Stopping Point
    • Some sequential gambles lack any optimal stopping rule because expected value increases without bound, meaning you’ll always be tempted to continue.
    • Example: triple-or-nothing betting (50% chance triple, 50% lose all) has no finite optimal stopping and leads to eventual ruin. Transcript: Host / Narrator (Algorithms to Live By episode) A simple example is the game of triple or nothing. Imagine you have a dollar and can play the following game as many times as you want. Bet all of your money and have a 50% chance of receiving triple the amount and a 50% chance of losing your entire stake. How many times should you play? Despite its simplicity, there is no optimal stopping rule for this problem, since each time you play, your average gains are a little higher. Starting with a dollar, you will get $3 half the time and nothing half the time. So on average, you will expect to end the first round with $1.50 in your pocket. Then if you were lucky in the first round, the two possibilities from the $3 you’ve just won are $9 and $0 for an average return of $4.50 from the second bet. The math shows that you should always keep playing. But if you follow this strategy, you will eventually lose everything. Some problems are better avoided than solved. (Time 0:39:18)
  • People Stop Early Because Time Always Costs Something
    • Humans tend to stop searches earlier than classical models predict, often due to implicit time costs like boredom or life obligations.
    • Experiments show average human success ~31% vs optimal 37%, consistent with acting as if each observation has a small search cost. Transcript: Host / Narrator (Algorithms to Live By episode) Whether it involves secretaries, fiancés, or apartments, life is full of optimal stopping. So the irresistible question is whether, by evolution or education or intuition, we actually do follow the best strategies. At first glance, the answer is no. About a dozen studies have produced the same result. People tend to stop early, leaving better applicants unseen. To get a better sense for these findings, we talked to UC Riverside’s Amnon Rappaport, who’s been running optimal stopping experiments in the laboratory for more than 40 years. The study that most closely follows the classical secretary problem was run in the 1990s by Rappaport and his collaborator Daryl Seale. In this study, people went through numerous repetitions of the secretary problem with either 40 or 80 applicants each time. The overall rate at which people found the best possible applicant was pretty good, about 31%, not far from the optimal 37%. Most people acted in a way that was consistent with the look than leap rule. But they leapt sooner than they should have, more than four-fifths of the time. Rappaport told us that he keeps this in mind when solving optimal stopping problems in his own life. Inserting for an apartment, for instance, he fights his own urge to commit quickly. Despite the fact that by nature I am very impatient and I want to take the first department, I try to control myself. But that impatience suggests another consideration that isn’t taken into account in the classical secretary problem, the role of time. After all, the whole time you’re searching for a secretary, you don’t have a secretary. What’s more, you’re spending the day conducting interviews instead of getting your own work done. This type of cost offers a potential explanation for why people stop early when solving a secretary problem in a lab. C. L. Rapoport showed that if the cost of seeing each applicant is imagined to be, for instance, 1% of the value of finding the best secretary, then the optimal strategy would perfectly align With where people actually switched from looking to leaping in their experiment. The mystery is that in Seal and Rapoport’s study, there wasn’t a cost for search. So why might people in the laboratory be acting like there was one? Because for people, there’s always a time caught. It doesn’t come from the design of the experiment. It comes from people’s lives. The endogenous time costs of searching, which aren’t usually captured by optimal stopping models, might thus provide an explanation for why human decision-making routinely diverges From the prescriptions of those models. As optimal stopping researcher Neil Bearden puts it, after searching for a while, we humans just tend to get bored. It’s not irrational to get bored, but it’s hard to model that rigorously. But this doesn’t make optimal stopping problems less important. It actually makes them more important because the flow of time turns all decision-making into optimal stopping. The theory of optimal stopping is concerned with the problem of choosing a time to take a given action, opens the definitive textbook on optimal stopping. And it’s hard to think of a more concise description of the human condition. We decide the right time to buy stocks and the right time to sell them, sure, but also the right time to open the bottle of wine we’ve been keeping around for a special occasion. The right moment to interrupt someone. The right moment to kiss them. Viewed this way, the secretary problem’s most fundamental yet most unbelievable assumption, its strict seriality, its inexorable one-way march, is revealed to be the nature of Time itself. As such, the explicit premise of the optimal stopping problem is the implicit premise of what it is to be alive. It’s this that forces us to decide based on possibilities we’ve not yet seen. This that forces us to embrace high rates of failure even when acting optimally. No choice recurs. We get similar choices again, but never that exact one. Hesitation, inaction, is just as irrevocable as action. With the motorist locked on the one-way road is to space. We are to the fourth dimension. (Time 0:40:46)