Search

The purpose of this paper is to show how insight obtained from a mean-field model can be used to create an architecture for approximate dynamic programming (ADP) for a certain class of games comprising of a large number of agents. The general technique is illustrated with the aid of a mean-field oscillator game model introduced in our prior work. The states of the model are interpreted as the phase angles for a collection of nonhomogeneous oscillators, and in this way the model may be regarded as an extension of the classical coupled oscillator model of Kuramoto. The paper introduces ADP techniques for design and adaptation (learning) of approximately optimal control laws for this model. For this purpose, a parameterization is proposed, based on an analysis of the mean-field PDE model for the game. In an offline setting, a Galerkin procedure is introduced to choose the optimal parameters while in an online setting, a steepest descent algorithm is proposed. The paper provides a detailed analysis of the optimal parameter values as well as the Bellman error with both the Galerkin approximation and the online algorithm. Finally, a phase transition result is described for the large population limit when each oscillator uses the approximately optimal control law. A critical value of the control penalty parameter is identified: above this value, the oscillators are incoherent; and below this value (when control is sufficiently cheap) the oscillators synchronize. These conclusions are illustrated with results from numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of risk-sensitive mean-field stochastic differential games. We show that under appropriate regularity conditions, the mean-field value of the stochastic differential game with exponentiated integral cost functional coincides with the value function satisfying a Hamilton –Jacobi– Bellman (HJB) equation with an additional quadratic term. We provide an explicit solution of the mean-field best response when the instantaneous cost functions are log-quadratic and the state dynamics are affine in the control. An equivalent mean-field risk-neutral problem is formulated and the corresponding mean-field equilibria are characterized in terms of backward-forward macroscopic McKean–Vlasov equations, Fokker–Planck–Kolmogorov equations, and HJB equations. We provide numerical examples on the mean field behavior to illustrate both linear and McKean–Vlasov dynamics. [ABSTRACT FROM PUBLISHER]

This paper concerns state estimation problems in a mean field control setting. In a finite population model, the goal is to estimate the joint distribution of the population state and the state of a typical individual. The observation equations are a noisy measurement of the population. The general results are applied to demand dispatch for regulation of the power grid, based on randomized local control algorithms. In prior work by the authors it is shown that local control can be designed so that the aggregate of loads behaves as a controllable resource, with accuracy matching or exceeding traditional sources of frequency regulation. The operational cost is nearly zero in many cases. The information exchange between grid and load is minimal, but it is assumed in the overall control architecture that the aggregate power consumption of loads is available to the grid operator. It is shown that the Kalman filter can be constructed to reduce these communication requirements, and to provide the grid operator with accurate estimates of the mean and variance of quality of service (QoS) for an individual load. [ABSTRACT FROM AUTHOR]

This paper presents a systematic method to analyze the stability of systems with single delay in which the coefficient polynomials of the characteristic equation depend on the delay. Such systems often arise in, for example, life science and engineering systems. A method to analyze such systems was presented by Beretta and Kuang in a 2002 paper, but with some very restrictive assumptions. This paper extends their results to the general case with the exception of some degenerate cases. It is found that a much richer behavior is possible when the restrictive assumptions are removed. The interval of interest for the delay is partitioned into subintervals so that the magnitude condition generates a fixed number of frequencies as functions of the delay within each subinterval. The crossing conditions are expressed in a general form, and a simplified derivation for the first-order derivative criterion is obtained. Illustrative examples are also presented in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we present necessary and sufficient conditions for two given functions to be the Lyapunov and the upper Bohl exponent of a certain discrete linear system with diagonal coefficients. The obtained conditions have a form of easily verifiable algebraic conditions. [ABSTRACT FROM AUTHOR]

This paper presents a discrete-time distributed and noncooperative routing algorithm, which is proved, via Lyapunov arguments, to asymptotically converge to a specific equilibrium condition among the traffic flows over the network paths, known as Wardrop equilibrium. This convergence result improves the discrete-time algorithms in the literature, which achieve approximate convergence to the Wardrop equilibrium. Numerical simulations show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

