Connections between Mean-Field Game and Social Welfare Optimization

Sen Li; Wei Zhang; Lin Zhao

Source-linked AI summary

Connections between Mean-Field Game and Social Welfare Optimization

Sen Li, Wei Zhang, Lin Zhao

arXiv:1703.10211v8Mar 29, 2017math.OC

TL;DR

The paper asks how to assess the efficiency of non-cooperative mean-field equilibria, including when games lack a potential function. It connects equilibrium to a modified social welfare optimization problem and shows that, under mild conditions, the equilibrium is efficient for that problem, including with non-convex costs and action spaces.

Problem
How can the efficiency of non-cooperative mean-field equilibria be assessed when the game lacks a potential function and equilibria may be inefficient?
Source: §1 · p. 1
Method
The paper constructs a modified social welfare optimization problem and relates its solution to the mean-field equilibrium.
Source: §1 · p. 2
Results
Under mild conditions, the mean-field equilibrium is efficient for the modified social welfare problem, even with non-convex individual costs and action spaces.
Source: §1 · p. 2
Takeaways & Limitations
The connection provides a way to evaluate and promote equilibrium efficiency and yields implications for existence, uniqueness, and computation.
Source: §1 · p. 2
Applying the results may require checking strong duality, especially when the social welfare problem is non-convex and Assumption 5 does not hold.
Source: §4.2 · p. 10

Abstract

from arXiv · show

This paper studies the connection between a class of mean-field games and a social welfare optimization problem. We consider a mean-field game in function spaces with a large population of agents, and each agent seeks to minimize an individual cost function. The cost functions of different agents are coupled through a mean-field term that depends on the mean of the population states. We show that although the mean-field game is not a potential game, under some mild condition the $\epsilon$-Nash equilibrium of the mean-field game coincides with the optimal solution to a social welfare optimization problem, and this is true even when the individual cost functions are non-convex. The connection enables us to evaluate and promote the efficiency of the mean-field equilibrium. In addition, it also leads to several important implications on the existence, uniqueness, and computation of the mean-field equilibrium. Numerical results are presented to validate the solution, and examples are provided to show the applicability of the proposed approach.

1 Introduction

Mean-field games model large populations of strategic agents whose costs are coupled through population-level information. This paper connects such games to modified social welfare optimization, addressing how to assess equilibrium efficiency even when the game is not a potential game.

1 Introduction

Mean-field games characterize interactions in large populations through an agent’s interaction with a mean-field term rather than detailed pairwise interactions.The mean-field equilibrium has been studied in relation to existence, uniqueness, and computation.Source: §1 · p. 1
Efficiency analysis matters because non-cooperative mean-field equilibria can be inefficient, particularly when the game lacks a potential function.Prior work also studied efficiency loss or derived conditions for efficiency, but those conditions could be restrictive.Source: §1 · pp. 1–2
The paper links mean-field equilibrium to a modified social welfare optimization problem for vector-space games with non-cooperative agents and costs coupled through average population states.The framework allows potentially infinite-dimensional spaces.Source: §1 · p. 2
Under mild conditions, the equilibrium is efficient for the modified social welfare problem even with non-convex individual costs and action spaces.The connection can evaluate equilibrium efficiency or help design a game for a given social cost.Source: §1 · p. 2
The paper derives implications for equilibrium existence, uniqueness, and computation, and contrasts its social-welfare approach with potential-function methods.It also reports that its ADMM example converges faster than an operator-based method.Source: §1 · p. 2

2 Mean-Field Games in Function Spaces

The paper formulates mean-field games in vector spaces and illustrates how varied models fit the framework. It then asks whether equilibrium can be made optimal for a suitably modified social welfare problem.

2 Mean-Field Games in Function Spaces

The vector-space formulation covers potentially infinite-dimensional games and is intended to focus analysis on strategic interactions rather than system-specific dynamics.The paper states that it includes several important classes of mean-field games as special cases.Source: §2 · p. 2

2.1 The Mean-Field Game

Each agent’s state follows a control-and-noise mapping, and its cost couples to other agents through a term depending on the average population state.The cost structure includes an individual component and mean-field coupling terms.Source: §2.1 · pp. 2–3

2.2.1 Discrete-time deterministic game

The discrete-time deterministic linear-quadratic game is shown to be a special case of the proposed mean-field game.Its mean-field coupling and cost terms are expressed using the matrices in the example.Source: §2.2.1 · p. 3

2.2.2 Continuous-time stochastic game

The continuous-time stochastic LQG game is also a special case after its objective is transformed to the proposed cost form.The example verifies the required Lipschitz conditions for its mean-field terms.Source: §2.2.2 · p. 4

