Equilibria of Dynamic Games with Many Players: Existence, Approximation, and Market Structure

Sachin Adlakha; Ramesh Johari; Gabriel Y. Weintraub

Source-linked AI summary

Equilibria of Dynamic Games with Many Players: Existence, Approximation, and Market Structure

Sachin Adlakha, Ramesh Johari, Gabriel Y. Weintraub

arXiv:1011.5537v5Nov 25, 2010cs.GT

TL;DR

The paper addresses obstacles to analyzing dynamic games as player numbers grow and connects this challenge to a longstanding industrial-organization question. It develops conditions under which stationary equilibrium exists and approximates Markov perfect equilibrium, while linking those conditions to fragmented market structure.

Problem
The paper addresses analytical obstacles that arise as the number of players grows large and engages a longstanding industrial-organization research question.
Method
The paper develops conditions on model primitives for stationary-equilibrium existence and approximation of Markov perfect equilibrium, using oblivious-player strategies in the stationary-equilibrium framework.
Results
The stated conditions ensure stationary equilibrium existence and approximation results, while also implying decreasing returns to higher states and fragmented market structure.
Takeaways & Limitations
The paper connects the validity of stationary equilibrium to market fragmentation in dynamic games with many players.
Takeaways & Limitations
The paper provides sufficient conditions, and when returns to higher states increase, stationary equilibrium may fail to approximate accurately or may not exist.

Abstract

from arXiv · show

In this paper we study stochastic dynamic games with many players; these are a fundamental model for a wide range of economic applications. The standard solution concept for such games is Markov perfect equilibrium (MPE), but it is well known that MPE computation becomes intractable as the number of players increases. We instead consider the notion of stationary equilibrium (SE), where players optimize assuming the empirical distribution of others' states remains constant at its long run average. We make two main contributions. First, we provide a rigorous justification for using SE. In particular, we provide a parsimonious collection of exogenous conditions over model primitives that guarantee existence of SE, and ensure that an appropriate approximation property to MPE holds, in a general model with possibly unbounded state spaces. Second, we draw a significant connection between the validity of SE, and market structure: under the same conditions that imply SE exist and approximates MPE well, the market becomes fragmented in the limit of many firms. To illustrate this connection, we study in detail a series of dynamic oligopoly examples. These examples show that our conditions enforce a form of "decreasing returns to larger states"; this yields fragmented industries in the limit. By contrast, violation of these conditions suggests "increasing returns to larger states" and potential market concentration. In that sense, our work uses a fully dynamic framework to also contribute to a longstanding issue in industrial organization: understanding the determinants of market structure in different industries.

1 Introduction

The paper develops stationary equilibrium (SE) as a tractable alternative to Markov perfect equilibrium (MPE) for stochastic games with many players, and connects SE validity to market fragmentation. Exogenous conditions guarantee SE existence and approximation of MPE while distinguishing decreasing-return, fragmented industries from increasing-return, potentially concentrated ones.

Motivation: MPE becomes difficult to compute and less plausible as the number of players grows because its state space expands and players must track others’ exact behavior.These obstacles motivate a simpler equilibrium concept for large-player stochastic games.
Stationary equilibrium: SE assumes players optimize against the long-run average distribution of other players’ states, making it simpler to compute and analyze than MPE.The approach uses the infinite-player limit to justify holding the empirical distribution fixed.
Theoretical foundations: The paper provides exogenous conditions on model primitives that guarantee SE existence, including in models with unbounded state spaces.This differs from prior SE existence results that typically study compact state spaces.
Theoretical foundations: The same conditions ensure that SE of infinite models appropriately approximate MPE of finite-player models as the number of agents increases.The conditions simultaneously deliver existence and a good approximation, rather than requiring approximation to be verified separately.
Market structure: Under these conditions, decreasing returns to higher states produce light-tailed equilibria and fragmented industries with no dominant firms in the many-firm limit.The paper interprets violations as increasing returns, under which SE may be inaccurate or fail to exist and market concentration may arise.
Market structure: The dynamic oligopoly examples show that increasing returns are associated with concentration, whereas decreasing returns support fragmentation and accurate SE approximations.The framework predicts market-structure features across a broad range of parameters and specifications in a fully dynamic setting.

2 Related Work

The paper situates its stationary-equilibrium results within literature on stochastic games, mean-field approaches, and approximation theory. It extends prior work by deriving primitive-based conditions that jointly deliver compactness, SE existence, MPE approximation, and market-structure implications.