Within the realm of smart buildings and smart cities, dynamic response management is playing an ever-increasing role, thus attracting the attention of scientists from different disciplines. Dynamic demand response management involves a set of operations aiming at decentralizing the control of loads in large and complex power networks. Each single appliance is fully responsive and readjusts its energy demand to the overall network load. A main issue is related to mains frequency oscillations resulting from an unbalance between supply and demand. In a nutshell, this paper contributes to the topic by equipping each consumer with strategic insight. In particular, we highlight three main contributions and a few other minor contributions. First, we design a mean-field game for a population of thermostatically controlled loads, study the mean-field equilibrium for the deterministic mean-field game, and investigate on asymptotic stability for the microscopic dynamics. Second, we extend the analysis and design to uncertain models, which involve both stochastic or deterministic disturbances. This leads to robust mean-field equilibrium strategies guaranteeing stochastic and worst-case stability, respectively. Minor contributions involve the use of stochastic control strategies rather than deterministic and some numerical studies illustrating the efficacy of the proposed strategies. [ABSTRACT FROM PUBLISHER]

This paper considers two classes of large population stochastic differential games connected to optimal and robust decentralized control of large-scale multiagent systems. The first problem (P1) is one where each agent minimizes an exponentiated cost function, capturing risk-sensitive behavior, whereas in the second problem (P2 ) each agent minimizes a worst-case risk-neutral cost function, where the “worst case” stems from the presence of an adversary entering each agent’s dynamics characterized by a stochastic differential equation. In both problems, the individual agents are coupled through the mean field term included in each agent’s cost function, which captures the average or mass behavior of the agents. We solve both P1 and P2 via mean field game theory. Specifically, we first solve a generic risk-sensitive optimal control problem and a generic stochastic zero-sum differential game, where the corresponding optimal controllers are applied by each agent to construct the mean field systems of P1 and P2. We then characterize an approximated mass behavior effect on an individual agent via a fixed-point analysis of the mean field system. For each problem, P1 and P2, we show that the approximated mass behavior is in fact the best estimate of the actual mass behavior in various senses as the population size, $N$, goes to infinity. Moreover, we show that for finite $N$, there exist $\epsilon$- Nash equilibria for both P1 and P2, where the corresponding individual Nash strategies are decentralized in terms of local state information and the approximated mass behavior. We also show that $\epsilon$ can be taken to be arbitrarily small when $N$ is sufficiently large. We show that the $\epsilon$- Nash equilibria of P1 and P2 are partially equivalent in the sense that the individual Nash strategies share identical control laws, but the approximated mass behaviors for P1 and P2 are different, since in P2, the mass behavior is also affected by the associated worst-case disturbance. Finally, we prove that the Nash equilibria for P1 and P2 both feature robustness, and as the parameter characterizing this robustness becomes infinite, the two Nash equilibria become identical and equivalent to that of the risk-neutral case, as in the one-agent risk-sensitive and robust control theory. [ABSTRACT FROM AUTHOR]

Natural systems are inextricably affected by noise. Within recent decades, the manner in which noise affects the collective behavior of self-organized systems, specifically, has garnered considerable interest from researchers and developers in various fields. To describe the collective motion of multiple interacting particles, Vicsek et al. proposed a well-known self-propelled particle (SPP) system, which exhibits a second-order phase transition from disordered to ordered motion in simulation; due to its non-equilibrium, randomness, and strong coupling nonlinear dynamics, however, there has been no rigorous analysis of such a system to date. To decouple systems consisting of deterministic laws and randomness, we propose a general method which transfers the analysis of these systems to the design of cooperative control algorithms. In this study, we rigorously analyzed the original Vicsek model under both open and periodic boundary conditions for the first time, and developed extensions to heterogeneous SPP systems (including leader-follower models) using the proposed method. Theoretical results show that SPP systems switch an infinite number of times between ordered and disordered states for any noise intensity and population density, which implies that the phase transition indeed takes a nontraditional form. We also investigated the robust consensus and connectivity of these systems. Moreover, the findings presented in this paper suggest that our method can be used to predict possible configurations during the evolution of complex systems, including turn, vortex, bifurcation, and flock merger phenomena as they appear in SPP systems. [ABSTRACT FROM PUBLISHER]

This paper introduces the backward mean-field (MF) linear-quadratic-Gaussian (LQG) games (for short, BMFLQG) of weakly coupled stochastic large-population system. In contrast to the well-studied forward mean-field LQG games, the individual state in our large-population system follows the backward stochastic differential equation (BSDE) whose terminal instead initial condition should be prescribed. Two classes of BMFLQG games are discussed here and their decentralized strategies are derived through the consistency condition. In the first class, the individual agents of large-population system are weakly coupled in their state dynamics and the full information can be accessible to all agents. In the second class, the coupling structure lies in the cost functional with only partial information structure. In both classes, the asymptotic near-optimality property (namely, $\epsilon$- Nash equilibrium) of decentralized strategies are verified. To this end, some estimates to BSDE, are presented in the large-population setting. [ABSTRACT FROM AUTHOR]

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 influenced 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. [ABSTRACT FROM PUBLISHER]

