Algorithms to Live By

by Brian Christian

  Gilbert and Mosteller used the same approach to derive the series of thresholds that should be used in the full-information secretary problem. The thresholds themselves are not described by a simple mathematical formula, but some approximations appear in their paper. The simplest approximation gives a threshold of tk = 1/(1 + 0.804/k + 0.183/k2) for applicant n − k. If the probability of a random applicant being better than applicant n − k is less than tk, then you should take that applicant. Because the denominator increases—at an increasing rate—as k increases, you should be rapidly lowering your threshold as time goes on.

  many more variants of the secretary problem: Freeman, “The Secretary Problem and Its Extensions” summarizes a large number of these variants. Here’s a quick tour of some of the most useful results.

  If the number of applicants is equally likely to be any number from 1 to n, then the optimal rule is to view the first n/e2 (which is approximately 13.5% of n) and take the next candidate better than the best seen so far, with a chance of success of 2/e2 (Presman and Sonin, “The Best Choice Problem for a Random Number of Objects”).

  If the number of applicants is potentially infinite, but the search stops after each applicant with probability p, the optimal rule is to view the first 0.18/p applicants, with a 23.6% chance of success (ibid.).

  Imagine you want to find the best secretary, but the value of doing so decreases the longer you search. If the payoff for finding the best secretary after viewing k applicants is dk, then the strategy that maximizes the expected payoff sets a threshold based on a number of applicants that is guaranteed to be less than 1/(1 − d) as the total number of applicants becomes large (Rasmussen and Pliska, “Choosing the Maximum”). If d is close to 1, then an approximation to the optimal strategy is to view the first −0.4348/log d applicants and then take the next candidate better than any seen so far. Following this strategy can result in viewing only a handful of applicants, regardless of the size of the pool.

  One way in which real life differs from idealized recruitment scenarios is that the goal might not be to maximize the probability of getting the best secretary. A variety of alternatives have been explored. Chow et al., “Optimal Selection Based on Relative Rank,” showed that if the goal is to maximize the average rank of the selected candidate, a different kind of strategy applies. Rather than a single threshold on the relative rank of the applicant, there is a sequence of thresholds. These thresholds increase as more candidates are observed, with the interviewer becoming less stringent over time. For example, with four applicants, the minimum relative rank a candidate needs to have to stop the search is 0 for the first applicant (never stop on the first), 1 for the second (stop only if they are better than the first), 2 for the third (stop if best or second best), and 4 for the fourth (just stop already!). Following this strategy yields an average expected rank of 17⁄8, better than the (1 + 2 + 3 + 4)/4 = 21⁄2 that would result from picking an applicant at random. The formula for the optimal thresholds is found by backward induction, and is complicated—we refer interested readers to the original paper.

  You can think about the difference between the classical secretary problem and the average-rank case in terms of how they assign payoffs to different ranks. In the classical problem, you get a payoff of 1 for picking the best and 0 for everybody else. In the average-rank case, you get a payoff equal to the number of applicants minus the rank of the selected applicant. There are obvious ways to generalize this, and multi-threshold strategies similar to the one that maximizes the average rank work for any payoff function that decreases as the rank of the applicant increases (Mucci, “On a Class of Secretary Problems”). Another interesting generalization—with important implications for discerning lovers—is that if the payoff is 1 for choosing the best but −1 for choosing anybody else (with 0 for making no choice at all), you should go through a proportion of applicants given by , then take the first person better than all seen so far (or nobody if they all fail this criterion) (Sakaguchi, “Bilateral Sequential Games”). So think hard about your payoff function before getting ready to commit!

  But what if you don’t just care about finding the best person, but about how much time you have together? Ferguson, Hardwick, and Tamaki, in “Maximizing the Duration of Owning a Relatively Best Object,” examined several variants on this problem. If you just care about maximizing the time you spend with the very best person in your set of n, then you should look at the first 0.204n + 1.33 people and leap for the next person better than all of them. But if you care about maximizing the amount of time you spend with somebody who is the best of all the people seen so far, you should just look at a proportion corresponding to 1/e2 ≈ 13.5%. These shorter looking periods are particularly relevant in contexts—such as dating—where the search for a partner might take up a significant proportion of your life.

  It turns out that it’s harder to find the second-best person than it is to find the best. The optimal strategy is to pass over the first half of the applicants, then choose the next applicant who is second best relative to those seen so far (Rose, “A Problem of Optimal Choice and Assignment”). The probability of success is just 1/4 (as opposed to 1/e for the best). So you’re better off not trying to settle.

  Finally, there are also variants that recognize the fact that while you are looking for a secretary, your applicants are themselves looking for a job. The added symmetry—which is particularly relevant when the scenario concerns dating—makes the problem even more complicated. Peter Todd, a cognitive scientist at Indiana University, has explored this complexity (and how to simplify it) in detail. See Todd and Miller, “From Pride and Prejudice to Persuasion Satisficing in Mate Search,” and Todd, “Coevolved Cognitive Mechanisms in Mate Search.”

  Selling a house is similar: The house-selling problem is analyzed in Sakaguchi, “Dynamic Programming of Some Sequential Sampling Design”; Chow and Robbins, “A Martingale System Theorem and Applications”; and Chow and Robbins, “On Optimal Stopping Rules.” We focus on the case where there are potentially infinitely many offers, but these authors also provide optimal strategies when the number of potential offers is known and finite (which are less conservative—you should have a lower threshold if you only have finitely many opportunities). In the infinite case, you should set a threshold based on the expected value of waiting for another offer, and take the first offer that exceeds that threshold.

  stopping price as a function of the cost of waiting: Expressing both the offer price p and cost of waiting for another offer c as fractions of our price range (with 0 as the bottom of the range and 1 as the top), the chance that our next offer is better than p is simply 1 − p. If (or when) a better offer arrives, the average amount we’d expect to gain relative to p is just (1−p)⁄2. Multiplying these together gives us the expected outcome of entertaining another offer, and this should be greater than or equal to the cost c to be worth doing. This equation (1 − p) ((1−p)⁄2) ≥ c can be simplified to , and solving it for p gives us the answer , as charted here.

  “The first offer we got was great”: Laura Albert McLay, personal interview, September 16, 2014.

  to model how people look for jobs: The formulation of job search as an optimal stopping problem is dealt with in Stigler, “The Economics of Information,” and Stigler, “Information in the Labor Market.” McCall, “Economics of Information and Job Search,” proposed using a model equivalent to the solution to the house-selling problem, and Lippman and McCall, “The Economics of Job Search,” discusses several extensions to this model. Just as the secretary problem has inspired a vast array of variants, economists have refined this simple model in a variety of ways to make it more realistic: allowing multiple offers to arrive on the same day, tweaking the costs for the seller, and incorporating fluctuation in the economy during the search. A good review of optimal stopping in a job-seeking context can be found in Rogerson, Shimer, and Wright, Search-Theoretic Models of the Labor Market.

  won’t be above your threshold now: As
