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]

This paper presents an inverse problem for mean field games where we find the mean field problem statement for which the given dynamics is the solution. We use distributed traffic as an example and derive the classic Lighthill Whitham Richards (LWR) model as a solution of the non-viscous mean field game. We also derive the same model by choosing a different problem where we use travel time, which is a distributed parameter, as the cost for the optimal control. We then study the stationary versions of these two problems and provide numerical solutions for the same. [ABSTRACT FROM PUBLISHER]

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 addresses the robust optimal filtering design over unreliable networks, where the data packet dropouts occur during the signal transmission from the sensor side to the filter. The designed filter is expected, under communication data loss, to provide a guaranteed robustness against disturbance/model uncertainty while achieving the minimized variance of the estimation error under Gaussian white noises and the worst case of the disturbance. The Nash game approach is adopted to deal with such a multiobjective filtering problem. Based on the concept of the mean-square stability, Nash equilibrium strategies are analytically applied in terms of two cross-coupled modified algebraic Riccati equations. The presented design method provides a systematic way to achieve a tradeoff of the estimation performance in the $\mathcal {H}_2$ and $\mathcal {H}_\infty$ senses in the presence of data loss. [ABSTRACT FROM AUTHOR]

This paper proposes an approach to control of discrete systems with incomplete information and sensing capabilities, with respect to temporal logic constraints. The approach introduces active sensing to alleviate computational effort in control design for systems interacting with uncontrollable environments under incomplete information. Particularly, it transforms a deterministic controller under complete information into a randomized, observation-based controller. Interleaving the latter with strategic queries to sensors, the temporal logic specification is proven to be satisfied almost surely. The effectiveness of the method is demonstrated with robotic motion planning examples. [ABSTRACT FROM PUBLISHER]

We consider an environmentwhere players need to decide whether to buy a certain product (or adopt a technology) or not. The product is either good or bad, but its true value is unknown to the players. Instead, each player has her own private information on its quality. Each player can observe the previous actions of other players and estimate the quality of the product. A classic result in the literature shows that in similar settings, informational cascades occur, where learning stops for the whole network and players repeat the actions of their predecessors. In contrast to this literature, in this paper, players get more than one opportunity to act. In each turn, a player is chosen uniformly at random from all the players and can decide to buy the product and leave the market or wait. Her utility is the total expected discounted reward, and thus, myopic strategies may not constitute equilibria. We provide a characterization of perfect Bayesian equilibria (PBEs) with forward-looking strategies through a fixed-point equation of dimensionality that grows only quadratically with the number of players. Using this tractable fixed-point equation, we show the existence of a PBE and characterize PBEs with threshold strategies. Based on this characterization, we study informational cascades in two regimes. First, we show that for a discount factor $\delta$ strictly smaller than 1, informational cascades happen with high probability as the number of players $N$ increases. Furthermore, only a small portion of the total information in the system is revealed before a cascade occurs. Second, and more surprisingly, we show that for a fixed $N$ , and for a sufficiently large $\delta < 1$ , when the product is bad, there exists an equilibrium where an informational cascade can happen only after at least half of the players revealed their private information, and consequently, the probability for a “bad cascade” where all the players buy the product vanishes exponentially with $N$. Finally, when $\delta =1$ and the product is bad, there exists an equilibrium where informational cascades do not happen at all. [ABSTRACT FROM AUTHOR]

This paper addresses cooperative environmental monitoring for Pan-Tilt-Zoom (PTZ) visual sensor networks. In particular, we investigate the optimal monitoring problem whose objective function value is intertwined with the uncertain state of the physical world. In addition, due to the large volume of vision data, it is desired for each sensor to execute processing through local computation and communication. To address these issues, we present a distributed solution to the problem based on game theoretic cooperative control and payoff-based learning. At the first stage, a utility function is designed so that the resulting game constitutes a potential game with potential function equal to the group objective function, where the designed utility is shown to be computable through local image processing and communication. Then, we present a payoff-based learning algorithm so that the sensors are led to the global objective function maximizers without using any prior information on the environmental state. Finally, we run experiments to demonstrate the effectiveness of the present approach. [ABSTRACT FROM PUBLISHER]

