Search

The Shapiro scheme, together with the closely related Frisch–Kalman scheme, has been an important approach to system identification and statistical analysis. A longstanding result on this scheme, known as the Shapiro theorem, is both informative and significant. This article imparts a geometric understanding to the Shapiro theorem and generalizes it to the asymmetric setting using the notion of cone-invariance. In particular, we establish the equivalence between two important properties of a real-valued square matrix—irreducible orthant-invariance and simplicity of its dominant eigenvalue under arbitrary diagonal perturbations. The result can be regarded as a converse Perron–Frobenius theorem. Furthermore, we investigate two applications of the proposed result in systems and control, namely, characterization of irreducibly orthant-monotone nonlinear systems and subspace tracking via decentralized control. We also extend the established result to accommodating polyhedral cones and obtain several insights. [ABSTRACT FROM AUTHOR]

In this article, we present a continuation method, which transforms spatially distributed ordinary differential equation (ODE) systems into a continuous partial differential equation (PDE). We show that this continuation can be performed for both linear and nonlinear systems, including multidimensional, space-varying, and time-varying systems. When applied to a large-scale network, the continuation provides a PDE describing the evolution of a continuous-state approximation that respects the spatial structure of the original ODE. Our method is illustrated by multiple examples, including transport equations, Kuramoto equations, and heat diffusion equations. As a main example, we perform the continuation of a Newtonian system of interacting particles and obtain the Euler equations for compressible fluids, thereby providing an original solution to Hilbert’s sixth problem. Finally, we leverage our derivation of Euler equations to solve a control problem multiagent systems, by designing a nonlinear control algorithm for robot formation based on its continuous approximation. [ABSTRACT FROM AUTHOR]

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]

In this article, we study the optimal control problem arising from the mean-field game formulation of the collective decision-making in honeybee swarms. A population of homogeneous players (the honeybees) has to reach consensus on one of two options. We consider three states: the first two represent the available options (or strategies), and the third one represents the uncommitted state. We formulate the continuous-time discrete-state mean-field game model. The contributions of this article are the following: 1) we propose an optimal control model where players have to control their transition rates to minimize a running cost and a terminal cost, in the presence of an adversarial disturbance; 2) we develop a formulation of the micro–macro model in the form of an initial-terminal value problem with switched dynamics; 3) we study the existence of stationary solutions and the mean-field Nash equilibrium for the resulting switched system; 4) we show that under certain assumptions on the parameters, the game may admit periodic solutions; and 5) we analyze the resulting microscopic dynamics in a structured environment where a finite number of players interact through a network topology. [ABSTRACT FROM AUTHOR]

In this article, we stabilize a discrete-time Markov process evolving on a compact subset of $\mathbb {R}^d$ to an arbitrary target distribution that has an $L^\infty (\cdot)$ density and does not necessarily have a connected support on the state space. We address this problem by stabilizing the corresponding Kolmogorov forward equation, the mean-field model of the system, using a density-dependent transition Kernel as the control parameter. Our main application of interest is controlling the distribution of a multiagent system in which each agent evolves according to this discrete-time Markov process. To prevent agent state transitions at the equilibrium distribution, which would potentially waste energy, we show that the Markov process can be constructed in such a way that the operator that pushes forward measures is the identity at the target distribution. In order to achieve this, the transition kernel is defined as a function of the current agent distribution, resulting in a nonlinear Markov process. Moreover, we design the transition kernel to be decentralized in the sense that it depends only on the local density measured by each agent. We prove the existence of such a decentralized control law that globally stabilizes the target distribution. Furthermore, to implement our control approach on a finite $N$ -agent system, we smoothen the mean-field dynamics via the process of mollification. We validate our control law with numerical simulations of multiagent systems with different population sizes. We observe that as $N$ increases, the agent distribution in the $N$ -agent simulations converges to the solution of the mean-field model, and the number of agent state transitions at equilibrium decreases to zero. [ABSTRACT FROM AUTHOR]

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]