a survey of the job-search problem puts it: “Assume previously rejected offers cannot be recalled, although this is actually not restrictive because the problem is stationary, so an offer that is not acceptable today will not be acceptable tomorrow” (ibid.).

  “parking for the faculty”: Clark Kerr, as quoted in “Education: View from the Bridge,” Time, November 17, 1958.

  “plan on expected traffic”: Donald Shoup, personal correspondence, June 2013.

  implemented in downtown San Francisco: More information on the SFpark system developed by the SFMTA, and its Shoup-inspired dynamic pricing, can be found at http://sfpark.org/how-it-works/pricing/. (Shoup himself is involved in an advisory role.) This program began taking effect in 2011, and is the first project of its kind in the world. For a recent analysis of the effects of the program, see Millard-Ball, Weinberger, and Hampshire, “Is the Curb 80% Full or 20% Empty?”

  when occupancy goes from 90% to 95%: Donald Shoup, personal interview, June 7, 2013. To be precise, the increase from 90% to 95% occupancy reflects an increase of 5.555 … percent.

  Assume you’re on an infinitely long road: The basic parking problem, as formulated here, was presented as a problem in DeGroot, Optimal Statistical Decisions. The solution is to take the first empty spot less than −log 2 / log(1−p) spots from the destination, where p is the probability of any given space being available.

  you don’t need to start seriously looking: Chapter 17 of Shoup’s The High Cost of Free Parking discusses the optimal on-street parking strategy when pricing creates an average of one free space per block, which, as Shoup notes, “depends on the conflict between greed and sloth” (personal correspondence). The question of whether to “cruise” for cheap on-street spots or to pay for private parking spaces is taken up in Shoup’s chapter 13.

  a variety of tweaks to this basic scenario: Tamaki, “Adaptive Approach to Some Stopping Problems,” allowed the probability of a spot being available to vary based on location and considered how these probabilities could be estimated on the fly. Tamaki, “Optimal Stopping in the Parking Problem with U-Turn,” added the possibility of U-turns. Tamaki, “An Optimal Parking Problem,” considered an extension to DeGroot’s model where parking opportunities are not assumed to be a discrete set of spots. Sakaguchi and Tamaki, “On the Optimal Parking Problem in Which Spaces Appear Randomly,” used this continuous formulation and allowed the destination to be unknown. MacQueen and Miller, “Optimal Persistence Policies,” independently considered a continuous version of the problem that allows circling the block.

  “I ride my bike”: Donald Shoup, personal interview, June 7, 2013.

  Forbes magazine identified Boris Berezovsky: Forbes, “World’s Billionaires,” July 28, 1997, p. 174.

  one of a new class of oligarchs: Paul Klebnikov, “The Rise of an Oligarch,” Forbes, September 9, 2000.

  “to hit just once, but on the head”: Vladimir Putin, interview with the French newspaper Le Figaro, October 26, 2000.

  book entirely devoted to the secretary problem: Berezovsky and Gnedin, Problems of Best Choice.

  analyzed under several different guises: There are various ways to approach the problem of quitting when you’re ahead. The first is maximizing the length of a sequence of wins. Assume you’re tossing a coin that has a probability p of coming up heads. You pay c dollars for each chance to flip the coin, and you get $1.00 when it comes up heads but lose all your accumulated gains when it comes up tails. When should you stop tossing the coin? The answer, as shown by Norman Starr in 1972, is to stop after r heads, where r is the smallest number such that pr+1 ≤ c. So if it’s a regular coin with p = 1/2, and it costs $0.10 to flip the coin, you should stop as soon as you get four heads in a row. The analysis of runs of heads appears in Starr, “How to Win a War if You Must,” where it is presented as a model for winning a war of attrition. A more comprehensive analysis is presented in Ferguson, “Stopping a Sum During a Success Run.”

  Maximizing the length of a run of heads is a pretty good analogy for some kinds of business situations—for a sequence of deals that cost c to set up, have a probability p of working out, and pay d on success but wipe out your gains on failure, you should quit after making r dollars such that pr/d+1 ≤ c/d. Ambitious drug dealers, take note.

  In the burglar problem discussed in the text, assume the average amount gained from each robbery is m and the probability of getting away with the robbery is q. But if the burglar is caught, which happens with probability 1 − q, he loses everything. The solution: quit when the accumulated gains are greater than or equal to mq/(1 − q). The burglar problem appears in Haggstrom, “Optimal Sequential Procedures When More Than One Stop Is Required,” as part of a more complex problem in which the burglar is also trying to decide which city to move to.

  found by a bodyguard: See, e.g., “Boris Berezovsky ‘Found with Ligature Around His Neck,’” BBC News, March 28, 2013, http://www.bbc.com/news/uk-21963080.

  official conclusion of a postmortem examination: See, e.g., Reuters, “Berezovsky Death Consistent with Hanging: Police,” March 25, 2013, http://www.reuters.com/article/2013/03/25/us-britain-russia-berezovsky-postmortem-idUSBRE92O12320130325.

  “Berezovsky would not give up”: Hoffman, The Oligarchs, p. 128.

  there is no optimal stopping rule: One condition for an optimal stopping rule to exist is that the average reward for stopping at the best possible point be finite (see Ferguson, Optimal Stopping and Applications). The “triple or nothing” game violates this condition—if heads come up k times followed by one tail, the best possible player gets 3k − 1 as a payoff, stopping right before that tail. The probability of this is 1/2k+1. The average over k is thus infinite.

  If you’re thinking that this could be resolved by assuming that people value money less the more they have—that tripling the monetary reward may not be tripling the utility people assign to that money—then there’s a simple work-around: you still get a game with no optimal stopping rule just by offering rewards that triple in their utility. For example, if the utility you assign to money increases as a logarithmic function of the amount of money, then the game becomes “cube or nothing”—the amount of money you could receive on the next gamble is raised to the power of three each time you win.

  Intriguingly, while there is no optimal stopping rule for “triple or nothing,” where your entire fortune is always on the line, there are nonetheless good strategies for playing games like this when you can choose how much of your bankroll to bet. The so-called Kelly betting scheme, named after J. L. Kelly Jr. and first described in Kelly, “A New Interpretation of Information Rate,” is one example. In this scheme, a player can maximize his rate of return by betting a proportion of (p(b+1)−1)⁄b of his bankroll on each of a sequence of bets that pay off b + 1 times the original stake with probability p. For our triple or nothing game, b = 2 and p = 0.5, so we should bet a quarter of our bankroll each time—not the whole thing, which inevitably leads to bankruptcy. An accessible history of Kelly betting appears in Poundstone, Fortune’s Formula.

  “pass through this world but once”: The provenance of this quotation is not fully certain, although it has been cited as a Quaker saying since the second half of the nineteenth century, and appears to have been attributed to Grellet since at least 1893. For more, see W. Gurney Benham, Benham’s Book of Quotations, Proverbs, and Household Words, 1907.

  “Spend the afternoon”: Dillard, Pilgrim at Tinker Creek.

  most closely follows the classical secretary problem: Seale and Rapoport, “Sequential Decision Making with Relative Ranks.”

  leapt sooner than they should have: Ibid. The typical place where people switched from looking to leaping was 13 applicants out of 40, and 21 applicants out of 80, or 32% and 26%, respectively.

  “by nature I am very impatient”: Amnon Rapoport, personal interview, June 11, 2013.

  Seale and Rapoport showed: Seale and Rapoport, “Sequential Decision Making with Relative Ranks.”

  “
