Algorithms to Live By

1. Optimal Stopping Problem
----------------------------
Intuitively, we think that rational decision making means exhaustively enumerating the options, weighing each one carefully and then selecting the best. But in practice, when the clock is ticking, few aspects of decision making are as important as this one: when to stop. 

2. Explore/Exploit
----------------------
A sobering property of trying new things is that the value of exploration, or finding a new favourite, only goes down over time. TLDR; if you're in a place for the long haul, try out new things. If it's your last night, go to the trusty old cafe. 

The Grittins index tells us how likely is it for the grass to be "greener on the other side of the fence." The untested rookie is seemingly worth more than the veteran since we know so little about him. 

If all this choice-making math is too much for you, focus on reducing regret. 

The Upper Confidence Bound algorithms offer a formal justification for the benefit of doubt. Be excited to meet new people and assume the best of them- this minimizes regret. 

A/B testing won Obama campaign millions, by using CONTRIBUTE instead of DONATE. 

Adaptive clinical trials seem more ethical than controlled experiments. Are they accepted now? 

People tend to over-explore. 

It might be worth going back to the bad restaurant after a few years, hoping the management is better now. Forgiveness. 

Early exploration may be ingrained into our nature - think of children doing all sorts of weird things. 

On advice from elders: When your grandfather tells you which restaurants are good, you should listen. But you should sometimes explore too (expecting them to be worse.)

Exploration NECESSARILY means being let down most of the time. 

3. Sorting
---------------
The most fundamental insight of Sorting Theory: scale hurts. 

At the cost of searching drops, sorting becomes less valuable. 

For Single elimination tournaments, Silver medal is a lie. Round Robin and Ladder are too expensive but more ROBUST. 

Nature is slow and steady, hence ROBUST. 

Much as we bemoan the daily rat race, the fact that it is a RACE rather than a FIGHT is what sets us apart from other animals. Other animals have pecking orders. 

4. Caching
------------
The easiest way to make a "common reading" curriculum is to put the recently returned book at the front (of the library) BRILLIANT. 

Caching web-page content and keeping them geographically closer, is what the giant AKAMAI does. Amazon uses "Anticipatory Package Shipping"

When you're deciding what to throw away: use LRU. 
When you're keeping things, exploit geography. Keep things where they're needed the most. 
Noguchi Filing system: Return everything to the left (open) side. This exploits Temporal Proximity. 

We forget BECAUSE we cache. Memory, thus, is perfect design in light of given constraints. 
Brain-fart = Cache Miss 

5. Scheduling 
---------------
Start with the lightest wash - Pipelining. 

Make your goals explicit. Choose the right metric. 

People PRE-Crastinate (do whatever is in front of them), even when it is irrational to do so. 

Pathfinder on Mars had the problem with its task scheduling: Priority Inversion. 

Think about Precedence Constraints. 

The slightest change in common/simple problems tips it over to the realm of `intractability`.

Even with perfect knowledge, scheduling may be intractable. Instead, thinking on your feet and doing the best you CAN do, may be better and much easier to compute. Speed vs accuracy tradeoff. 

Preemption isn't free. Context switches are expensive. You are right to use Pomodoro/be lazy when you don't have much time before the next scheduled one. 

Brian things Writing Code is like like blacksmithing, it takes some time to warm up. 

If you do too many things, you will likely run into THRASHING. A system that uses all its resources to just keep switching and organizing, instead of doing something useful. 
Solution? Just learn to say no. 
And if you're already overloaded, work DUMBER instead of HARDER. At least you'll get something done. 

Throughput vs Responsiveness: Establishing a minimum amount of time commitment to a given task may be the right balance. Decide how responsive you want to be, and if you want to get things done, be no more than that. You may also use INTERRUPT COALESCING to do work in batches at fixed intervals. 

6. Bayes's Rule
----------------- 
Laplace's law lets us make predictions based on observations = w+1/n+2

Bayes's law needs some prior, even if it is a guess. 

Knowing about how the distributions look like for different kids of data gives us good intuition, which leads to good priors to be used with Bayes's law. 
- Power-law, Normal, Erlang distributions and Multiplicative, average or additive rules 

In cases we don't have good priors, our intuitions/predictions are crap. 

