Pure Nash Equilibria and Best-Response Dynamics in Random Games

Ben Amiet, Andrea Collevecchio, Marco Scarsini, Stephen Zhong

Research output: Contribution to journalArticleResearchpeer-review

Abstract

In finite games, mixed Nash equilibria always exist, but pure equilibria may fail to exist. To assess the relevance of this nonexistence, we consider games where the payoffs are drawn at random. In particular, we focus on games where a large number of players can each choose one of two possible strategies and the payoffs are independent and identically distributed with the possibility of ties. We provide asymptotic results about the random number of pure Nash equilibria, such as fast growth and a central limit theorem, with bounds for the approximation error. Moreover, by using a new link between percolation models and game theory, we describe in detail the geometry of pure Nash equilibria and show that, when the probability of ties is small, a best-response dynamics reaches a pure Nash equilibrium with a probability that quickly approaches one as the number of players grows. We show that various phase transitions depend only on a single parameter of the model, that is, the probability of having ties.
Original languageEnglish
Number of pages23
JournalMathematics of Operations Research
DOIs
Publication statusAccepted/In press - 14 Jun 2020

Cite this