Multi-Timescale Distributed Approach to Generalized-Nash-Equilibrium Seeking in Noncooperative Nonconvex Games

Banghua Huang , Yang Liu ,,,Kit Ian Kou , and Weihua Gui

Dear Editor,

The distributed generalized-Nash-equilibrium (GNE) seeking in noncooperative games with nonconvexity is the topic of this letter.Inspired by the sequential quadratic programming (SQP) method, a multi-timescale multi-agent system (MAS) is developed, and its convergence to a critical point of the game is proven.To illustrate the qualities and efficacy of the theoretical findings, a numerical example is elaborated.

With the rapid development of MAS theories and distributed optimization, distributed Nash-equilibrium (NE) seeking has become a meaningful research topic [1]-[7].In a paradigm of noncooperative games, cost function and action set of an individual player depend on its own action, and together with the other player’s actions.Besides,NEs are important solutions among the strategies of a noncooperative game.At an NE, if other players keep their current strategies,then no player can improve its benefits by changing its strategies.In the game modeled in the practical networks (e.g., [8]), each player is capable to receive partial decision information (the player’s own information and its neighbors’ information) only.Hence, it is essential for each player to estimate the strategies, in a distributed manner,adopted by all the other players.To this end, many distributed NE seeking methods have been proposed and captured attention from many areas [1], [9]-[15].Specifically, the landmark leader-following consensus-based distributed NE seeking strategy was first proposed in [1].Then, numerous effective methods for seeking NEs have emerged in the past few years.For example, a distributed method for seeking generalized NE based on gradient projection is proposed in [9], a distributed continuous-time penalty method is proposed for seeking GNE in [10], a distributed method is proposed for seeking NEs with Markovian switching topologies [11], a distributed method is proposed for seeking GNE with nonsmooth cost functions in [12], a distributed NE seeking method with actuator constraints is proposed in [13], a distributed NE seeking method subject to quantitative communications is proposed in [14], a distributed NE seeking method with bounded disturbances is proposed in [15].In the studies aforementioned, the cost function and action sets in the games are assumed to be convex.However, the distributed NE seeking meth-

Corresponding author: Yang Liu.

Citation: B.Huang, Y.Liu, K.Kou, and W.Gui, “Multi-timescale distributed approach to generalized-Nash-equilibrium seeking in noncooperative nonconvex games,”IEEE/CAA J.Autom.Sinica, vol.11, no.3, pp.791-793, Mar.2024.

B.Huang is with the School of Mathematical Sciences, Zhejiang Normal University, Jinhua 321004, China (e-mail: huangbanghua@zjnu.edu.cn).

Y.Liu is with the Key Laboratory of Intelligent Education Technology and Application of Zhejiang Province, Jinhua 321004, and also with the School of Mathematical Sciences, Zhejiang Normal University, Jinhua 321004, China(e-mail: liuyang@zjnu.edu.cn).

K.Kou is with the Faculty of Science and Technology, University of Macau, Macau, China (e-mail: kikou@umac.mo).

W.Gui is with the School of Automation, Central South University,Changsha 410083, China (e-mail: gwh@csu.edu.cn).

Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org.

Digital Object Identifier 10.1109/JAS.2023.123909 ods for the games with nonconvex cost functions and constraints are not studied.

The SQP method is one of the effective approaches for constrained nonlinear or nonconvex optimization [16].Driven by the idea of SQP, a two-timescale neural network is developed for nonconvex optimization [17].To echo the nonconvex optimization solver based on multi-timescale neural networks, we develop a multitimescale MAS for seeking the critical point of the nonconvex game.The main contributions are summarized as follows: 1) Based on the idea of SQP, we develop a multi-timescale MAS for GNE-seeking of nonconvex games.2) Compared with the existing distributed NE seeking approach for the convex games in [1], [9]-[15], the proposed MAS with proper timescales is proven to be convergent to a critical point of a nonconvex game.

whereλandμare Lagrange multipliers.

Equations (2) is said be a Karush-Kuhn-Tucker (KKT) conditions in optimization theory.Under several assumptions, e.g., second-order sufficiency conditions [18], a point satisfying KKT conditions (2) is a local solution.Therefore, the seeking of critical points contributes to the seeking of local GNEs.

The SQP method is an effective method for constrained nonconvex optimization, and it has two stages [16]: At the first stage, a quadratic programming subproblem of game (1) is formulated as follows:

where xkand zkis the decision vector and the directional vector at thek-th iteration, andMis a given positive definite matrix.At the second stage, xkis updated by the following iteration rule:

whereαis the step size andz*kis the optimal solution of subproblem(3).

Remark 1: In the idea of SQP, we do not need to solve nonconvex constrained game (1) directly, instead, we use rule (4) to update the decision variable and we solve optimization subproblem (3) at each iteration of (4).Note that subproblem (3) at each iteration is a convex optimization problem with respect to z, which avoids using the nonconvexity of cost functions.

Main results: Inspired by [1] and [17], a continuous-time generalization of a SQP approach in the form of multi-timescale MAS-based distributed op[timization] i s proposed.Letyijbe playeri’s estimate onxj, yi=colyi1,...,yiNand y=col[y1,...,yN].Then, a multitimescale MAS for seeking the NE of the game (1) is described

Fig.1.The communication network topology among players.

Fig.2(a) implies that MAS (5) is convergent to x*, which illustrates the validity of Theorems 1 and 2.In contrast, Fig.2(b) shows that the MAS in [9] is not convergent to NE x*.

Fig.2.The transient states of MAS (5) and MAS (6) in [9].

Conclusion: In this letter, we suggest a distributed GNE-seeking strategy for nonconvex games.To echo the SQP optimization method, we develop a multi-timescale MAS for constrained games in the presence of nonconvexity.With a proper timescale setting, we prove the convergence of the MAS to one of the game’s critical points.To demonstrate the viability of the suggested multi-timescale MAS, we also offer an example.

Acknowledgments: This work was partially supported by the National Natural Science Foundation of China (62173308), the Natural Science Foundation of Zhejiang Province of China (LR20F0 30001), the Jinhua Science and Technology Project (2022-1-042),University of Macau (MYRG2022-00108-FST, MYRG-CRG2022-00010-ICMS), the Science and Technology Development Fund,Macau S.A.R (0036/2021/AGJ), and Chinese Guangdong’s S&T project (2022A0505020028).