“Finite Rationality and Interpersonal Complexity in Repeated Games,” E. Kalai & W. Stanford (1988)

We haven’t talked about any good hardcore theory for a while now, so let’s take a look at some results from an extension of games that deal with something called a finite automata. First, the results from Kalai and Stanford’s well-known Econometrica, then an interesting equilibrium concept based on automata from a 2004 JET by Rani Spiegler.

Since Herbert Simon (no, friends, restrictions of infinitely complex decisionmaking did not start with Kahneman and Tversky!), many economists have been wary about requiring agents in their models to be “too smart.” A natural restriction on, say, strategies in a repeated game is that those strategies involve a finite amount of complexity, in a way to be made precise shortly. For example, you might imagine a firm playing a repeated game, where even if the CEO is “infinitely smart,” he must explain the firm strategy to a subordinate in some finite length of time. Computer scientists long ago constructed an idea that captures this exactly: the finite automata. Roughly, a strategy can be played by a finite automata if, summing up every subgame including those off the equilibrium path, the knowledge of game history necessary to play the strategy can be summarized by a finite number of “states”. For example, consider a repeated prisoner’s dilemma. A player whose strategy plays Cooperate (C) no matter what the history and no matter the other player does in the current period is playing a strategy of complexity one. A player who plays tit-for-tat is playing a strategy of complexity two: C if the opponent played C in the previous period, and D otherwise. An infinite automata would be needed to play a strategy that, taking the binary expansion of pi, defects every time the current period is 0, cooperates if the current period is 1, and plays defect for the next two periods if anyone defects on a 1 period.

Infinitely repeated games with discounting have the unfortunate property of being bound by a folk theorem: any individually rational set of payoffs can be sustained in equilibrium, if we let the discount rate go to 1. The construction of equilibrium strategies can be tricky indeed. It’s safe to say that many game theorists do not “believe” that a lot of equilibria you can construct with folk theorems are reasonable predictions of the outcome of a game. One reason for this disbelief is that the necessary equilibrium-sustaining strategies can be very difficult to figure out. This may make you wonder: what do we gain by restricting ourselves to strategies playable by a finite automata?

Kalai and Stanford show that we actually don’t gain very much. Consider the following intuition from a repeated prisoner’s dilemma. The grim trigger strategy is of countably infinite complexity, and it sustains (C,C) as an equilibrium. But there is a related epsilon-equilibrium of finite complexity: just have both players cooperate in every period after N, where N is sufficiently far away in the future, but otherwise play grim trigger. This intuition generalizes such that there is a finite complexity set of strategies generating a subgame perfect epsilon-equilibrium whose vector of payoffs is epsilon close to that of any payoff vector that can be generated using infinitely complex strategies. In a nice class of games (which includes repeated prisoner’s dilemma), the necessary complexity of any one player’s strategy can be determined by the product of complexity of all other players. This implies that in a two player game (satisfying the required conditions), there are equilibria where both players use strategies of identically minimal complexity. Intuitively, if I want to punish someone, I will need them to be able to react to all the contingencies I induce, so I need them to be “as smart” as I am in the sense above.

Kalai and Stanford is neither the first nor the last word on finite automata in games – a field called algorithmic game theory, where computers play games against each other, has obvious uses for such results. A nice use of automata in standard game theory is a recent paper by Rani Speigler on NEWTs – Nash Equilibria with Tests. The idea is that, if a player is to play some strategy in a repeated game other than a myopic best response, he sometimes needs to “justify” that stage game strategy to an outside observer or referee. In particular, if I claim to be avoiding myopic best response because of a threat by my opponent that I am worried about, the outside observer would like me to test that threat; e.g., if I claim that cutting military spending will lead my enemy to ramp up his own military, and that this is why I can’t cut spending, I must cut for at least one period to show this result. In 2×2 games, NEWTs get rid of a lot of undesirable equilibria. For instance, if there is a stage game payoff that is both individually rational and Pareto optimal, then that is the only strategy profile played in a NEWT after a short experimentation phase. A game where (A,A) pays (3,3), (B,A) and (A,B) pay (1,1) and (B,B) pays (0,0) can sustain any average per-period payoff per player between 1 and 3 as a perfect equilibria by the standard folk theorem result. In a NEWT, any player who deviates to B for some periods needs to justify that by the threat that the opponent will, say, play B forever if I don’t go to B for the next few periods. The outside observer in the NEWT implicitly wants you to justify your belief in that off-equilibrium threat by actually going to B for a period (and if you do so, clearly the opponent will stay playing A). Outside of two-player games, though, I’m afraid this solution concept might be a bit tough to use; do any of you readers know of an extension to more general games?

https://europealumni.kellogg.northwestern.edu/research/math/papers/679.pdf (Kalai and Stanford final working paper; full publication in Econometrica 1988).

http://www.tau.ac.il/~rani/newt.pdf “Testing Threats in Repeated Games,” by R. Spiegler, final version from 2004 JET. Big thumbs up to Rani for putting final published versions of his papers on his website.