I recently finished reading Algorithms to Live By, a highly enlightening take on what happens when you apply computer science to problems in cognitive psychology. The result is a veritable ton of clever ideas to help tackle situations that come up in everyday life. The solutions were so inspiring to me (likely because I have a historical affinity for computer science) that I wanted to create a quick reference to keep handy at all times.
This is my attempt to outline the general life advice derived from the algorithms covered in the book. Some of this may not make any sense if you don’t have a background in computer science, but that’s what the full book is for — I highly recommend it for people of all backgrounds!
Optimal Stopping — Look then Leap
Situation
Trying to choose the best option out of a series of candidates, given a finite set or time limit
Algorithm
Spend the first 37% of time or 37% of candidates simply evaluating, choosing none of them. After that point, immediately choose the first candidate strictly better than those you’ve seen before.
Variants
- Rejection: If you have a 50/50 chance of having your choice rejected, start making offers to candidates earlier, at the 25% mark.
- Recall: If you’re able to return to past candidates with a 50/50 chance of being rejected on a second try, extend the initial evaluation period to the 61% mark and only go back to a previous candidate once the remaining 39% is exhausted.
- Full Information: If you have a measurable objective criterion, you can set an acceptable “threshold” above which you immediately accept a candidate. This threshold should go down as you run out of candidates/time. (Also known as “lowering your standards” over time.)
- Sunk Costs: If you must pay a cost to wait for candidates, your threshold should lower in proportion to the costs and you should never attempt to recall an old candidate.
Explore/Exploit — Multi-arm bandits
Situation
Deciding whether to explore new options or stick to something you know you like
Algorithm
Focus on regret — choose the option that will result in the minimal amount of potential regret at the end of the time period in question.
Variants
- Confidence Intervals: If you know the confidence intervals for two options, choose the option with the higher upper confidence bound. (Best potential satisfaction, not average estimate.) This is also known as “optimism in the face of uncertainty.”
- Gittins Index: If you can somehow calculate the dynamic allocation index of each option (a payout rate where if offered in lieu of the option, you would never choose it again) and then compare them, always choose the option with the higher index. Untested “exploratory” options will look better early on, while known “exploit” options will be better later.
Sorting
Situation
Needing to organize a set of n objects in some comparative order
Algorithm
Mergesort! Divide the items into separate groups and sort them individually. Then merge groups one pair at a time. For n objects, this takes O(n log n) time.
Variants
- Bucket Sort: Create m buckets (categories) that you estimate will be of similar size, and do a pass on all items to get them grouped by bucket first. Then sort within each bucket, and (if necessary), merge all the buckets into a final set. The grouping takes O(nm) time.
- Search instead: Actually don’t sort everything. The lower the cost of searching/scanning for something, the less worthwhile it is to do the upfront work of sorting. (Example: email)
- Comparison Counting Sort: In the face of a noisy comparator (potential for errors in comparisons), just take each item and compare it to all the others in the group, tallying how many items it is greater than. This number becomes its rank in the final list. (Also known as “round-robin.”)
- Cardinal order: If you can agree on a measure of caliber across all items, they can be naturally sorted without doing pairwise comparisons. Creating this agreed-upon ‘pecking order’ also simplifies negotiations and prevents in-fighting.
Caching
Situation
Deciding what to do when you run out of capacity to store things
Algorithm
Create multiple storage units (one smaller one you can access quickly, and one larger one that takes longer to access). As the smaller unit becomes full, evict objects that you’ll need the longest time from now.
Variants
- FIFO (First-In-First-Out): Evict objects that have been sitting in the cache the longest. (Usually not the best solution.)
- LRU (Least Recently Used): Evict objects that have gone the longest untouched. Extension of this is to place the most recently used objects near the “front” or wherever is most easily accessible, instead of filing into a complex grouping.
Scheduling
Situation
Planning your days
Algorithm
First choose a metric to optimize for. In the case of optimizing for reducing “maximum lateness” of tasks, do the tasks with the Earliest Due Date.
Variants
- Moore’s Algorithm (minimizing number of tasks late): Start out with Earliest Due Date, but as soon as it seems one won’t make it, look across all items and throw out the biggest one.
- Shortest Processing Time: Always do the quickest task you can, to minimize “sum of completion times”. You could also add relative weights to each task and try to minimize sum of weighted completion times by doing the tasks with highest importance-per-unit-time first.
- Priority inheritance: If a low-priority task is blocking a high-priority task, it should become high-priority itself.
- Setup with two machines in sequence (e.g. laundry): Take the step that requires the shortest amount of time. If it involves the first machine, do it first; if it involves the second machine, do it last. Repeat the process for all steps, planning down to the middle of the set of steps.
- Task Preemption: If a new task appears, compare its due date or processing time with your current task and switch only if it should be executed in front of the one you’re currently on. Be careful of the cost of context switching however.
- Thrashing: To prevent becoming overloaded with switching between too many tasks — get more bandwidth (ask for help), learn to say no, pick a simpler way to calculate priority order to save time, establish a minimum amount of time to work on each task (timeboxing), or coalesce potential interrupts (like email) to take care of all at once.
Predicting the Future
Situation
Needing to make an guess about how long something will last with minimal data (i.e. a single observation).
Algorithm
Multiply the probabilities of preexisting beliefs with observed evidence to come up with a best guess of future odds. Concretely, this translates to setting expectations for how long something will last based on how long it has already existed.
Variants
- Informed priors: Adjust estimate if you know something about the subject matter (e.g. human life spans, quality of construction, etc.).
- Power-law distributions: Multiply quantity observed so far by a constant. For the base case of uninformed priors, the constant is 2.
- Normal distributions: Use the distribution’s average — and if the observation has already passed the average, predict a bit further.
- Erlang distributions: Predict that things will go on just a constant amount further. (These estimates are “memoryless”.)
Overfitting
Situation
Determining how much data to collect in order to make a decision
Algorithm
Don’t over think. It’s not always better to use a more complex model with more factors to consider. In fact, predictions become drastically worse and you end up optimizing for the wrong things with perverse effects.
Variants
- Cross-Validation: Take away data points at random and see if the model predicts the missing ones. Use other forms of evaluation to check for correlation.
- Penalize Complexity: For every factor added to the model, there must be a corresponding significant improvement in the results. Use heuristics when you don’t have full confidence in the information you have.
- Early Stopping: Slow the speed of incoming data to prevent the model from becoming more complex with time (and avoid rushing into fads). More time to consider a problem may lead to overfitting. Going with your first instinct may be the most rational solution the more complex, unstable, and uncertain a decision may be.
Relaxation
Situation
Figuring out how to deal with intractable problems
Algorithm
Relax the problem — remove some constraints and solve the easier variant, which will inform the solution for the real one. This gets you “close enough” most of the time.
Variants
- Continuous Relaxation: Instead of having hard discrete constraints (i.e. whole numbers), allow for continuous solutions (i.e. fractions) and round them as necessary.
- Lagrangian Relaxation: Turn the constraints into penalties in the scoring system for solutions. Allow breaking rules and seeing what the consequences would be.
Randomness
Situation
Deciding when to rely on chance versus fully reasoning out an answer
Algorithm
When a problem is intractable (discrete optimizations commonly so) and can’t be comprehended in entirety, it is worthwhile to start by running a few sample simulations (Monte Carlo Method). Enough observations of output can quickly give rise to near-certainty on which direction to head in. Tolerate an error rate in order to save significant time or space.
Variants
- Hill Climbing: Assemble a baseline solution and then permute it, looking for a slight local improvement. You may reach a local maximum, at which point you either make a few random changes or pick a brand new random baseline solution to start from.
- Metropolis Algorithm: Do Hill Climbing, but as you make tweaks, randomly accept changes that hurt the solution. However, the worse the alteration is, the less willing you should be to take it. This helps you escape local maxima.
- Simulated Annealing: Start with more jittering (accepting random inferior modifications more readily) early on, then becoming more conservative later. After some time, only accept strict improvements (pure Hill Climbing).
Networking
Situation
Wanting to know if your message is getting through to another party, or how to deal with nonresponsiveness
Algorithm
If you don’t get a response within a certain period (depending on what’s reasonable for the medium), try again in one unit of time, then randomly between 1–2 units, then randomly between 1–4 units, 1–8 units, etc. (Exponential Backoff)
Variants
- Additive Increase, Multiplicative Decrease: If struggling to allocate limited resources in uncertain and fluctuating (congested) conditions, try adding things linearly until system collapse — then divide by half and start increasing again.
- Backchannels: When listening to someone speak, it is important to send feedback in the form of acknowledgements — this helps them regulate the flow of information and results in better storytelling.
- Tail Drop for Bufferbloat: When a queue of requests gets too large for a system to handle, it is actually better if the system starts rejecting new requests rather than deferring indefinitely. An explicit notification about overload would save both parties time and uncertainty.
Game Theory
Situation
Wanting to understand the minds of other people in a competitive setting
Algorithm
The Nash equilibrium of strategies (a set of strategies that both parties would be satisfied following with full transparency) is actually not globally optimal. (See the prisoners’ dilemma or tragedy of the commons.) Instead, change the game: change the equilibrium point itself, making a different set of strategies mutually beneficial or changing the worst case to be not as bad.
Variants
- Evolutionary mechanism design: Human emotions like anger or love tend to override rational behavior — but this may actually end up better for society as a whole.
- Information cascades: Be wary of fads and bubbles — many people rushing to the same conclusion may actually just be self-reinforcing beliefs and corresponding actions. If you have doubts, take them seriously and find some way to broadcast them as you move forward lest others continue to be misled.
- Vickrey Auctions: The holy grail of mechanism design is to change the game in a way where honesty becomes the best policy. This is often possible by deferring decisions to agents you trust to represent your best interests, instead of trying to over-solve yourself.
Computational Kindness
Situation
Presenting problems (or solutions) to other people
Algorithm
Protect others from unnecessary tension, friction, and mental labor. Don’t present too many options and don’t make them think too hard. This is ultimately how we be good to each other. 🙂
