Pure Nash Equilibria and Best-Response Dynamics in Random Games

Ben Amiet, Andrea Collevecchio, Marco Scarsini and Ziwen Zhong

Papers from arXiv.org

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 i.i.d. 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 Nash equilibria and show that, when the probability of ties is small, a best-response dynamics reaches a Nash equilibrium with a probability that quickly approaches one as the number of players grows. We show that a multitude of phase transitions depend only on a single parameter of the model, that is, the probability of having ties.

Date: 2019-05, Revised 2020-06
New Economics Papers: this item is included in nep-gth, nep-hpe and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://arxiv.org/pdf/1905.10758 Latest version (application/pdf)

Related works:
Journal Article: Pure Nash Equilibria and Best-Response Dynamics in Random Games (2021)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:1905.10758

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().