Speaker: Doyne Farmer, (Home Page)
Paper: "When Will Players Coordinate on the Nash Equilibrium of a Game"
(Joint work with Tobias Galla and James Sanders)
In game theory it is common to assume that outcomes are described by Nash equilibria. But under what circumstances are players able to coordinate on a Nash equilibrium? What if there are an enormous number of Nash equilibria to choose from? Is it possible to know in advance when players will easily converge to a unique equilibrium? And what are the alternatives when they do not converge?
We address these questions for the case of randomly generated games, with players using several different learning rules, including reinforcement learning and level k learning. We find that there are striking regularities in the resulting behavior. For games with many possible moves (which are nice because they are analytically tractable), we find that the behavior can be predicted in advance by only two parameters. One of these is the correlation between the playoffs of the players, which characterizes the extent to which the game is zero sum, and the other is the timescale for learning. When the game is zero sum and the timescale for learning is short, the strategies converge to a unique equilibrium, but when the opposite is true, they live on a chaotic attractor that can be of high dimension, so that the behavior is substantially random. With more players the chaotic region increases. Under level k learning the chaotic region decreases, but does so very slowly as the level of learning gets deeper. This work suggests that in many circumstances the standard assumption that economic behavior can be characterized by a unique equilibrium, or even a small number of equilibria, may be wrong.