Our prior work has studied the enforcement of opacity security properties using insertion functions. Given a system that is not opaque, the so-called All Insertion Structure (AIS) is a game structure, played by the system and the insertion function, that embeds all valid insertion functions. In this paper, we first propose a more compact AIS that can be constructed with lower computational complexity. We then introduce the maximum total cost and the maximum mean cost, and use them as quantitative objectives to solve for optimal insertion functions. Specifically, we first determine if an insertion function with a finite total cost exists. If such an insertion function exists, we synthesize an optimal total-cost insertion function. Otherwise, we construct an optimal mean-cost insertion function. In either case, we find an optimal insertion strategy on the AIS, with respect to the corresponding cost objective. The algorithmic procedures are adapted from results developed for minimax games and mean payoff games. The resulting optimal strategy is represented as a subgraph of the AIS that consists of all the system actions and the optimal insertion actions. Finally, we use this subgraph to synthesize an optimal insertion function that is encoded as an I/O automaton. [ABSTRACT FROM PUBLISHER]

This paper is concerned with distributed learning and optimization in large-scale settings. The well-known fictitious play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multiagent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP (SFP) is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte Carlo (i.e., sampling based) approach. Despite its computational advantages, a shortcoming of SFP is that the number of samples that must be drawn at each iteration grows without bound as the algorithm progresses. In this paper, we propose single sample FP (SSFP)—A variant of SFP in which only one sample needs to be drawn in each round of the algorithm. Convergence of SSFP to the set of Nash equilibria is proven. Simulation results show the performance of SSFP is comparable to that of SFP, despite drawing far fewer samples. [ABSTRACT FROM PUBLISHER]

In this paper, Nash equilibrium seeking among a network of players is considered. Different from many existing works on Nash equilibrium seeking in noncooperative games, the players considered in this paper cannot directly observe the actions of the players who are not their neighbors. Instead, the players are supposed to be capable of communicating with each other via an undirected and connected communication graph. By a synthesis of a leader-following consensus protocol and the gradient play, a distributed Nash equilibrium seeking strategy is proposed for the noncooperative games. Analytical analysis on the convergence of the players’ actions to the Nash equilibrium is conducted via Lyapunov stability analysis. For games with nonquadratic payoffs, where multiple isolated Nash equilibria may coexist in the game, a local convergence result is derived under certain conditions. Then, a stronger condition is provided to derive a nonlocal convergence result for the nonquadratic games. For quadratic games, it is shown that the proposed seeking strategy enables the players’ actions to converge to the Nash equilibrium globally under the given conditions. Numerical examples are provided to verify the effectiveness of the proposed seeking strategy. [ABSTRACT FROM AUTHOR]

Prior work on automatic control synthesis for cyber-physical systems under logical constraints has primarily focused on environmental disturbances or modeling uncertainties, however, the impact of deliberate and malicious attacks has been less studied. In this paper, we consider a discrete-time dynamical system with a linear temporal logic (LTL) constraint in the presence of an adversary, which is modeled as a stochastic game. We assume that the adversary observes the control policy before choosing an attack strategy. We investigate two problems. In the first problem, we synthesize a robust control policy for the stochastic game that maximizes the probability of satisfying the LTL constraint. A value iteration based algorithm is proposed to compute the optimal control policy. In the second problem, we focus on a subclass of LTL constraints, which consist of an arbitrary LTL formula and an invariant constraint. We then investigate the problem of computing a control policy that minimizes the expected number of invariant constraint violations while maximizing the probability of satisfying the arbitrary LTL constraint. We characterize the optimality condition for the desired control policy. A policy iteration based algorithm is proposed to compute the control policy. We illustrate the proposed approaches using two numerical case studies. [ABSTRACT FROM AUTHOR]

This paper aims to reduce the communication and computation costs of the Nash equilibrium seeking strategy for the $N$ -coalition noncooperative games. The objective is achieved by the following two manners: 1) an interference graph is introduced to describe the interactions among the agents in each coalition and 2) the Nash equilibrium seeking strategy is designed with the interference graphs considered. The convergence property of the proposed Nash equilibrium seeking strategy is analytically investigated. It is shown that the agents’ actions generated by the proposed method converge to a neighborhood of the Nash equilibrium of the graphical $N$ -coalition noncooperative games under certain conditions. Several special cases where there is only one coalition and/or there are coalitions with only one agent are considered. The results for the special cases demonstrate that the proposed seeking strategy achieves the solution seeking for noncooperative games, social cost minimization problems, and single-agent optimization problems in a unified framework. Numerical examples are presented to support the theoretical results. [ABSTRACT FROM AUTHOR]

