PaperlayerView exact revision on arXiv

Source-linked AI summary

Markov-Nash Equilibria in Mean-Field Games with Discounted Cost

Naci Saldi, Tamer Başar, Maxim Raginsky

arXiv:1612.07878v2eess.SYcs.SYmath.OC

TL;DR

Discrete-time mean-field game research has mostly focused on discrete or countable state spaces and cost-only coupling. This paper formulates discounted-cost games with Polish state spaces and proves that a mean-field equilibrium exists and yields approximate Markov-Nash policies for sufficiently large finite populations.

  • Problem

    Prior discrete-time mean-field game work has mostly considered discrete or countable state spaces with agents coupled through costs alone.

    Source: §1 · p. 1

  • Method

    The paper defines Markov-Nash optimality among Markov policies and uses a limiting mean-field game to construct a policy for finite-agent games.

    Source: §1 · p. 2

  • Results

    Under the stated assumptions, a mean-field equilibrium exists, and its policy is an ε-Markov-Nash equilibrium for every sufficiently large N.

    Source: §3 · p. 9, §4 · p. 15

  • Takeaways & Limitations

    The mean-field approach supplies nearly Markov-Nash equilibria for finite-population discounted-cost games when the population is sufficiently large.

    Source: §6 · p. 32

    Verification of condition (j) depends strongly on system components, making a global assumption to ensure it difficult to find.

    Source: §5 · p. 31

Abstract

from arXiv · show

In this paper, we consider discrete-time dynamic games of the mean-field type with a finite number $N$ of agents subject to an infinite-horizon discounted-cost optimality criterion. The state space of each agent is a locally compact Polish space. At each time, the agents are coupled through the empirical distribution of their states, which affects both the agents' individual costs and their state transition probabilities. We introduce a new solution concept of the Markov-Nash equilibrium, under which a policy is player-by-player optimal in the class of all Markov policies. Under mild assumptions, we demonstrate the existence of a mean-field equilibrium in the infinite-population limit $N \to \infty$, and then show that the policy obtained from the mean-field equilibrium is approximately Markov-Nash when the number of agents $N$ is sufficiently large.

1. Introduction.

Discrete-time mean-field game results are comparatively few, and existing work has mostly used discrete or countable state spaces with coupling through costs alone. This paper studies discounted-cost games with Polish state spaces, where the empirical state distribution affects both costs and transitions, and establishes mean-field and approximate finite-population equilibria.

1. Introduction.

  • Continuous-time mean-field games use the Nash certainty equivalence principle to reduce a decentralized game to a single-agent decision problem consistent with population behavior.The continuous-time characterization involves forward Fokker-Planck and backward Hamilton-Jacobi-Bellman equations.Source: §1 · p. 1
  • Prior discrete-time mean-field games mostly use finite or countable state spaces and couple agents through costs alone; Adlakha et al. is closest but assumes invariant distributions under stationary policies.The paper contrasts its setting with that prior work, which has at most countable state spaces.Source: §1 · p. 1
  • The paper studies infinite-horizon discounted games with Polish state spaces and distribution-dependent costs and transitions, proving mean-field equilibrium existence and approximate Markov-Nash equilibrium for sufficiently large populations.The authors describe this as the first result demonstrating an exact or approximate equilibrium policy for a general discrete-time mean-field game with finitely many agents.Source: §1 · p. 2

2. Finite Player Game with Discounted Cost.

The section formulates the finite-agent discounted-cost game, explains the challenges of decentralized information and scale, and introduces the Markov-Nash equilibrium approach. It also states regularity assumptions and a result allowing optimality infima to be restricted to weakly continuous Markov policies.