Prior literature: Prior SE existence results focus on restricted game classes, compact state spaces, strategic complementarities, or specific oligopoly models.Earlier approximation results likewise rely on bounded or exogenously compact state spaces, linear-quadratic payoffs, or other specialized settings.
Paper's contribution: The paper replaces endogenous compactness or equilibrium-outcome assumptions with exogenous conditions on model primitives.These conditions guarantee compactness, existence of SE, and an appropriate approximation property.
Market structure: The paper connects equilibrium validity to market structure, using its conditions to derive sharp insights into dynamic industries.This contribution places SE approximation and industry structure within a fully dynamic framework.
Approximation: Unlike prior work, the framework combines primitive-based guarantees that all SE are light-tailed with asymptotic approximation of MPE.The paper emphasizes that light-tail conditions are guaranteed for all SE rather than imposed only on selected equilibrium outcomes.
Scope and extensions: The model is more general than related work and accommodates applications such as spillovers and learning-by-doing, but excludes endogenous entry and exit.The paper also claims a stronger approximation property than the cited prior work.

3 Preliminaries and Definitions

The paper formulates anonymous stochastic games and defines MPE, SE, and the asymptotic Markov equilibrium property. Players interact through aggregate state distributions, while MPE strategies track the full population state and become computationally difficult as the game grows.

Stochastic game model: The model is a discrete-time anonymous stochastic game with m players, individual states and actions, Markov transitions, discounted payoffs, and population-state interactions.Anonymity means payoffs and transitions depend on the empirical distribution of other players' states rather than their identities.
Stationary equilibrium: SE provides an alternative in which players use the long-run population distribution, and the asymptotic Markov equilibrium property requires SE to approximate MPE as player count increases.The paper motivates this approach by the expectation that fluctuations average out in large games.
Stochastic game model: Player states evolve conditionally independently through a transition kernel determined by the player’s state, action, and population state.The conditional-independence assumption rules out aggregate shocks common to all players and supports the asymptotic analysis.
Markov perfect equilibrium: A symmetric MPE requires every player’s cognizant strategy to maximize expected discounted payoff while tracking the current states of all players.Cognizant strategies depend on both the player’s own state and the current population state.
Markov perfect equilibrium: MPE computation becomes challenging because the population-state space grows rapidly with the number of agents or individual states.This curse of dimensionality restricts practical MPE computation to models with few agents and few individual states.

4 Preview of Results and Motivating Examples

The paper uses stationary equilibria to study when many-player dynamic industries fragment or concentrate. Its conditions support SE existence and approximation while distinguishing decreasing-return settings with fragmentation from increasing-return settings associated with concentration.

Economic interpretation: The paper’s conditions encode decreasing returns to higher states, whereas their violation corresponds roughly to increasing returns and possible market concentration.This dichotomy is used across the motivating industrial-organization examples.
Overview: The paper establishes conditions under which SE exist, approximate finite-player equilibria, and provide a tool for analyzing market structure.The analysis targets stochastic games with potentially unbounded state spaces, where existence and approximation are difficult to establish.
Overview: Light-tailed stationary equilibria satisfy the AME property and prevent a single dominant firm from emerging as the number of firms grows.Light tails limit population mass at large states and connect the approximation result to market fragmentation.
4.1 Dynamic Oligopoly Models: In the dynamic oligopoly model, decreasing returns to firm quality ensure SE existence, the AME property, and fragmentation in the many-firm limit.The sufficient condition is that the single-stage profit function exhibits decreasing returns to firm quality.
4.3 Learning-By-Doing: For learning-by-doing, diminishing returns prevent unbounded experience growth, allowing light-tailed SE and market fragmentation; without them, light-tailed SE may fail to exist.The examples apply the same theoretical architecture to different dynamic sources of firm advantage.

5 Theory: Existence

The theory constructs SE as fixed points of an equilibrium correspondence and supplies primitive conditions ensuring existence over unbounded state spaces. These conditions also yield light-tailed equilibria, which support the later AME result and imply fragmented market structure.