This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) and provides a stochastic-stability analysis in repeatedly played, positive-utility, finite strategic-form games. Prior work in this class of learning dynamics primarily analyzes asymptotic convergence through stochastic approximations, where convergence can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through an ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the analysis to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing asymptotic convergence that is based upon an explicit characterization of the invariant probability measure of the induced Markov chain. We further provide a methodology for computing the invariant probability measure in positive-utility games, together with an illustration in the context of coordination games. [ABSTRACT FROM AUTHOR]

Controlling complex systems to desired states is of primary importance in science and engineering. In the classical control framework, the plants to be controlled usually do not have their own payoff or objective functions; however, this is not the case in many practical situations in, for examples, social, economic, and “intelligent” engineering systems. This motivates our introduction of the game-based control system (GBCS), which has a hierarchical decision-making structure: one regulator and multiple agents. The regulator is regarded as the global controller that makes decision first, and then, the agents try to optimize their respective objective functions to reach a possible Nash equilibrium as a result of noncooperative dynamic game. A fundamental issue in the GBCS is: Is it possible for the regulator to change the macrostates by regulating the Nash equilibrium formed by the agents at the lower level? This leads to the investigation of controllability of the Nash equilibrium of the GBCS. In this paper, we will first formulate this new problem in a general nonlinear framework and then focus on linear systems. Some explicit necessary and sufficient algebraic conditions on the controllability of the Nash equilibrium are given for a linear GBCS, by solving the controllability problem of the associated forward and backward dynamic equations, which is a key technical issue and has rarely been explored in the literature. [ABSTRACT FROM AUTHOR]

This paper studies two-player zero-sum repeated Bayesian games in which every player has a private type that is unknown to the other player, and the initial probability of the type of every player is publicly known. The types of players are independently chosen according to the initial probabilities, and are kept the same all through the game. At every stage, players simultaneously choose actions, and announce their actions publicly. For finite horizon cases, an explicit linear program is provided to compute players’ security strategies. Moreover, this paper shows that a player's sufficient statistics, which is independent of the strategy of the other player, consists of the belief over the player's own type, the regret over the other player's type, and the stage. Explicit linear programs, whose size is linear in the size of the game tree, are provided to compute the initial regrets, and the security strategies that only depends on the sufficient statistics. For discounted cases, following the same idea in the finite horizon, this paper shows that a player's sufficient statistics consists of the belief of the player's own type and the antidiscounted regret with respect to the other player's type. Besides, an approximated security strategy depending on the sufficient statistics is provided, and an explicit linear program to compute the approximated security strategy is given. This paper also obtains a bound on the performance difference between the approximated security strategy and the security strategy, and shows that the bound converges to 0 exponentially fast. [ABSTRACT FROM AUTHOR]

This paper investigates the impact of quantized inter-agent communications on the asymptotic and transient behavior of gradient-based Nash-seeking algorithms in non-cooperative games. Using the information-theoretic notion of entropy power, we establish a universal lower bound on the asymptotic rate of exponential mean-square convergence to the Nash equilibrium (NE). This bound depends on the inter-agent data rate and the local behavior of the agents' utility functions, and is independent of the quantizer structure. Next, we study transient performance and derive an upper bound on the average time required to settle inside a specified ball around the NE, under uniform quantization. Furthermore, we establish an upper bound on the probability that agents' actions lie outside this ball, and show that this bound decays double-exponentially with time. Finally, we propose an adaptive quantization scheme that allows the gradient algorithm to converge to the NE despite quantized inter-agent communications. [ABSTRACT FROM AUTHOR]

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behavior. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this paper, we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behavior over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori. [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]