2. Finite Player Game with Discounted Cost.

  • Policies may depend on an agent’s full history, while Markov policies select actions using only the current state.The paper also defines weakly continuous Markov policies as those whose action kernels vary continuously with state.Source: §2 · p. 3
  • Agents face discounted costs based on c(x,a,µ), and their transition kernel also depends on the empirical state distribution.The discount factor satisfies β∈(0,1).Source: §2 · pp. 2–3
  • Decentralized local information and the curse of dimensionality make Nash equilibrium existence and characterization challenging, motivating approximate decentralized equilibria.The stated difficulty remains even when agents have full state information.Source: §2 · p. 4
  • The mean-field equilibrium policy is an ε-Markov-Nash equilibrium in finite games for sufficiently large N, while being a true Nash equilibrium in the infinite-population regime.The authors first establish an equilibrium in the limiting game and then apply its policy to the finite-agent game.Source: §2 · p. 4

2.1. Assumptions.

  • Assumption 1 requires continuous costs, compact actions, locally compact states, and weakly continuous transition probabilities.The assumptions also include continuity of the transition kernel’s w-moment.Source: §2.1 · p. 6
  • Under Assumption 1, Theorem 2.3 allows optimality infima to be restricted to weakly continuous Markov policies.The paper notes that bounded-cost cases can be covered by slight modifications of the unbounded-cost proofs.Source: §2.1 · p. 8

3. Mean-field games and mean-field equilibria.

The paper treats the infinite-population mean-field game as a single-agent control problem against a state-measure flow, and defines equilibrium by matching an optimal policy to the flow it generates. Under Assumption 1, a mean-field equilibrium exists.

3. Mean-field games and mean-field equilibria.

  • A mean-field game models collective behavior as an exogenous state-measure flow with fixed initial condition, while a single agent minimizes discounted cost against that flow.The paper characterizes mean-field games as single-agent stochastic control problems constrained by the state distribution at each time step.Source: §3 · pp. 8–9
  • A mean-field equilibrium pairs a policy optimal for a flow with the flow induced by that policy.The paper defines maps for policy optimality and flow generation, then requires both conditions to hold together.Source: §3 · p. 9
  • Restricting the mean-field equilibrium construction to Markov policies entails no loss of optimality.The paper concludes that the resulting policy is player-by-player optimal among all admissible policies in the infinite-population game.Source: §3 · p. 9
  • Under Assumption 1, the mean-field game admits a mean-field equilibrium.The proof establishes a fixed point of Γ and constructs the equilibrium from it.Source: §3 · pp. 9, 15
  • The proof reduces equilibrium existence to finding a fixed point of Γ, then disintegrates that fixed point into a Markov policy and its state marginal.The fixed point theorem is applied after establishing Γ’s properties.Source: §3 · pp. 12, 15

4. Existence of Approximate Markov-Nash Equilibria.

This section establishes that assigning the mean-field equilibrium policy to every agent yields an ε-Markov-Nash equilibrium for sufficiently large populations, under Assumptions 1 and 2 and weak continuity of the mean-field policy. It does so by deriving finite-horizon convergence of empirical distributions and applying that result in the main theorem’s proof.

4. Existence of Approximate Markov-Nash Equilibria.

  • For every ε > 0, a sufficiently large N makes the profile assigning each agent policy π an ε-Markov-Nash equilibrium, assuming Assumptions 1 and 2 and weak continuity of π.The theorem states that there is a positive integer N(ε) such that the result holds for each N ≥ N(ε).Source: §4 · p. 15
  • As N grows, empirical state distributions converge at each time to μ_t, so a generic agent's state evolution closely tracks the mean-field equilibrium flow.The proof uses this convergence to relate finite-population dynamics to the infinite-population equilibrium.Source: §4 · pp. 15, 18, 19, 20
  • In the infinite-population limit, the law of the empirical state distribution is insensitive to one agent deviating while all other agents follow π.The deviation considered is a weakly continuous Markov policy for Agent 1; Agents 2 through N retain the mean-field equilibrium policy.Source: §4 · p. 21
  • For every t ≥ 0 and every sequence g_N ∈ C_v(X) with sup_N ||g_N||_v < ∞, Proposition 4.9 establishes that the stated empirical-distribution expression equals 0.The proof uses Lemma 4.8 to show that the last term converges to zero as N → ∞.Source: §4 · p. 26
  • Corollary 4.11 is introduced as a consequence of Proposition 4.5 and Theorem 4.10, while the text separately says the paper’s main result is ready to be proved.Source: §4 · p. 27
  • For all N ≥ N(ε), the proof establishes the required inequality for each agent, reducing the argument to Agent 1 by symmetry and invoking Corollary 4.11.The transition probabilities and one-stage costs are the same for all agents.Source: §4 · p. 27