Mean field game theory has been developed largely following two routes. One of them, called the direct approach, starts by solving a large-scale game and next derives a set of limiting equations as the population size tends to infinity. The second route is to apply mean field approximations and formalize a fixed point problem by analyzing the best response of a representative player. This paper addresses the connection and difference of the two approaches in a linear quadratic (LQ) setting. We first introduce an asymptotic solvability notion for the direct approach, which means for all sufficiently large population sizes, the corresponding game has a set of feedback Nash strategies in addition to a mild regularity requirement. We provide a necessary and sufficient condition for asymptotic solvability and show that in this case the solution converges to a mean field limit. This is accomplished by developing a re-scaling method to derive a low-dimensional ordinary differential equation (ODE) system, where a non-symmetric Riccati ODE has a central role. We next compare with the fixed point approach which determines a two-point boundary value (TPBV) problem, and show that asymptotic solvability implies feasibility of the fixed point approach, but the converse is not true. We further address non-uniqueness in the fixed point approach and examine the long time behavior of the non-symmetric Riccati ODE in the asymptotic solvability problem. [ABSTRACT FROM AUTHOR]

Aggregate load modeling is of fundamental importance for systematic analysis and design of various demand response strategies. Instead of keeping track of the trajectories of individual loads, the aggregate modeling problem focuses on characterizing the density evolution of the load population. Most existing models are only applicable to thermostatically controlled loads (TCLs) with first-order linear dynamics. This paper develops a unified aggregate modeling approach that can be used for general TCLs as well as deferrable loads. We propose a deterministic hybrid system model to describe individual load dynamics under demand response rules, and develop a general stochastic hybrid system (SHS) model to capture the population dynamics. We also derive a set of partial differential equations (PDEs) that govern the probability density evolution of the SHS. Our results cannot be obtained using the existing SHS tools in the literature as the proposed SHS model involves both random and deterministic switchings with general switching surfaces in multidimensional domains. The derived PDE model includes many existing aggregate load modeling results as special cases and can be used in many other realistic modeling scenarios that have not been studied in the literature. [ABSTRACT FROM AUTHOR]

This paper studies the linear–quadratic mean-field game (MFG) for a class of stochastic delayed systems. We consider a large-population system, where the dynamics of each agent is modeled by a stochastic differential delayed equation. The consistency condition is derived through an auxiliary system, which is an anticipated forward–backward stochastic differential equation with delay (AFBSDDE). The wellposedness of such an AFBSDDE system can be obtained using a continuation method. Thus, the MFG strategies can be defined on an arbitrary time horizon, not necessary on a small time horizon by a commonly used contraction mapping method. Moreover, the decentralized strategies are verified to satisfy the $\epsilon$ -Nash equilibrium property. For illustration, three special cases of delayed systems are further explored, for which the closed-loop and open-loop MFG strategies are derived, respectively. [ABSTRACT FROM AUTHOR]