This paper is concerned with a scenario of active target defense modeled as a zero-sum differential game. The differential game theory as developed by Isaacs provides the correct framework for the analysis of pursuit-evasion conflicts and the design of optimal strategies for the players involved in the game. This paper considers an Attacker missile pursuing a Target aircraft protected by a Defender missile which aims at intercepting the Attacker before the latter reaches the Target aircraft. A differential game is formulated where the two opposing players/teams try to minimize/maximize the distance between the Target and the Attacker at the time of interception of the Attacker by the Defender and such time indicates the termination of the game. The Attacker aims to minimize the terminal distance between itself and the Target at the moment of its interception by the Defender. The opposing player/team consists of two cooperating agents: The Target and the Defender. These two agents cooperate in order to accomplish the two objectives: Guarantee interception of the Attacker by the Defender and maximize the terminal Target-Attacker separation. In this paper, we provide a complete, closed form solution of the active target defense differential game; we synthesize closed-loop state feedback optimal strategies for the agents and obtain the Value function of the game. We characterize the Target's escape set and show that the Value function is continuous and continuously differentiable over the Target's escape set, and that it satisfies the Hamilton–Jacobi–Isaacs equation everywhere in this set. [ABSTRACT FROM AUTHOR]

An introduction to a number of research papers within the issue is presented on topics including optimal dynamic quantizer for nonlinear control systems, robust control in experimental design and synchronization of nonlinear oscillators.

The note considers the problem of computing pure Nash equilibrium (NE) strategies in distributed (i.e., network-based) settings. The paper studies a class of inertial best-response dynamics based on the fictitious play (FP) algorithm. It is shown that inertial best-response dynamics are robust to informational limitations common in distributed settings. Fully distributed variants of FP with inertia and joint strategy FP (JSFP) with inertia are developed and convergence is proven to the set of pure NE. The distributed algorithms developed in the paper rely on consensus methods. Results are validated using numerical simulations. [ABSTRACT FROM AUTHOR]

In this paper, a security problem in networked control systems (NCS) is studied. In a standard linear quadratic Gaussian (LQG) control scenario in NCS, a so-called false data injection attack could be launched by a malicious attacker to deteriorate the system performance without being detected. To defend against such attacks, a defender on the NCS side needs to allocate defense resources among the sensors to secure the data, and the defense investment determines the costs of compromising certain sensors. After observing the defender’ action, the attacker decides the target sensors to compromise. While both sides are subject to the resource constraints, the interactive decision-making between the defender and the attacker is investigated in a Stackelberg game (leader–follower game) framework. The optimal solutions for both sides under different types of budget constraints are analyzed. Simulation examples are provided to illustrate the main results. [ABSTRACT FROM AUTHOR]

In a hierarchical Stackelberg v/s Stackelberg game, a collection of players called leaders play a Nash game constrained by the equilibrium conditions of a distinct Nash game played amongst another set of players, called followers. Generically, follower equilibria are non-unique as a function of leader strategies and the decision problems of leaders are highly nonconvex and lacking in standard regularity conditions. Consequently, the provision of sufficient conditions for the existence of global or even local equilibria remains a largely open question. In this paper, we present what is possibly the first general existence result for equilibria for this class of games. Importantly, we impose no single-valuedness assumption on the equilibrium of the follower-level game. Specifically, under the assumption that the objectives of the leaders admit a quasi-potential function, a notion introduced in this paper, the global and local minimizers of a suitably defined optimization problem are shown to be the global and local equilibria of the game. In effect, existence of equilibria can be guaranteed by the solvability of an optimization problem which holds under mild conditions. We motivate quasi-potential games through an application in communication networks. [ABSTRACT FROM PUBLISHER]

This paper considers the optimal decentralized control of linear systems with stochastically switched cost and system matrices depending on local parameters. Two types of dynamic switched problems are considered, with partially nested and one-step delayed sharing information structures. For the former case, parameters and measurements follow a partially nested structure with the parameters possibly being correlated across all stages. For the latter case, parameters are assumed to be Markov processes, with their values along with measurements available instantaneously to local controllers, but with a one time step delay to others. The solution to both these problems rely on the optimal solution to a static (one-stage) stochastic-parameter problem with local type dependent Gaussian measurements, and for this purpose the static quadratic team problem is examined in some generality. Using an operator theoretic framework, it is shown that the sequential update scheme always converges to the team optimal strategy for general static quadratic team setups. This, when applied to the static stochastic-parameter problem, yields the team optimal strategy. The corresponding strategy is affine in the measurements with the parameter dependent coefficients obtained by solving a set of linear equations. These equations are immediately solvable when the total number of parameter values is finite. However, for the case of infinite parameter values, the update scheme also provides a mechanism to determine an approximation to the team optimal strategy. [ABSTRACT FROM PUBLISHER]

