On the existence of pure epsilon-equilibria
summary
The gist
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.
In short
The paper investigates when pure epsilon-equilibria exist in many-agent games by analyzing how agent utilities are correlated and whether agents' actions are correlated. It uses a 'Master Theorem' to classify action profiles based on these dependencies, showing that for large numbers of agents, the probability of finding an epsilon-equilibrium converges to 1 under certain conditions.
Key concepts
- Pure Epsilon-Equilibrium
- This is a state where no agent can improve their outcome by deviating by more than a tiny amount (epsilon > 0). It's a relaxation of the standard Nash equilibrium concept, allowing for near-optimal stable outcomes even when perfect optimization isn't possible.
- Master Theorem
- A classification tool used to categorize action profiles in many-agent games based on their dependence structure. It helps determine whether an action profile is likely to be a pure epsilon-equilibrium by analyzing its local and global dependencies.
- Correlation Across Action Profiles
- This refers to situations where the utility received by one agent depends not just on their own actions, but also on the actions taken by other agents. The paper shows that this correlation significantly impacts whether an epsilon-equilibrium exists.
- Asymptotic Distribution
- This describes how the number of pure epsilon-equilibria behaves as the number of agents becomes very large. The paper predicts this behavior, showing it can converge to a standard Gaussian distribution under specific conditions related to correlations.
Terminology used across episodes
This episode discusses
The paper
On the existence of pure epsilon-equilibria · Read on arXiv
Bary S.R. Pradelski, Bassel Tarbush
CNRS · University of Oxford
Transcript
Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.
Ruth: We're looking at the paper: "On the existence of pure epsilon-equilibria".
Warren: Here's the gist of the paper. 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<ref:2502.07585#pg2> 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 ≈ 0.63<ref:2502.07585#pg4> 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<ref:2502.07585#pg5> Existence Conditions Across Models The paper investigates the existence and distribution of pure epsilon-equilibria in many-agent games by studying different dependency structures of utilities, including independence across agents and action profiles, correlation across agents but not action profiles, and correlations across action profiles<ref:2502.07585#pg3> The results are framed within a "Master Theorem" that classifies action profiles based on whether they are pure epsilon-equilibria<ref:2502.07585#pg2> (i) Independent, continuous case: When utilities are drawn independently across agents and across action profiles from a continuous distribution, as the number of agents n gets large, the probability that a game admits a pure Nash equilibrium converges to 1 - 1/e ≈ 0.63<ref:2502.07585#pg8> For any epsilon > 0, the probability that a pure epsilon-equilibrium exists converges to 1 as n gets large, and the standardized number of pure epsilon-equilibria converges in distribution to a standard Gaussian if epsilon is smaller than the range of possible utilities<ref:2502.07585#pg8> (ii) Correlation across agents: When utilities are drawn independently across action profiles but with positive or negative correlation across agents, as the number of agents gets large, the probability that a pure Nash equilibrium exists converges to 1 and their standardized number converges in distribution to a standard Gaussian<ref:2502.07585#pg9> For any epsilon > 0, existence obtains even for negatively correlated utilities if the correlation-tuning parameter is bounded below by a constant exceeding-2epsilon<ref:2502.07585#pg10> (iii) Correlation across action profiles: When utilities are drawn independently across agents but are correlated across action profiles, as the number of agents gets large, the number of pure Nash equilibria converges in distribution to Poisson(1) and hence the probability that a pure Nash equilibrium exists converges to 1 - 1/e For epsilon > 0, the standardized number of pure epsilon-equilibria converges in distribution to a standard Gaussian and the probability that a pure epsilon-equilibrium exists converges to 1 (iv) Utility ties: When utilities are measured at a finite resolution (utility ties), if the set from which utilities are drawn grows faster than the number of agents, the number of pure Nash equilibria converges in distribution to Poisson(1) and hence the probability that a pure Nash equilibrium exists converges to 1 - 1/e If it grows slower than the number of agents, the standardized number converges in distribution to a standard Gaussian and the probability that a pure Nash equilibrium exists converges to 1 How the training signal is built The core of the analysis relies on defining well-behaved indicator grids for action profiles, where an indicator I a records whether a profile a is a pure epsilon-equilibrium The Master Theorem then uses Chen–Stein and Stein’s method to analyze the asymptotic distribution of the sum of these indicators The Master Theorem reduces the proofs of Theorems 1 to 5 to two steps: first, showing that the induced indicator grid is well-behaved, and second, showing that the asymptotic conditions of the Master Theorem hold The dependence range r n,m is shown to be 1 in models with independence and grows with n in graphical games Where the gains come from The asymptotic behavior of the sum of indicators is governed by its mean; if the mean converges to a constant then the sum is asymptotically Poisson, if the mean diverges then it is asymptotically Gaussian with probability converging to 1 The proof of Theorem C.1 and Theorem C.2 utilizes bounds derived from Lemma A.3 and Lemma A.4, which establish relationships between the distribution of sums of dependent Bernoulli random variables and Poisson or Gaussian distributions The Master Theorem Part (ii) is satisfied when the quantity min (mu n,m b 2 n,m / sigma 3 n,m, mu n,m b n,m p n,m + theta n,m + theta n,m) converges to 0 This condition is satisfied in cases where the variance lower bound and the mean term are sufficiently small relative to the threshold epsilon Pruning redundant reasoning tokens The paper establishes that relaxing the requirement of optimization by allowing agents to be within any epsilon > 0 of their respective optima ensures the general existence of stable outcomes This is demonstrated through Theorem 1 Part (b), which shows that for any fixed epsilon > 0 the probability that a game admits a pure epsilon-equilibrium converges to 1 as the number of agents gets large The analysis also provides tight thresholds for zero-sum games, showing that asymptotic non-existence of pure epsilon-equilibria holds even for small but positive values of epsilon when agents have sufficiently many actions This threshold on epsilon is tight for zero-sum games with sufficiently many actions The study extends to correlation across action profiles, where the existence of pure epsilon-equilibria is determined by a tolerance-correlation trade-off The threshold on epsilon is tight for zero-sum games with sufficiently many actions The paper unifies and explains seemingly contradictory results from previous literature by showing that the common framework of the Master Theorem allows disparate results to be understood within a single structure The equivalence between the independent-continuous model and the independent-discrete model is established at a specific epsilon star, which replicates outcomes from one model in the other Where the gains come from The results are applied to various game structures, including matching games, network games on expander graphs, and graphical games The analysis of correlation across action profiles involves restricting the interaction graph to be a gamma-expander This expansion property is crucial for establishing the independence required by the Master Theorem for these games The utility model in zero-sum cases with lambda = -1 exhibits log-concave densities, which simplifies the analysis of the mean and variance of pure epsilon-equilibria This property allows for a direct application of Markov's inequality to establish convergence to 1 for zero-sum games The analysis of the variance in correlation across action profiles involves intricate lower bounding techniques, where the variance is shown to be bounded below by terms that tend to zero as n increases This ensures that the standardized number of pure epsilon-equilibria converges in distribution to a standard Gaussian under certain conditions Pruning redundant reasoning tokens The paper provides explicit bounds for the variance of the number of pure epsilon-equilibria, showing that it is bounded by terms like (n M) 17/2 e(-n 20 ln 2) These bounds are derived through careful application of Lemma D.3 and the geometric properties of the indicator grids The proof of Theorem 4 demonstrates that for epsilon > 0 and c > 1/ln(1/theta epsilon F,2), the variance lower bound tends to zero, satisfying the hypotheses of the Master Theorem Part (ii) The paper also shows that for zero-sum games with sufficiently many actions, asymptotic non-existence of pure epsilon-equilibria holds even for small but positive values of epsilon This is a significant extension of prior results in the literature The study also shows that the indicator grids induced by the independence-continuous model and by the independent-discrete model are identical up to epsilon star, implying that they satisfy the same asymptotic conclusions under identical circumstances This formal equivalence allows replicating outcomes from one model in the other The paper concludes by showing that for any (A, j) in the index set, a game whose utilities are drawn from J n,(A,j) induces an indicator grid where the dependence range is 1 and local pair-correlation is of order at most n This structure allows for a unified analysis using the Master Theorem The results are highly general, applying to various strategic environments such as matching games and network games The paper provides a framework where epsilon-equilibrium is treated as an ordinal relaxation of optimization, which is consistent with literature on bounded rationality This approach is complementary to existing existence results, as games adhering to sufficient conditions for pure epsilon-equilibrium have measure zero in this setting The Master Theorem provides a common framework for understanding seemingly disparate results by bounding the dependence between nearby profiles The paper concludes with a result that for any (A, j) in the index set, a game whose utilities are drawn from J n,(A,j) induces an indicator grid where the dependence range is 1 and local pair-correlation is of order at most n This structure allows for a unified analysis using the Master Theorem The results are highly general, applying to various strategic environments such as matching games and network games
Title and authors: Ruth: So we're looking at this paper titled "On the existence of pure epsilon-equilibria," written by Bary S.R. Pradelski and Bassel Tarbush, and it seems like the main focus is on how to find stable outcomes in these many-agent games when you don't have to be perfectly optimized.
Warren: It sounds like they’re tackling the idea that even if agents aren't playing their absolute best moves, as long as they are within some small epsilon of their best move, we still get stable outcomes in a lot of these complex games where everyone's payoff depends on everyone else’s choices.
Iris: So it seems like the core question they’re asking is what conditions on the game structure and how those payoffs are distributed allow us to guarantee that at least one pure epsilon-equilibrium exists when we let agents be slightly suboptimal <ref:2502.07585#pg1>.
Ruth: Exactly, and they start by setting up a framework called a "master theorem" that sorts action profiles based on whether they qualify as a pure epsilon-equilibrium <ref:2502.07585#pg2>.
Warren: And the implication for us is that this isn't just about finding the absolute best strategy; it’s about understanding the landscape of stable outcomes when agents have some room to maneuver, even if that room is tiny, epsilon greater than zero <ref:2502.07585#pg1>.
Iris: They seem to be using this large number limit approach, looking at what happens as the number of agents gets really big to see which behaviors are likely to appear in the long run <ref:2502.07585#pg2>.
The paper's summary: Ruth: The paper summarizes their findings by breaking down how different dependency structures—like whether utilities are independent or correlated across agents—affect the existence of these epsilon-equilibria <ref:2502.07585#pg3>.
Warren: It’s interesting because they look at three main scenarios: utilities being independent and continuous, correlation across agents but not actions, and correlation across actions themselves <ref:2502.07585#pg3>.
Iris: For the independent continuous case, as the number of agents gets large, the probability that a pure Nash equilibrium exists is known to be around one minus one over e, about sixty-three percent <ref:2502.07585#pg8>.
Ruth: But for epsilon greater than zero in that same independent continuous setting, they show the probability of finding a pure epsilon-equilibrium actually converges to one as the number of agents increases <ref:2502.07585#pg1>.
Warren: That’s a big difference, right? So even when you can't find the perfect optimum, being close enough is almost certain for large numbers of agents in that specific setup <ref:2502.07585#pg1>.
Iris: And they also looked at utility ties, which is when payoffs are measured with some finite resolution, and their findings there depend on how fast those utility values grow compared to the number of agents <ref:2502.07585#pg3>.
The paper's improvements: Ruth: One of the key improvements they make is showing that this master theorem framework can unify results from a lot of different prior literature by showing how disparate things fit together <ref:2502.07585#pg1>.
Warren: They specifically point out that they establish an equivalence between the independent continuous model and the independent discrete model at a certain epsilon star, which means their results from one setup match up with the other under specific conditions <ref:2502.07585#pg1>.
Iris: And they also provide some very tight thresholds for zero-sum games, showing that even when agents have a lot of actions, you still have an asymptotic non-existence of pure epsilon-equilibria for small but positive epsilon <ref:2502.07585#pg1>.
Ruth: And they also identified a correlation threshold dependent on epsilon that is tight for zero-sum games, which is something new to focus on in that area <ref:2502.07585#pg1>.
Warren: So the improvement here isn't just proving existence; it’s defining exactly where the boundaries are for when you can expect these outcomes to exist under different correlation patterns <ref:2502.07585#pg1>.
Iris: And they use graphical games on interaction graphs with logarithmic expansion to analyze the correlation across action profiles, which is a specific tool they use to make sure their independence assumptions hold for those models <ref:2502.07585#pg3>.
Conclusion: Ruth: So to wrap up the "On the existence of pure epsilon-equilibria" paper, it seems like the main message is that relaxing the optimization requirement by allowing agents to be within some epsilon greater than zero of their best move ensures stable outcomes in a broad class of many-agent games <ref:2502.07585#pg1>.
Warren: They show that for any fixed epsilon greater than zero, the probability that a game admits a pure epsilon-equilibrium converges to one as the number of agents gets large <ref:2502.07585#pg1>.
Iris: And they also provide these precise thresholds for correlation across action profiles, showing how you need to balance tolerance against correlation to get existence in zero-sum games <ref:2502.07585#pg1>.
Ruth: It’s a lot of structure here, but the core idea is that the master theorem provides a common way to look at these different dependency patterns without getting lost <ref:2502.07585#pg1>.
Warren: So we have this framework that helps us predict where those epsilon-equilibria show up, whether it’s in zero-sum games or games with more complex interactions <ref:2502.07585#pg1>.
Iris: I just want to say that they do a lot of careful work on the variance bounds, showing that for certain conditions, the standard number of pure epsilon-equilibria converges in distribution to a standard Gaussian <ref:2502.07585#pg3>.
Ruth: It’s solid work on asymptotic behavior, moving beyond just checking if a solution exists to describing the shape of the distribution around that solution <ref:2502.07585#pg3>.
Warren: So for anyone interested in how AI might predict these things in large games, this paper gives them a solid mathematical structure to work with <ref:2502.07585#pg1>.
More episodes
- Daily Summary for 2026-11-19
- 2608.21274-Recommendation Quality and the Concentration of Consumption: Experimental Evidence from Netflix
- 2408.02757-A nonparametric test for diurnal variation in spot correlation processes
- 2306.16393-High-Dimensional Canonical Correlation Analysis
- 2605.17299-Geometric Brownian motion with intermittent entries and exits
- 2607.04753-Fooling Yourself: how narratives shape beliefs
- 2408.14671-Inference on Treatment Effects with Repeatedly Mismeasured High-Dimensional Controls
- 2201.06898-Difference-in-Differences Estimators for Treatments Continuously Distributed at Every Period
- 2501.15307-Influence Functions: A Unified Differentiation-Based Framework
- The day in conversation for 2026-11-19