We consider a continuum of phase oscillators on the circle interacting through an impulsive instantaneous coupling. In contrast with previous studies on related pulse-coupled models, the stability results obtained in the continuum limit are global. For the nonlinear transport equation governing the evolution of the oscillators, we propose (under technical assumptions) a global Lyapunov function which is induced by a total variation distance between quantile densities. The monotone time evolution of the Lyapunov function completely characterizes the dichotomic behavior of the oscillators: either the oscillators converge in finite time to a synchronous state or they asymptotically converge to an asynchronous state uniformly spread on the circle. The results of the present paper apply to popular phase oscillators models (e.g., the well-known leaky integrate-and-fire model) and show a strong parallel between the analysis of finite and infinite populations. In addition, they provide a novel approach for the (global) analysis of pulse-coupled oscillators. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to synthesize initial mean consensus behavior of a set of agents from the fundamental optimization principles of i) stochastic dynamic games, and ii) optimal control. In the stochastic dynamic game model each agent seeks to minimize its individual quadratic discounted cost function involving the mean of the states of all other agents. In this formulation we derive the limiting infinite population mean field equation system and explicitly compute its unique solution. The resulting mean field (MF) control strategies drive each agent to track the overall population's initial state distribution mean, and by applying these decentralized strategies, any finite population system reaches mean consensus asymptotically as time goes to infinity. Furthermore, these control laws possess an \varepsilonN-Nash equilibrium property where \varepsilonN goes to zero as the population size N goes to infinity. Finally, the analysis is extended to the case of random mean field couplings. In the social cooperative formulation the basic objective is to minimize a social cost as the sum of the individual cost functions containing mean field coupling. In this formulation we show that for any individual agent the decentralized mean field social (MF Social) control strategy is the same as the mean field Nash (MF Nash) equilibrium strategy. Hence $MF-Nash\ Controls\ UNash^N=\rm MF-Social\ Controls\ USoc^N.$On the other hand, the solution to the centralized LQR optimal control formulation yields the Standard Consensus (SC) algorithm whenever the graph representing the corresponding topology of the network is Completely Connected (CC). Hence $Cent.\ LQR\ Controls\ UCent^N=\rm SC-CC\ Controls\ USC^N.$Moreover, a system with centralized control laws reaches consensus on the initial state distribution mean as time and population size N go to infinity. Hence, asymptotically in time $\eqalignno&MF-Nash\ Controls\ UNash^N\!=\!\,\rm MF-Social\ Controls\ USoc^N\cr&\!=\!\,\rm Cent.\ \rm LQR\ Controls\ UCent^\infty \!=\! \,\rm SC-CC\ Controls\ USC^\infty.$Finally, the analysis is extended to the long time average (LTA) cost functions case. [ABSTRACT FROM AUTHOR]

Huang (2010) and Nguyen and Huang (2012) solved the linear quadratic mean field systems and control problem in the case where there is a major agent (i.e. non-asymptotically vanishing as the population size goes to infinity) together with a population of minor agents (i.e. individually asymptotically negligible). The new feature in this case is that the mean field becomes stochastic and then, by minor agent state extension, the existence of $\epsilon$-Nash equilibria together with the individual agents' control laws that yield the equilibria may be established. This paper presents results initially announced by Caines and Kizilkale (2013, 2014) where it is shown that if the major agent's state is partially observed by the minor agents, and if the major agent completely observes its own state, all agents can recursively generate estimates (in general individually distinct) of the major agent's state and the mean field, and thence generate feedback controls yielding $\epsilon$ -Nash equilibria. [ABSTRACT FROM PUBLISHER]

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, toward 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. [ABSTRACT FROM AUTHOR]

We consider the problem of reconstructing the initial states of a finite group of structurally identical linear systems in the situation that output measurements of the individual systems are received at discrete time steps and in an anonymized manner: While we do know all output measurements of the individual systems in the group, we do not know which output measurement corresponds to which system. This state estimation problem addresses the essence of state estimation problems for populations, in which the output measurements of the individual systems are given only as statistics. We adopt a measure theoretical approach in which the group is modelled by an LTI system describing the structure of the individual systems and an initial state which is expressed by a discrete measure. In this framework we derive a geometric characterization for the state estimation to admit a unique solution, which combined with a result on the observability of linear systems under irregular sampling, yields a sufficient condition for the sampled observability of discrete ensembles. As a supplement to our theoretical findings, we provide illustrations by means of simulation examples. Furthermore we consider the practical state estimation problem under noisy output measurements. [ABSTRACT FROM PUBLISHER]

This article addresses analysis and control of the SIR model of infectious diseases in the framework of input-to-state stability (ISS) with respect to the net flow of susceptible individuals into a region in both disease-free and epidemic situations. The key development is the construction of a continuously differentiable strict Lyapunov function. First, this article clarifies that a continuously differentiable Lyapunov function whose derivative is nonpositive can deduce asymptotic stability on the whole state space. Second, it is demonstrated that a new idea of rendering the derivative strictly negative allows one to detect a margin proving ISS of the SIR model. The accomplishment is based on the pursuit of a Lyapunov function that is not entirely separable into components. It contrasts with previously studied and popular Lyapunov functions that are proven to be incapable of assessing robustness properties such as ISS. Third, two types of feedback control laws are proposed for mass vaccination of immigrants and inhabitants by making use of the strict Lyapunov functions. One type modifies the other type by focusing on the reduction of peaks of the infected population within the ISS guarantees. [ABSTRACT FROM AUTHOR]

