Algorithms to Live By

Brian Christian & Tom Griffiths

13 annotations Mar 2022 data

1. Optimal Stopping: When to Stop Looking

  • The nature of serial monogamy, writ large, is that its practitioners are confronted with a fundamental, unavoidable problem. When have you met enough people to know who your best match is? And what if acquiring the data costs you that very match? It seems the ultimate Catch-22 of the heart.
  • The 37% Rule* derives from optimal stopping's most famous puzzle, which has come to be known as the "secretary problem."
  • 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
  • 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 who doesn't exist
  • Instead, the optimal solution takes the form of what we'll call the Look-Then-Leap 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.
  • 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: look at the first 37% of the applicants,* choosing none, then be ready to leap for anyone better than all those you've seen so far.
  • 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 the 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.
  • Then the math says you should keep looking noncommittally until you've seen 61% of applicants, and then only leap if someone in the remaining 39% of the pool proves to be the best yet
  • what makes for a good or a 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."
  • In other words, if a 95th-percentile applicant happens to be the first one we evaluate, we know it instantly and can confidently hire them on the spot—that is, of course, assuming we don't think there's a 96th-percentile applicant in the pool.
  • Full information means that we don't need to look before we leap
  • Threshold Rule, where we immediately accept an applicant if they are above a certain percentile. We don't need to look at an initial group of candidates to set this threshold—but we do, however, need to be keenly aware of how much looking remains available.
  • The chance of ending up with the single best applicant in this full-information version of the secretary problem comes to 58%—still far from a guarantee, but considerably better than the 37% success rate offered by the 37% Rule in the no-information game. If you have all the facts, you can succeed more often than not, even as the applicant pool grows arbitrarily large.