When you come to the 2^100 forks in the road...

In some simple games, it is easy to spot Nash equilibria. For example, if I prefer Chinese food and you prefer Italian, but our strongest preference is to dine together, two obvious equilibria are for both of us to go to the Chinese restaurant or both of us to go to the Italian restaurant. Even if we start out knowing only our own preferences and we can’t communicate our strategies before the game, it won’t take too many rounds of missed connections and solitary dinners before we thoroughly understand each other’s preferences and, hopefully, find our way to one or the other equilibrium.
 
But imagine if the dinner plans involved 100 people, each of whom has decided preferences about which others he would like to dine with, and none of whom knows anyone else’s preferences. Nash proved in 1950 that even large, complicated games like this one do always have an equilibrium (at least, if the concept of a strategy is broadened to allow random choices, such as you choosing the Chinese restaurant with 60 percent probability). But Nash — who died in a car crash in 2015 — gave no recipe for how to calculate such an equilibrium.
 
By diving into the nitty-gritty of Nash’s proof, Babichenko and Rubinstein were able to show that in general, there’s no guaranteed method for players to find even an approximate Nash equilibrium unless they tell each other virtually everything about their respective preferences. And as the number of players in a game grows, the amount of time required for all this communication quickly becomes prohibitive.
 
For example, in the 100-player restaurant game, there are 2&100 ways the game could play out, and hence 2^100 preferences each player has to share. By comparison, the number of seconds that have elapsed since the Big Bang is only about 2^59.
 

Interesting summary of a paper published last year that finds that for many games, there is not clear path to even an approximate Nash equilibrium. I don't know whether this is depressing or appropriate to the state of the world right now, it's probably both. Also, it's great to have mathematical confirmation of the impossibility of choosing where to eat when with a large group.

Regret is a fascinating emotion. Jeff Bezos' story of leaving D.E. Shaw to start Amazon based on a regret minimization framework is now an iconic entrepreneurial myth, and in most contexts people frame regret the same way, as something to be minimized. That is, regret as a negative.

In the Bezos example, regret was a valuable constant to help him come to an optimal decision at a critical fork in his life. Is this its primary evolutionary purpose? Is regret only valuable when we feel its suffocating grip on the human heart so we avoid it in the future? As a decision-making feedback mechanism?

I commonly hear that people regret the things they didn't do more than the things they do. Is that true? Even in this day and age where one indiscretion can ruin a person for life?

In storytelling, regret serves two common narrative functions. One is as the corrosive element which reduces a character, over a lifetime of exposure, to an embittered, cynical drag on those around them. The second is as the catalyst for the protagonist to make a critical life change, of which the Bezos decision is an instance of the win-win variety.

I've seen regret in both guises, and while we valorize regret as life-changing, I suspect the volume of regret that chips away at people's souls outweighs the instances where it changes their lives for the better, even as I have no way of quantifying that. Regardless, I have no contrarian take on minimizing regret for those who suffer from it.

In that sense, this finding on the near impossibility of achieving a Nash equilibrium in complex scenarios offers some comfort. What is life or, perhaps more accurately, how we perceive our own lives but as a series of decisions, compounded across time.

We do a great job of coming up with analogies for how complex and varied the decision tree is ahead of us. The number of permutations of how a game of chess or Go might be played is greater than the number of atoms in the universe, we tell people. But we should do a better job of turning that same analogy backwards in time. If you then factor in the impact of other people in all those forks in the road, across a lifetime, what we see is just as dense a decision tree behind us ahead of us. At any point in time, we are at a node on a tree with so many branches behind it that it exceeds our mind's grasp. Not so many of those branches are so thick as to deserve the heavy burden of regret.

One last tidbit from the piece which I wanted to highlight.

But the two fields have very different mindsets, which can hamper interdisciplinary communication: Economists tend to look for simple models that capture the essence of a complex interaction, while theoretical computer scientists are often more interested in understanding what happens as the models grow increasingly complex. “I wish my colleagues in economics were more aware, more interested in what computer science is doing,” McLennan said.

Game theory of thrones

Peter Antonioni uses game theory to analyze the situation in Westeros to see if he can determine who will end up on the Iron Throne.

Game theory doesn’t look at behaviour so much as it looks at outcomes, assuming that people will choose the highest payoff if they can.

Martin even helps on a couple of occasions by spelling out those payoffs. Advising Joffrey, the fearsome Tywin Lannister gives a great example of what to do in a repeated game:
 
Joffrey, when your enemies defy you, you must serve them steel and fire. When they go to their knees, however, you must help them back to their feet. Elsewise no man will ever bend the knee to you.
 
This is a pretty good distillation of a what game theorists call tit-for-tat. If you start off with equal participants in a repeated game, the best overall strategies combine punishing transgression with forgiveness; there are variants, but all of them get better results than “all or nothing” punishment strategies such as the grim trigger.
 
Tywin’s strategy works in this case because it assumes a capability for punishment. In advising Joffrey, he’s not telling him how to gain the Iron Throne but how to hang on to it. The equilibrium stays stable as long as the Throne can dominate all of the potential competitors, as Aegon I could with his dragons. Then, rebellion is easily put down, and whatever the consequence to the smallfolk of Westeros, at least they don’t get the kind of devastation inflicted on the Riverlands by the War of the Five Kings.
 

