Drawn from Source 1 and Source 2, which form the basis for the summary below.

Optimal Stopping

Imagine the following scenario: you have to hire a secretary from a pool of fixed applicants. You have to interview the candidates one by one and make a hire/no-hire decision right after each interview. If you pass on someone, you cannot come back to them. If you hire someone, the process stops and they are your new secretary. How do you maximize your chances to find the best secretary in the group? This is the famous Secretary Problem, and it forms the basis for the discussion in this chapter.

You probably don’t want to hire the first person you interview, since you don’t know what the baseline is. You don’t want to hire the last person either: you almost certainly have passed on your best candidate at this point. So the optimal strategy involves interviewing and rejecting the first few candidates no matter how good they are: just to set up the baseline first and then hiring the best you’ve seen so far after. This optimal point turns out to be 1/e or about 37%. Reject 37% of the applicants, and then hire the next one better than anyone you’ve seen so far. Variants of this Secretary Problem and the accompanying 37% Rule apply to vast areas of real life too — from dating to parking your car to selling/buying a house: knowing when to stop looking is crucial. Before you get too excited, here’s the sobering bit: this optimal strategy fails 63% of the time.

Exploration vs. Exploitation

It’s Saturday and it’s your cheat day. Do you open Yelp and explore a new restaurant, or do you go back to the sandwich place you’ve been craving all week? Do you put on Spotify’s Daily Mix, or do you just go back to listening to your favorite albums? In other words, do you explore, or do you exploit? This is the exploration vs. exploitation problem.

Simply put, exploration is gathering information, and exploitation is using the information you have to get a known good result. When balancing favorite experiences and new ones, nothing matters as much as the interval over which we plan to enjoy them.

From A/B testing websites to A/B testing human drugs via clinical trials, software engineers and pharmaceutical companies alike are trying to figure out where the balance lies. The book also discusses a number of strategies like the Win-Stay, Lose-Shift algorithm: choose an arm at random, and keep pulling it as long as it keeps paying off. If the arm doesn’t pay off after a particular pull, then switch to the other one. Although this simple strategy is far from a complete solution, Robbins proved in 1952 that it performs reliably better than chance. Exploration in itself has value, since trying new things increases our chances of finding the best. So taking the future into account, rather than focusing just on the present, drives us toward novelty.

Regret and Optimism

If the Gittins index is too complicated, or if you’re not in a situation well characterized by geometric discounting, then you have another option: focus on regret. When we choose what to eat, who to spend time with, or what city to live in, regret looms large — presented with a set of good options, it is easy to torture ourselves with the consequences of making the wrong choice. These regrets are often about the things we failed to do, the options we never tried.

Researchers in recent decades have set about looking for algorithms that offer the guarantee of minimal regret. Of the ones they’ve discovered, the most popular are known as Upper Confidence Bound algorithms: pick the option for which the top of the confidence interval is highest.

Upper Confidence Bound algorithms implement a principle that has been dubbed “optimism in the face of uncertainty.” Optimism, they show, can be perfectly rational. By focusing on the best that an option could be, given the evidence obtained so far, these algorithms give a boost to possibilities we know less about. As a consequence, they naturally inject a dose of exploration into the decision-making process, leaping at new options with enthusiasm because any one of them could be the next big thing. The success of Upper Confidence Bound algorithms offers a formal justification for the benefit of the doubt. Following the advice of these algorithms, you should be excited to meet new people and try new things — to assume the best about them, in the absence of evidence to the contrary.

In the long run, optimism is the best prevention for regret. Over a lifetime, you’re going to make a lot of decisions. And it’s actually rational to emphasize exploration — the new rather than the best, the exciting rather than the safe, the random rather than the considered — for many of those choices, particularly earlier in life. What we take to be the caprice of children may be wiser than we know.

Sorting

Sorting algorithms are usually the first ones that any introductory Computer Science course covers. Topics discussed here go from the Big O notation that serves as a yardstick for measuring the performance of algorithms, to the bouquet of sorting algorithms themselves: bubble, insertion, merge and quick sorts.