5. Example.

The example uses an additive-noise model and verifies conditions under which the mean-field equilibrium and the large-population approximate Markov-Nash result apply. It also discusses a sufficient condition for the required policy continuity and extends the results to finite horizons.

Additive noise model

  • Under conditions (i)–(vii), the additive-noise model satisfies Assumption 1 and admits a mean-field equilibrium.The conditions include compact actions, continuity and growth bounds, and α^2β < 1.Source: §5 · pp. 28–29
  • Conditions (viii)–(x) ensure Assumption 2, including Hölder continuity in y for d and f and a positive lower bound on |g|.The noise is standard normal.Source: §5 · pp. 29, 31

Condition (j)

  • Verifying condition (j) is systems-dependent, and a unique minimizer of Rν,h(x, ·) provides a sufficient route to the required weak continuity.Under (j’), the mean-field policy is continuous when the minimizing function is continuous; the passage establishes continuity using uniqueness and compactness of A.Source: §5 · p. 31

Finite-horizon extension

  • The paper states that the same quantitative results extend to finite-horizon costs, with Proposition 3.10 requiring a different proof.The finite-horizon case cannot use the fixed-point argument used for the infinite-horizon case.Source: §5 · pp. 31–32
  • The finite-horizon conclusions also apply to subgames starting at time τ with initial measure μτ and to finite-agent games with i.i.d. initial measures drawn from μτ.The policy from time τ through T is an ε-Markov-Nash equilibrium in the finite-agent subgame.Source: §5 · p. 32

6. Conclusion.

The paper establishes nearly Markov-Nash equilibria for sufficiently large finite populations under infinite-horizon discounted costs. It identifies imperfect information, average-cost, and risk-sensitive criteria as directions for future study.

Conclusion

  • Under mild technical conditions, a mean-field equilibrium policy yields an ε-Markov-Nash equilibrium for sufficiently large finite populations with infinite-horizon discounted costs.The paper first establishes equilibrium existence in the limiting mean-field game, then applies its policy to the finite-population game.Source: §6 · p. 32

Future directions

  • Imperfect-information mean-field games and average-cost and risk-sensitive criteria remain future research directions.The paper suggests a vanishing-discount approach as a possible route to average-cost results.Source: §6 · p. 32

Appendix.

The appendix supports the main results with proofs that recast the finite-agent game as an MDP and establish approximation and convergence steps. It also uses successive approximations for Proposition 3.10.

Proofs

  • The proof of Theorem 2.3 approximates an arbitrary Markov policy with a continuous one while controlling the change in cost.Lusin’s theorem and a continuous extension are used to construct the approximation.Source: A. Proof of Theorem 2.3 · pp. 32–33
  • The finite-agent game is represented as an MDP with state space X^N × P(X), action space A^N, and a transition probability.The cost for this MDP is the β-discounted cost of the N-agent policy profile.Source: A. Proof of Theorem 2.3 · p. 33
  • For Proposition 3.2, the initial distribution, policy, and state-measure flow define a unique probability measure, and the proof uses induction over time.The appendix also invokes Tonelli’s theorem to establish equality of the discounted costs for the compared policies.Source: B. Proof of Proposition 3.2 · p. 34
  • Proposition 3.10 is proved using successive approximations, with the operators T^(n) and T contractive with modulus σβα.The proof compares iterates and uses compact-set convergence to complete the argument.Source: C. Proof of Proposition 3.10 · pp. 34–35

D. Auxiliary Lemma.

The section states an auxiliary lemma generalizing [11, Lemma A.2] to unbounded real-valued functions and sketches a proof using Jensen’s inequality.

D. Auxiliary Lemma.

Loading 1612.07878v2…