Distributed Algorithms for Searching Generalized Nash Equilibrium of Noncooperative Games

Resilient Distributed Nash Equilibrium Control for Nonlinear MASs Under DoS Attacks

This article investigates the resilient distributed Nash equilibrium (NE) control problem for nonlinear multiagent systems (MASs) that suffers from denial-of-service (DoS) attacks in the communication network. Different from the existing works on NE seeking in noncooperative games, it is the first trial to consider the resilient distributed NE control problem for nonlinear MASs under DoS attacks. To overcome the challenges caused by the considered problem, a new layered NE control method is developed, which consists of a resilient distributed NE seeking algorithm, two-stage cascade filters, and a resilient adaptive controller. Specifically, the resilient distributed NE seeking algorithm is proposed to ensure that the actions in this algorithm converge to the NE even under DoS attacks. Then, the improved actions with smooth characteristics are designed by introducing novel two-stage cascade filters. By using newly designed actions and their derivatives, a resilient adaptive controller is proposed to ensure that the output of MASs converges to the NE. Finally, simulation results are provided to verify the effectiveness of the proposed strategy.

Target-Attackers-Defenders Linear-Quadratic Exponential Stochastic Differential Games With Distributed Control

This article investigates stochastic differential games involving multiple attackers, defenders, and a single target, with their interactions defined by a distributed topology. By leveraging principles of topological graph theory, a distributed design strategy is developed that operates without requiring global information, thereby minimizing system coupling. Additionally, this study extends the analysis to incorporate stochastic elements into the target-attackers-defenders games, moving beyond the scope of deterministic differential games. Using the direct method of completing the square and the Radon-Nikodym derivative, we derive optimal distributed control strategies for two scenarios: one where the target follows a predefined trajectory and another where it has free maneuverability. In both scenarios, our research demonstrates the effectiveness of the designed control strategies in driving the system toward a Nash equilibrium. Notably, our algorithm eliminates the need to solve the coupled Hamilton-Jacobi equation, significantly reducing computational complexity. To validate the effectiveness of the proposed control strategies, numerical simulations are presented in this article.

Hierarchical Robust Generalized Nash Equilibrium Seeking of High-Order Uncertain Nonlinear Systems

This article investigates the distributed generalized Nash equilibrium (GNE) seeking problem of noncooperative games (NGs) for high-order strict-feedback nonlinear multiagent systems (MASs). In particular, the feasible action set of each agent is not only subject to local set and inequality constraints but also coupled through an equality constraint with other agents. This constraint structure is more general and covers most of the constraints in the GNE seeking literature. To accomplish the concerned GNE seeking objective, we propose a novel hierarchical GNE seeking approach in this article to decouple the distributed GNE seeking algorithm design into two layers. First, we construct a distributed primary-dual GNE estimator to generate virtual reference signals that converge to the GNE. Then, with the output of the estimator as the reference signal, we develop an adaptive tracking controller to solve the resultant tracking problems under output constraints. To overcome the negative effects of the disturbances, novel compensating terms associated with smooth functions and positive integrable time-varying functions are incorporated in the controller design, which thereby realizes the exact GNE seeking in the presence of nonvanishing mismatched disturbances. At last, an example is given to support the theoretical analysis of the proposed algorithms.

Distributed Nash equilibrium seeking in noncooperative game with partial decision information of neighbors

In the real world, individuals may conceal some of their real decision information to their neighbors due to competition. It is a challenge to explore the distributed Nash equilibrium when individuals play the noncooperative game with partial decision information in complex networks. In this paper, we investigate the distributed Nash equilibrium seeking problem with partial decision information of neighbors. Specifically, we construct a two-layer network model, where players in the first layer engage in game interactions and players in the second layer exchange estimations of real actions with each other. We also consider the case where the actions of some players remain unchanged due to the cost of updating or personal reluctance. By means of the Lyapunov function method and LaSalle's invariance principle, we obtain the sufficient conditions in which the consensus of individual actions and estimations can be achieved and the population actions can converge to the Nash equilibrium point. Furthermore, we investigate the case with switched topologies and derive the sufficient conditions for the convergence of individual actions to Nash equilibrium by the average dwell time method. Finally, we give numerical examples for cases of fixed and switched topologies to verify our theoretical results.

Attack-Resilient Distributed Nash Equilibrium Seeking of Uncertain Multiagent Systems Over Unreliable Communication Networks