We address the observability problem for ensembles that are described by probability distributions. The problem is to reconstruct a probability distribution of the initial state from the time-evolution of the probability distribution of the output under a classical finite-dimensional linear system. We present two solutions to this problem, one based on formulating the problem as an inverse problem and the other one based on reconstructing all the moments of the distribution. The first approach leads us to a connection between the reconstruction problem and mathematical tomography problems. In the second approach we use the framework of tensor systems to describe the dynamics of the moments, which leads to a more systems theoretic treatment of the reconstruction problem. Furthermore we show that both frameworks are inherently related. The appeal of having two dual viewpoints, the first being more geometric and the second one being more systems theoretic, is illuminated in several examples of theoretical or practical importance. [ABSTRACT FROM PUBLISHER]

The article introduces and solves a structural controllability problem for continuum ensembles of linear time-invariant systems. All the individual linear systems of an ensemble are sparse, governed by the same sparsity pattern. Controllability of an ensemble system is, by convention, the capability of using a common control input to simultaneously steer every individual systems in it. A sparsity pattern is structurally controllable if it admits a controllable linear ensemble system. A main contribution of the article is to provide a graphical condition that is necessary and sufficient for a sparsity pattern to be structurally controllable. Like other structural problems, the property of being structural controllable is monotone. We provide a complete characterization of minimal sparsity patterns as well. [ABSTRACT FROM AUTHOR]

A new mathematical formulation of evolutionary game dynamics on networked populations is proposed. The model extends the standard replicator equation to a finite set of players organized on an arbitrary network of connections (graph). Classical results of multipopulation evolutionary game theory are used in combination with graph theory to obtain the mathematical model. Specifically, the players, located at the vertices of the graph, are interpreted as subpopulations of a multipopulation dynamical game. The members of each subpopulation are replicators, engaged at each time instant into 2-player games with the members of other connected subpopulations. This idea allows us to write an extended equation describing the game dynamics of a finite set of players connected by a graph. The obtained equation does not require any assumption on the game payoff matrices nor graph topology. Stability of steady states, Nash equilibria and the relationship of the proposed model to the standard replicator equation are discussed. The dynamical behavior of the model over different graphs is also investigated by means of extended simulations. [ABSTRACT FROM AUTHOR]

It is well known that evolution is a fundamental phenomenon driving nature. And random drift is a basic force for population evolution. This technical note aims at constructing a unified theoretical framework for analyzing and intervening in random drift of binary states on general networks. In detail, a general methodology is developed for calculating the fixation probability with different dynamics, including the Wright-Fisher (WF), birth-death (BD), and death-birth (DB) processes. In particular, we prove that the fixation probability of a mutant at node $k$ corresponds to the $k$-th element of stationary distribution of a stochastic matrix deduced from the weight matrix of the networks. Intuitively, it provides an effective way to discover the invasion hubs of structured population and further to intervene in random drift on networks. Finally, a typical example is then given to validate the above theoretical results. [ABSTRACT FROM AUTHOR]

For noncooperative games the mean field (MF) methodology provides decentralized strategies which yield Nash equilibria for large population systems in the asymptotic limit of an infinite (mass) population. The MF control laws use only the local information of each agent on its own state and own dynamical parameters, while the mass effect is calculated offline using the distribution function of i) the population's dynamical parameters, and ii) the population's cost function parameters, for the infinite population case. These laws yield approximate equilibria when applied in the finite population. [ABSTRACT FROM AUTHOR]

This articleproposes an extension to a family of evolutionary game dynamics called escort replicator dynamics (ERD), defined by (Harper, 2011) based on information-geometric concepts. Specifically, the objective of this article is to propose three types of convenient so-called escort functionsand evaluate the stability of ERD under the use of these functions. Since it is proven that ERD is stable using the proposed definitions, ERD is able to confine trajectories of the state vector in regions defined by upper and lower boundaries which can be, but are not required to be, nonnegative. From an engineering application perspective, these proposed escort functions are convenient since they allow to extend replicatorlike dynamics applications to engineering problems with feasible regions more general than the standard simplex or the nonnegative orthant. From a population dynamics perspective the proposed escort functions are useful to represent upper and lower limits on the share of a population that is allowed to play a given pure strategy of the underlying symmetric game. [ABSTRACT FROM AUTHOR]

