Explaining “Hell is Game Theory Folk Theorems”

I, along with many commenters, found the explanation in Hell is Game Theory Folk Theorems somewhat unclear. I am re-explaining some of the ideas from that post here. Thanks to jessicata for writing a post on such an interesting topic.

1-shot prisoner’s dilemma.

In a 1-shot prisoner’s dilemma, defecting is a dominant strategy. Because of this, (defect, defect) is the unique Nash equilibrium of this game. Which kind of sucks, since (cooperate, cooperate) would be better for both players.

Nash equilibrium.

Nash equilibrium is just a mathematical formalism. Consider a strategy profile, which is a list of which strategy each player chooses. A strategy profile is a Nash equilibrium if no player is strictly better off switching their strategy, assuming everyone else continues to play their strategy listed in the strategy profile.

Notably, Nash equilibrium says nothing about:

  • What if two or more people team up and deviate from the Nash equilibrium strategy profile?

  • What if people aren’t behaving fully rationally? (see bounded rationality)

Nash equilibria may or may not have predictive power. It depends on the game. Much work in game theory involves refining equilibrium concepts to have more predictive power in different situations (e.g. subgame perfect equilibrium to handle credible threats, trembling hand equilibrium to handle human error).

n-shot prisoner’s dilemma.

OK, now what if people agree to repeat a prisoner’s dilemma n=10 times? Maybe the repeated rounds can build trust among players, causing cooperation to happen?

Unfortunately, the theory says that (defect, defect) is still the unique Nash equilibrium. Why? Because in the 10th game, players don’t care about their reputation anymore. They just want to maximize payoff, so they may as well defect. So, it is common knowledge that each player will defect in the 10th game. Now moving to the 9th game, players know their reputation doesn’t matter in this game, because everyone is going to defect in the 10th game anyway. So, it is common knowledge that each player will defect in the 9th game. And so on… This thought process is called backwards induction.

This shows that the unique Nash equilibrium is still (defect, defect), even if the number of repetitions is large. Why might this lack predictive power?

  • In the real world there might be uncertainty about the number of repetitions.

  • (again) people might not behave fully rationally—backwards induction is kind of complicated!

Probably the simplest way to model “uncertainty about the number of repetitions” is by assuming an infinite number of repetitions.

infinitely repeated prisoner’s dilemma. OK, now assume the prisoner’s dilemma will be repeated forever.[1]

Turns out, now, there exists a Nash equilibrium which involves cooperation! Here is how it goes. Each player agrees to play cooperate, indefinitely. Whenever any player defects, the other player responds by defecting for the rest of all eternity (“punishment”).

technical Q: Hold on a second. I thought Nash equilibrium was “static” in the sense that it just says: given that everybody is playing a Nash equilibrium strategy profile, if a single person deviates (while everyone else keeps playing according to the Nash equilibrium strategy profile), then they will not be better off from deviating. This stuff where players choose to punish other players in response to bad behavior seems like a stronger equilibrium concept not covered by Nash.

A: Nope! A (pure) strategy profile is a list of strategies for each player. In a single prisoner’s dilemma, this is just a choice of “cooperate” or “defect”. In a repeated prisoner’s dilemma, this is much more complicated. A strategy is a complete contingency plan of what the player plans to do, given any possible history of the repeated game (even unrealized histories). So, for example, in the 5th game, a strategy isn’t just a choice of “cooperate” or “defect”. It is a choice of: “What do I do if the other player has played (C,C,C,C) until now? What do I do if the other player has played (C,C,C,D) until now? What do I do if the other player has played (C,C,D,D) until now? [...]” So, for this infinitely repeated game, the strategy profile of “everyone cooperates, until one asshole defects, and then we punish the asshole forever” is in fact simply a list of strategies (= complete contingency plans) for each player. And, it happens to be a Nash equilibrium.

the Hell example.

Finally, we explain what the hell is going on in the Hell example. Recall the setup:

Stage game: There are 100 players. Each player picks an integer between 30 and 100. Then, every player earns disutility equal to the average of the numbers everybody picked. (The “hell” intuition is because: imagine the number between 30 and 100 as temperature in Celcius. The bigger the number the worse off you are.)

Note that playing 30 is a strictly dominant strategy in the stage game: no matter what the other people do, you make the average slightly cooler by playing 30, so you may as well do that. So, the unique Nash equilibrium of the one-shot Hell game is where everyone puts 30.

Now consider what happens when this Hell game is infinitely repeated. Weirdly, there are many more Nash equilibria than just “everyone puts 30”. Why? Same intuition as with the prisoner’s dilemma.

For example, here’s a Nash equilibrium: “Everyone agrees to put 99 each round. Whenever someone deviates from 99 (for example to put 30), punish them by putting 100 for the rest of eternity.”

Why is this strategy profile a Nash equilibrium? Because no player is better off deviating from this strategy profile, assuming all other players stick to the strategy profile. Specifically: any player that deviates (for example by putting 30), will get a small bit of relief in the short term. But then, because of the way this strategy profile is specified, that player (along with everyone else) will have to live with a temperature of 100 (minus epsilon) for the rest of time. Which is worse than just going with the default and putting 99 each round.

The number 99 isn’t unique—this works with any payoff between 30 and 100. (This is the technical condition of “feasibility”.) There’s also another technical condition about minimax individual rationality: basically, each player can always guarantee themselves their own minimax payoff, by definition of minimax. So, there can never be a Nash equilibrium where a player earns less than their minimax payoff, because they have a profitable deviation by playing their minimax strategy instead. Something something don’t get distracted by the boilerplate.

What are folk theorems in general? They are theorems (with actual proofs—they’re called “folk” because they were already well-known in the 50s, but people did not bother to codify them in the academic literature until the 70s) which discuss situations like the Hell game. Usually they have the form: “If some stage game is repeated many times, then there are very many equilibria, which work by having players punish anyone who deviates.” The reason why there are lots of these theorems is you can vary this basic setup, for example by introducing a discount factor.

Conclusion/​TLDR.

  • Nash equilibrium is just a mathematical formalism that says: “no player is better off unilaterally deviating from this particular strategy profile”. It sometimes has predictive power but sometimes does not.

  • Folk theorems say that repeated games often have very many Nash equilibria, some of which are weird and would never happen in a one-shot setting.

    • For example, infinitely repeated prisoner’s dilemma has a Nash equilibrium where everyone plays cooperate, until someone defects, in which case everyone plays defect until the end of time. (In addition to the standard “everyone defects until the end of time” equilibrium.)

    • And, this infinitely repeated Hell game has a whole bunch of Nash equilibria: for any temperature x between 30 and 99, all players can agree to play x, until someone defects, in which case everyone plays 100 until the end of time.

  • The infinitely repeated Hell game having so many Nash equilibria really demonstrates how limited the concept of Nash equilibrium can be. How the hell would the strategy profile “Everyone plays 99, unless someone defects [by the way this could be by playing 30, an action which literally helps everyone], in which case we play 100” arise in the real world? The answer is… that’s a good question. Sometimes obviously bad Nash equilibria occur and sometimes we avoid them. These sorts of questions start to leave the realm of theoretical game theory (where you model problems with rigorous definitions and prove theorems about them) and enter behavioral economics, sociology, etc.

  1. ^

    Technical note: you might wonder what a player’s utility from this game is. You can’t just give player utility equal to the sum of their payoffs in each of the individual stage games, because 1+1+1+… and 2+2+2+… are both infinity. Instead, each player will earn utility equal to the average of their payoffs in each of the stage games. Or more specifically, the lim inf of partial averages.