Fixed-point framework: The fixed-point approach applies Kakutani’s theorem to an equilibrium correspondence, requiring compactness, convexity, and appropriate continuity.A stationary equilibrium is obtained as a fixed point of Φ under these requirements.
Light-tailed equilibria: Light-tailed population states assign limited mass to large states, and the paper uses a weighted 1-p norm to formalize this property.Larger p places greater weight on larger states, so finite 1-p norms correspond to lighter tails.
Existence result: Under the existence conditions, all stationary equilibria are light-tailed, establishing the stronger characterization needed for the AME result.The paper states that these conditions produce a compact, convex invariant set and that every resulting SE has finite 1-p norm.
Continuity: Continuity assumptions on actions, payoffs, and transition kernels ensure that the equilibrium correspondence has a closed graph.The assumptions include compact actions, bounded increments, a payoff growth bound, and joint continuity in actions and population states.
Economic interpretation: The resulting conditions impose decreasing returns to higher states, yielding fragmented markets and supporting the use of SE as an approximation tool.The paper explicitly connects light tails to fragmentation and uses them with continuity assumptions to establish AME.

6 Theory: Approximation

Under the stated assumptions, stationary equilibria satisfy the AME property, linking existence to approximation of large finite-player dynamics. The result requires light-tailed invariant distributions and extends to population-dependent payoffs.

AME property: Under Assumption 1, any stationary equilibrium with f ∈ Fp satisfies the AME property.The paper identifies this as Theorem 2 and notes that the same assumption is also required for the relevant stationary equilibria to exist.
Existence and approximation: The AME property follows directly from existence under the paper’s assumptions, making the relationship between the two a central theoretical insight.
Proof mechanism: The proof uses convergence of empirical population states to f, payoff continuity, and growth-rate bounds under a finite 1-p-norm.The light-tail condition f ∈ Fp ensures that states rarely become too large under the invariant distribution.
Scope and novelty: The AME result is more general than related work because payoffs and transition kernels may depend on the population state.This dependence means agents’ states need not evolve independently and requires a different proof technique.
Limitation: The light-tail condition is consequential: stationary equilibria can exist without it even when the AME property fails.
Extensions: The theorem extends to payoff functions indexed by the number of players when πm converges to π and Assumption 1 is strengthened.Appendix B generalizes the result to settings where actual finite-player payoffs depend on m.

7 Examples Revisited

The examples show that the assumptions linking stationary-equilibrium existence and AME also impose market fragmentation. Across applications, this mechanism appears as decreasing returns or bounded growth at larger firm states.

Cross-example connection: The paper’s assumptions imply light-tailed stationary equilibria, so industries have fragmented market structures while AME holds.
Verification strategy: The examples reduce verification to Assumption 4 after continuity and convexity conditions are established, with Corollary 1 and Theorem 2 delivering the conclusions.
Product quality: For θ < 1, firms have decreasing marginal payoff returns to higher states, which stabilizes individual-firm dynamics and supports fragmentation.The condition makes the relevant transition image compact and separates fragmented from potentially concentrated industries.
Spillovers: The spillover example requires spillover effects not to become too large, reflecting the compactness condition needed for the main results.
Depreciation and growth: Decreasing marginal returns combined with depreciation prevent unbounded firm growth, producing fragmentation as the number of firms becomes large.
Learning by doing: In learning-by-doing models, decreasing productivity gains at higher states ensure light-tailed stationary equilibria and AME.A learning effect that remains very strong at large scale is associated with likely market concentration.

8 Conclusions

The paper establishes conditions ensuring stationary equilibrium exists, is light-tailed, and approximates MPE in large finite games. Its examples connect these conditions to decreasing returns and fragmented market structures.

Main conclusions: The main results provide a parsimonious set of primitive assumptions ensuring stationary equilibrium exists in a broad class of games.
Main conclusions: The same assumptions make stationary equilibrium light-tailed, approximate MPE in large finite games, and yield fragmented market structures.
Economic interpretation: The examples interpret the primitive conditions as enforcing decreasing returns to higher states.
Future research: Entry and exit, finite-model connections to oblivious equilibrium, and nonstationary equilibrium are identified as directions for future research.The nonstationary extension is motivated by approximating transitional short-run dynamics rather than long-run behavior.
Heterogeneous players: The paper extends its framework to heterogeneous players by incorporating type into an expanded state, after which the preceding results apply.Different types use different strategies because strategies depend on the extended state.

A.2 Coupling Through Actions

The framework extends to games where players’ actions jointly affect population state-action profiles, payoffs, and transitions. With finite action spaces, the AME and existence results continue under adapted assumptions.