Sort Is Prophylaxis for Search: Computer science, as undergraduates are taught, is all about tradeoffs. And one of the most central tradeoffs is between sorting and searching. The basic principle is this: the effort expended on sorting materials is just a preemptive strike against the effort it’ll take to search through them later. What the precise balance should be depends on the exact parameters of the situation, but thinking about sorting as valuable only to support future search tells us something surprising: err on the side of messiness. Sorting something that you will never search is a complete waste; searching something you never sorted is merely inefficient. The question, of course, becomes how to estimate ahead of time what your future usage will be.

The chapter ends with a discussion on tournaments of various types: round-robin, ladder, single-elimination and so on. After all, tournaments are just another sorting problem, and so are the pecking orders and dominance hierarchies in the animal (and human) kingdom. Keeping things sorted just makes life easier.

Caching

The idea of keeping around pieces of information that you refer to frequently is so powerful that it is used in every aspect of computation. Processors have caches. Hard drives have caches. Operating systems have caches. Web browsers have caches.

Least Recently Used (LRU): evicting the item that’s gone the longest untouched (Stewart’s “When was the last time I wore it or used it?”). First, when you are deciding what to keep and what to throw away, LRU is potentially a good principle to use — much better than FIFO. You shouldn’t necessarily toss that T-shirt from college if you still wear it every now and then. But the plaid pants you haven’t worn in ages? Those can be somebody else’s thrift-store bonanza. Second, exploit geography. Make sure things are in whatever cache is closest to the place where they’re typically used.

A final insight, which hasn’t yet made it into guides on closet organization, is that of the multi-level memory hierarchy. Having a cache is efficient, but having multiple levels of caches — from smallest and fastest to largest and slowest — can be even better. Where your belongings are concerned, your closet is one cache level, your basement another, and a self-storage locker a third. (These are in decreasing order of access speed, of course, so you should use the LRU principle as the basis for deciding what gets evicted from each level to the next.) But you might also be able to speed things up by adding yet another level of caching: an even smaller, faster, closer one than your closet.

Scheduling

Thus we encounter the first lesson in single-machine scheduling literally before we even begin: make your goals explicit. We can’t declare some schedule a winner until we know how we’re keeping score. This is something of a theme in computer science: before you can have a plan, you must first choose a metric.

If you’re concerned with minimizing maximum lateness, then the best strategy is to start with the task due soonest and work your way toward the task due last. This strategy, known as Earliest Due Date, is fairly intuitive.

Minimizing the sum of completion times leads to a very simple optimal algorithm called Shortest Processing Time: always do the quickest task you can. Even if you don’t have impatient clients hanging on every job, Shortest Processing Time gets things done. (Perhaps it’s no surprise that it is compatible with the recommendation in Getting Things Done to immediately perform any task that takes less than two minutes.) Again, there’s no way to change the total amount of time your work will take you, but Shortest Processing Time may ease your mind by shrinking the number of outstanding tasks as quickly as possible. Its sum-of-completion-times metric can be expressed another way: it’s like focusing above all on reducing the length of your to-do list. If each piece of unfinished business is like a thorn in your side, then racing through the easiest items may bring some measure of relief.

The weighted version of Shortest Processing Time is a pretty good candidate for best general-purpose scheduling strategy in the face of uncertainty. It offers a simple prescription for time management: each time a new piece of work comes in, divide its importance by the amount of time it will take to complete. If that figure is higher than for the task you’re currently doing, switch to the new one; otherwise stick with the current task. This algorithm is the closest thing that scheduling theory has to a skeleton key or Swiss Army knife, the optimal strategy not just for one flavor of problem but for many.

A commitment to fastidiously doing the most important thing you can, if pursued in a head-down, myopic fashion, can lead to what looks for all the world like procrastination. As with a car spinning its tires, the very desire to make immediate progress is how one gets stuck. “Things which matter most must never be at the mercy of things which matter least,” Goethe allegedly proclaimed; but while that has the ring of wisdom about it, sometimes it’s just not true. Sometimes that which matters most cannot be done until that which matters least is finished, so there’s no choice but to treat that unimportant thing as being every bit as important as whatever it’s blocking. This is related to the concept of priority inversion (remember the Mars story).

Context Switching