2.2.3 Network Routing Games

The network routing example models players allocating traffic across paths, with each edge’s congestion cost increasing with its flow.The routing game is reformulated as a special case of the proposed mean-field game.Source: §2.2.3 · p. 4

2.3 Objective of this Paper

The paper asks whether a modified social welfare objective can be constructed whose optimum coincides with the mean-field equilibrium.This differs from simply summing individual utilities, under which prior work found the equilibrium can be inefficient.Source: §2.3 · pp. 4–5
The proposed analysis proceeds by characterizing equilibrium through mean-field equations and then relating those equations to a social welfare optimization problem.Source: §2.3 · p. 5

3 Characterizing The Mean-Field Equilibrium

The section characterizes equilibrium through a self-consistent system of mean-field responses and shows that, under stated conditions, a solution is an ϵ-Nash equilibrium. Its deviation tolerance can become arbitrarily small as the population grows.

3 Characterizing The Mean-Field Equilibrium

The system uses a mean-field value y to induce agents’ optimal responses, which collectively generate a mean-field term close to y.The equilibrium equations impose consistency between the responses and the mean-field term they generate.Source: §3 · p. 5
The supporting lemma assumes bounded second moments of agent states and a globally Lipschitz mean-field map; each optimal-response problem must also admit a solution.The paper notes that continuity of the cost functional and compactness of the admissible control set are one sufficient condition for response-solution existence, while allowing multiple solutions.Source: §3 · p. 5
A solution to equations (16)–(18) is an ϵ-Nash equilibrium of the mean-field game.The result applies if the equation system has a solution.Source: §3 · p. 6
The deviation tolerance can be arbitrarily small for sufficiently large populations, but the specified equations do not characterize every possible ϵ-Nash equilibrium.The paper focuses on equilibria that solve equations (16)–(18), while other ϵ-Nash equilibria may exist with different tolerances.Source: §3 · p. 6
Unlike ’s continuum model, these equations are derived for a finite population; equivalence as N grows requires empirical means to converge.Without that convergence, the equations are not well-defined as N approaches infinity.Source: §3 · pp. 6–7

4 Connection to Social Welfare Optimization

The paper replaces the classical total-cost welfare objective, which need not align with a mean-field equilibrium, with a modified problem using a virtual agent. Under strong duality and further conditions on the mean-field coupling, it establishes when social optima and equilibria coincide, and contrasts this approach with potential-game methods.

4 Connection to Social Welfare Optimization

The classical total-cost objective need not have the mean-field equilibrium as its optimizer; a virtual agent and added balance constraint define a modified welfare problem.The virtual agent acts as a supplier, with the other agents as demands.Source: §4 · p. 7

4.1 Connections under Strong Duality

When φ is differentiable with ∇φ(z)=NF(z) and the modified problem has strong duality, every social optimum is a mean-field equilibrium; the converse follows if the equilibrium is unique.For integral-over-time models where F depends locally on the trajectory, φ can be derived using variational analysis; for arbitrary F, finding or constructing φ may be nontrivial.Source: §4.1 · pp. 8–9

4.2 Special Case with Monotone Mean-Field Coupling

With strong duality and monotone F, mean-field equilibria and global social optima coincide in both directions; Assumption 5 provides a convex special case.When Assumption 5 does not hold, the welfare problem may be non-convex, so strong duality must be checked to apply the results.Source: §4.2 · pp. 9–10

4.3 Relation to Potential Games

The game is generally not a potential game; where it reduces to one, welfare optimization yields an ϵ-Nash equilibrium and decentralized computation whose time is independent of agent count.Potential minimization instead yields a Nash equilibrium, and its computational complexity increases with the number of agents.Source: §4.3 · p. 10

5 Implication on Existence, Uniqueness and Computation

The paper uses the connection between mean-field equilibrium and social welfare optimization to derive conditions for equilibrium existence and uniqueness, and a primal-dual method for computing it.

5.1 Existence of the Mean-Field Equilibrium

Under monotone coupling, a mean-field equilibrium exists if and only if the social welfare problem has strong duality.Without the monotonicity assumption, strong duality is a sufficient existence condition.Source: §5.1 · pp. 10–11

5.2 Uniqueness of the Mean-Field Equilibrium

Strict convexity of the social welfare problem with respect to (u1, . . . , uN, z) is sufficient for a unique mean-field equilibrium.The paper relates earlier uniqueness conditions—convex costs and monotone or strictly increasing coupling—to strict convexity of this optimization problem.Source: §5.2 · p. 11

5.3 Computation of the Mean-Field Equilibrium