Set-membership filter (SMF) has been extensively studied for state estimation in the presence of bounded noises with unknown statistics. Since it was first introduced in the 1960s, the studies on SMF have used the set-based description as its mathematical framework. One important issue that has been overlooked is the optimality of SMF. In this article, we put forward a new mathematical framework for SMF using concepts of uncertain variables. We first establish two basic properties of uncertain variables, namely, the law of total range (a nonstochastic version of the law of total probability) and the equivalent Bayes’ rule. This enables us to put forward a general SMFing framework with established optimality. Furthermore, we obtain the optimal SMF under a nonstochastic Markov condition, which is shown to be fundamentally equivalent to the Bayes filter. Note that the classical SMF in the literature is only equivalent to the optimal SMF we obtained under the nonstochastic Markov condition. When this condition is violated, we show that the classical SMF is not optimal and it only gives an outer bound on the optimal estimate. [ABSTRACT FROM AUTHOR]

In the traditional game-theoretic set up, where agents select actions and experience corresponding utilities, a Nash equilibrium is a configuration where no agent can improve their utility by unilaterally switching to a different action. In this article, we introduce the novel notion of inertial Nash equilibrium to account for the fact that in many practical situations switching action does not come for free. Specifically, we consider a population game and introduce the coefficients $c_{ij}$ describing the cost an agent incurs by switching from action $i$ to action $j$. We define an inertial Nash equilibrium as a distribution over the action space where no agent benefits in switching to a different action, while taking into account the cost of such switch. First, we show that the set of inertial Nash equilibria contains all the Nash equilibria, is in general nonconvex, and can be characterized as a solution to a variational inequality. We then argue that classical algorithms for computing Nash equilibria cannot be used in the presence of switching costs. Finally, we propose a better-response dynamics algorithm and prove its convergence to an inertial Nash equilibrium. We apply our results to study the taxi drivers’ distribution in Hong Kong. [ABSTRACT FROM AUTHOR]

In this article, we extend the theory of deterministic mean-field/aggregative games to multipopulation games. We consider a set of populations, each managed by a population coordinator (PC), of selfish agents playing a global noncooperative game, whose cost functions are affected by an aggregate term across all agents from all populations. In particular, we impose that the agents cannot exchange information between themselves directly; instead, only a PC can gather information on its own population and exchange local aggregate information with the neighboring PCs. To seek an equilibrium of the resulting (partial-information) game, we propose an iterative algorithm where each PC broadcasts a mean-field signal, namely, an estimate of the overall aggregative term, to its own population only. In turn, we let the local agents react with the best response and the PCs cooperate for estimating the aggregative term. Our main technical contributions are to cast the proposed scheme as a fixed-point iteration with errors, namely, the interconnection of a Krasnoselskij–Mann iteration and a linear consensus protocol, and, under a nonexpansiveness condition, to show convergence towards an $\varepsilon$ -Nash equilibrium, where $\varepsilon$ is inversely proportional to the population size. [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]

