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.