Game connectivity and adaptive dynamics in many-action games
We study the typical structure of games in terms of their connectivity properties. A game is said to be `connected' if it has a pure Nash equilibrium and the property that there is a best-response path from every action profile which is not a pure Nash equilibrium to every pure Nash equilibrium, and it is generic if it has no indifferences. In previous work we showed that, among all -player -action generic games that admit a pure Nash equilibrium, the fraction that are connected tends to as gets sufficiently large relative to . The present paper considers the large- regime, which behaves differently: we show that the connected fraction tends to as gets large, where . In other words, a constant fraction of many-action games are not connected. However, is small and tends to rapidly with , so as increases all but a vanishingly small fraction of many-player-many-action games are connected. Since connectedness is conducive to equilibrium convergence we obtain, by implication, that there is a simple adaptive dynamic that is guaranteed to lead to a pure Nash equilibrium in all but a vanishingly small fraction of generic games that have one. Our results are based on new probabilistic and combinatorial arguments which allow us to address the large- regime that the approach used in our previous work could not tackle. We thus complement our previous work to provide a more complete picture of game connectivity across different regimes.