Competitive noncooperative online decision-making agents whose actions increase congestion of scarce resources constitute a model for widespread modern large-scale applications. To ensure sustainable resource behavior, we introduce a novel method to steer the agents toward a stable population state, fulfilling the given coupled resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian. Assuming that the online learning agents have only noisy first-order utility feedback, we show that for a polynomially decaying agents step size/learning rate, the population's dynamic will almost surely converge to generalized Nash equilibrium. A particular consequence of the latter is the fulfillment of resource constraints in the asymptotic limit. Moreover, we investigate the finite-time quality of the proposed algorithm by giving a nonasymptotic time decaying bound for the expected amount of resource constraint violation. [ABSTRACT FROM AUTHOR]

In-silico control of complex stochastic biological systems is a promising area of cybergenetics, which provides enabling theoretical and practical tools for the real-time control of living cells with digital computers. We demonstrate here that simple proportional-integral control laws can be used to control both the mean and the variance of the expression product of a simple gene expression network. Extensions to more general unimolecular networks, networks with input delay, and to a gene expression network involving protein dimerization are also provided. Notably, no moment closure method is used for dealing with the network with dimerization. The obtained results are illustrated by simulations. [ABSTRACT FROM AUTHOR]

Goal-driven selective attention (GDSA) is a remarkable function that allows the complex dynamical networks of the brain to support coherent perception and cognition. Part I of this two-part article proposes a new control-theoretic framework, termed hierarchical selective recruitment (HSR), to rigorously explain the emergence of GDSA from the brain's network structure and dynamics. This part completes the development of HSR by deriving conditions on the joint structure of the hierarchical subnetworks that guarantee top-down recruitment of the task-relevant part of each subnetwork by the subnetwork at the layer immediately above, while inhibiting the activity of task-irrelevant subnetworks at all the hierarchical layers. To further verify the merit and applicability of this framework, we carry out a comprehensive case study of selective listening in rodents and show that a small network with HSR-based structure can explain the data with remarkable accuracy while satisfying the theoretical stability and timescale separation requirements of HSR. Our technical approach relies on the theory of switched systems and provides a novel converse Lyapunov theorem for state-dependent switched affine systems that is of independent interest. [ABSTRACT FROM AUTHOR]

This article presents a multicommodity, discrete-time, distributed, and noncooperative routing algorithm, which is proved to converge to an equilibrium in the presence of heterogeneous, unknown, time-varying but bounded delays. Under mild assumptions on the latency functions, which describe the cost associated with the network paths, two algorithms are proposed: The former assumes that each commodity relies only on measurements of the latencies associated with its own paths; the latter assumes that each commodity has (at least indirectly) access to the measures of the latencies of all the network paths. Both algorithms are proven to drive the system state to an invariant set that approximates and contains the Wardrop equilibrium, defined as a network state in which no traffic flow over the network paths can improve its routing unilaterally, with the latter achieving a better reconstruction of the Wardrop equilibrium. Numerical simulations show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

Inspired by the concepts of deep learning in artificial intelligence and fairness in behavioral economics, we introduce deep teams in this article. In such systems, agents are partitioned into a few subpopulations so that the dynamics and cost of agents in each subpopulation is invariant to the indexing of agents. The goal of agents is to minimize a common cost function in such a manner that the agents in each subpopulation are not discriminated or privileged by the way they are indexed. Two nonclassical information structures are studied. In the first one, each agent observes its local state as well as the empirical distribution of the states of agents in each subpopulation, called deep state, whereas in the second one, the deep states of a subset (possibly all) of subpopulations are not observed. Novel dynamic programs are developed to identify globally optimal and suboptimal solutions for the first and second information structures, respectively. The computational complexity of finding the optimal solution in both space and time is polynomial (rather than exponential) with respect to the number of agents in each subpopulation and is linear (rather than exponential) with respect to the control horizon. This complexity is further reduced in time by introducing a forward equation, which we call deep Chapman-Kolmogorov equation, described by multiple convolutional layers of binomial probability distributions. Two different prices are defined for computation and communication, and it is shown that under mild conditions they converge to zero as the number of quantization levels and the number of agents tend to infinity. In addition, the main results are extended to infinite-horizon discounted models and arbitrarily asymmetric cost functions. Finally, a service management example with 200 users is presented. [ABSTRACT FROM AUTHOR]

