Source-linked AI summary
Decentralized Convergence to Nash Equilibria in Constrained Deterministic Mean Field Control
Sergio Grammatico, Francesca Parise, Marcello Colombino, John Lygeros
TL;DR
With constraints, agents’ optimal responses are generally unavailable in closed form. The paper proposes decentralized model-free feedback iterations with guaranteed global convergence to a mean field Nash equilibrium for large populations.
Problem
With constraints, the optimal response of each agent is generally not known in closed form.
Method
The paper proposes several model-free decentralized feedback iterations for constrained mean field control problems.
Results
The proposed iterations have guaranteed global convergence to a mean field Nash equilibrium for large populations under sufficient conditions on the problem data.
Takeaways & Limitations
The convergence result provides mild sufficient conditions and subsumes an earlier convergence result limited to quadratic cost functions.
Takeaways & Limitations
The discussion assumes the players’ best-response mappings are continuous and compact valued, with a non-increasing property.
Abstract
from arXiv · showhide
This paper considers decentralized control and optimization methodologies for large populations of systems, consisting of several agents with different individual behaviors, constraints and interests, and affected by the aggregate behavior of the overall population. For such large-scale systems, the theory of aggregative and mean field games has been established and successfully applied in various scientific disciplines. While the existing literature addresses the case of unconstrained agents, we formulate deterministic mean field control problems in the presence of heterogeneous convex constraints for the individual agents, for instance arising from agents with linear dynamics subject to convex state and control constraints. We propose several model-free feedback iterations to compute in a decentralized fashion a mean field Nash equilibrium in the limit of infinite population size. We apply our methods to the constrained linear quadratic deterministic mean field control problem and to the constrained mean field charging control problem for large populations of plug-in electric vehicles.
I. INTRODUCTION
The paper addresses decentralized deterministic mean field control when agents have heterogeneous convex constraints. It develops feedback-based methods that approach mean field Nash equilibria as populations grow and applies them to constrained control and PEV charging.
- Motivation: Mean field and aggregative games model large populations whose agents are influenced by aggregate population behavior.Mean field games emphasize infinite-population limits and statistical population properties.
- Problem: Classical mean field game computation requires agents to access statistical information about population behavior.The paper identifies this information structure as a challenge for decentralized solution methods.
- Approach: The paper instead assumes agents react optimally to a common external signal broadcast by a central population coordinator.The coordinator designs an incentive signal so decentralized responses satisfy desired properties of the deterministic mean field game.
- Contributions: The proposed mean field control approach computes almost Nash equilibria for deterministic mean field games with heterogeneous convex constraints.The constraints can arise from different linear dynamics and convex state and input constraints.
- Contributions: Several feedback iterations converge to an incentive signal generating a mean field equilibrium in a decentralized and scalable fashion.The paper establishes regularity properties of the relevant mappings and uses them to support the iterations.
- Applications: Applications cover constrained linear quadratic deterministic mean field control and constrained mean field charging for large populations of plug-in electric vehicles.The paper reports extensions to literature results in these applications.
Notation
The notation defines real-number sets, integer indexing, matrix operations, Hilbert-space norms, and basic mapping conventions used throughout the paper.
- Notation: R, R>0, and R≥0 denote the real, positive-real, and non-negative-real sets, respectively.
- Notation: N denotes natural numbers, Z denotes integer numbers, and Z[a,b] denotes the integers in [a,b].
- Notation: The transpose, block-diagonal, Kronecker-product, identity, zero, and all-ones matrix conventions are specified explicitly.
- Notation: For Q ≻ 0, H_Q is R^n equipped with inner product ⟨x,y⟩_Q := x^⊤Qy and its induced norm.
- Notation: A mapping is Lipschitz in H_Q when its Q-norm differences are bounded by a constant times input Q-norm differences.
II. CONSTRAINED LINEAR QUADRATIC DETERMINISTIC MEAN FIELD CONTROL AS MOTIVATING EXAMPLE
The motivating example formulates constrained linear-quadratic deterministic mean field control for heterogeneous linear agents. A coordinator broadcasts an incentive so constrained optimal responses approach a noncooperative equilibrium.
- Problem formulation: Each agent has discrete-time linear dynamics, time-varying state and input constraints, and a finite-horizon control problem.The constraints are represented using finite-dimensional convex quadratic programs.
- Problem formulation: An agent’s optimal feasible evolution depends on the decisions of all other agents through the average population state.This dependence yields an aggregative deterministic mean field game.
- Mean field control: The constrained LQ mean field control problem steers optimal responses toward a noncooperative equilibrium using an appropriate incentive signal.The coordinator broadcasts a macroscopic incentive related to aggregate behavior.
- Information structure: Agents lack detailed information about other agents and their distributions, reacting instead to coordinator-broadcast information related to aggregate behavior.
- Computational formulation: The finite-horizon formulation embeds state and input constraints in convex quadratic programs that are efficiently solvable numerically.Feasibility can be checked through convex feasibility problems, including parametrically in the initial state.
A. Constrained deterministic mean field game with quadratic cost function
The section formulates a deterministic mean field game with heterogeneous compact convex constraints and quadratic costs, then defines decentralized optimal-response and aggregation mappings. The mean field control objective is to find a broadcast signal whose induced strategies form an approximate mean field Nash equilibrium.
- The model considers N heterogeneous agents choosing strategies in individual compact convex constraint sets X_i.
- Each agent minimizes a deterministic quadratic cost depending on its strategy and the weighted aggregate of population strategies.
- A mean field Nash equilibrium requires that no agent can improve its cost by changing strategy against the population aggregation.
- The optimal-response mapping fixes a broadcast signal while each agent optimizes only its own strategy over X_i.
- The decentralized control problem iteratively broadcasts an aggregate computed from agents’ responses until the signal converges to one inducing an approximate equilibrium.
C. Mean field Nash equilibrium in the limit of infinite population size
The section connects fixed points of the aggregation mapping to mean field Nash equilibria for large populations. Under uniform compactness, a fixed point yields an approximation whose error scales as O(1/N).
- For large populations, an individual strategy contributes negligibly to the aggregate, so optimal response to a macroscopic signal approximates best response to the other agents.
- Under uniform compactness, any fixed point of the aggregation mapping generates a mean field Nash equilibrium in the infinite-population limit.
- For every ε > 0, there is a population threshold N̄_ε such that fixed-point-induced strategies form a mean field ε-Nash equilibrium for N ≥ N̄_ε.
- ε_N = O(1/N) for a fixed point at population size N.
- The approximation assumes uniformly bounded aggregation parameters, preventing any single agent from having disproportionate influence as population size grows.
A. Mathematical tools from fixed point operator theory
The section organizes fixed-point iterations by mapping regularity: stronger properties permit simpler iterations, while weaker properties require relaxation. The available convergence guarantees differ across contraction, firm nonexpansiveness, nonexpansiveness, and strict pseudocontractiveness.
- Picard–Banach iteration converges to a fixed point for contractive and firmly nonexpansive mappings.
- Krasnoselskij iteration converges for nonexpansive mappings on compact convex sets, whereas Picard–Banach need not converge for every nonexpansive mapping.
- Mann iteration converges to a fixed point for strictly pseudocontractive mappings under the stated diminishing-step conditions.
- The hierarchy yields Mann guarantees for CON, FNE, NE, and SPC mappings; Krasnoselskij guarantees for CON, FNE, and NE; and Picard–Banach guarantees for CON and FNE.
- Mappings weaker than contractions may have multiple fixed points, implying potentially multiple mean field Nash equilibria unless the aggregation mapping is contractive.
B. Main results: Regularity and decentralized convergence
The paper establishes regularity properties for individual optimizer mappings and their aggregation, then derives decentralized fixed-point iterations that converge to mean field equilibria under stated conditions.
- Regularity: The aggregation mapping A inherits the regularity properties of the individual optimizer mappings.Under Theorem 2’s conditions, A is Lipschitz continuous and has a fixed point.
- Regularity: The mapping A is Lipschitz continuous, has a fixed point, and is SPC in H_C−∆ when ∆≺C.
- Decentralized convergence: The resulting fixed-point iterations guarantee global convergence to a fixed point of A under their respective conditions.Different iterations apply in different norms and have problem-specific applicability ranges.
- Heterogeneous constraints: Decentralized convergence conditions are independent of the individual constraint sets and therefore apply naturally to heterogeneous populations.
- Decentralized convergence: Algorithm 1 implements the decentralized feedback iteration and converges to a fixed point of A under Corollary 1’s conditions.
- Equilibrium interpretation: Any fixed point of A generates a mean field ε_N-Nash equilibrium, but not an exact Nash equilibrium for finite N.The finite-population qualification follows because agents receive only aggregate information.
C. Discussion on decentralized convergence results in aggregative games
The discussion positions the proposed parallel fixed-point methods within aggregative-game convergence results and explains their applicability to constrained linear-quadratic mean field control.
- Parallel updates: Simultaneous or parallel responses are computationally more convenient than sequential updates in large-scale games.
- Existing convergence results: Prior aggregative-game results often assume one-dimensional compact strategy intervals and continuous, compact-valued, non-increasing best-response mappings.
- Generalization: When ∆≺C, −A is monotone, providing an n-dimensional generalization of the non-increasing property.
- Generalization: Theorem 3’s convergence result subsumes the earlier quadratic-cost result under mild conditions on the problem data.
- LQ mean field control: In constrained LQ mean field control, the average mapping A represents the population average of optimal tracking trajectories and the fixed point requires the trajectory to equal that average.
- LQ mean field control: For the LQ case, the mapping A is not necessarily contractive, so suitable fixed-point iterations are selected using the regularity results.
B. Production planning example
The production-planning example applies the framework to heterogeneous firms with constrained linear dynamics and evaluates the resulting fixed point through unilateral deviation benefits.
- Model: Each firm solves a finite-horizon optimal tracking problem in response to a production signal z.
- Model: The example models a heterogeneous population of firms whose production levels follow linear dynamics with heterogeneous state and input constraints.
- Iteration: For the chosen parameters, the aggregation mapping A is nonexpansive, so the Krasnosel'skii iteration guarantees convergence to a fixed point.The example uses p0 = 10, ρ = 1, T = 20, and γ = −1.
- Evaluation: The fixed point is evaluated as an ε_N-Nash equilibrium by comparing each firm’s fixed-point cost with its optimal cost under knowledge of the other firms’ production plan.
- Evaluation: ε_N decreases to zero as population size N increases, relative to the optimal cost in the homogeneous case with expected constraints.
C. Decentralized constrained charging control for large populations of plug-in electric vehicles
The paper applies decentralized feedback iterations to constrained mean field charging control for large populations of plug-in electric vehicles. The Mann iteration converges under positive quadratic regularization, while Picard–Banach can oscillate for small regularization.
- Charging-control model: Each PEV must obtain a target charge over a finite horizon while satisfying charging-input and state-related constraints.The setting uses discrete-time linear dynamics, charging controls, finite horizons, and convex constraints.
- Charging-control model: The electricity price depends affinely on inflexible demand and aggregate PEV demand, and each agent minimizes its own charging cost.The price is p(z) := 2(az + c), with a > 0 and c ≥ 0; a quadratic term regularizes the linear cost.
- Feedback iterations: The mean field charging problem is represented as a fixed point of the aggregation mapping formed from agents’ optimal charging controls.The fixed point corresponds to the average of the optimal controls under the price signal.
- Feedback iterations: The Mann iteration converges to a fixed point and therefore solves the constrained charging problem in the infinite-population limit.The convergence guarantee applies for δ > 0 and is stated as convergence to a mean field almost-Nash solution.
- Numerical illustration: For small δ, the Mann iteration recovers a desirable valley-filling solution, whereas Picard–Banach oscillates indefinitely.The figures use δ = 10^-4 and the setting without upper bounds; the paper reports a limit cycle for Picard–Banach and convergence for Mann.
- Scope and extensions: The study remains deterministic, and realistic PEV case studies and stochastic constrained extensions are identified as future work.The paper also notes that social global optimality and several heterogeneous-cost generalizations were not considered.
C. Main proofs
The proofs establish regularity of individual optimizer mappings and transfer those properties to the aggregate mapping. These properties then yield fixed-point existence, uniqueness or convergence guarantees for several iterations under corresponding matrix conditions.
- Mean field equilibrium: A fixed point of the aggregation mapping corresponds to a mean field Nash equilibrium, and the finite-population approximation error is O(1/N).At sufficiently large population sizes, an agent at the mean field fixed point is ε-close to its true optimal cost.
- Optimizer regularity: The constrained optimizer is obtained by projecting the unconstrained optimizer onto each compact convex feasible set.The optimizer mapping is analyzed through metric projection in the weighted Hilbert space induced by Q + Δ.
- Optimizer regularity: Under the stated assumptions, individual optimizer mappings share a common Lipschitz constant.The proof uses quadratic costs on compact domains and establishes a uniform bound across agents.
- Aggregate mapping: The aggregation mapping inherits the regularity properties of the individual optimizer mappings because it is their convex hull or weighted average.The aggregate mapping is shown to be Lipschitz and compact-valued, supporting fixed-point existence.
- Iteration guarantees: Picard–Banach converges when the aggregate mapping is contractive or firmly nonexpansive, with uniqueness when it is contractive.Krasnoselskij convergence follows under nonexpansiveness, while Mann convergence follows under strong pseudocontractivity.
- Charging specialization: In the charging case, δ > a/2 guarantees Picard–Banach convergence, while 0 < δ < a/2 guarantees Mann convergence through strong pseudocontractivity.The threshold follows from the matrix condition δ^2 − (δ − a)^2 > 0, equivalent to δ > a/2 for contractivity.