# Game Connectivity and Adaptive Dynamics

arXiv: https://arxiv.org/abs/2309.10609 · HTML: https://mlsanity.com/paper/2309.10609/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2023.

## Built on by (most cited first, 1 of 1)

- [What preferences can - and cannot - predict in multi-agent online learning](https://mlsanity.com/paper/2608.13810/) (2026)

## Abstract (arXiv)

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 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 every generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity.