Algorithms to Live By
The Computer Science of Human Decisions
Introduction
As of today’s date, Algorithms to Live By (AtLB) scores an average of 4.13 / 5.00 across over 2.5k ratings on goodreads.
AtLB made the MiT Technology Review Best Books of 2016 and Forbes’ Must Read Brain Books of the same year.
Summary
AtLB is a captivating read for those unfamiliar with the intricacies of computer science and how it manifests in our daily lives. Whether it’s deciding on a new restaurant to try, efficiently finding your next home, or optimizing your sock drawer, this book unveils how the brilliance of computer science has already addressed these everyday dilemmas. The authors guide us through the unexpected implications that computer science offers, presented in a manner that makes it easily accessible to a wider audience under the umbrella of popular science. While they skillfully refrain from downplaying its impact, reading this book will undoubtedly reshape your perception of sorting and problem-solving
An Overview of the Book
Each of the book’s eleven chapters delves into specific problem domains, unraveling the algorithms crafted to tackle them. From seemingly ‘simple’ tasks like optimized sorting of library books to the profound insights into behavioural economics explored in the game theory chapter, the book covers a spectrum of complexity in the problems addressed. The authors skillfully illustrate these concepts, infusing the text with a wealth of relatable examples, making it approachable even for those not well-versed in numerical intricacies.
In the sections below, I will explore some of the more engaging aspects of the book’s content.
A Gentle Introduction to Operational Research
The authors skillfully address prevalent misconceptions about both computer science and human behavior in a manner that resonates with their audience. They challenge the notion that humans are too fuzzy-minded and fallible to benefit from optimization, emphasizing that many real-world challenges can indeed be optimised, albeit within defined parameters. Although certain problems may prove intractable due to an overwhelming number of potential solutions, the authors adeptly navigate this complexity by outlining how problems can be defined at their outset.
The introductory chapter poignantly captures these concepts through a relatable scenario — the search for the perfect New York apartment. By briefly exploring the optimal stopping problem in this context—whether to make an offer for an apartment or risk losing out on potentially the best one on the market, the authors provide readers with a glimpse into the fascinating direction of the book.
“…spend 37% of your apartment hunt (eleven days, if you’ve given yourself a month for the search) noncommittally exploring options. Leave the checkbook at home; you’re just calibrating. But after that point, be prepared to immediately commit - deposit and all - to the very first place that beats whatever you’ve already seen.” [2, p. 2]
At that point, the authors hit the reader with a little taste of the magic in this book - that this problem is in many ways solved. That this same type of solution can be applied to a range of real world problems from parking your car to choosing a long-term partner, the concept that there exists a proof that at 37% of your search time you should immediately flip to committing has an almost Douglas Adams sort of quality to it.
42: the “Answer to the Ultimate Question of Life, the Universe, and Everything” [3]
Optimal Stopping
Chapter 1 of the book dedicates more to explaining the debated origins of what has become known as ‘The Secretary Problem’ - a common description of the Catch-22 described in the introduction. In the context of hiring an employee for example, hiring at random regardless of the candidate’s performance from a pool of 100 candidates would result in success for the employer on average 1% of the time. Success implies selecting the best applicant available in the pool.
By following the optimal stopping strategy, the average chances of hiring the best candidate within the pool increases to 37%. Whether or not you feel that is a good outcome is sort of subjective, but the authors discuss that this outcome remains stable as you scale up the applicant pool while random recruitment does not. For instance, interviewing a million candidates while adhering to optimal stopping could result in successfully recruiting the best candidate 37% of the time. Conversely, random recruitment under the same conditions would yield success at a rate of merely 0.0001%.
The example of scaling up this problem prompted me to consider some potential flaws in human behaviour, that would render any recruitment campaign unfair - optimised or otherwise. Standardising the recruitment process is known to be extremely challenging. Treating the problem like trial design, controlling for factors quickly results in confounding variables. If choosing to minimise variation in the appraisal process, you may consider retaining the same panel for each interview. Ensuring that the panel’s attention and mood are not affected by a demanding interview schedule becomes the next problem. Attempting to control for that results in extending the schedule period, possibly from days to months.
““…no free lunch” (NFL) theorems… for any algorithm, any elevated performance over one class of problems is offset by performance over another class” [4]
The secretary problem is based on the presumption that an interviewer can only make relative comparisons or rankings of candidates, lacking absolute criteria or standardized aptitude tests to measure them against. Such an approach to interviewing, devoid of an objective threshold, would rightly be criticized for its susceptibility to human bias.
Additionally, the secretary problem assumes that an offer of employment would always lead to the candidate accepting, while passing up on a candidate would result in losing out on the possibility of recruiting that candidate forever. Few recruitment campaigns could operate under such conditions, however these assumptions could hold more relevance to scenarios such as selecting a parking space or selecting a long-term partner. Possibly. Although humans are complex organisms, the motivations driving that behaviour may lead to stable, predictable outcomes when considering a larger sample size.
In my assessment, the authors provided an intriguing treatment of optimal stopping solutions, prompting contemplation on their relevance to everyday scenarios and broader implications. However, I remain cautious about generalising this approach to most real-world scenarios, given the potential violations of the problem’s underlying assumptions.
Sorting
At the outset of the book, I realised that I had relied upon sorting algorithms in my professional and everyday life, but was a bit oblivious to their implementation. It is a commonplace need when exploring data to be able to sort columns of values in order to spot trends, identify outliers or problem values within a table. The authors demonstrate that sorting has become so deeply integrated into our lives that we may not even consciously acknowledge its presence or its role in enhancing our efficiency. Some of the more tangible sorting requirements explored are returning library books, the results of your Google search query and managing your Email inbox. Being able to sort based on any ordinal aspect of our data proves pivotal, allowing us to sequence our results and efficiently extract meaning.
‘“What’s the best way to sort a million thirty-two-bit integers?” Without missing a beat, Obama cracked a wry smile and replied, “I think the Bubble Sort would be the wrong way to go.”’ [2, p. 65]
This chapter explores different sort algorithm’s efficacy. Shunning bubble-sort, dancing through insertion-sort, illustrating bucket-sort with actual buckets, talking through merge-sort complete with its own flow chart - the diversity on offer here is unexpected.
Consider the method you choose for sorting your sock drawer. It may seem trivial, but it could have more fundamental implications than you might think. Did you ever imagine that you might be wasting precious moments of your life employing an inefficient insertion sort method? Perhaps the prospect of sock sorting inefficiencies isn’t the most pressing concern, but it does underscore a fascinating point — sorting algorithms, even in the realm of socks, can have a surprising impact on our daily routines. After all, can anything get more fundamental than starting with your socks?
Perhaps the most meaningful takeaway for me in this chapter, is the concept that relaxing the rules of the sort can be acceptable in certain circumstances, and leads to pretty big performance gains. In all cases, performing a sort is useless without a search. Deciding on the accuracy (and time) of the sort should first consider the needs of the subsequent search.
“Sorting something that you will never search is a complete waste; searching something you never sorted is merely inefficient” [2, p. 72]
Consider a scenario where you have a vast dataset of customer transactions. If the objective is to quickly identify recent transactions within the last week, a more relaxed sorting approach might be perfectly adequate, prioritizing speed over precise chronological order. This relaxation of the sort rules can significantly improve the search efficiency and overall system performance. Understanding when and how to optimize the sort based on the requirements of the subsequent search is a crucial skill in efficiently handling data and making informed decisions.
Relaxing the constraints on the accuracy of the sort and pre-sorting popular search items is revealed to be the approach adopted by many of the big search engines. With big data at their disposal, Google can ensure popular search terms have cached sorted results to be served immediately, ensuring a smooth experience for their users. The amount of resource and infrastructure in caching high traffic sorts across different territories must be mind-boggling.
This glimpse into the inner workings of search engine optimization not only makes the abstract concepts of sorting tangible but also instills a sense of admiration for the innovative minds behind these technological advancements. Paired with the forthcoming chapter on caching, the insights gained here are remarkably applicable to our everyday lives, shedding light on the strategies that power our online searches and experiences.
Caching
This chapter is my highlight of the book. Beginning with a tangible concept of treating your wardrobe as a physical cache for your clothes, this chapter goes on to explore the evolution of memory management. Beginning with the fundamental trade off between capacity and performance, the authors discuss the invention of the memory hierarchy. This concept that forms the basis of modern memory management introduces a hierarchical structure, with a small, fast (high performance) amount of memory used to cache high frequency data. This memory cache would be coupled with larger, less expensive forms of slower-access memory.
“The key, of course, would be managing that small, fast, precious memory so it had what you were looking for as often as possible.” [2, p. 87]
Clever optimisation of a more and more elaborate cache system is cited as the principle solution to the disparity in the exponential improvement of processing power relative to memory performance over the previous half a century. Again, the authors with their ability to ground the computer science in tangible analogy. Imagine a factory able to double its productivity year on year only to find that its output is soon limited by its supply chain - it simply cannot ingest the raw material at a rate to satisfy its output potential. Overcoming the problem of memory performance, referred to as the ‘memory wall’ has been crucial in securing performant applications and devices.
Managing the state of the cache is treated with some detail. Competing algorithms for cache eviction - rules used to decide which memory to free up and when - are compared against the success criteria of avoiding what is known as a cache miss. A cache miss is a state where the data that you are looking for cannot be found within the cache and therefore must be retrieved from the slower memory store. Achieving this state appears to be on a par with divining the future, as who knows what the user will ask for next. Of the competing cache eviction algorithms considered are:
- Random Eviction: Overwriting old data from the cache at random. Apparently not as poor a choice as it sounds.
- First in, First Out (FIFO): Overwriting the data that first entered the cache.
- Least Recently Used (LRU): Overwriting the data that has remained untouched for the longest duration.
Among these, the ‘Least Recently Used’ algorithm emerges as the optimal choice, consistently outperforming the others in preventing cache misses. The authors go on to illuminate the far-reaching implications of this optimization, spanning from the physical construction of processors to the logistics of Amazon’s warehouses.
“Computers’ default file-browsing interface makes you click through folders in alphabetical order - but the power of LRU suggest that you should override this, and display your files by”Last Opened” rather than “Name”. What you’re looking for will almost always be at or near the top.” [2, p. 98]
Analysis and Evaluation
AtLB proves to be an engaging read, making the intricate world of computer science accessible even to those without an undergrad in the field. The book adeptly navigates through five decades of computational thought and its implementation, ensuring the content never overwhelms the casual reader. One of its strengths lies in emphasizing tangible analogies and illustrating practical implications for everyday life, prompting thought and curiosity.
There are a number of instances where the problem domains have been framed in a way that has not aged so well. By today’s standard, The Secretary Problem could do with an overhaul. The authors acknowledge that the framing of this problem is a product of its time and that it could use an overhaul. But an aspect of AtLB is to provide the historic context and evolution of an idea, where it is available. In doing so, the authors reveal the stories of the people behind the big ideas, aspects of their life, work and the problems they were wrangling.
For IT professionals, while AtLB may not break new ground, it excels in illustrating the impact of optimization in a way that surpasses many formal textbooks. The book effectively builds awareness around the subject and its role in advancing society, providing a valuable framework for professionals in the field.
Comparisons
This book offers a treatment of understanding the nuts and bolts and how society has implemented and optimised in response to the knowledge. This book can therefore be compared to a broad selection of popular science. Some similar books are:
Naked Statistics by Charles Wheelan [5] explores how statistics can be misused to obfuscate key findings or serve a political agenda. It serves as a toolkit for understanding algorithms and being aware of their potential misapplications, providing readers with the ability to discern and critically analyse statistical information.
Hello World by Hannah Fry [6] delves into the implementation of algorithms in complex domains like Crime, Justice, and Healthcare. The book grapples with intricate ethical challenges, approaching the subject with warranted skepticism and scrutinising the far-reaching implications of algorithmic applications in various societal domains.
In contrast, AtLB offers a distinctly optimistic treatment, aiming to educate and instill an appreciation for the scale and implication of optimized solutions. It provides readers with an understanding of how computational thought has shaped our world and the positive impacts it can have in our rapidly evolving society.
Recommendation
I completed my reading of ‘AtLB’ in January of 2023, and to pen down this review, I revisited the book, speed-reading through noteworthy sections to reacquaint myself with its messages. At times I began deep reading the material, drawn in by its captivating narrative and insightful content. The book is a treasure trove of anecdotes and key summaries.
In my estimation, this is too good to miss for anyone with an interest in logic, analysis or is generally curious about exactly what computer science has achieved for us so far.