Convergence of best response dynamics to pure Nash equilibrium

Question

In a 2 player game with a unique pure nash equilibrium (PNE), what are the conditions for the best response dynamics to converge to this PNE? Both players have concave and continuous utility functions and the best response functions are linear. I see in my simulations that no matter where I start, the iterated best response dynamics always finds the Nash Equilibrium, but is there a generalization of this and a theorem you can direct me to? Thanks.

Answer 1

The paper you're after is Milgrom & Roberts (1990) Econometrica 'Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities'.

In particular, supermodular games, as defined in the paper, are a broad class of games in which iterated best-response dynamics converge to (pure strategy) Nash equilibrium (though these need not be unique). One sometimes sees this in simple oligopoly models where best-replies happen to be contractions; this is, of course, far from necessary though as the linked paper illustrates.

In particular, a simple two-player case when best replies converge is given by when:

1. Each agent's strategy space is a compact interval in $\mathbb{R}$.
2. Payoff functions for each player are twice continuously differentiable.
3. The cross derivatives of the payoff functions are positive.

For a significant step up in generality see Theorem 4 in particular.