Source-linked AI summary
Dynamic control of agents playing aggregative games with coupling constraints
Sergio Grammatico
TL;DR
The paper addresses how to steer noncooperative agents with aggregative costs and shared convex constraints toward an aggregative equilibrium. It uses a semi-decentralized coordinator and an operator-theoretic dynamic control law, obtaining global convergence and demonstrations in congestion control and demand side management.
Problem
The problem is to coordinate noncooperative agents coupled through average population behavior and shared constraints toward an aggregative equilibrium.
Method
A central coordinator broadcasts incentive signals based on average decentralized responses, while a dynamic control law computes equilibrium incentives by finding the zero of a sum of monotone operators.
Results
The control law globally converges from any initial condition to the zero corresponding to an aggregative equilibrium, under the stated design choices.
Takeaways & Limitations
The approach provides a model-free semi-decentralized coordination mechanism applicable to network congestion control and demand side management.
Abstract
from arXiv · showhide
We address the problem to control a population of noncooperative heterogeneous agents, each with convex cost function depending on the average population state, and all sharing a convex constraint, towards an aggregative equilibrium. We assume an information structure through which a central coordinator has access to the average population state and can broadcast control signals for steering the decentralized optimal responses of the agents. We design a dynamic control law that, based on operator theoretic arguments, ensures global convergence to an equilibrium independently on the problem data, that are the cost functions and the constraints, local and global, of the agents. We illustrate the proposed method in two application domains: network congestion control and demand side management.
I. INTRODUCTION
The paper studies coordination of noncooperative agents with aggregative interactions and coupling constraints, using a semi-decentralized coordinator that broadcasts incentives based on average responses. It develops a dynamic, operator-theoretic control law with global convergence and applies it to congestion control and demand side management.
- Competitive agents are coupled through aggregate effects, creating coordination challenges in applications including smart-grid demand management and network congestion control.
- The coordinator broadcasts common incentive signals computed from the average of agents’ decentralized optimal responses, without requiring agents to exchange information.
- The target is an aggregative equilibrium in which agents’ strategies satisfy local and shared constraints while remaining individually optimal.
- A multivariable mapping is constructed whose unique zero produces the incentive signal generating the desired equilibrium, enabling semi-decentralized splitting methods.
- The proposed dynamic control law guarantees global convergence with minimal information and no problem-data assumptions beyond convexity, while appropriate parameters yield a global logarithmic convergence rate.
- The approach is illustrated in network congestion control and demand side management, and builds on variational, convex, and monotone operator analysis.
II. AGGREGATIVE GAMES WITH COUPLING CONSTRAINTS
The paper formulates generalized aggregative games with vector decisions, convex local and shared constraints, and strongly convex costs. It defines the equilibrium target, establishes existence, and notes that equilibria need not be unique.
- Each agent chooses a vector strategy from an individual feasible set, while all agents share a coupling constraint.
- Agents minimize costs depending on the population-average strategy and a coordinator-imposed control vector associated with the shared constraint.
- Compact, convex constraints satisfying Slater’s qualification and strongly convex cost functions ensure existence and single-valued, continuous optimal responses.
- An aggregative equilibrium requires shared-constraint feasibility and individual optimality given other agents’ strategies and the control vector.
- An aggregative equilibrium exists under the standing assumptions.
- Aggregative equilibria can be non-unique, and selecting the globally best equilibrium is outside the paper’s scope.
III. DYNAMIC CONTROL OF THE AGENTS’ DECENTRALIZED OPTIMAL RESPONSES
The coordinator steers agents’ decentralized optimal responses by seeking a fixed point of the aggregation mapping, reformulated as a zero-finding problem. A forward-backward dynamic control law computes this zero with suitable averaging steps.
- Fixed points of the aggregation mapping: Agents respond optimally to common incentive signals without exchanging information or knowing competitors’ strategies.The coordinator uses the resulting decentralized responses within the semi-decentralized architecture.
- Fixed points of the aggregation mapping: The target pair (σ̄, λ̄) makes the average optimal response a fixed point of the aggregation mapping within the coupling constraint set.Such a pair exists, while uniqueness depends on the choice of matrix gain K.
- From fixed points to zeros: The equilibrium-search problem is reformulated as finding a zero of an appropriate multivariable mapping using semi-decentralized iterations.The mapping is constructed from the same two arguments used by the aggregation mapping.
- Dynamic control as zero finding algorithm: The proposed dynamic control law computes a zero of Θ = M + Γ using a forward-backward splitting method for monotone mappings.The steps use a sufficiently small ϵ and averaging sequence α_t satisfying the stated design conditions.
- Dynamic control as zero finding algorithm: The control scheme iterates coordinator broadcasts and receives aggregate responses until convergence.Algorithm 1 summarizes this coordinator-agent exchange.
IV. GLOBAL CONVERGENCE
The proposed dynamic control law decomposes a mapping into monotone components and converges globally to the unique aggregative equilibrium under suitable gain and step-size choices.
- Equilibrium characterization: The mapping Θ is the sum of M and Γ, and its unique zero corresponds to the incentive signal generating the desired equilibrium.Strict monotonicity yields uniqueness under the stated design choice.
- Monotonicity: Choosing K ≻0 and C + K ≻0 makes the linear mapping M monotone and Γ β-cocoercive in a suitable Hilbert space.These properties allow the mapping Θ to be treated with monotone-operator splitting methods.
- Global convergence: Under design choices 1–3, the dynamic sequence converges from any initial condition to the zero of Θ.The convergence result applies globally and does not depend on the initial condition.
- Convergence rate: With constant αt = ᾱ ∈ (0, 1), the iteration has a global logarithmic convergence rate.The rate is established for the constant-step case.
- Equilibrium convergence: Under design choices 2–4, the sequence converges with the logarithmic rate to an aggregative equilibrium for the game with coupling constraints.The result combines global convergence with the equilibrium interpretation of the zero of Θ.
B. Proof of Theorem 2 (Monotonicity)
The proof constructs the operator decomposition underlying the control iteration, showing cocoercivity of the response mapping and averagedness of the resulting fixed-point operator.
- Optimal-response regularity: Strong convexity makes each inverse subdifferential single-valued, globally Lipschitz continuous, cocoercive, and strictly monotone.The optimal response can therefore be represented through an inverse subdifferential mapping.
- Cocoercivity: The mappings Γi are transformed into β-cocoercive operators in a weighted Hilbert space, and their aggregate Γ remains β-cocoercive and strictly monotone.The transformation uses invertible matrices and a positive-definite metric induced by the design choices.
- Fixed-point formulation: The fixed-point operator is T = (I + ϵM)^−1(Id − ϵΓ), and its fixed points are exactly the zeros of M + Γ.This identifies the dynamic iteration with a monotone-operator splitting scheme.
- Iteration schemes: The resulting iteration is nonexpansive and supports global convergence guarantees, including Krasnoselʹskii and Mann variants.The constant-step choice αt = ᾱ ∈ (0, 1) corresponds to Krasnoselʹskii iteration.
- Averaged operators: Because the resolvent and forward components are firmly nonexpansive, T is 2/3-averaged in the weighted Hilbert space.The proof uses composition and convex-combination properties of averaged operators.
A. Features of the dynamic control scheme
The semi-decentralized architecture lets a coordinator control incentives using aggregate information while agents independently solve parallel local optimization problems.
- Coordination: Each iteration requires one-to-all coordination between the central computer and the agents’ decentralized optimal responses.The local computations are parallelizable strongly convex optimization problems.
- Communication: Only one vector in R^n is broadcast per iteration, independently of the population size N.The population may be arbitrarily large, while the coordinator needs only aggregate information A.
- Coordinator control: The coordinator selects the step sizes, ε, gain K, and stopping criterion for the dynamic iteration.Agents therefore do not need to agree on control-signal step sizes or termination conditions.
- Agent autonomy: Agents remain fully noncooperative and need not exchange information with one another.The centralized choices avoid agreement points that could be exposed to malicious agent behavior.
- Privacy: The coordinator keeps the incentive mechanism and global coupling constraint private, while agents keep their costs and local constraints private.The architecture separates coordinator-held global information from agent-held local information.
B. Generalized Nash aggregative games
The paper studies generalized Nash aggregative games with convex local and shared constraints, relating their dynamics to equilibrium computation and projected-response systems.
- Game formulation: A generalized Nash aggregative game combines aggregative costs and a shared coupling constraint.Each agent’s optimal strategy depends on the population average and a common vector associated with the shared constraint.
- Convexity: The game is jointly convex because it has one unique shared convex constraint.Several decomposition methods are available for jointly convex generalized Nash equilibrium problems.
- Dual reformulation: Introducing a dual-variable agent removes the coupling constraint and yields an equivalent non-generalized Nash equilibrium formulation under regularity assumptions.The dual variable represents the shared-constraint multiplier and has no clear counterpart in the proposed dynamic iteration.
- Limits of prior methods: Existing distributed algorithms often require differentiable costs and coupling constraints, while monotonicity of the game mapping does not hold in general.Convex problem data alone do not guarantee monotonicity, including in aggregative setups.
- Response dynamics: For strongly convex quadratic costs, the decentralized best responses become projection dynamics onto the agents’ local constraint sets.For general strongly convex functions, the response is instead expressed through an inverse subdifferential mapping.
VI. APPLICATIONS
The paper illustrates its dynamic control law in network congestion control and plug-in electric-vehicle charging under shared constraints. Simulations report convergence to equilibrium across many experiments and population sizes.
- A. Network congestion control: Network users select flow profiles minimizing aggregative disutility under local routing and shared network-capacity constraints.The coordinator can impose congestion prices associated with violations of the shared capacity constraint.
- A. Network congestion control: Fixed routing policies use scalar flow demands and convex non-quadratic intrinsic disutility functions.Each routing vector is nonnegative and sums to one, while the intrinsic cost is f_i(ξ_i) := −20 ln(1+ξ_i).
- B. Charging coordination for plug-in electric vehicles with transmission line constraints: Plug-in electric vehicles minimize battery-degradation and electricity-pricing costs over 14 charging intervals with individual and shared transmission-line constraints.The charging costs and constraints are randomized to represent population variability, with tighter capacities during daytime intervals.
VII. CONCLUSION AND OUTLOOK
The paper concludes that its model-free dynamic control law converges globally to an aggregative equilibrium under strong convexity and compactness. Simulations indicate reasonable iteration counts independent of population size, while several extensions remain open.
- Conclusion: The method controls competitive agents with convex average-coupled costs and convex local and coupling constraints toward an aggregative equilibrium.The conclusion frames this as the paper’s central problem and result.
- Conclusion: The proposed model-free dynamic control law has a global convergence guarantee under strong convexity and compactness, without further assumptions on problem data.The guarantee concerns the stated cost functions and local and global constraints.
- Conclusion: Numerical simulations achieve an aggregative equilibrium within a reasonable number of iterations independently of population size.The simulations include convergence trajectories and iteration counts across experiments and population sizes.
- Outlook: The paper does not consider probabilistic constraints, leaving stochastic uncertainty as an extension direction.A possible future approach is to solve a deterministic approximation and interpret the result probabilistically.
- Outlook: The analysis assumes agents update from coordinator signals rather than decision histories, leaving memory and cumulative costs for future study.Asynchronous strategy updates are also identified as a practically relevant generalization.
- Outlook: The control parameters have feasible design choices, but maximizing convergence speed requires appropriate, potentially optimal, parameter selection.The connection with cooperative multi-agent dynamics is described as active research.
APPENDIX
The appendix proves equilibrium by combining a fixed-point argument with dual decomposition for a separable convex optimization problem. The resulting limit satisfies the shared constraint and equilibrium definition.
- Fixed-point construction: Compactness and continuity of the best-response mapping provide a fixed point for the aggregate state.The optimizer mapping takes values in the compact joint constraint set and is Lipschitz continuous.
- Dual decomposition: The auxiliary problem has separable convex cost and a linear coupling constraint, enabling solution through dual decomposition.Its Lagrangian is separable, so the component problems can be treated separately.
- Dual decomposition: Slater’s constraint qualification yields a unique optimal dual multiplier for the auxiliary problem.The proof uses this multiplier in establishing convergence of the coordinator signal.
- Equilibrium conclusion: At convergence, the aggregate strategy satisfies the shared constraint and the limiting pair meets the aggregative-equilibrium definition.The proof derives feasibility from the limiting relation and then invokes the equilibrium definition.
B. Proof of Theorem 1
The proof establishes equilibrium properties by comparing aggregate and individual best responses under strong convexity. It also derives a vanishing cost difference between aggregative and Nash equilibria as population size grows.
- Best-response comparison: The proof defines equilibrium responses as x_i⋆(Cσ̄ + Kλ̄), evaluated at the fixed aggregate state and multiplier.The aggregate state is σ̄ := (1/N)Σ_i x̄_i.
- Best-response comparison: Strong convexity makes the modified costs strongly convex for sufficiently large N, yielding single-valued best responses.The proof adds a quadratic term involving the symmetric part of C.
- Best-response comparison: The proof uses Lipschitz continuity of inverse subdifferentials and compactness of the joint constraint set to bound response differences.The shorthand variables v and v_i isolate the aggregate-versus-individual argument difference.
- Large-population consequence: Theorem 1 implies that the optimal-cost difference between aggregative and Nash equilibria vanishes as population size tends to infinity.This is stated as an immediate consequence in Remark 2.
- Regularity condition: When the functions f_i are also Lipschitz continuous, the theorem supplies a positive bound parameter used in the proof.The passage states existence of d ∈ R>0 under this additional regularity.