We consider a class of dynamic collective choice models with social interactions, whereby a large number of nonuniform agents have to individually settle on one of multiple discrete alternative choices, with the relevance of their would-be choices continuously impacted by noise and the unfolding group behavior. This class of problems is modeled here as a so-called min-LQG game, i.e., a linear quadratic Gaussian dynamic and noncooperative game, with an additional combinatorial aspect in that it includes a final choice-related minimization in its terminal cost. The presence of this minimization term is key to enforcing some specific discrete choice by each individual agent. The theory of mean field games is invoked to generate a class of decentralized agent feedback control strategies, which are then shown to converge to an exact Nash equilibrium of the game as the number of players increases to infinity. A key building block in our approach is an explicit solution to the problem of computing the best response of a generic agent to some arbitrarily posited smooth mean field trajectory. Ultimately, an agent is shown to face a continuously revised discrete choice problem, where greedy choices dictated by current conditions must be constantly balanced against the risk of the future process noise upsetting the wisdom of such decisions. We show that any Nash equilibrium of the game is defined by an a priori computable probability matrix, which describes the distribution of the players’ choices over the alternatives. The results are illustrated through simulations. [ABSTRACT FROM AUTHOR]

We consider mean field games between a dominant leader and many followers, such that each follower is subject to a heterogeneous delay effect from the leader's action, who in turn can exercise governance on the population through this influence. The delay effects are assumed to be discretely distributed among the followers. Given regular enough coefficients, we describe a necessary condition for the existence of a solution for the equilibrium by a system of coupled forward–backward stochastic differential equations and stochastic partial differential equations. We provide a thorough study for the particular linear quadratic case. By adopting a functional approach, we obtain the time-independent sufficient condition, which warrants the unique existence of the solution of the whole mean field game problem. Several numerical illustrations with different time horizons and populations are demonstrated. [ABSTRACT FROM AUTHOR]

This note develops new containment control algorithms for two classes of heterogeneous multiagent systems. In a first scenario, the controls are zero during portions of successive time intervals, while in a second scenario, the system follows constant-velocity trajectories during portions of successive intervals. Some sufficient conditions are derived for the two classes of intermittent containment control. Finally, several illustrative examples are provided to show the effectiveness of the obtained results. [ABSTRACT FROM AUTHOR]

We consider a dynamic collective choice problem where a large number of agents are cooperatively choosing between multiple destinations while being influenced by the behavior of the group. For example, in a robotic swarm exploring a new environment, a robot might have to choose between multiple sites to visit, but at the same time it should remain close to some group to achieve coordinated tasks. Finding a social optimum for our problem reduces to solving a set of linear quadratic regulator problems, whose number, however, increases exponentially with the size of the population. Alternatively, we develop via the mean field games methodology a set of decentralized strategies characterized via the fixed points of a suitable operator. In the homogeneous parameter agents case, the procedure reduces to solving a vector fixed point equation of size $l$ equal to the number of destinations, followed by each agent comparing only $l$ regulator costs, independently of the number of agents. When the latter is sufficiently large, the strategies qualify as approximately socially optimal. To compute the approximate social optimum, each agent only needs to know its own state and the statistical distributions of the agents’ initial states and problem parameters. A numerical example illustrates the benefits of cooperative strategies compared to noncooperative ones in achieving an adequate splitting of agents among multiple destinations that each require collective attention. [ABSTRACT FROM AUTHOR]

To study how sustainable cooperation might emerge among self-interested interacting individuals, we investigate the long-run behavior of the decision-making dynamics in a finite, well-mixed population of individuals, who play collectively over time a population game. Repeatedly each individual is activated asynchronously to update her decision to either cooperate or defect according to the myopic best-response rule. The game's payoff matrices, chosen to be those of either prisoner's dilemma or snowdrift games to underscore cooperation-centered social dilemmas, are fixed, but can be distinct for different individuals. So, the overall population is heterogeneous. We first classify such heterogeneous individuals into different types according to their cooperating tendencies stipulated by their payoff matrices. Then, we show that no matter what initial strategies the individuals decide to use, surprisingly one can always identify one type of individuals as a benchmark such that after a sufficiently long but finite time, individuals more cooperative compared to the benchmark always cooperate, while those less cooperative compared to the benchmark defect. When such fixation takes place, the total number of cooperators in the population either becomes fixed or fluctuates at most by one. Such insight provides theoretical explanation for some complex behavior recently reported in simulation studies that highlight the puzzling effect of individuals’ heterogeneity on collective decision-making dynamics. [ABSTRACT FROM PUBLISHER]