This article investigates the distributed Nash equilibrium (NE) seeking problem of uncertain multiagent systems in unreliable communication networks. In this problem, the action of each agent is subject to a class of nonlinear systems with uncertain dynamics, and the communication network among agents will be affected by the nonperiodic denial of service (DoS) attacks. Note that, in this insecure network environment, the existence of DoS attacks will directly destroy the connectivity of the network, which leads to performance degradation or even failure of the most existing distributed NE seeking algorithms. To address this problem, we propose a two-stage distributed NE seeking strategy, including the attack-resilient distributed NE estimator and the neuroadaptive tracking controller. The estimator based on the projection subgradient method and the consensus protocol can converge exponentially to virtual NE against DoS attacks. Then, the neuroadaptive tracking controller is designed for uncertain multiagent systems with the output of the estimator as the reference signal such that the actual action of all agents can reach NE. Based on the Lyapunov stability theory and improved average dwell time automaton, the stability of the estimator and the controller is proven, and all signals in the closed-loop system are uniformly bounded. Numerical examples are presented to verify the effectiveness of the proposed strategy.

An Augmented Game Approach for Design and Analysis of Distributed Learning Dynamics in Multiagent Games

In this article, an augmented game approach is proposed for the formulation and analysis of distributed learning dynamics in multiagent games. Through the design of the augmented game, the coupling structure of utility functions among all the players can be reformulated into an arbitrary undirected connected network while the Nash equilibria are preserved. In this case, any full-information game learning dynamics can be recast into a distributed form, and its convergence can be determined from the structure of the augmented game. We apply the proposed approach to generate both deterministic and stochastic distributed gradient play and obtain several negative convergent results about the distributed gradient play: 1) a Nash equilibrium is convergent under the classic gradient play, yet its corresponding augmented Nash equilibrium may be not convergent under the distributed gradient play and, on the other side, 2) a Nash equilibrium is not convergent under the classic gradient play, yet its corresponding augmented Nash equilibrium may be convergent under the distributed gradient play. In particular, we show that the variational stability structure (including monotonicity as a special case) of a game is not guaranteed to be preserved in its augmented game. These results provide a systematic methodology about how to formulate and then analyze the feasibility of distributed game learning dynamics.

Bridging the Micro and Macro: Calibration of Agent-Based Model Using Mean-Field Dynamics

Calibration of agent-based models (ABM) is an essential stage when they are applied to reproduce the actual behaviors of distributed systems. Unlike traditional methods that suffer from the repeated trial and error and slow convergence of iteration, this article proposes a new ABM calibration approach by establishing a link between agent microbehavioral parameters and systemic macro-observations. With the assumption that the agent behavior can be formulated as a high-order Markovian process, the new approach starts with a search for an optimal transfer probability through a macrostate transfer equation. Then, each agent's microparameter values are computed using mean-field approximation, where his complex dependencies with others are approximated by an expected aggregate state. To compress the agent state space, principal component analysis is also introduced to avoid high dimensions of the macrostate transfer equation. The proposed method is validated in two scenarios: 1) population evolution and 2) urban travel demand analysis. Experimental results demonstrate that compared with the machine-learning surrogate and evolutionary optimization, our method can achieve higher accuracies with much lower computational complexities.

Nash Equilibrium Seeking for Graphic Games With Dynamic Event-Triggered Mechanism

In this article, a discrete-time Nash equilibrium (NE) seeking problem is studied for a class of graphic games. In order to reduce the signal transmission frequency between adjacent players, a dynamic event-triggered mechanism is designed. For the purpose of regulating the actions of players to the NE points, a discrete-time NE seeking strategy is designed by only using the local action information. Then, sufficient conditions are provided to ensure that the actions of all players converge to the NE point. Finally, a numerical example of a multisatellite communication coordination problem is given to verify the effectiveness of the proposed NE seeking method.

Differential Graphical Games for Constrained Autonomous Vehicles Based on Viability Theory

This article proposes an optimal-distributed control protocol for multivehicle systems with an unknown switching communication graph. The optimal-distributed control problem is formulated to differential graphical games, and the Pareto optimum to multiplayer games is sought based on the viability theory and reinforcement learning techniques. The viability theory characterizes the controllability of a wide range of constrained nonlinear systems; and the viability kernel and the capture basin are the pillars of the viability theory. The capture basin is the set of all initial states, in which there exist control strategies that enable the states to reach the target in finite time while remaining inside a set before reaching the target. In this regard, the feasible learning region is characterized by the reinforcement learner. In addition, the approximation of the capture basin provides the learner with prior knowledge. Unlike the existing works that employ the viability theory to solve control problems with only one agent and differential games with only two players, the viability theory, in this article, is utilized to solve multiagent control problems and multiplayer differential games. The distributed control law is composed of two parts: 1) the approximation of the capture basin and 2) reinforcement learning, which are computed offline and online, respectively. The convergence properties of the parameters' estimation errors in reinforcement learning are proved, and the convergence of the control policy to the Pareto optimum of the differential graphical game is discussed. The guaranteed approximation results of the capture basin are provided and the simulation results of the differential graphical game are provided for multivehicle systems with the proposed distributed control policy.

