The Evolution of Conventions

Consider an $n$-person game that is played repeatedly, but by different agents. In each period, $n$ players are drawn at random from a large finite population. Each player chooses an optimal strategy based on a sample of information about what other players have done in the past. The sampling defines a stochastic process that, for a large class of games that includes coordination games and common interest games, converges almost surely to a pure strategy Nash equilibrium. Such an equilibrium can be interpreted as the “conventional” way of playing the game. If, in addition, the players sometimes experiment or make mistakes, then society occasionally switches from one convention to another. In this case some conventions (i.e., equilibria) are “a priori” more probable than others. Moreover, as the likelihood of mistakes goes to zero, only some of the equilibria have positive probability in the limit. We show how to compute these “stochastically stable equilibria” using the theory of perturbed Markov processes.