eBook - ePub
Algorithms to Live By
The Computer Science of Human Decisions
Brian Christian, Griffiths
This is a test
Share book
- English
- ePUB (mobile friendly)
- Available on iOS & Android
eBook - ePub
Algorithms to Live By
The Computer Science of Human Decisions
Brian Christian, Griffiths
Book details
Book preview
Table of contents
Citations
Frequently asked questions
How do I cancel my subscription?
Can/how do I download books?
At the moment all of our mobile-responsive ePub books are available to download via the app. Most of our PDFs are also available to download and we're working on making the final remaining ones downloadable now. Learn more here.
What is the difference between the pricing plans?
Both plans give you full access to the library and all of Perlegoâs features. The only differences are the price and subscription period: With the annual plan youâll save around 30% compared to 12 months on the monthly plan.
What is Perlego?
We are an online textbook subscription service, where you can get access to an entire online library for less than the price of a single book per month. With over 1 million books across 1000+ topics, weâve got you covered! Learn more here.
Do you support text-to-speech?
Look out for the read-aloud symbol on your next book to see if you can listen to it. The read-aloud tool reads text aloud for you, highlighting the text as it is being read. You can pause it, speed it up and slow it down. Learn more here.
Is Algorithms to Live By an online PDF/ePUB?
Yes, you can access Algorithms to Live By by Brian Christian, Griffiths in PDF and/or ePUB format, as well as other popular books in Computer Science & Computer Science General. We have over one million books available in our catalogue for you to explore.
Information
1 Optimal Stopping
When to Stop Looking
Though all Christians start a wedding invitation by solemnly declaring their marriage is due to special Divine arrangement, I, as a philosopher, would like to talk in greater detail about this âŚ
âJOHANNES KEPLER
If you prefer Mr. Martin to every other person; if you think him the most agreeable man you have ever been in company with, why should you hesitate?
âJANE AUSTEN, EMMA
Itâs such a common phenomenon that college guidance counselors even have a slang term for it: the âturkey drop.â High-school sweethearts come home for Thanksgiving of their freshman year of college and, four days later, return to campus single.
An angst-ridden Brian went to his own college guidance counselor his freshman year. His high-school girlfriend had gone to a different college several states away, and they struggled with the distance. They also struggled with a stranger and more philosophical question: how good a relationship did they have? They had no real benchmark of other relationships by which to judge it. Brianâs counselor recognized theirs as a classic freshman-year dilemma, and was surprisingly nonchalant in her advice: âGather data.â
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.
As we have seen, this Catch-22, this angsty freshman cri de coeur, is what mathematicians call an âoptimal stoppingâ problem, and it may actually have an answer: 37%.
Of course, it all depends on the assumptions youâre willing to make about love.
The Secretary Problem
In any optimal stopping problem, the crucial dilemma is not which option to pick, but how many options to even consider. These problems turn out to have implications not only for lovers and renters, but also for drivers, homeowners, burglars, and beyond.
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 midcentury 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 fiftysome years 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 read about the problem in â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. Shoenfield, â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 eighth-century India; it was heavy-handedly âEuropeanizedâ in the fifteenth century, as its shahs became kings, its viziers turned to queens, and its elephants became bishops. Likewise, optimal stopping problems have had a number of incarnations, each reflecting the predominating concerns of its time. In the nineteenth century such problems were typified by baroque lotteries and by women choosing male suitors; in the early twentieth century by holidaying motorists searching for hotels and by male suitors choosing women; and in the paper-pushing, male-dominated mid-twentieth 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 who 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-in-5 chance of being the best so far, the sixth has a 1-in-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.a. the first applicant, period) is rash. If 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 ones.
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-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.
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âll 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: 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.
How to optimally choose a secretary.
As it turns out, following this optimal strategy ultimately gives us a 37% chance of hiring the best applicant; itâs one of the problemâs curious mathematical symmetries that the strategy itself and its chance of success work out to the very same number. The table above shows the optimal strategy for the secretary problem with different numbers of applicants, demonstrating how the chance of successâlike the point to switch from looking to leapingâconverges on 37% as the number of applicants increases.
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 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. If we were hiring at random, for instance, then in a pool of a hundred 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 a hundred 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.
Loverâs Leap
The passion between the sexes has appeared in every age to be so nearly the same that it may always be considered, in algebraic language, as a given quantity.
âTHOMAS MALTHUS
I married the first man I ever kissed. When I tell this to my children they just about throw up.
âBARBARA BUSH
Before he became a professor of operations research at Carnegie Mellon, Michael Trick was a graduate student, looking for love. â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 eighteen to forty, the 37% Rule gave age 26.1 years as the point at which to switch from looking to leaping. A number that, as it happened, was exactly Trickâ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 if she was Perfect (the assumptions of the model donâ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.â
Mathematicians have been having trouble with love since at least the seventeenth century. The legendary astronomer Johannes Kepler is today perhaps best remembered for discovering that planetary orbits are elliptical and for being a crucial part of the âCopernican Revolutionâ that included Galileo and Newton and upended humanityâs sense of its place in the heavens. But Kepler had terrestrial concerns, too. After the death of his first wife in 1611, Kepler embarked on a long and arduous quest to remarry, ultimately courting a total of eleven women. Of the first four, Kepler liked the fourth the best (âbecause of her tall build and athletic bodyâ) but did not cease his search. âIt would have been settled,â Kepler wrote, âhad not both love and reason forced a fifth woman on me. This one won me over with love, humble loyalty, economy of household, diligence, and the love she gave the stepchildren.â
âHowever,â he wrote, âI continued.â
Keplerâs friends and relations went on making introductions for him, and he kept on looking, but halfheartedly. His thoughts remained with number five. After eleven courtships in total, he decided he would search no further. âWhile preparing to travel to Regensburg, I returned to the fifth woman, declared myself, and was accepted.â Kepler and ...