Pure Nash Equilibria and Best-Response Dynamics in Random Games

Ben Amiet (), Andrea Collevecchio, Marco Scarsini and Ziwen Zhong ()
Additional contact information
Ben Amiet: School of Mathematics, Monash University, Melbourne, Victoria 3800, Australia
Ziwen Zhong: School of Mathematics, Monash University, Melbourne, Victoria 3800, Australia

Mathematics of Operations Research, 2021, vol. 46, issue 4, 1552-1572

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.

Keywords: pure Nash equilibrium, random game, percolation, best response dynamics, Primary: 91A10, secondary: 91A06, 60K35, Primary: Games/group decisions: noncooperative; secondary: probability: Markov processes (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1102 (application/pdf)

Related works:
Working Paper: Pure Nash Equilibria and Best-Response Dynamics in Random Games (2020)
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:inm:ormoor:v:46:y:2021:i:4:p:1552-1572

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().