Game connectivity and adaptive dynamics in many-action games
For game theorists and economists, this work clarifies the typical structure of large games and provides a practical convergence guarantee for adaptive dynamics.
The paper studies the connectivity of many-action games, showing that as the number of actions grows, a constant fraction of games are not connected, but for many players this fraction is small and vanishes rapidly. They also provide an adaptive dynamic that converges to a pure Nash equilibrium in almost all generic games that have one.
We study the typical structure of games in terms of their connectivity properties. A game is `connected' if it has a pure Nash equilibrium and there is a best-response path from every action profile which is not a pure Nash equilibrium to every pure Nash equilibrium; a game is generic if it has no indifferences. In previous work we showed that, among all $n$-player $k$-action generic games that admit a pure Nash equilibrium, the fraction that are connected tends to $1$ as $n$ gets sufficiently large relative to $k$. Here, we consider the large-$k$ regime, which behaves differently: we show that the connected fraction tends to $1-ζ_n$ as $k$ gets large, where $ζ_n>0$ is an explicit constant. Thus, a constant fraction of many-action games are \emph{not} connected. However, for $n\geq3$, $ζ_n$ is small and tends to $0$ rapidly with $n$, so as $n$ increases all but a vanishingly small fraction of many-player-many-action games are connected. Since connectedness is conducive to equilibrium convergence, we find a simple adaptive dynamic that is guaranteed to converge to a pure Nash equilibrium in all but a vanishingly small fraction of generic games that have one. We rely on new probabilistic and combinatorial arguments to tackle the large-$k$ regime.