We have found that both programming and writing require keeping in mind the state of the entire system, and thus carry inordinately large context-switching costs. A friend of ours who writes software says that the normal workweek isn’t well suited to his workflow, since for him sixteen-hour days are more than twice as productive as eight-hour days. Brian, for his part, thinks of writing as a kind of blacksmithing, where it takes a while just to heat up the metal before it’s malleable. He finds it somewhat useless to block out anything less than ninety minutes for writing, as nothing much happens in the first half hour except loading a giant block of “Now, where was I?” into his head.

If you find yourself doing a lot of context switching because you’re tackling a heterogeneous collection of short tasks, you can also employ another idea from Computer Science: Interrupt Coalescing. If you have five credit card bills, for instance, don’t pay them as they arrive; take care of them all in one go when the fifth bill comes. As long as your bills are never due less than thirty-one days after they arrive, you can designate, say, the first of each month as “bill-paying day,” and sit down at that point to process every bill on your desk, no matter whether it came three weeks or three hours ago. Likewise, if none of your email correspondents require you to respond in less than twenty-four hours, you can limit yourself to checking your messages once a day. This is essentially batching TODOs.

Perhaps the patron saint of the minimal-context-switching lifestyle is the legendary programmer Donald Knuth. “I do one thing at a time,” he says. “This is what computer scientists call batch processing — the alternative is swapping in and out. I don’t swap in and out.” Knuth isn’t kidding. On January 1, 2014, he embarked on “The TeX Tuneup of 2014,” in which he fixed all of the bugs that had been reported in his TeX typesetting software over the previous six years. His report ends with the cheery sign-off “Stay tuned for The TeX Tuneup of 2021!” Likewise, Knuth has not had an email address since 1990. “Email is a wonderful thing for people whose role in life is to be on top of things. But not for me; my role is to be on the bottom of things. What I do takes long hours of studying and uninterruptible concentration.”

Bayes’ Rule

For any possible drawing of w winning tickets in n attempts, the expectation is simply the number of wins plus one, divided by the number of attempts plus two: (w+1)/(n+2). This incredibly simple scheme for estimating probabilities is known as Laplace's Law, and it is easy to apply in any situation where you need to assess the chances of an event based on its history. If you make ten attempts at something and five of them succeed, Laplace’s Law estimates your overall chances to be 6/12 or 50%, consistent with our intuitions.

Laplace’s Law offers us the first simple rule of thumb for confronting small data in the real world. Even when we’ve made only a few observations — or only one — it offers us practical guidance. Want to calculate the chance your bus is late? The chance your softball team will win? Count the number of times it has happened in the past plus one, then divide by the number of opportunities plus two. And the beauty of Laplace’s Law is that it works equally well whether we have a single data point or millions of them.

Bayes' Rule gives a remarkably straightforward solution to the problem of how to combine pre-existing beliefs with observed evidence: multiply their probabilities together. Notably, having some pre-existing beliefs is crucial for this formula to work. The richer the prior information we bring to Bayes’s Rule, the more useful the predictions we can get out of it. Bayes’s Rule tells us that when it comes to making predictions based on limited evidence, few things are as important as having good priors — that is, a sense of the distribution from which we expect that evidence to have come. Good predictions thus begin with having good instincts about when we’re dealing with a normal distribution and when with a power-law distribution. As it turns out, Bayes’s Rule offers us a simple but dramatically different predictive rule of thumb for each.

The Copernican Principle emerges: if we want to predict how long something will last, and have no other knowledge about it whatsoever, the best guess we can make is that it will continue just as long as it’s gone on so far. This is a key topic in the book Antifragile. Examining the Copernican Principle, we saw that when Bayes’s Rule is given an uninformative prior, it always predicts that the total life span of an object will be exactly double its current age. In fact, the uninformative prior, with its wildly varying possible scales — the wall that might last for months or for millennia — is a power-law distribution.

  • And for any power-law distribution, Bayes’ Rule indicates that the appropriate prediction strategy is a Multiplicative Rule: multiply the quantity observed so far by some constant factor. For an uninformative prior, that constant factor happens to be 2, hence the Copernican prediction.
  • When we apply Bayes’ Rule with a normal distribution as a prior, on the other hand, we obtain a very different kind of guidance. Instead of a multiplicative rule, we get an Average Rule: use the distribution’s “natural” average — its single, specific scale — as your guide. For instance, if somebody is younger than the average life span, then simply predict the average; as their age gets close to and then exceeds the average, predict that they’ll live a few years more.
  • Between those two extremes, there’s actually a third category of things in life: those that are neither more nor less likely to end just because they’ve gone on for a while. Sometimes things are simply invariant. The Danish mathematician Agner Krarup Erlang, who studied such phenomena, formalized the spread of intervals between independent events into the function that now carries his name: the Erlang distribution. The Erlang distribution gives us a third kind of prediction rule, the Additive Rule: always predict that things will go on just a constant amount longer.