The strategic maneuvering and statecraft are the most intriguing aspects of Game of Thrones. I'm less interested in the economics or religion, though I was amused by this proposal for a central bank in Westeros.

Overall, the rulers, religions, and other institutions of the known world all seem to lack the fundamental characteristics necessary to function as a central bank of Westeros. The difficulty of creating long lasting, independent, and benevolent institutions, I would argue, is why the Seven Kingdoms of Westeros use a commodity currency and lack monetary policy. But I don’t think a central bank in Westeros is impossible. In fact, there is one institution in the realm that does have these characteristics and could potentially serve as a central bank: the Night’s Watch.
 
The watch operates independently of the crown, has existed for thousands of years, and is dedicated to the public good. The longevity of the Watch is undebatable, as it was reportedly founded 8,000 years before the time of Game of Thrones.   Their staunch independence is evidenced by the nuetrality they maintained during the rebellion that unseated the Targaryens. The Watch’s military might ensures they can maintain that independence. Their dedication to the public good is seen in the mission of the Watch, which is the protection of the Seven Kingdoms.
 
Members of the watch currently serve in one of three groups: Rangers, Builders, and Stewards. It’s easy to imagine adding Economists as a fourth group, and adding price stability and full employment to oath that all members must swear to. Public acceptance would likely require the crown mandating that Night’s Watch currency be accepted as legal tender. But after that, the Night’s Watch could independently determine the money supply and even conduct monetary policy.
 

Sawmell Tarly, Westeros Fed Reserve Chairman?

The game theory of the toilet seat problem

By toilet seat problem I refer to the problem of a couple living together, one man and one woman, sharing one toilet. To be more mathematically specific:

For Marsha the seat position transfer cost is 0 since all operations are performed with the seat in the down position. For John the cost is greater than 0 since seat position transfers must be performed.
 
Let p be the probability that John will perform a #1 operation vs a #2 operation. Assume that John optimizes his seat position transfer cost (see remark 3 below.) Then it is easy to determine that John’s average cost of seat position transfer per toilet opeation is
 
B = 2p(1-p)C
 
where B is the bachelor cost of toilet seat position transfers per toilet operation.
 
Now let us consider the scenario where John and Marsha cohabit and both use the same toilet. In our analysis we shall assume that John and Marsha perform toilet operations with the same frequency (see remark 4 below) and that the order in which they perform them is random. They discover to their mutual displeasure that their cohabitation adversely alters the toilet seat position transfer cost function for each of them. What is more there is an inherent conflict of interest.
 

This is one of the more rigorous game theory considerations of the toilet seat problem I've read. The solution proposed at the end seems sensible enough.

Let's not allow our current technological constraints and limited imagination confine our solution set, however. I propose a different, even more ideal solution.

We develop a toilet seat that is in communication with the Apple Watch worn by both the man and the woman. When the woman walks into the bathroom, her Apple Watch authenticates itself to the toilet seat which then automatically lowers itself. Meanwhile, when the man walks in, the toilet seat remains in whatever position it's in, per the widely accepted bachelor toilet seat strategy. One could try to further optimize for the man by learning, Nest-style, the general pattern of #1 and #2 operations and caching the last 24 to 48 hours worth of such operations, but the added complexity may only capture a slight marginal decrease in cost to him.

There is yet another solution, brought to mind by episode 4 of season 4 of Curb Your Enthusiasm, in which Larry David admits to peeing sitting down. Optimal for her, and, David claims, good for him as well.

“If I pee twenty times in a day I can get through the whole New York Times, for god's sake!”

That's two posts today that mention bathroom operations. My mind is really in the toilet.

Game theory of life

In what appears to be the first study of its kind, computer scientists report that an algorithm discovered more than 50 years ago in game theory and now widely used in machine learning is mathematically identical to the equations used to describe the distribution of genes within a population of organisms. Researchers may be able to use the algorithm, which is surprisingly simple and powerful, to better understand how natural selection works and how populations maintain their genetic diversity.

By viewing evolution as a repeated game, in which individual players, in this case genes, try to find a strategy that creates the fittest population, researchers found that evolution values both diversity and fitness.

Some biologists say that the findings are too new and theoretical to be of use; researchers don’t yet know how to test the ideas in living organisms. Others say the surprising connection, published Monday in the advance online version of the Proceedings of the National Academy of Sciences, may help scientists understand a puzzling feature of natural selection: The fittest organisms don’t always wipe out their weaker competition. Indeed, as evidenced by the menagerie of life on Earth, genetic diversity reigns.

Fascinating. It's tempting to try to imagine where the value of both fitness and diversity might extend outside of genetics. Clearly it has value in finance in portfolio theory; perhaps it matters in organizations, too? Personal ideology? Friend selection? Team construction?

Salute to the Cold War game theorists