In this paper, a class of infinite-horizon, nonzero-sum differential games and their Nash equilibria are studied and the notion of \epsilon\alpha -Nash equilibrium strategies is introduced. Dynamic strategies satisfying partial differential inequalities in place of the Hamilton–Jacobi–Isaacs partial differential equations associated with the differential games are constructed. These strategies constitute (local) \epsilon\alpha -Nash equilibrium strategies for the differential game. The proposed methods are illustrated on a differential game for which the Nash equilibrium strategies are known and on a Lotka–Volterra model, with two competing species. Simulations indicate that both dynamic strategies yield better performance than the strategies resulting from the solution of the linear-quadratic approximation of the problem. [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]

Game theory is emerging as a popular tool for distributed control of multiagent systems. To take advantage of these game theoretic tools, the interactions of the autonomous agents must be designed within a game-theoretic environment. A central component of this game-theoretic design is the assignment of a local utility function to each agent. One promising approach to utility design is assigning each agent a utility function according to the agent's Shapley value. This method frequently results in games that possess many desirable features, such as the existence of pure Nash equilibria with near-optimal efficiency. In this paper, we explore the relationship between the Shapley value utility design and the resulting efficiency of both pure Nash equilibria and coarse correlated equilibria. To study this relationship, we introduce a simple class of resource allocation problems. Within this class, we derive an explicit relationship between the structure of the resource allocation problem and the efficiency of the resulting equilibria. Lastly, we derive a bicriteria bound for this class of resource allocation problems—a bound on the value of the optimal allocation relative to the value of an equilibrium allocation with additional agents. [ABSTRACT FROM AUTHOR]

This technical note studies a resilient control problem for discrete-time, linear time-invariant systems subject to state and input constraints. State measurements and control commands are transmitted over a communication network and could be corrupted by adversaries. In particular, we consider the replay attackers who maliciously repeat the messages sent from the operator to the actuator. We propose a variation of the receding-horizon control law to deal with the replay attacks and analyze the resulting system performance degradation. A class of competitive (resp. cooperative) resource allocation problems for resilient networked control systems is also investigated. [ABSTRACT FROM AUTHOR]

There are only a few learning algorithms applicable to stochastic dynamic teams and games which generalize Markov decision processes to decentralized stochastic control problems involving possibly self-interested decision makers. Learning in games is generally difficult because of the non-stationary environment in which each decision maker aims to learn its optimal decisions with minimal information in the presence of the other decision makers who are also learning. In stochastic dynamic games, learning is more challenging because, while learning, the decision makers alter the state of the system and hence the future cost. In this paper, we present decentralized Q-learning algorithms for stochastic games, and study their convergence for the weakly acyclic case which includes team problems as an important special case. The algorithms are decentralized in that each decision maker has access only to its own decisions and cost realizations as well as the state transitions; in particular, each decision maker is completely oblivious to the presence of the other decision makers. We show that these algorithms converge to equilibrium policies almost surely in large classes of stochastic games. [ABSTRACT FROM AUTHOR]

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]

This paper studies the decentralized quadratic cheap talk and signaling game problems when an encoder and a decoder, viewed as two decision makers, have misaligned objective functions. The main contributions of this study are the extension of Crawford and Sobel's cheap talk formulation to multi-dimensional sources and to noisy channel setups. We consider both (simultaneous) Nash equilibria and (sequential) Stackelberg equilibria. We show that for arbitrary scalar sources, in the presence of misalignment, the quantized nature of all equilibrium policies holds for Nash equilibria in the sense that all Nash equilibria are equivalent to those achieved by quantized encoder policies. On the other hand, all Stackelberg equilibria policies are fully informative. For multi-dimensional setups, unlike the scalar case, Nash equilibrium policies may be of non-quantized nature, and even linear. In the noisy setup, a Gaussian source is to be transmitted over an additive Gaussian channel. The goals of the encoder and the decoder are misaligned by a bias term and encoder's cost also includes a penalty term on signal power. Conditions for the existence of affine Nash equilibria as well as general informative equilibria are presented. For the noisy setup, the only Stackelberg equilibrium is the linear equilibrium when the variables are scalar. Our findings provide further conditions on when affine policies may be optimal in decentralized multi-criteria control problems and lead to conditions for the presence of active information transmission in strategic environments. [ABSTRACT FROM PUBLISHER]