On Distributed Implementation of Switch-Based Adaptive Dynamic Programming

Switch-based adaptive dynamic programming (ADP) is an optimal control problem in which a cost must be minimized by switching among a family of dynamical modes. When the system dimension increases, the solution to switch-based ADP is made prohibitive by the exponentially increasing structure of the value function approximator and by the exponentially increasing modes. This technical correspondence proposes a distributed computational method for solving switch-based ADP. The method relies on partitioning the system into agents, each one dealing with a lower dimensional state and a few local modes. Each agent aims to minimize a local version of the global cost while avoiding that its local switching strategy has conflicts with the switching strategies of the neighboring agents. A heuristic algorithm based on the consensus dynamics and Nash equilibrium is proposed to avoid such conflicts. The effectiveness of the proposed method is verified via traffic and building test cases.

Nonsmooth Continuous-Time Distributed Algorithms for Seeking Generalized Nash Equilibria of Noncooperative Games via Digraphs

In this article, the problem of distributed generalized Nash equilibrium (GNE) seeking in noncooperative games is investigated via multiagent networks, where each player aims to minimize his or her own cost function with a nonsmooth term. Each player's cost function and feasible action set in the noncooperative game are both determined by actions of others who may not be neighbors, as well as his/her own action. Particularly, feasible action sets are constrained by private convex inequalities and shared linear equations. Each player can only have access to his or her own cost function, private constraint, and a local block of shared constraints, and can only communicate with his or her neighbours via a digraph. To address this problem, a novel continuous-time distributed primal-dual algorithm involving Clarke's generalized gradient is proposed based on consensus algorithms and the primal-dual algorithm. Under mild assumptions on cost functions and graph, we prove that players' actions asymptotically converge to a GNE. Finally, a simulation is presented to demonstrate the effectiveness of our theoretical results.

Distributed Generalized Nash Equilibrium Seeking and Its Application to Femtocell Networks

In this article, distributed algorithms are developed to search the generalized Nash equilibrium (NE) with global constraints. Relations between the variational inequality and the NE are investigated via the Karush-Kuhn-Tucker (KKT) optimal conditions, which provide the underlying principle for developing the distributed algorithms. Two time-varying consensus schemes are proposed for each agent to estimate the actions of others, by which a distributed framework is established. The algorithm with fixed-gains is designed with certain system knowledge, while the adaptive algorithm is proposed to address the problem when the system parameters are not available. The asymptotic convergence to the NE is established through the Lyapunov theory and the consensus theory. The power control problem in a femtocell network is formulated as a Nash game and is solved by the proposed algorithms. The simulation results are provided to verify the effectiveness of theoretical development.

On Iterative Proportional Updating: Limitations and Improvements for General Population Synthesis

Population synthesis is the foundation of the agent-based social simulation. Current approaches mostly consider basic population and households, rather than other social organizations. This article starts with a theoretical analysis of the iterative proportional updating (IPU) algorithm, a representative method in this field, and then gives an extension to consider more social organization types. The IPU method, for the first time, proves to be unable to converge to an optimal population distribution that simultaneously satisfies the constraints from individual and household levels. It is further improved to a bilevel optimization, which can solve such a problem and include more than one type of social organization. Numerical simulations, as well as population synthesis using actual Chinese nationwide census data, support our theoretical conclusions and indicate that our proposed bilevel optimization can both synthesize more social organization types and get more accurate results.

TiDEC: A Two-Layered Integrated Decision Cycle for Population Evolution

Agent-based simulation is a useful approach for the analysis of dynamic population evolution. In this field, the existing models mostly treat the migration behavior as a result of utility maximization, which partially ignores the endogenous mechanisms of human decision making. To simulate such a process, this article proposes a new cognitive architecture called the two-layered integrated decision cycle (TiDEC) which characterizes the individual's decision-making process. Different from the previous ones, the new hybrid architecture incorporates deep neural networks for its perception and implicit knowledge learning. The proposed model is applied in China and U.S. population evolution. To the best of our knowledge, this is the first time that the cognitive computation is used in such a field. Computational experiments using the actual census data indicate that the cognitive model, compared with the traditional utility maximization methods, cannot only reconstruct the historical demographic features but also achieve better prediction of future evolutionary dynamics.

Distributed Algorithms Involving Fixed Step Size for Mixed Equilibrium Problems With Multiple Set Constraints