The new field of game theory had already provoked several re-thinks about nuclear policy in the 1950s and 1960s, and that’s what saved us. In the 1950s, game theorist John von Neumann understood that nuclear weapons imposed an existential crisis on humanity, and required a completely different attitude towards conflict. He developed the doctrine of Mutually Assured Destruction (MAD), based on concepts of rational deterrence and the Nash equilibrium. By the time he died in 1957, he’d taught the Pentagon policy-makers that if the U.S. and the Soviet Union could utterly destroy each other even after one launched a nuclear first strike, there could be no rational incentive for nuclear war. This was the most important insight in applied psychology, ever. You don’t have to feel emotional sympathy with the enemy; you only have to expect that he will act in accordance with his perceived costs, benefits, and risks. The more certain he is that a nuclear assault will result in his own extermination, the less likely he is to launch one.

...

So, even before I was born, the game theorists had tamed the existential threat of nuclear weapons through some simple psychological insights. We must respect the enemy’s rationality even if we cannot sympathize with his ideals. We must understand his costs and benefits even if we don’t share his fears and hopes. We must behave rationally enough that we don’t attack first (which would be suicidal) – yet we must act crazy and vengeful enough that the enemy thinks we’ll retaliate if we’re attacked, even after it would be futile and spiteful (Robert Frank nicely explained this deterrence logic in his classic book Passions within Reason.) And we must understand that if both players do this, both will be safe.

It's not Memorial Day, it's Veterans Day, but this piece on appreciating the Cold War game theorists still felt timely.

The Nash Equilibrium of Silicon Valley

A "Nash equilibrium" solution is one where, when both parties have considered all available moves, minimizes damage to themselves under the assumption the other player is a selfish dickhead. In a capitalist environment like America's, with no social controls or other factors besides ruthless logic, this is the default behavior. And it should be, if games are strictly competitive and humans are built like computers.

A "Pareto optimal" solution is one which, given all the possibilities of action, produces the best outcome for both parties (with some negotiable surplus).

The Prisoner's Dilemma demonstrates that a Nash equilibrium solution is not always Pareto optimal. The "confess-confess" solution is the Nash equilibrium. You will always be better off screwing the other person over, whether they are honest or dishonest. The "deny-deny" solution is Pareto optimal. If both parties can somehow trust each other, they will both be better off selecting this solution.

...
When someone like Elon Musk comes along, someone who is clearly is working very hard toward Pareto optimal outcomes (watch or read about his personal history), we simply cannot fathom that his actions can't be explained outside a traditional Nash-equilibrium, dog-eat-dog model of capitalism.

Of course, this applies way beyond Tesla. I believe the current skepticism around Silicon Valley's "Make The World a Better Place" mentality is deeply rooted in historical anxiety about institutional capitalism. I don't think this anxiety is misplaced. Rather, I think that technology, specifically the World Wide Web presents a "way out" of this dilemma. It will take time, but ultimately, the Web's power is that it can mimic the "accountability" aspect of local transactions, but on a global scale.
 

From Chris Johnson, whose blog I just stumbled across for the first time.

The unfortunate part of the Game of Thrones between the tech titans in Silicon Valley (Amazon, Apple, Google, Facebook, Twitter) is that the industry as a whole has tended towards Nash Equilibriums. 

In general, healthy competition is good for consumers, and I'm of that camp, especially when there is one dominant entity. In many areas, though, we have companies devoting precious resources to building out a near clone of another's company's services just for defensive purposes. It's not just an issue with patents. Is it critical that we have yet another streaming music service? Another mapping app for mobile devices? Is it good for consumers when services for one company are kept off another company's hardware/software ecosystem just for competitive reasons? So many of our best and brightest are building repeated work because of tribal (company) affiliation.

Teach your garden to weed itself

From an excerpt from Steven Levitt and Stephen Dubner's new book Think Like a Freak:

Van Halen's live show boasted a colossal stage, booming audio and spectacular lighting. All this required a great deal of structural support, electrical power and the like. Thus the 53-page rider, which gave point-by-point instructions to ensure that no one got killed by a collapsing stage or a short-circuiting light tower. But how could Van Halen be sure that the local promoter in each city had read the whole thing and done everything properly?

Cue the brown M&M's. As Roth tells it, he would immediately go backstage to check out the bowl of M&M's. If he saw brown ones, he knew the promoter hadn't read the rider carefully—and that "we had to do a serious line check" to make sure that the more important details hadn't been botched either.

And so it was that David Lee Roth and King Solomon both engaged in a fruitful bit of game theory—which, narrowly defined, is the art of beating your opponent by anticipating his next move.

Both men faced a similar problem: How to sift the guilty from the innocent when no one is stepping forward to profess their guilt? A person who is lying or cheating will often respond to an incentive differently than an honest person. Wouldn't it be nice if this fact could be exploited to ferret out the bad guys?

We believe it can—by tricking the guilty parties into unwittingly revealing their guilt through their own behavior. What should this trick be called? In honor of King Solomon, we'll name it as if it is a lost proverb: Teach Your Garden to Weed Itself.
 

I'd read the brown Van Halen brown M&M story before in Atul Gawande's wonderful book The Checklist Manifesto, but this excerpt contains one story I hadn't seen before, about the medieval ritual of adjudicating by some horrific ordeal.