A primal-dual algorithm computes the mean-field equilibrium by iteratively updating agent decisions and the dual variable for the corresponding social welfare problem.The procedure constructs the optimization problem using φ, has agents solve their individual problems, then updates and broadcasts the dual variable.Source: §5.3 · p. 11
Proposition 4 states that Algorithm 1 converges to the mean-field equilibrium of (3) when Assumption 5 holds and the step size ι_k tends to zero.Source: §5.3 · p. 11
The paper identifies existing mean-field equilibrium algorithms as special cases of its primal-dual method, including the algorithms in [9] and.For the linear-quadratic game in, the method corresponds to a scaled-step-size version of the primal-dual algorithm.Source: §5.3 · p. 12

6 Case Studies

The case studies apply the social-welfare connection to EV charging with monotone coupling and to a separate non-monotone game. They illustrate equilibrium computation and show how the direction of the equilibrium–optimum relation depends on the conditions.

6.1 Example: Special Case with Monotone Mean-Field Coupling

The EV charging game's equilibrium is exactly the optimizer of its strictly convex social welfare problem, so it exists and is unique.The example models EV batteries as linear systems with finite-horizon charging costs coupled through an electricity price based on average charging energy.Source: §6.1 · pp. 12–13
ADMM reaches the EV charging optimum after about 50 iterations, versus 100 for Mann iteration.The comparison uses 100 sets of EV parameters over 36 five-minute control periods, with both algorithms run for 200 iterations.Source: §6.1 · p. 13
The apparent faster convergence of Mann iteration in the average-control norm does not mean its mean-field variable converges sooner; that variable converges only after 100 iterations.The authors emphasize that convergence requires both z and ui to converge.Source: §6.1 · p. 13

6.2 Example: Non-Monotone Mean-Field Coupling

The non-monotone example's equilibrium need not be socially optimal in general, although uniqueness makes the relation two-way under the stated conditions.The example establishes uniqueness, and hence social optimality, when 0 < κ < 2.Source: §6.2 · p. 14
For the non-monotone example, if 0 < κ < 2, the mean-field equilibrium is the globally optimal solution of the social welfare problem.For κ > 0, every socially optimal solution is a mean-field equilibrium; the social welfare problem has strong duality despite being non-convex.Source: §6.2 · pp. 13–14

7 conclusion

The paper connects mean-field equilibrium with social welfare optimization, including for non-convex individual costs and action spaces. It also reports implications for equilibrium efficiency, existence, uniqueness, and computation.

7 conclusion

The mean-field equilibrium is an optimal solution to a social welfare optimization problem for convex and non-convex individual costs and action spaces.Source: §7 · p. 14
This connection supports evaluating and promoting equilibrium efficiency and has implications for equilibrium existence, uniqueness, and computation.Source: §7 · p. 14
Numerical simulations validate the approach; future work would extend it to infinitely many agents and distribution-dependent mean-field terms.Source: §7 · p. 14

A: Proof of Lemma 1

The proof establishes that the function space X is isomorphic to L2 by constructing a linear, surjective inner-product-preserving mapping. Since L2 is complete, this establishes completeness of X.

A: Proof of Lemma 1

The proof uses the completeness of L2 to establish completeness of X through their isomorphism.Source: A: Proof of Lemma 1 · p. 14
A mapping g from L2 to X is defined by gt(l(t)) = e^(ρt/2)l(t).Source: A: Proof of Lemma 1 · p. 14
The mapping is linear, surjective, and preserves inner products, establishing the isomorphism between L2 and X.Source: A: Proof of Lemma 1 · p. 14

B: Proof of Lemma 2

The proof bounds terms using Lipschitz continuity and a bounded second moment, with an uncorrelatedness condition, to obtain convergence at rate 1/N.

B: Proof of Lemma 2

The estimates use Lipschitz continuity of F and bounded second moment of xi.Source: B: Proof of Lemma 2 · p. 15
The quantity under analysis converges to 0; the cited passage does not specify a numerical rate, so no particular convergence rate is asserted.Source: B: Proof of Lemma 2 · p. 15
The proof also invokes that xi and xj are uncorrelated.Source: B: Proof of Lemma 2 · p. 15

C: Proof of Lemma 3

The proof decomposes an inequality into three terms and shows that they converge to zero at rate 1/N, using Lipschitz bounds on the gradient of G.

C: Proof of Lemma 3

The proof uses that the derivative of G is Lipschitz continuous and bounds its gradient using ∇G(0) and β.Source: C: Proof of Lemma 3 · p. 15
All three terms on the right-hand side of the inequality are shown to converge to 0 at rate 1/N.Source: C: Proof of Lemma 3 · p. 15
One displayed bound uses β and the second moment of xi, with the latter bounded by C.Source: C: Proof of Lemma 3 · p. 16