This article studies uniform stabilization and social optimality for linear quadratic (LQ) mean field control problems with multiplicative noise, where agents are coupled via dynamics and individual costs. The state and control weights in cost functionals are not limited to be positive semidefinite. This leads to an indefinite LQ mean field control problem, which may still be well-posed due to deep nature of multiplicative noise. We first obtain a set of forward–backward stochastic differential equations (FBSDEs) from variational analysis, and construct a feedback control by decoupling the FBSDEs. By virtue of solutions to two Riccati equations, we design a set of decentralized control laws, which is further shown to be asymptotically social optimal. Some equivalent conditions are given for uniform stabilization of the systems with the help of linear matrix inequalities. A numerical example is given to illustrate the effectiveness of the proposed control laws. [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 this article, we study the problem of estimating the state of the linearized Kermack–McKendrick partial differential equation (PDE) model in real time. Especially, we assume that the model contains two kinds of delays. One of them is contained in the nonlocal boundary condition, which expresses the latent period of infection. The other is an observation delay, which corresponds to the time needed for counting the number of infected people at an infection elapsed time. The element of time lags can be expressed by a transport equation. As a result, the system with two delays is equivalently written by a $3\times 3$ hyperbolic system. In this article, we construct observers with three gain functions, using a backstepping method of PDEs. Then, the triple of the designed gain belongs to the domain of the generator governing the state evolution of the error system. Furthermore, based on this fact and the semigroup theory, it is shown that the error system is $L^2$ -stable in the Hilbert space. [ABSTRACT FROM AUTHOR]

In two-player repeated games, zero-determinant (ZD) strategies enable a player to unilaterally enforce a linear payoff relation between her own and her opponent's payoff irrespective of the opponent's strategy. This manipulative nature of the ZD strategies attracted significant attention from researchers due to their close connection to controlling distributively the outcome of evolutionary games in large populations. In this article, necessary and sufficient conditions are derived for a payoff relation to be enforceable in multiplayer social dilemmas with a finite expected number of rounds that is determined by a fixed and common discount factor. Thresholds exist for such a discount factor above which desired payoff relations can be enforced. Our results show that depending on the group size and the ZD strategist's initial probability to cooperate their existing extortionate, generous, and equalizer ZD strategies. The threshold discount factors rely on the desired payoff relation and the variation in the single-round payoffs. To show the utility of our results, we apply them to multiplayer social dilemmas, and show how discounting affects ZD Nash equilibria. [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]

Partially observed major–minor nonlinear and linear quadratic Gaussian (PO MM LQG) mean field game (MFG) systems where the major agent's state is partially observed by each minor agent, and the major agent completely observes its own state have been analyzed in the literature. In this article, PO MM LQG MFG problems with general information patterns are studied where the major agent has partial observations of its own state, and each minor agent has partial observations of its own state and the major agent's state. The assumption of partial observations by all agents leads to a new situation involving the recursive estimation by each minor agent of the major agent's estimate of its own state. For the general case of PO MM LQG MFG systems, the existence of ε-Nash equilibria, together with the individual agents’ control laws yielding the equilibria, are established via the separation principle. [ABSTRACT FROM AUTHOR]

Aggregative games have many industrial applications, and computing an equilibrium in those games is challenging when the number of players is large. In the framework of atomic aggregative games with coupling constraints, we show that variational Nash equilibria of a large aggregative game can be approximated by a Wardrop equilibrium of an auxiliary population game of smaller dimension. Each population of this auxiliary game corresponds to a group of atomic players of the initial large game. This approach enables an efficient computation of an approximated equilibrium, as the variational inequality characterizing the Wardrop equilibrium is of smaller dimension than the initial one. This is illustrated in an example in the smart grid context. [ABSTRACT FROM AUTHOR]

Large-size populations consisting of a continuum of identical and noncooperative agents with stochastic dynamics are useful in modeling various biological and engineered systems. This article addresses the stochastic control problem of designing optimal state-feedback controllers that guarantee the closed-loop stability of the stationary density of such agents with nonlinear Langevin dynamics, under the action of their individual steady-state controls. We represent the corresponding coupled forward–backward partial differential equations as decoupled Schrödinger equations, by applying two variable transforms. Spectral properties of the linear Schrödinger operator that underlie the stability analysis are used to obtain explicit control design constraints. Our interpretation of the Schrödinger potential as the cost function of a closely related optimal control problem motivates a quadrature based algorithm to compute the finite-time optimal control. [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]

We study the problem of detecting an attack on a stochastic cyber-physical system. We aim to treat the problem in its most general form. We start by introducing the notion of asymptotically detectable attacks, as those attacks introducing changes to the system's output statistics which persist asymptotically. We then provide a necessary and sufficient condition for asymptotic detectability. This condition preserves generality as it holds under no restrictive assumption on the system and attacking scheme. To show the importance of this condition, we apply it to detect certain attacking schemes which are undetectable using simple statistics. Our necessary and sufficient condition naturally leads to an algorithm which gives a confidence level for attack detection. We present simulation results to illustrate the performance of this algorithm. [ABSTRACT FROM AUTHOR]

Contagious processes, such as spread of infectious diseases, social behaviors, or computer viruses, affect biological, social, and technological systems. Epidemic models for large populations and finite populations on networks have been used to understand and control both transient and steady-state behaviors. Typically it is assumed that after recovery from an infection, every agent will either return to its original susceptible state or acquire full immunity to reinfection. We study the network SIRI (Susceptible-Infected-Recovered-Infected) model, an epidemic model for the spread of contagious processes on a network of heterogeneous agents that can adapt their susceptibility to reinfection. The model generalizes existing models to accommodate realistic conditions in which agents acquire partial or compromised immunity after first exposure to an infection. We prove necessary and sufficient conditions on model parameters and network structure that distinguish four dynamic regimes: infection-free, epidemic, endemic, and bistable. For the bistable regime, which is not accounted for in traditional models, we show how there can be a rapid resurgent epidemic after what looks like convergence to an infection-free population. We use the model and its predictive capability to show how control strategies can be designed to mitigate problematic contagious behaviors. [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]

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]

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 paper develops an effective distributed strategy for the solution of constrained multiagent stochastic optimization problems with coupled parameters across the agents. In this formulation, each agent is influenced by only a subset of the entries of a global parameter vector or model, and is subject to convex constraints that are only known locally. Problems of this type arise in several applications, most notably in disease propagation models, minimum-cost flow problems, distributed control formulations, and distributed power system monitoring. This paper focuses on stochastic settings, where a stochastic risk function is associated with each agent and the objective is to seek the minimizer of the aggregate sum of all risks subject to a set of constraints. Agents are not aware of the statistical distribution of the data and, therefore, can only rely on stochastic approximations in their learning strategies. We derive an effective distributed learning strategy that is able to track drifts in the underlying parameter model. A detailed performance and stability analysis is carried out showing that the resulting coupled diffusion strategy converges at a linear rate to an $O(\mu)$ neighborhood of the true penalized optimizer. [ABSTRACT FROM AUTHOR]