It’s not irrational to get bored”: Neil Bearden, personal correspondence, June 26, 2013. See also Bearden, “A New Secretary Problem.”

  turns all decision-making into optimal stopping: This kind of argument was first made by Herbert Simon, and it was one of the contributions for which he received the Nobel Prize. Simon began his remarkable career as a political scientist, writing a dissertation on the perhaps unpromising topic of administrative behavior. As he dug into the problem of understanding how organizations composed of real people make decisions, he experienced a growing dissatisfaction with the abstract models of decision-making offered by mathematical economics—models that line up with the intuition that rational action requires exhaustive consideration of our options.

  Simon’s investigation of how decisions actually get made in organizations made it clear to him that these assumptions were incorrect. An alternative was needed. As he put it in “A Behavioral Model of Rational Choice,” “the task is to replace the global rationality of economic man with a kind of rational behavior that is compatible with the access to information and the computational capacities that are actually possessed by organisms, including man, in the kinds of environments in which such organisms exist.”

  The kind of solution that Simon proposed as a more realistic account of human choice—what he dubbed “satisficing”—uses experience to set some threshold for a satisfactory, “good enough” outcome, then takes the first option to exceed that threshold. This algorithm has the same character as the solutions to the optimal stopping problems we have considered here, where the threshold is either determined by spending some time getting a sense for the range of options (as in the secretary problem) or based on knowing the probability of different outcomes. Indeed, one of the examples Simon used in his argument was that of selling a house, with a similar kind of solution to that presented here.