This paper is motivated by the desire to develop optimal defensive control strategies that discourage an attacker from engaging in attack while simultaneously encouraging retreat. We develop a general, two-player, differential game in which one player represents an attacker and the opposing player represents the defender. The attacker possesses superior dynamics such that it is capable of terminating the game either in engagement or retreat as it so chooses. The defender is incapable of directly preventing engagement. Instead, the defender uses the manipulation of the attacker’s utility function as a form of indirect control in an attempt to make retreat a more attractive option over engagement. The solution to the overall engage or retreat differential game is found by solving two related optimization problems: the differential game of engagement and the optimal constrained retreat. The equilibrium open-loop control strategies and resulting game values of the attack or retreat game are expressed in terms of the solutions to these subproblems. Within the optimal constrained retreat problem, a value function constraint is imposed in order to prevent the attacker from moving into regions where engagement becomes optimal. This leads to regions of constrained retreat which we refer to as escort regions. [ABSTRACT FROM PUBLISHER]

In this paper, we consider a class of noncooperative $N$- player finite-horizon linear-quadratic dynamic games with linear constraints. We introduce a constrained feedback information structure and provide necessary and sufficient conditions for the existence of a constrained feedback Nash equilibrium. For this class of games we show that the constrained feedback Nash equilibrium can be obtained from a feedback Nash equilibrium associated with an unconstrained multi-parametric linear-quadratic game where the parameters satisfy an equilibrium property. We show that this relation leads to a fixed-point interpretation. Further, under a few additional assumptions, we show that these fixed points can be obtained as solutions of a single large-scale linear-complementarity problem, thereby providing a method to compute the constrained feedback Nash equilibria. We illustrate our results with a numerical example. [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]

In this paper, the finite-horizon and the infinite-horizon indefinite mean-field stochastic linear-quadratic optimal control problems are studied. Firstly, the open-loop optimal control and the closed-loop optimal strategy for the finite-horizon problem are introduced, and their characterizations, difference and relationship are thoroughly investigated. The open-loop optimal control can be defined for a fixed initial state, whose existence is characterized via the solvability of a linear mean-field forward-backward stochastic difference equation with stationary conditions and a convexity condition. On the other hand, the existence of a closed-loop optimal strategy is shown to be equivalent to any one of the following conditions: the solvability of a couple of generalized difference Riccati equations, the finiteness of the value function for all the initial pairs, and the existence of the open-loop optimal control for all the initial pairs. It is then proved that the solution of the generalized difference Riccati equations converges to a solution of a couple of generalized algebraic Riccati equations. By studying another generalized algebraic Riccati equation, the existence of the maximal solution of the original ones is obtained together with the fact that the stabilizing solution is the maximal solution. Finally, we show that the maximal solution is employed to express the optimal value of the infinite-horizon indefinite mean-field linear-quadratic optimal control. Furthermore, for the question whether the maximal solution is the stabilizing solution, the necessary and the sufficient conditions are presented for several cases. [ABSTRACT FROM PUBLISHER]

In this paper, we investigate a distributed Nash equilibrium computation problem for a time-varying multi-agent network consisting of two subnetworks, where the two subnetworks share the same objective function. We first propose a subgradient-based distributed algorithm with heterogeneous stepsizes to compute a Nash equilibrium of a zero-sum game. We then prove that the proposed algorithm can achieve a Nash equilibrium under uniformly jointly strongly connected (UJSC) weight-balanced digraphs with homogenous stepsizes. Moreover, we demonstrate that for weighted-unbalanced graphs a Nash equilibrium may not be achieved with homogenous stepsizes unless certain conditions on the objective function hold. We show that there always exist heterogeneous stepsizes for the proposed algorithm to guarantee that a Nash equilibrium can be achieved for UJSC digraphs. Finally, in two standard weight-unbalanced cases, we verify the convergence to a Nash equilibrium by adaptively updating the stepsizes along with the arc weights in the proposed algorithm. [ABSTRACT FROM AUTHOR]

We consider a sequence of transferable utility (TU) games where, at each time, the characteristic function is a random vector with realizations restricted to some set of values. The first part of the paper contributes to the definition of a robust (coalitional) TU game and the development of a distributed bargaining protocol. We prove the convergence with probability 1 of the bargaining process to a random allocation that lies in the core of the robust game under some mild conditions on the underlying communication graphs. The second part of the paper addresses the more general case where the robust game may have empty core. In this case, with the dynamic game we associate a dynamic average game by averaging over time the sequence of characteristic functions. Then, we consider an accordingly modified bargaining protocol. Assuming that the sequence of characteristic functions is ergodic and the core of the average game has a nonempty relative interior, we show that the modified bargaining protocol converges with probability 1 to a random allocation that lies in the core of the average game. [ABSTRACT FROM AUTHOR]