Moments of continuous random variables admitting a probability density function are studied. We show that, under certain assumptions, the moments of a random variable can be characterized in terms of a Sylvester equation and of the steady-state output response of a specific interconnected system. This allows to interpret well-known notions and results of probability theory and statistics in the language of systems theory, including the sum of independent random variables, the notion of mixture distribution and results from renewal theory. The theory developed is based on tools from center manifold theory, the theory of the steady-state response of nonlinear systems, and the theory of output regulation. Our formalism is illustrated by means of several examples and can be easily adapted to the case of discrete and multivariate random variables. [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]

We consider the framework of aggregative games, in which the cost function of each agent depends on his own strategy and on the average population strategy. As first contribution, we investigate the relations between the concepts of Nash and Wardrop equilibria. By exploiting a characterization of the two equilibria as solutions of variational inequalities, we bound their distance with a decreasing function of the population size. As second contribution, we propose two decentralized algorithms that converge to such equilibria and are capable of coping with constraints coupling the strategies of different agents. Finally, we study the applications of charging of electric vehicles and of route choice on a road network. [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]

A fundamental question in systems biology is what combinations of mean and variance of the species present in a stochastic biochemical reaction network are attainable by perturbing the system with an external signal. To address this question, we show that the moments evolution in any generic network can be either approximated or, under suitable assumptions, computed exactly as the solution of a switched affine system. We then propose a new method to approximate the reachable set of such a switched affine system. A remarkable feature of our approach is that it allows one to easily compute projections of the reachable set for pairs of moments of interest, without requiring the computation of the full reachable set, which can be prohibitive for large networks. As a second contribution, we also show how to select the external signal in order to maximize the probability of reaching a target set. To illustrate the method, we study a renowned model of the controlled gene expression and we derive estimates of the reachable set, for the protein mean and variance, that are more accurate than those available in the literature and consistent with experimental data. [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]

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]

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]

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]

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]

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]