These three very different patterns of optimal prediction — the Multiplicative, Average, and Additive Rules — all result directly from applying Bayes’s Rule to the power-law, normal, and Erlang distributions, respectively. And given the way those predictions come out, the three distributions offer us different guidance, too, on how surprised we should be by certain events.

  • In a power-law distribution, the longer something has gone on, the longer we expect it to continue going on. So a power-law event is more surprising the longer we’ve been waiting for it — and maximally surprising right before it happens. A nation, corporation, or institution only grows more venerable with each passing year, so it’s always stunning when it collapses.
  • In a normal distribution, events are surprising when they’re early — since we expected them to reach the average — but not when they’re late. Indeed, by that point they seem overdue to happen, so the longer we wait, the more we expect them.
  • And in an Erlang distribution, events by definition are never any more or less surprising no matter when they occur. Any state of affairs is always equally likely to end regardless of how long it’s lasted.

Overfitting

It is indeed true that including more factors in a model will always, by definition, make it a better fit for the data we have already. But a better fit for the available data does not necessarily mean a better prediction. This is what statisticians call Overfitting. So one of the deepest truths of machine learning is that, in fact, it’s not always better to use a more complex model, one that takes a greater number of factors into account. And the issue is not just that the extra factors might offer diminishing returns — performing better than a simpler model, but not enough to justify the added complexity. Rather, they might make our predictions dramatically worse.

Detecting Overfitting using Cross-Validation: Simply put, Cross-Validation means assessing not only how well a model fits the data it’s given, but how well it generalizes to data it hasn’t seen. Paradoxically, this may involve using less data.

How to Combat Overfitting using Penalizing Complexity: One way to choose among several competing models is the Occam's Razor principle, which suggests that, all things being equal, the simplest possible hypothesis is probably the correct one. Of course, things are rarely completely equal, so it’s not immediately obvious how to apply something like Occam’s razor in a mathematical context. Grappling with this challenge in the 1960s, Russian mathematician Andrey Tikhonov proposed one answer: introduce an additional term to your calculations that penalizes more complex solutions. If we introduce a complexity penalty, then more complex models need to do not merely a better job but a significantly better job of explaining the data to justify their greater complexity. Computer scientists refer to this principle — using constraints that penalize models for their complexity — as Regularization.

Early Stopping: In machine learning, the advantages of moving slowly emerge most concretely in a regularization technique known as Early Stopping. In many situations, however, tuning the parameters to find the best possible fit for given data is a process in and of itself. What happens if we stop that process early and simply don’t allow a model the time to become too complex? Again, what might seem at first blush like being halfhearted or unthorough emerges, instead, as an important strategy in its own right.

Relaxation

A constrained optimization problem: how to find the single best arrangement of a set of variables, given particular rules and a scorekeeping measure. A famous constrained optimization problem is the Traveling Salesman Problem.

Defining Difficulty: The Cobham–Edmonds thesis: an algorithm should be considered efficient if it runs in what’s called “polynomial time” — that is, O(n²), O(n³), or in fact n to the power of any number at all. A problem, in turn, is considered tractable if we know how to solve it using an efficient algorithm. A problem we don’t know how to solve in polynomial time, on the other hand, is considered intractable. And at anything but the smallest scales, intractable problems are beyond the reach of solution by computers, no matter how powerful.

Constraint Relaxation: One of the simplest forms of relaxation in computer science is known as Constraint Relaxation. In this technique, researchers remove some of the problem’s constraints and set about solving the problem they wish they had. Then, after they’ve made a certain amount of headway, they try to add the constraints back in. That is, they make the problem temporarily easier to handle before bringing it back to reality. What relaxation cannot do is offer you a guaranteed shortcut to the perfect answer. But computer science can also quantify the tradeoff that relaxation offers between time and solution quality. In many cases, the ratio is dramatic, a no-brainer — for instance, an answer at least half as good as the perfect solution in a quadrillionth of the time. The message is simple but profound: if we’re willing to accept solutions that are close enough, then even some of the hairiest problems around can be tamed with the right techniques.

Lagrangian Relaxation: The idea behind Lagrangian Relaxation is simple. An optimization problem has two parts: the rules and the scorekeeping. In Lagrangian Relaxation, we take some of the problem’s constraints and bake them into the scoring system instead. That is, we take the impossible and downgrade it to costly. (In a wedding seating optimization, for instance, we might relax the constraint that tables each hold ten people max, allowing overfull tables but with some kind of elbow-room penalty.) When an optimization problem’s constraints say “Do it, or else!”, Lagrangian Relaxation replies, “Or else what?” Once we can color outside the lines — even just a little bit, and even at a steep cost — problems become tractable that weren’t tractable before.

Continuous Relaxation: Relaxations offer us a number of advantages. For one, they offer a bound on the quality of the true solution. If we’re trying to pack our calendar, imagining that we can magically teleport across town will instantaneously make it clear that eight one-hour meetings is the most we could possibly expect to fit into a day; such a bound might be useful in setting expectations before we face the full problem. Second, relaxations are designed so that they can indeed be reconciled with reality — and this gives us bounds on the solution from the other direction. When Continuous Relaxation tells us to give out fractional vaccines, we can just immunize everyone assigned to receive half a vaccine or more, and end up with an easily calculated solution that requires at worst twice as many inoculations as in a perfect world. Maybe we can live with that.

Randomness

Sampling: when we want to know something about a complex quantity, we can estimate its value by sampling from it (Monte Carlo Method). A close examination of random samples can be one of the most effective means of making sense of something too complex to be comprehended directly.

Hill Climbing: Once you’ve assembled a baseline itinerary, you might test some alternatives by making slight perturbations to the city sequence and seeing if that makes an improvement. For instance, if we are going first to Seattle, then to Los Angeles, we can try doing those cities in reverse order: L.A. first, then Seattle. For any given itinerary, we can make eleven such two-city flip-flops; let’s say we try them all and then go with the one that gives us the best savings. From here we’ve got a new itinerary to work with, and we can start permuting that one, again looking for the best local improvement. This is an algorithm known as Hill Climbing — since the search through a space of solutions, some better and some worse, is commonly thought of in terms of a landscape with hills and valleys, where your goal is to reach the highest peak. Eventually you will end up with a solution that is better than all of its permutations; no matter which adjacent stops you flip, nothing beats it. It’s here that the hill climbing stops. Does this mean you’ve definitely found the single best possible itinerary, though? Sadly, no. You may have found only a so-called “local maximum,” not the global maximum of all the possibilities.

Shotgun Hill Climbing: One approach is to augment Hill Climbing with what’s known as jitter: if it looks like you’re stuck, mix things up a little. Make a few random small changes (even if they are for the worse), then go back to Hill Climbing; see if you end up at a higher peak. Another approach is to completely scramble our solution when we reach a local maximum, and start Hill Climbing anew from this random new starting point. This algorithm is known, appropriately enough, as “Random-Restart Hill Climbing” — or, more colorfully, as “Shotgun Hill Climbing.” It’s a strategy that proves very effective when there are lots of local maxima in a problem.

Metropolis Algorithm: But there’s also a third approach: instead of turning to full-bore randomness when you’re stuck, use a little bit of randomness every time you make a decision. This technique, developed by the same Los Alamos team that came up with the Monte Carlo Method, is called the Metropolis Algorithm. The Metropolis Algorithm is like Hill Climbing, trying out different small-scale tweaks on a solution, but with one important difference: at any given point, it will potentially accept bad tweaks as well as good ones.

Networking

Packet Switching, ACKnowledgements, triple handshakes, exponential backoff and the algorithms of forgiveness: networking is another topic full of gems. Connecting people is one of the most fundamental and impactful areas of Computer Science — we’re talking about the internet here. How to control the flow, how to avoid congestion (Additive Increase, Multiplicative Decrease), how to establish Backchannels (and the role of white noise and little acknowledgments in everyday real-life conversations!), and how to avoid buffer bloats: these are some of the topics that are part of any Computer Networking class, but it was great to see them in a new light.

Game Theory

The Nash equilibrium offers a prediction of the stable long-term outcome of any set of rules or incentives. As such, it provides an invaluable tool for both predicting and shaping economic policy, as well as social policy in general. As Nobel laureate economist Roger Myerson puts it, the Nash equilibrium “has had a fundamental and pervasive impact in economics and the social sciences which is comparable to that of the discovery of the DNA double helix in the biological sciences.”

  • Dominant Strategies, for Better or Worse: Even when we can reach an equilibrium, just because it’s stable doesn’t make it good. It may seem paradoxical, but the equilibrium strategy — where neither player is willing to change tack — is by no means necessarily the strategy that leads to the best outcomes for the players. Nowhere is that better illustrated than in game theory’s most famous, provocative, and controversial two-player game: the prisoner's dilemma.
  • The Tragedy of the Commons: So what can we, as players, do when we find ourselves in such a situation — either the two-party prisoner’s dilemma, or the multi-party tragedy of the commons? In a sense, nothing. The very stability that these bad equilibria have, the thing that makes them equilibria, becomes damnable. By and large we cannot shift the dominant strategies from within. But this doesn’t mean that bad equilibria can’t be fixed. It just means that the solution is going to have to come from somewhere else.

Mechanism Design: Change the Game

While game theory asks what behavior will emerge given a set of rules, mechanism design (sometimes called Reverse Game Theory) works in the other direction, asking: what rules will give us the behavior we want to see?

Scaling up this logic results in a potent argument for the role of government. In fact, many governments do have laws on the books mandating minimum vacations and limiting shop hours. Laws like these often stem from the colonial era and were initially religious in nature. Indeed, religion itself provides a very direct way of modifying the structure of games of this kind. In particular, a religious law such as “Remember the Sabbath day” neatly solves the problem faced by the shopkeepers, whether enforced by an all-powerful God or by the more proximate members of a religious community. And adding divine force to injunctions against other kinds of antisocial behavior, such as murder, adultery, and theft, is likewise a way to solve some of the game-theoretic problems of living in a social group. God happens to be even better than government in this respect, since omniscience and omnipotence provide a particularly strong guarantee that taking bad actions will have dire consequences.

Information cascades offer a rational theory not only of bubbles, but also of fads and herd behavior more generally. They offer an account of how it’s easily possible for any market to spike and collapse, even in the absence of irrationality, malevolence, or malfeasance.

  • For one, be wary of cases where public information seems to exceed private information, where you know more about what people are doing than why they’re doing it, where you’re more concerned with your judgments fitting the consensus than fitting the facts. When you’re mostly looking to others to set a course, they may well be looking right back at you to do the same.
  • Second, remember that actions are not beliefs; cascades get caused in part when we misinterpret what others think based on what they do. We should be especially hesitant to overrule our own doubts — and if we do, we might want to find some way to broadcast those doubts even as we move forward, lest others fail to distinguish the reluctance in our minds from the implied enthusiasm in our actions.
  • Last, we should remember from the prisoner’s dilemma that sometimes a game can have irredeemably lousy rules. There may be nothing we can do once we’re in it, but the theory of information cascades may help us to avoid such a game in the first place.

If you’re the kind of person who always does what you think is right, no matter how crazy others think it is, take heart. The bad news is that you will be wrong more often than the herd followers. The good news is that sticking to your convictions creates a positive externality, letting people make accurate inferences from your behavior. There may come a time when you will save the entire herd from disaster.

Auctions

There’s one auction design in particular that cuts through the burden of mental recursion like a hot knife through butter. It’s called the Vickrey auction. Named for Nobel Prize–winning economist William Vickrey, the Vickrey auction, just like the first-price auction, is a “sealed bid” auction process. That is, every participant simply writes down a single number in secret, and the highest bidder wins. However, in a Vickrey auction, the winner ends up paying not the amount of their own bid, but that of the second-place bidder. That is to say, if you bid $25 and I bid $10, you win the item at my price: you only have to pay $10.