Inspired by successful biological collective decision mechanisms such as honey bees searching for a new colony or the collective navigation of fish schools, we consider a scenario where a large number of agents engaged in a dynamic game have to make a choice among a finite set of different potential target destinations. Each individual both influences and is influenced by the group's decision, as represented by the mean trajectory of all agents. The model can be interpreted as a stylized version of opinion crystallization in an election for example. In the most general formulation, agents’ biases are dictated by a combination of initial position, individual dynamics parameters, and a priori individual preference. Agents are assumed linear and coupled through a modified form of quadratic cost, whereby the terminal cost captures the discrete choice component of the problem. Following the mean field games methodology, we identify sufficient conditions under which allocations of destination choices over agents lead to self-replication of the overall mean trajectory under the best response by the agents. Importantly, we establish that when the number of agents increases sufficiently, 1) the best response strategies to the self-replicating mean trajectories qualify as epsilon-Nash equilibria of the population game; and 2) these epsilon-Nash strategies can be computed solely based on the knowledge of the joint probability distribution of the initial conditions, dynamics parameters, and destination preferences, now viewed as random variables. Our results are illustrated through numerical simulations. [ABSTRACT FROM PUBLISHER]

Recent innovations in the design of computer viruses have led to new trade-offs for the attacker. Multiple variants of a malware may spread at different rates and have different levels of visibility to the network. In this work we examine the optimal strategies for the attacker so as to trade off the extent of spread of the malware against the need for stealth. We show that in the mean-field deterministic regime, this spread-stealth trade-off is optimized by computationally simple single-threshold policies. Specifically, we show that only one variant of the malware is spread by the attacker at each time, as there exists a time up to which the attacker prioritizes maximizing the spread of the malware, and after which she prioritizes stealth. [ABSTRACT FROM AUTHOR]

A novel class of auction-based games is formulated to study coordination problems arising from charging a population of electric vehicles (EVs) over a finite horizon. To compete for energy allocation over the horizon, each individual EV submits a multidimensional bid, with the dimension equal to two times the number of time-steps in the horizon. Use of the progressive second price (PSP) auction mechanism ensures that incentive compatibility holds for the auction games. However, due to the cross elasticity of EVs over the charging horizon, the marginal valuation of an individual EV at a particular time is determined by both the demand at that time and the total demand over the entire horizon. This difficulty is addressed by partitioning the allowable set of bid profiles based on the total desired energy over the entire horizon. It is shown that the efficient bid profile over the charging horizon is a Nash equilibrium of the underlying auction game. An update mechanism for the auction game is designed. A numerical example demonstrates that the auction process converges to an efficient Nash equilibrium. The auction-based charging coordination scheme is adapted to a receding horizon formulation to account for disturbances and forecast uncertainty. [ABSTRACT FROM PUBLISHER]

Current distributed routing control algorithms for dynamic networks model networks using the time evolution of density at network edges, while the routing control algorithm ensures edge density to converge to a Wardrop equilibrium, which was characterized by an equal traffic density on all used paths. We rearrange the density model to recast the problem within the framework of mean-field games. In doing that, we illustrate an extended state-space solution approach and we study the stochastic case where the density evolution is driven by a Brownian motion. Further, we investigate the case where the density evolution is perturbed by a bounded adversarial disturbance. For both the stochastic and the worst-case scenarios, we provide conditions for the density to converge to a pre-assigned set. Moreover, we analyze such conditions from two different perspectives, repeated games with vector payoffs and inclusion theory. [ABSTRACT FROM AUTHOR]

Networked games prevail in a wide range of evolutionary collective phenomena on social, biological, and engineering networks. An important and challenging problem is how to understand and then further intervene in the evolutionary networked game dynamics. This technical note aims at developing a microscopic deterministic formulation for analyzing and controlling the evolutionary game dynamics on complex networks. By utilizing the typical characteristics of multi-agent systems, the proposed approach establishes a systematic framework with micro-macro-intervention mechanism to analyze and control the networked game dynamics. Based on the proposed method, this technical note further explores several key issues, including consensus of strategies, cooperation among individuals and control of the network game dynamics. These results indicate us that the feedback from neighborhoods to each individual can alter the tendency of defection for adaptive dynamics. While for imitation dynamics on networks, it is much more effective to boost cooperation by awarding cooperators with high degree. Moreover, the effectiveness of different cooperation mechanisms has been clarified. The developed microscopic deterministic approach sheds some lights on the understanding and intervening in the collective decision-making behaviors in social and engineering networks. [ABSTRACT FROM AUTHOR]