The network routing literature contains many results showing that tolls can be used to improve the efficiency of network traffic routing. These results typically require toll-designers to have an exact characterization of the network and user population. We relax this strict informational dependence and present a simple setting in which scaled marginal-cost tolls can be guaranteed to provide significant efficiency improvements over the un-tolled case, even if the toll-sensitivities of the users are unknown. [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 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 paper considers a remote state estimation problem with multiple sensors observing a dynamical process, where sensors transmit local state estimates over an independent and identically distributed (i.i.d.) packet dropping channel to a remote estimator. At every discrete time instant, the remote estimator decides whether each sensor should transmit or not, with each sensor transmission incurring a fixed energy cost. The channel is shared such that collisions will occur if more than one sensor transmits at a time. Performance is quantified via an optimization problem that minimizes a convex combination of the expected estimation error covariance at the remote estimator and expected energy usage across the sensors. For transmission schedules dependent only on the estimation error covariance at the remote estimator, this work establishes structural results on the optimal scheduling which show that: 1) for unstable systems, if the error covariance is large then a sensor will always be scheduled to transmit and 2) there is a threshold-type behavior in switching from one sensor transmitting to another. Specializing to the single sensor case, these structural results demonstrate that a threshold policy (i.e., transmit if the error covariance exceeds a certain threshold and don't transmit otherwise) is optimal. We also consider the situation where sensors transmit measurements instead of state estimates, and establish structural results including the optimality of threshold policies for the single sensor, scalar case. These results provide a theoretical justification for the use of such threshold policies in variance based event triggered estimation. Numerical studies confirm the qualitative behavior predicted by our structural results. [ABSTRACT FROM AUTHOR]

This paper proposes a new continuous-time first best contract framework that has the ability to explicitly limit the agent's risks. This limitation of risk is achieved by formulating the contract design problem as a mean-variance constrained stochastic optimal control problem. To obtain a globally optimal contract even when system dynamics are nonlinear, we develop a dynamic programming-based solution approach. The major theoretical challenge arises from the variance inequality constraint. To overcome this difficulty, we track and limit the agent's risk using a new stochastic system, whose state value can be interpreted as the agent's remaining budget for risks. We also propose an approximately decoupled contract design approach for multiple agents to resolve the scalability issue inherent in dynamic programming. The procedures in this contract design for multiple agents can be completely parallelized. We show that this approximate contract satisfies each agent's individual rationality condition and has a provable suboptimality bound. The performance and usefulness of the proposed contract method and its application to demand response are demonstrated using data on the electric energy consumption of customers in Austin, Texas, and the locational marginal price data from the Electricity Reliability Council of Texas. [ABSTRACT FROM AUTHOR]

For linear discrete state-space models, under certain conditions, the linear least-mean-squares filter estimate has a convenient recursive predictor/corrector format, aka the Kalman filter. The purpose of this paper is to show that the linear minimum variance distortionless response (MVDR) filter shares exactly the same recursion, except for the initialization which is based on a weighted least-squares estimator. If the MVDR filter is suboptimal in mean-squared error sense, it is an infinite impulse response distortionless filter (a deconvolver) which does not depend on the prior knowledge (first- and second-order statistics) on the initial state. In other words, the MVDR filter can be pre-computed and its behaviour can be assessed in advance independently of the prior knowledge on the initial state. [ABSTRACT FROM AUTHOR]

In this note, we consider the statistical ranking and selection problem of finding the best alternative when the performances of each alternative must be estimated by sampling. We provide a myopic allocation policy that asymptotically achieves the sampling ratios given by the optimal computing budget allocation, an approximate solution of the optimal large deviations rate for the decreasing probability of false selection. We analyze the asymptotic sampling ratio for both known variances and unknown variances under a Bayesian framework. Numerical results substantiate the theoretical results. [ABSTRACT FROM AUTHOR]

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]

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]

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]

We investigate the control of evolutionary games on networks, in which each edge represents a two-player repeating game between neighboring agents. After each round of games, agents can imitate the strategies of better performing neighbors, while a subset of agents can be assigned strategies and thus serve as control inputs. We seek here the smallest set of control agents needed to drive the network to a desired uniform strategy state. After presenting exact solutions for complete and star networks and describing a general solution approach that is computationally practical only for small networks, we design a fast algorithm for approximating the solution on arbitrary networks using a weighted minimum spanning tree and strategy propagation algorithm. The resulting approximation is exact for certain classes of games on complete and star networks and simulations suggest that the algorithm performs well in more general cases. [ABSTRACT FROM PUBLISHER]