Zero-sum asymmetric information games model decision-making scenarios involving two competing players who have different information about the game being played. A particular case is that of nested information, where one (informed) player has superior information over the other (uninformed) player. This paper considers the case of nested information in repeated zero-sum games and studies the computation of strategies for both the informed and uninformed players for finite-horizon and discounted infinite-horizon nested information games. For finite-horizon settings, we exploit that for both players, the security strategy, and also the opponent's corresponding best response, depend only on the informed player's history of actions. Using this property, we formulate an linear program (LP) computation of player strategies that is linear in the size of the uninformed player's action set. For the infinite-horizon discounted game, we construct LP formulations to compute the approximated security strategies for both players, and show that the worst-case performance difference between the approximated security strategies and the security strategies converges to zero exponentially. Finally, we illustrate the results on a network interdiction game between an informed system administrator and an uniformed intruder. [ABSTRACT FROM AUTHOR]

In this paper, the multiagent pursuit-evasion (MPE) games are solved in order to obtain optimal strategic policies for all players. In these games, multiple pursuers attempt to intercept multiple evaders who try to avoid capture. A graph-theoretic approach is employed to study the interactions of the agents with limited sensing capabilities, such that distributed control policies are obtained for every agent. Furthermore, the minimization of performance indices associated with the goals of the agents is guaranteed. Nash equilibrium among the players is obtained by means of optimal policies that use the solutions of the Hamilton–Jacobi–Isaacs (HJI) equations of the game. Minmax strategies are also proposed to guarantee a security-level performance when the solutions of the HJI equations for Nash equilibrium do not exist. Scenarios for finite-time capture and for asymptotic rendezvous are analyzed, and emergent behaviors are obtained by means of modifications of the proposed general-case performance indices. The containment control results are shown to be special cases of the solutions of the MPE games. [ABSTRACT FROM AUTHOR]

We consider distributed computation of generalized Nash equilibrium (GNE) over networks, in games with shared coupling constraints. Existing methods require that each player has full access to opponents’ decisions. In this paper, we assume that players have only partial-decision information, and can communicate with their neighbors over an arbitrary undirected graph. We recast the problem as that of finding a zero of a sum of monotone operators through primal-dual analysis. To distribute the problem, we doubly augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We introduce a single-layer algorithm, fully distributed with respect to both primal and dual variables. We show its convergence to a variational GNE with fixed step sizes, by reformulating it as a forward–backward iteration for a pair of doubly-augmented monotone operators. [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]

This paper is devoted to the characterization of existence and uniqueness conditions for the stabilizing solution of a large class of Riccati equations arising in stochastic dynamic games. As an application of the obtained results, we consider in a second step the problem of a zero-sum two players linear quadratic difference game for a stochastic discrete-time dynamical system subject to both random switching of its coefficients and multiplicative noise. We show that in the solution of such a control problem, a crucial role is played by the stabilizing solution of the considered class of Riccati difference equations. [ABSTRACT FROM AUTHOR]

In this paper, we study a linear–quadratic mean-field-type game problem under jump–diffusion–regime switching state dynamics that include mean-field terms in the states and in the cost function. In the cost functional, we consider conditional variance of both the states and control actions, mean of both states and control actions, and covariance terms. The underlying problem is solved in a semiexplicit way by using the direct method. [ABSTRACT FROM AUTHOR]

The article presents summaries of various research papers published in the issue. The paper "Nonlinear Stabilization Under Sampled and Delayed Measurements, and with Inputs Subject to Delay and Zero-Order Hold," by I. Karafyllis and M. Krstic deals with the stabilization of nonlinear systems. Another paper "A Beamlet-Based Graph Structure for Path Planning Using Multiscale Information," by Y. Lu and team addresses the problem of computing the single pair shortest path on a given graph.

