Rare Nash Equilibria and the Price of Anarchy in Large Static Games

Daniel Lacker () and Kavita Ramanan ()
Additional contact information
Daniel Lacker: Columbia University, New York, New York 10027
Kavita Ramanan: Brown University, Providence, Rhode Island 02912

Mathematics of Operations Research, 2019, vol. 44, issue 2, 400-422

Abstract: We study a static game played by a finite number of agents, in which agents are assigned independent and identically distributed random types and each agent minimizes its objective function by choosing from a set of admissible actions that depends on its type. The game is anonymous in the sense that the objective function of each agent depends on the actions of other agents only through the empirical distribution of their type-action pairs. We study the asymptotic behavior of Nash equilibria, as the number of agents tends to infinity, first by deriving laws of large numbers characterizing almost sure limit points of Nash equilibria in terms of so-called Cournot-Nash equilibria of an associated nonatomic game. Our main results are large deviation principles that characterize the probability of rare Nash equilibria and associated conditional limit theorems describing the behavior of equilibria conditioned on a rare event. The results cover situations when neither the finite-player game nor the associated nonatomic game has a unique equilibrium. In addition, we study the asymptotic behavior of the price of anarchy, complementing existing worst-case bounds with new probabilistic bounds in the context of congestion games, which are used to model traffic routing in networks.

Keywords: nonatomic games; mean field games; Nash equilibrium; Cournot-Nash equilibrium; large deviation principle; price of anarchy; congestion games; entry games; conditional limit theorems (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2018.0929 (application/pdf)

Related works:
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:44:y:2019:i:2:p:400-422

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 ().