no. 16 · Tuesday 17 November 2026
Finding pure Nash equilibria in large random games
Abstract
Best Response Dynamics (BRD) constitute a family of strategy update rules designed to identify Pure Nash Equilibria (PNEs) in strategic games. In each iteration, a player is selected uniformly at random and adopts a best response strategy, maximising their payoff given the current strategies of the other players. If no improvement is possible for the selected player, another is chosen. The process terminates upon reaching a state where no player wishes to deviate, corresponding to a PNE. However, convergence is not guaranteed as either PNEs may not exist, or the dynamics may become confined within substructures of the game, which we call traps, that admit no PNEs. We investigate this behaviour in the context of random games with $N$ players, each choosing between two actions and receiving independently and identically distributed payoffs. The payoff distribution is permitted to have atoms, allowing for the possibility of ties. The induced dynamics define a class of random walks on the $N$-dimensional hypercube, where the landscape includes two types of absorbing sets: PNEs and traps. Our analysis encompasses BRD, simple random walks, and a broad class of nearest-neighbour processes. We prove that, with high probability, these dynamics reach a PNE before encountering any trap. Our results complete and generalise the ones by Amiet, Collevecchio, Scarsini and Zhong (2021), using a different approach.
- comments
- 28 pages, 4 figures, 1 table. To appear in Mathematics of Operations Research
- fields
- Probability