To a game theorist, a Vickrey auction has a number of attractive properties. And to an algorithmic game theorist in particular, one property especially stands out: the participants are incentivized to be honest. In fact, there is no better strategy than just bidding your “true value” for the item — exactly what you think the item is worth.

  • Bidding any more than your true value is obviously silly, as you might end up stuck buying something for more than you think it’s worth.
  • And bidding any less than your true value (i.e., shading your bid) risks losing the auction for no good reason, since it doesn’t save you any money — because if you win, you’ll only be paying the value of the second-highest bid, regardless of how high your own was.

This makes the Vickrey auction what mechanism designers call “strategy-proof,” or just “truthful.” In the Vickrey auction, honesty is literally the best policy. Even better, honesty remains the best policy regardless of whether the other bidders are honest themselves. In the prisoner’s dilemma, we saw how defection turned out to be the “dominant” strategy — the best move no matter whether your partner defected or cooperated. In a Vickrey auction, on the other hand, honesty is the dominant strategy. This is the mechanism designer’s holy grail. You do not need to strategize or recurse.

Conclusion: Computational Kindness

Any dynamic system subject to the constraints of space and time is up against a core set of fundamental and unavoidable problems. These problems are computational in nature, which makes computers not only our tools but also our comrades.

From this come three simple pieces of wisdom.

  • First, there are cases where computer scientists and mathematicians have identified good algorithmic approaches that can simply be transferred over to human problems. The 37% Rule, the Least Recently Used criterion for handling overflowing caches, and the Upper Confidence Bound as a guide to exploration are all examples of this.
  • Second, knowing that you are using an optimal algorithm should be a relief even if you don’t get the results you were looking for. The 37% Rule fails 63% of the time. Maintaining your cache with LRU doesn’t guarantee that you will always find what you’re looking for; in fact, neither would clairvoyance. Using the Upper Confidence Bound approach to the explore/exploit tradeoff doesn’t mean that you will have no regrets, just that those regrets will accumulate ever more slowly as you go through life. Even the best strategy sometimes yields bad results — which is why computer scientists take care to distinguish between “process” and “outcome.” If you followed the best possible process, then you’ve done all you can, and you shouldn’t blame yourself if things didn’t go your way. Outcomes make news headlines — indeed, they make the world we live in — so it’s easy to become fixated on them. But processes are what we have control over. As Bertrand Russell put it, “it would seem we must take account of probability in judging of objective rightness.… The objectively right act is the one which will probably be most fortunate. I shall define this as the wisest act.” We can hope to be fortunate — but we should strive to be wise. Call it a kind of computational Stoicism.
  • Finally, we can draw a clear line between problems that admit straightforward solutions and problems that don’t. If you wind up stuck in an intractable scenario, remember that heuristics, approximations, and strategic use of randomness can help you find workable solutions. A theme that came up again and again in our interviews with computer scientists was: sometimes “good enough” really is good enough. What’s more, being aware of complexity can help us pick our problems: if we have control over which situations we confront, we should choose the ones that are tractable.

Seemingly innocuous language like “Oh, I’m flexible” or “What do you want to do tonight?” has a dark computational underbelly that should make you think twice. It has the veneer of kindness about it, but it does two deeply alarming things. First, it passes the cognitive buck: “Here’s a problem, you handle it.” Second, by not stating your preferences, it invites the others to simulate or imagine them. And as we have seen, the simulation of the minds of others is one of the biggest computational challenges a mind (or machine) can ever face. In such situations, computational kindness and conventional etiquette diverge. Politely withholding your preferences puts the computational problem of inferring them on the rest of the group. In contrast, politely asserting your preferences (“Personally, I’m inclined toward x. What do you think?”) helps shoulder the cognitive load of moving the group toward resolution. Alternatively, you can try to reduce, rather than maximize, the number of options that you give other people — say, offering a choice between two or three restaurants rather than ten. If each person in the group eliminates their least preferred option, that makes the task easier for everyone. And if you’re inviting somebody out to lunch, or scheduling a meeting, offering one or two concrete proposals that they can accept or decline is a good starting point. None of these actions is necessarily “polite,” but all of them can significantly lower the computational cost of interaction.

Computational kindness isn’t just a principle of behavior; it’s also a design principle. One of the chief goals of design ought to be protecting people from unnecessary tension, friction, and mental labor. (This is not just an abstract concern; when mall parking becomes a source of stress, for instance, shoppers may spend less money and return less frequently.)