Failing the Marshmellow test and doing worse later in life may be because children learn that adults are not dependable. It's important to grow up in a good environment with adults present and trustworthy. 

If you want to be a good intuitive Bayesian, protect your priors. This may mean turning off the news. 

7. Overfitting 
---------------
Extra factors, other than giving us diminishing returns, may even give us worse performance. 

Incentive structures work, but you have to be very careful because people overfit to them, and this may have negative unforeseen consequences. 

Example, Training scars. Police officer giving back gun to criminal right after disarming them because that motion has been drilled into muscle memory. Use validation sets to protect against/detect these. 

Constrained by the past = less fit for the present, but more robust for the future. On the limitations of slow human evolution

More time = more complexity.
When in the dark, the best-laid plans are the simplest. Occam's razor. 

8. Relaxation
--------------
Relaxing constraints in a problem make it suboptimal, but infinitely faster. 

Maybe relax from Discrete to Continous, solve and then change back domain? 

Relax + ScoreKeep on a metric to punish that action. Lagrangian Relaxation. Parenting 101. 

Relaxations give us a baseline model/realistic bound on the solution. 

9. Randomness
--------------
Space vs Time tradeoff is the most familial in Computer Science. 

Greedy Algorithm = Myopic = Local Optimization = Anarchy is still withing a certain % of the optimal. 

Hill Climbing, Metropolis Algorithm, Simulated Annealing (decreasing random noise inserted)

Always act on good ideas, even if you sometimes act on bad ones. 
Likelihood of following a bad idea should be inversely proportional to how bad the idea is. Front-load randomness and then slowly temper yourself. 

10. Networking 
--------------
For Circuit switching, performance decreases exponentially with size. For packet switching, it increases with size. 

ACK packets are important. So is numbering packets and a protocol. This helps you not go into the rabbit hole of infinite recursion. 

Exponential Backoff for congestion resolution. 
We also use AIMD (Additive Increase, Multiplicative Decrease) to give us the Sawtooth shape

"control without hierarchy"

Peter Principle = if you've been rising and got stuck, you perform badly in the current job. So firms sometimes use the Cravath system: only hire recent grads and fire people who got stagnated. Maybe use AIMD instead? 

Backchannels: flow control in linguistics. You may be performing terribly at speaking because the audience is not responding. 

Problem: Bufferbloat 
Possible Solution? Tail Drop: Just drop packets as the buffer fills up. 
Advice: This is the problem with our current networking. We're always BUFFERED with notifications. 
Implementing: Explicit Congestion Notification

11. Game Theory
---------------
Determining how many equilibria a problem has, let alone finding it, has proven intractable. (exponential)

The major insight of traditional game theory: with every agent playing rationally, the equilibria that are established need not necessarily be the best outcome for all agents involved. 

Mechanism Design, by doing game theory in a reversed way, sets up wanted equilibria. 

Individually, we're better off making rational decisions. As a society, we're better off with irrational defiance. (Would you tackle a burglar or give the store owner the equivalent cash?)

Information cascades can make "consensus" unglued from reality and every agent acts "rationally" by making the irrational decision. 

Be wary of cases where public information exceeds private information, where you know more about what people are doing than why they're doing it. 
Remember, actions are not beliefs. Cascades happen because we misinterpret what people THINK based on what they DO. 

Vikrey equilibrium is the best kind of auction because everyone is forced to be honest. CORS! This cuts the Fordian knot of recursion, and may just as well be optimal in most cases!

*** Conclusion
---------------
There are a lot of algorithms that can be mapped directly to the human domain. 

Remember, if you've followed the best possible PROCESS, you've done all you could. May not guarantee the best OUTCOME. Don't beat yourself up over it. 

If you're stuck on a complex problem, approximate, relax and use strategic randomness. Sometimes good enough is good enough. 

Giving people specifically, limited choices is most of the times better than giving them full flexibility (meeting scheduling, for example)

Be "Computationally Kind" by taking some of the computational burdens off other people. 
Make the problem easier for people, most problems are intractable and hard in the real world. 

Instead of being polite, be polite in stating your preferences. (I'm inclined towards x, what do you think?)

Be more forgiving to yourself. 

In the face of hard problems, making assumptions, choosing simpler solutions, using approximations, the trade-off error instead of delay, and taking chances != being irrational. It's the definition of rationality.