In this brief, the problem of distributively solving a mixed equilibrium problem (EP) with multiple sets is investigated. A network of agents is employed to cooperatively find a point in the intersection of multiple convex sets ensuring that the sum of multiple bifunctions with a free variable is nonnegative. Each agent can only access information associated with its own bifunction and a local convex set. To solve this problem, a distributed algorithm involving a fixed step size is proposed by combining the mirror descent algorithm, the primal-dual algorithm, and the consensus algorithm. Under mild conditions on bifunctions and the graph, we prove that all agents' states asymptotically converge to a solution of the mixed EP. A numerical simulation example is provided for demonstrating the effectiveness of theoretical results.

Distributed Generalized Nash Equilibrium Seeking for Monotone Generalized Noncooperative Games by a Regularized Penalized Dynamical System

In this work, we study the generalized Nash equilibrium (GNE, see Definition 1) seeking problem for monotone generalized noncooperative games with set constraints and shared affine inequality constraints. A novel projected gradient-based regularized penalized dynamical system is proposed to solve this issue. The idea is to use a differentiable penalty function with a time-varying penalty parameter to deal with the inequality constraints. A time-varying regularization term is used to deal with the ill-poseness caused by the monotonicity assumption and the time-varying penalty term. The proposed dynamical system extends the regularized dynamical system in the literature to the projected gradient-based regularized penalized dynamical system, which can be used to solve generalized noncooperative games with set constraints and coupled constraints. Furthermore, we propose a distributed algorithm by using leader-following consensus, where the players have access to neighboring information only. For both cases, the asymptotic convergence to the least-norm variational equilibrium of the game is proven. Numerical examples show the effectiveness and efficiency of the proposed algorithms.

On Distributed Nash Equilibrium Computation: Hybrid Games and a Novel Consensus-Tracking Perspective

With the incentive to solve Nash equilibrium computation problems for networked games, this article tries to find answers for the following two problems: 1) how to accommodate hybrid games, which contain both continuous-time players and discrete-time players? and 2) are there any other potential perspectives for solving continuous-time networked games except for the consensus-based gradient-like algorithm established in our previous works? With these two problems in mind, the study of this article leads to the following results: 1) a hybrid gradient search algorithm and a consensus-based hybrid gradient-like algorithm are proposed for hybrid games with their convergence results analytically investigated. In the proposed hybrid strategies, continuous-time players adopt continuous-time algorithms for action updating, while discrete-time players update their actions at each sampling time instant and 2) based on the idea of consensus tracking, the Nash equilibrium learning problem for continuous-time games is reformulated and two new computation strategies are subsequently established. Finally, the proposed strategies are numerically validated.

Scaled Consensus of Second-Order Nonlinear Multiagent Systems With Time-Varying Delays via Aperiodically Intermittent Control

In this paper, the scaled consensus of multiagent systems (MASs) with second-order nonlinear dynamics and time-varying delays is investigated, where agents are supposed to aperiodically communicate with each other under a directed graph at some disconnected time intervals. Different from the existing works, we consider the case where time-varying delays exist in both nonlinear dynamics and communication networks. First, to address this problem, we propose a novel scaled consensus protocol. Second, using Lyapunov theory and graph theory, it is proved that under mild conditions, MASs with second-order nonlinear dynamics exponentially reach scaled consensus. Moreover, we extend our results to the case of leader-following scaled consensus. Finally, the simulation examples are included to verify the effectiveness of the theoretical results.

Asynchronous Distributed Algorithms for Seeking Generalized Nash Equilibria Under Full and Partial-Decision Information

This paper investigates asynchronous algorithms for distributedly seeking generalized Nash equilibria with delayed information in multiagent networks. In the game model, a shared affine constraint couples all players' local decisions. Each player is assumed to only access its private objective function, private feasible set, and a local block matrix of the affine constraint. We first give an algorithm for the case when each agent is able to fully access all other players' decisions. By using auxiliary variables related to communication links and the edge Laplacian matrix, each player can carry on its iteration asynchronously with only private data and possibly delayed information from its neighbors. Then, we consider the case when agents cannot know all other players' decisions, called a partial-decision information case. We introduce a local estimation of the overall agents' decisions and incorporate consensus dynamics on these local estimations. The two algorithms do not need any centralized clock coordination, fully exploit the local computation resource, and remove the idle time due to waiting for the "slowest" agent. Both algorithms are developed by preconditioned forward-backward operator splitting, and their convergence is shown by relating them to asynchronous fixed-point iterations, under proper assumptions and fixed and nondiminishing step-size choices. Numerical studies verify the algorithms' convergence and efficiency.