Sparse Large-Scale Random Games are Weakly Acyclic

For dynamics that do not couple between players, not much is known on convergence to a Nash equilibrium (NE) beyond the case of potential games. However, empirically, many dynamics do in fact converge to a NE. We aim to narrow this gap by showing that a large family of sparse graphical games have converging approximate better-replay (or best-response) dynamics. Graphical games well capture scenarios where not all players (and actions) directly affect all other players (and actions), which is often the case in games on networks. Our result follows by defining a random graphical game and show that under certain sparsity conditions, it is weakly-acyclic with high probability (with respect to the number of players). Weak acyclicity is a necessary condition for converge which is also sufficient for many randomized dynamics.