Population state-action profile: The population state becomes a distribution over states and actions, with finite action spaces and randomized strategies over actions.
Model extension: When payoffs and transitions depend on competitors’ simultaneous actions, players evaluate them using expectations over randomized competitor strategies.
AME property: Under the extended assumptions, the AME property continues to hold for games with coupling through actions.The proof tracks the empirical state-action profile and carries over the convergence argument.
Existence analysis: The stationary-equilibrium existence analysis redefines invariant distributions over state-action pairs while retaining the maps P(f), D(µ,f), and Φ(f).
Existence result: Assumptions 1 and 4 imply existence of stationary equilibrium and finite 1-p norm for all such equilibria, using the closed-graph and compactness results.
Scope boundary: Finite action spaces are computationally manageable, while compact Euclidean action spaces require additional measure-theoretic complexity.

B Approximation: Sequence of Payoff Functions

For sequences of payoff functions indexed by player count, the paper strengthens its assumptions to establish that stationary equilibria retain the AME property. It also contrasts limit-model stationary equilibria with finite-model oblivious equilibria and notes possible failures under increasing returns.

The generalized result accommodates payoff functions πm that vary with the number of agents and converge to a limit payoff function π.
Under Assumption 5, any stationary equilibrium with f ∈ Fp satisfies the AME property.
Finite-model oblivious equilibria optimize against a constant long-run population state, whereas stationary equilibria are defined in the limit model.
Under a uniform light-tail condition, the sequence of finite-model oblivious equilibria satisfies the AME property.
Limit-model stationary equilibria may fail to exist even when oblivious equilibria exist for every finite model, particularly with increasing returns to scale.
The paper applies its results to supply-chain competition and consumer learning as additional examples.

C.1 Supply Chain Competition

The supply-chain application models firms that bid for inventory replenishment under demand uncertainty and procurement competition. Under proportional allocation, an SE exists and every SE has the AME property, supported by inventory costs that generate decreasing returns at high states.

Firms’ inventory evolves through demand depletion and procurement replenishment, with allocations increasing in own bids and decreasing in the population profile.
The limiting proportional-allocation function is increasing in a firm’s bid and decreasing in the population profile.
The firm’s single-period payoff equals retail revenue from demand served minus inventory-holding and procurement costs.
An SE exists for the proportional-allocation supply-chain model, and all SE possess the AME property.
Existence follows under positive expected demand together with continuity and boundedness conditions, zero allocation at zero bids, and negative inventory drift from myopically optimal zero bidding.
Because holding inventory is costly, payoffs decrease for sufficiently large inventories, yielding light-tailed population states under fairly weak primitive assumptions.

C.2 Consumer Learning

The consumer-learning application models experience-dependent product choice, where effort improves expected quality but experience and population expertise reduce outcome uncertainty. Its equilibrium result again depends on conditions preventing experience from generating increasing returns at high states.

Product quality is normally distributed with mean proportional to effort and variance depending on individual and population experience.
The model assumes uncertainty decreases with individual experience and with more expert population experience.
An individual’s experience changes through effort-driven learning and player-specific depreciation, while evolving stochastically over time.
The consumer-learning model has an SE whose AME property follows under the proposition’s stated conditions.
The sufficient-action set is constructed from myopically optimal actions, with negative state drift required for sufficiently small effort.
If marginal effort costs are not sufficiently large relative to marginal utility gains, high experience can continue increasing and a light-tailed SE may not exist.
The paper identifies a dichotomy: decreasing returns to higher states yield SE existence and AME, whereas increasing returns may not.

D Existence and AME: Preliminary Lemmas

The preliminary lemmas establish dynamic-programming regularity for unbounded state spaces using a weighted sup norm. They show contraction, convergence, continuity, Bellman optimality, and existence of optimal oblivious strategies.

Bounded increments and growth-rate bounds ensure finite value bounds needed for the contraction and convergence arguments.
The weighted sup norm uses W(x) = (1 + ∥x∥∞)^n to control value functions on the unbounded state space.
Under Assumption 1, the dynamic-programming operator is a k-stage ρ-contraction in the weighted sup norm for some 0 < ρ < 1.
Value iteration converges to the optimal value function, which satisfies the Bellman equation for every population state.
The value function is continuous in the population state, supporting continuity of the equilibrium correspondence.
At least one optimal oblivious strategy exists for every population state, and it maximizes the Bellman right-hand side state by state.

E.1 Closed Graph: Proof

The proof establishes that the best-response correspondence P is compact-valued and upper hemicontinuous, then uses these properties to show Φ has a closed graph.

E.1 Closed Graph: Proof: P(f) is compact for every f, and P is upper hemicontinuous on Fp.The argument builds compact-valued action correspondences using continuity and compactness, then applies closed-graph reasoning.
E.1 Closed Graph: Proof: For each state x, the optimal-action set P_x(f) is nonempty, compact-valued, and upper hemicontinuous by Berge’s maximum theorem.The maximand is jointly continuous in action and population state, while the action space A is compact.
E.1 Closed Graph: Proof: Compactness of P's range and upper hemicontinuity allow convergent subsequences of optimal strategies to remain optimal at the limit.Given fk → f and gk → g with gk ∈ Φ(fk), a subsequence of optimal strategies converges pointwise to µ ∈ P(f).
E.1 Closed Graph: Proof: Continuity of transitions and bounded increments lets the invariant-distribution relation pass to the limit, yielding g ∈ D(µ, f).The proof uses continuity in the population state and the fact that transitions vanish outside a bounded neighborhood of the current state.

E.2 Convexity: Proof

The proof shows that invariant distributions preserve convexity, while strict concavity or unique optimal actions deliver uniqueness of the optimal oblivious strategy.

E.2 Convexity: Proof: If two invariant distributions arise from optimal strategies, a strategy assembled from their positive-support actions remains optimal and supports the common invariant distribution.The construction defines µ using one optimal strategy where the target distribution is zero and combines actions where it is positive.
E.2 Convexity: Proof: Linearity of the Bellman objective in actions makes every convex combination of two optimal actions optimal.This preserves optimality when constructing a strategy associated with a convex combination of invariant distributions.
E.2 Convexity: Proof: The constructed distribution satisfies the invariant-distribution equations because terms outside its positive-support set vanish.The proof expands the equations for the two original distributions, sums over pure actions, and uses g(x)=0 outside the support.
E.2 Convexity: Proof: Under Assumptions 1 and 3, the optimal value function is strictly increasing, making the Bellman objective strictly concave in action.Strict concavity follows when payoff concavity and stochastic concavity of the transition kernel provide at least one strict component.
E.2 Convexity: Proof: Under Assumptions 1 and 2, the optimal action is unique, so P(f) is a singleton.The same singleton conclusion also follows under Assumptions 1 and 3 through uniqueness of the optimizer.

E.3 Compactness: Proof

The compactness proof combines monotonicity, coupling, tail control, and Foster–Lyapunov arguments to establish existence and compactness properties for stationary-equilibrium objects.

E.3 Compactness: Proof: Given x′ ≥ x, the transition increments can be coupled so that the resulting next state from x′ is at least the one from x almost surely.The coupling uses stochastically ordered increment distributions and extends inductively across periods.
E.3 Compactness: Proof: Optimal strategies approach the action set A′ at sufficiently large states, because otherwise a profitable deviation contradicts optimality.The contradiction argument constructs a deviation from a large state and uses bounded increments and tail payoff behavior.
E.3 Compactness: Proof: Every stationary-equilibrium correspondence Φ(f) is nonempty because an optimal oblivious strategy induces a Markov chain with an invariant distribution.The proof establishes a closed communicating class and then applies a Foster–Lyapunov criterion to obtain positive recurrence.
E.3 Compactness: Proof: The induced Markov chain has at least one closed class, since repeated reachability within a finite set would otherwise contradict the construction.States outside the finite set can reach it with positive probability, and the finite-set argument forces repetition.
E.3 Compactness: Proof: The relevant distribution set is compact in the 1-p-norm after proving completeness and total boundedness through finite-state truncation.A finite projection covers the bounded region, while a tail bound controls the remainder uniformly.

F AME: Proof

The AME proof shows that, under the paper’s continuity, tail, and bounded-increment conditions, finite-player population distributions converge to the stationary-equilibrium population state.

F AME: Proof: As the number of players grows, the finite-game empirical distribution approaches the limiting stationary-equilibrium population distribution.The key lemma establishes this convergence for the population excluding a focal player, with almost-sure convergence over the initial population sampling.
F AME: Proof: The proof handles coupled state transitions and unbounded state spaces by controlling population tails with a light-tail condition.These two features prevent a direct independent-particle argument and require an induction over time periods.
F AME: Proof: With independently sampled initial states, the strong law of large numbers gives convergence of empirical state frequencies at the initial period.Finite-state truncation and bounded convergence control the remaining tail contribution.
F AME: Proof: The induction step uses continuity of the transition kernel in population state and a refined Bernoulli law of large numbers to propagate convergence across periods.The proof applies the induction hypothesis to transition probabilities and then invokes Lemma 11 for state-frequency averages.
F AME: Proof: The coupled-player construction compares a focal player using a cognizant strategy with other players using the oblivious strategy µ.This setup defines the finite-player value comparison underlying the AME argument.