Source-linked AI summary
Distributed Nash equilibrium seeking for aggregative games with coupled constraints
Shu Liang, Peng Yi, Yiguang Hong
TL;DR
The paper addresses distributed generalized Nash equilibrium seeking for nonlinear aggregative games with linear coupled constraints. It proposes a projected, non-smooth continuous-time tracking algorithm and proves convergence under stated game and graph assumptions, with numerical illustration.
Problem
Existing distributed aggregative-game algorithms do not handle the combination of nonlinear aggregation, non-quadratic costs, and coupled constraints targeted here.
Method
The paper uses projected equilibrium-seeking dynamics interconnected with non-smooth consensus tracking for aggregation and dual variables.
Results
The proposed system is stable and converges to the set of equilibrium and dual-variable solutions under Assumptions 1 and 2.
Takeaways & Limitations
The design provides a distributed continuous-time procedure for seeking variational GNEs while requiring only local information exchange and preserving some private information.
Takeaways & Limitations
The convergence result relies on smoothness, strict monotonicity, compact convex feasibility, a constraint qualification, and Filippov well-posedness for the discontinuous dynamics.
Abstract
from arXiv · showhide
In this paper, we study a distributed continuous-time design for aggregative games with coupled constraints in order to seek the generalized Nash equilibrium by a group of agents via simple local information exchange. To solve the problem, we propose a distributed algorithm based on projected dynamics and non-smooth tracking dynamics, even for the case when the interaction topology of the multi-agent network is time-varying. Moreover, we prove the convergence of the non-smooth algorithm for the distributed game by taking advantage of its special structure and also combining the techniques of the variational inequality and Lyapunov function.
1 Introduction
The paper targets distributed generalized Nash equilibrium seeking for nonlinear aggregative games with linear coupled constraints, using continuous-time methods under time-varying network topologies. Its algorithm combines projected equilibrium-seeking dynamics with non-smooth tracking and provides convergence analysis.
- The paper develops a distributed continuous-time algorithm for nonlinear aggregative games with linear coupled constraints and time-varying topologies.
- The problem involves aggregative games where local costs depend on nonlinear aggregation and players’ feasible decisions are coupled by linear constraints.
- The model generalizes earlier aggregative games through nonlinear aggregation, non-quadratic costs, coupled constraints, and possible non-potential structure.
- The proposed system has interconnected projected-gradient and consensus dynamics for equilibrium seeking and synchronization of aggregation and dual variables.
- The algorithm avoids best-response subproblems and preserves privacy because local costs, decisions, and constraint coefficients need not be shared.
- The convergence proof combines variational inequality techniques with Lyapunov stability theory.
2 Preliminaries
The preliminaries introduce convex analysis, projection properties, variational inequalities, monotonicity, regularized gap functions, and graph-theoretic concepts used in the analysis.
- The section defines convex sets and the projection map onto a closed convex set.
- Projection satisfies a variational inequality property and is nonexpansive under the Euclidean norm.
- A variational inequality seeks x in a set Ω satisfying the associated inequality, with solutions denoted SOL(Ω,F).
- For continuous F on compact Ω, VI solutions exist; strict monotonicity on a closed set gives at most one solution.
- The regularized gap function is constructed from a projection, and its gradient is expressed using F, the Jacobian J_F, and the identity matrix.
- The communication network is represented by a graph whose edges encode information reception, with connectedness defined through paths between nodes.
3 Problem Formulation
The paper formulates an N-player aggregative game with local strategy sets, nonlinear aggregation, and linear coupled constraints, then characterizes variational GNEs through a variational inequality. Under smoothness, strict monotonicity, feasibility, and constraint qualification, the variational GNE is unique, and the distributed design assumes an undirected connected time-varying graph.
- 3 Problem Formulation: Each player minimizes a local cost over a local strategy set, and the joint strategy profile stacks all players’ decision variables.
- 3 Problem Formulation: Each cost depends on the player’s decision and an aggregation map whose local contributions may be nonlinear.
- 3 Problem Formulation: The feasible strategy set intersects individual strategy constraints with a set imposing linear coupled constraints defined through matrices A_i and vector b.
- 3 Problem Formulation: A generalized Nash equilibrium requires every player to choose a best feasible response, so no unilateral feasible change decreases its cost.
- 3 Problem Formulation: A variational GNE is defined as a solution of VI(K,F), and every solution of this VI is a GNE when K is convex.
- Assumption 1: The analysis assumes twice-continuously differentiable costs, strictly monotone F, compact convex Ω, and the constraint qualification 0 ∈ rint(Ω−X).
- Assumption 1: Under these assumptions, the game admits a unique variational GNE, with existence supplied by smoothness and feasibility and uniqueness by monotonicity.
- Assumption 1: The distributed problem assumes an undirected connected time-varying graph and seeks the variational GNE.
4 Main Results
The paper develops a distributed continuous-time algorithm for aggregative games with coupled constraints and analyzes its stability and convergence under stated assumptions. The analysis combines tracking, projected dynamics, variational-equilibrium characterization, and Lyapunov arguments.
- Distributed Algorithm: Additional distributed max-consensus calculations obtain the parameter bounds needed to set α, β, and γ within N − 1 steps.The calculation propagates local values zi using neighbor exchanges and updates based on the supremum.
- Distributed Algorithm: The algorithm uses projected dynamics with non-smooth tracking variables for aggregation and dual estimates, while allowing time-varying interaction topologies.The design is fully distributed and can preserve privacy because local costs, decisions, and constraint coefficients need not be shared.
- Correctness and Convergence Analysis: The aggregation estimates ηi(t) and dual estimates λi(t) converge exponentially to σ(x(t)) and the network-wide dual estimate ¯λ(t), respectively.These tracking properties supply the vanishing error terms used in the convergence analysis.
- Correctness and Convergence Analysis: Under Assumption 1, the variational GNE is unique, and it is characterized by membership of (x*, ¯λ*) in the solution set X* × Λ*.Theorem 2 establishes the equivalence between the variational GNE and the projected primal-dual solution characterization.
5 Numerical Examples
Two numerical examples illustrate the proposed algorithm in aggregative games with linear coupled constraints, including a Nash–Cournot game with time-varying communication topology and a demand response management game.
- 5.1 Nash-Cournot Game: The Nash–Cournot firms’ costs depend on production quantity and an aggregate-dependent market price, with p = d − Nσ(x).The aggregation function is σ(x) = 1/N summed over firms’ quantities.
- 5.1 Nash-Cournot Game: Figure 1 compares strategy-profile trajectories without and with the linear coupled constraint, showing convergence to the NE and GNE, respectively.The upper trajectory corresponds to the unconstrained case and the lower trajectory to the coupled-constraint case.
- 5.1 Nash-Cournot Game: The Nash–Cournot example uses 20 firms, with firms 1–10 sharing a resource constraint, a time-varying randomly generated communication graph, and algorithm parameters α = 20, β = 400, γ = 20.Each firm selects production quantity xi ∈ [0, 20].
- 5.2 Demand Response Management: The demand response example considers N = 5 electricity users whose energy consumptions lie in individual intervals and whose costs depend on nonlinear aggregation.The numerical setting uses the same parameters as Ye and Hu (2017), including N = 5, ki = 1, a = 0.04, and p0 = 5.
- 5.2 Demand Response Management: The unconstrained game has NE x∗ = [45, 46.4, 51.3, 56.2, 61.1]T, while imposing the additional linear constraint yields GNE x∗ = [45.2, 50.1, 55, 59.9, 64.8]T.Figure 2 displays convergence to the NE without the constraint and the GNE with the constraint.
6 Conclusions
The paper studies aggregative games with linear coupled constraints and proposes a distributed continuous-time projection-based algorithm for GNE seeking, with convergence established analytically and illustrated numerically.
- 6 Conclusions: The paper considers aggregative games with linear coupled constraints and proposes a distributed continuous-time projection-based algorithm for seeking generalized Nash equilibria.The conclusions identify variational inequalities and Lyapunov functions as the bases for proving correctness and convergence.
- 6 Conclusions: The correctness and convergence of the proposed non-smooth algorithm are proved using variational inequalities and Lyapunov functions.Two numerical examples are provided to illustrate the result.
- 6 Conclusions: Two numerical examples illustrate the proposed distributed algorithm for the considered game class.