Title: Rare Nash Equilibria and the Price of Anarchy in Large Static Games,
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 characterizes 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.