We study price competition among primaries in a Cognitive Radio Network (CRN) with multiple primaries and secondaries located in a large region. In every slot, each primary has unused bandwidth with some probability, which may be different for different primaries. Also, there may be a random number of secondaries. A primary can lease out its unused bandwidth to a secondary in exchange for a fee. Each primary tries to attract secondaries by setting a lower price for its bandwidth than the other primaries. Radio spectrum has the distinctive feature that transmissions at neighboring locations on the same channel interfere with each other, whereas the same channel can be used at far-off locations without mutual interference. So in the above price competition scenario, each primary must jointly select a set of mutually non-interfering locations within the region (which corresponds to an independent set in the conflict graph representing the region) at which to offer bandwidth and the price at each location. In this paper, we analyze this price competition scenario as a game and seek a Nash Equilibrium (NE). For the game at a single location, we explicitly compute a NE and prove its uniqueness. Also, for the game at multiple locations, we identify a class of conflict graphs, which we refer to as mean valid graphs, such that the conflict graphs of a large number of topologies that commonly arise in practice are mean valid. We explicitly compute a NE in mean valid graphs and show that it is unique in the class of NE with symmetric independent set selection strategies of the primaries. [ABSTRACT FROM PUBLISHER]

We study battery filling policies with hard deadlines when the supply of energy can be modulated. This occurs for example with an electric plug-in vehicle using an adjustable electricity service for charging; such a service is offered in some countries as a means to provide flexibility to operators, and typically involves non-scheduled service reductions combined with a service guarantee that constrains these reductions. The problem for the battery user is to determine a charging policy, which we call a “consumption policy,” that meets a given “full battery” deadline while minimizing the energy cost (i.e., the bill paid to the electricity provider). As the charging efficiency is diminishing with respect to consumption, it is not optimal to charge as much and as early as possible. On the other hand service reductions cannot be predicted but it is possible to gain some information on the worst case reduction by analyzing past reductions. In this context, the computation of a causal consumption policy is an open problem. In this paper we consider a battery user interested in charging her battery while minimizing the worst case cost, where the total cost is a sum of two terms that reflect ( i) the total energy consumption and ( ii) the distance to a full battery at the deadline. We prove that there exists a causal consumption policy that minimizes the worst-case cost of the user. We find that the policy is threshold-based and give an efficient method to explicitly compute it at any time based solely on knowledge of past reductions, of the service guarantees and on the current distance to completion. Our method is based on the use of service curves and game theory. [ABSTRACT FROM PUBLISHER]

This paper is concerned with the first passage discounted payoff criterion for continuous-time $N$ -person nonzero-sum stochastic games in countable states and Borel action spaces, where the discount factor is nonconstant. For the game with unbounded reward functions and transition rates, the optimality is over the set of all randomized history-dependent policies. After showing the uniqueness of the solution to the Shapley equation, we give some suitable conditions imposed on the primitive data for the existence of Nash equilibria. Then, a financial system is introduced to illustrate the applications of the main result here. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of distributed Nash equilibrium (NE) seeking over networks, a setting in which players have limited local information on the others’ decisions. We start from a continuous-time gradient-play dynamics that converges to an NE under strict monotonicity of the pseudogradient and assumes perfect information. We consider how to modify it in the case of partial, or networked information between players. We propose an augmented gradient-play dynamics with correction, in which players communicate locally only with their neighbors to compute an estimate of the other players’ actions. We derive the new dynamics based on the reformulation as a multiagent coordination problem over an undirected graph. We exploit incremental passivity properties and show that a synchronizing, distributed Laplacian feedback can be designed using relative estimates of the neighbors. Under a strict monotonicity property of the pseudogradient, we show that the augmented gradient-play dynamics converges to consensus on the NE of the game. We further discuss two cases that highlight the tradeoff between properties of the game and the communication graph. [ABSTRACT FROM AUTHOR]

This paper is concerned with the open-loop linear–quadratic (LQ) Stackelberg game of the mean-field stochastic systems in finite horizon. By means of two generalized differential Riccati equations, the follower first solves a mean-field stochastic LQ optimal control problem. Then, the leader turns to solve an optimization problem for a linear mean-field forward–backward stochastic differential equation. By introducing new state and costate variables, we present a sufficient condition for the existence and uniqueness of the Stackelberg strategy in terms of the solvability of some Riccati equations and a convexity condition. Furthermore, it is shown that the open-loop Stackelberg equilibrium admits a feedback representation involving the new state and its mean. Finally, two examples are given to show the effectiveness of the proposed results. [ABSTRACT FROM AUTHOR]