Game Connectivity and Adaptive Dynamics
For game theorists and economists, it shows that connectivity is typical in games with pure Nash equilibria, enabling simple dynamics to succeed in most cases.
This paper proves that in almost all generic games with a pure Nash equilibrium, the best-response graph is connected, meaning every non-equilibrium action profile can reach every equilibrium via best-response paths. This implies that simple adaptive dynamics converge almost surely to a pure Nash equilibrium in such games, contrasting with the impossibility for all generic games.
We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that, among games that are `generic' (without indifferences) and that have a pure Nash equilibrium, all but a small fraction are \emph{connected}, meaning that every action profile that is not a pure Nash equilibrium can reach every pure Nash equilibrium via best-response paths. This has important implications for dynamics in games. In particular, we show that there are simple, uncoupled, adaptive dynamics for which period-by-period play converges almost surely to a pure Nash equilibrium in all but a small fraction of generic games that have one (which contrasts with the known fact that there is no such dynamic that leads almost surely to a pure Nash equilibrium in \emph{every} generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity.