On the existence of pure epsilon-equilibria

Abstract

Departing from optimizing behavior by any $\epsilon >0$ ensures the existence of stable outcomes in a broad class of many-agent games where utilities are drawn from a joint distribution. Specifically, in a game with iid drawn utilities from a continuous distribution and any $\epsilon >0$, we show that as the number of agents gets large the probability that a pure $\epsilon$-equilibrium exists converges to 1, while, by contrast, the probability that a pure Nash equilibrium exists is known to converge to $1-1/e\approx 0.63$. The asymptotic existence of pure $\epsilon$-equilibrium extends to utilities that are negatively correlated across agents, and we identify a correlation threshold dependent on $\epsilon$ that is tight for the zero-sum case. We also study the cases of correlation across action profiles and of utility ties and, in all cases, we also characterize the asymptotic distribution of pure $\epsilon$-equilibria. Regarding pure Nash equilibrium---i.e., when $\epsilon =0$---our results nest, organize, and extend the existing literature. All our results and those from the prior literature are applications of our ``master theorem'', which builds on the Chen--Stein method and Stein's method.