Multiplayer Pursuit-Evasion Games in Three-Dimensional Flow Fields Unfortunately, the acknowledgement text was not submitted during the acceptance of the manuscript.

Preface to the Focused Issue on Dynamic Games in Cyber Security

Iterative Computation of Security Strategies of Matrix Games with Growing Action Set Abstract This paper studies how to efficiently update the saddle-point strategy, or security strategy of one player in a matrix game when the other player develops new actions in the game. It is well known that the saddle-point strategy of one player can be computed by solving a linear program. Developing a new action will add a new constraint to the existing LP. Therefore, our problem becomes how to efficiently solve the new LP with a new constraint. Considering the potentially huge number of constraints, which corresponds to the large size of the other player’s action set, we use the shadow vertex simplex method, whose computational complexity is lower than linear with respect to the size of the constraints, as the basis of our iterative algorithm. We first rebuild the main theorems in the shadow vertex method with a relaxed non-degeneracy assumption to make sure such a method works well in our model, then analyze the probability that the old optimum remains optimal in the new LP, and finally provide the iterative shadow vertex method whose average computational complexity is shown to be strictly less than that of the shadow vertex method. The simulation results demonstrate our main results about the probability of re-computing the optimum and the computational complexity of the iterative shadow vertex method.

Risk-Sensitive Mean Field Games via the Stochastic Maximum Principle Abstract In this paper, we consider risk-sensitive mean field games via the risk-sensitive maximum principle. The problem is analyzed through two sequential steps: (i) risk-sensitive optimal control for a fixed probability measure, and (ii) the associated fixed-point problem. For step (i), we use the risk-sensitive maximum principle to obtain the optimal solution, which is characterized in terms of the associated forward–backward stochastic differential equation (FBSDE). In step (ii), we solve for the probability law induced by the state process with the optimal control in step (i). In particular, we show the existence of the fixed point of the probability law of the state process determined by step (i) via Schauder’s fixed-point theorem. After analyzing steps (i) and (ii), we prove that the set of N optimal distributed controls obtained from steps (i) and (ii) constitutes an approximate Nash equilibrium or \(\epsilon \)-Nash equilibrium for the N player risk-sensitive game, where \(\epsilon \rightarrow 0\) as \(N \rightarrow \infty \) at the rate of \(O(\frac{1}{N^{1/(n+4)}})\). Finally, we discuss extensions to heterogeneous (non-symmetric) risk-sensitive mean field games.

Zero-Sum Stochastic Games over the Field of Real Algebraic Numbers Abstract We consider a finite state, finite action, zero-sum stochastic games with data defining the game lying in the ordered field of real algebraic numbers. In both the discounted and the limiting average versions of these games, we prove that the value vector also lies in the same field of real algebraic numbers. Our method supplies finite construction of univariate polynomials whose roots contain these value vectors. In the case where the data of the game are rational, the method also provides a way of checking whether the entries of the value vectors are also rational.

Climb on the Bandwagon: Consensus and Periodicity in a Lifetime Utility Model with Strategic Interactions Abstract What is the emergent long-run equilibrium of a society, where many interacting agents bet on the optimal energy to put in place in order to climb on the Bandwagon? In this paper, we study the collective behavior of a large population of agents being either Left or Right: The core idea is that agents benefit from being with the winner party, but, on the other hand, they suffer a cost in changing their status quo. At the microscopic level, the model is formulated as a stochastic, symmetric dynamic game with N players. In the macroscopic limit as \(N \rightarrow +\,\infty \), the model can be rephrased as a mean field game, whose equilibria describe the “rational” collective behavior of the society. It is of particular interest to detect the emerging long time attractors, e.g., consensus or oscillating behavior. Significantly, we discover that bandwagoning can be persistent at the macrolevel: We provide evidence, also on the basis of numerical simulations, of endogenously generated periodicity.

An Efficient Dynamic Allocation Mechanism for Security in Networks of Interdependent Strategic Agents Abstract Motivated by security issues in networks, we study the problem of incentive mechanism design for dynamic resource allocation in a multi-agent networked system. Each strategic agent has a private security state which can be safe or unsafe and is only known to him. At every time, each agent faces security threats from outside as well as from his unsafe neighbors. Therefore, the agents’ states are correlated and have interdependent stochastic dynamics. Agents have interdependent valuations, as each agent’s instantaneous utility depends on his own security state as well as his neighbors’ security states. There is a network manager that can allocate a security resource to one agent at each time so as to protect the network against attacks and maximize the overall social welfare. We propose a dynamic incentive mechanism that implements the efficient allocation and is ex-ante (in expectation) individually rational and budget balanced. We present a reputation-based payment that mitigates any risk that the agents or the network manager may face to get a negative utility or to run a budget deficit, respectively, for some realizations of the network stochastic evolution. Therefore, our results provide a dynamic incentive mechanism that implements efficient allocations in networked systems with strategic agents that have correlated types and interdependent valuations, and is approximate ex-post individually rational and budget balanced.

Dynamic Games in Cyber-Physical Security: An Overview Abstract Due to complex dependencies between multiple layers and components of emerging cyber-physical systems, security and vulnerability of such systems have become a major challenge in recent years. In this regard, game theory, a powerful tool for modeling strategic interactions between multiple decision makers with conflicting objectives, offers a natural paradigm to address the security-related issues arising in these systems. While there exists substantial amount of work in modeling and analyzing security problems using game-theoretic techniques, most of the existing literature in this area focuses on static game models, ignoring the dynamic nature of interactions between the main players (defenders vs. attackers). In this paper, we focus only on dynamic game analysis of cyber-physical security problems and provide a general overview of the existing results and recent advances based on application domains. We also discuss several limitations of the existing models and identify several hitherto unaddressed directions for future research.

Dynamic Exploitation of Myopic Best Response Abstract How can a rational player manipulate a myopic best response player in a repeated two-player game? We show that in games with strategic substitutes or strategic complements the optimal control strategy is monotone in the initial action of the opponent, in time periods, and in the discount rate. As an interesting example outside this class of games we present a repeated “textbook-like” Cournot duopoly with nonnegative prices and show that the optimal control strategy involves a cycle.

Multiplayer Pursuit-Evasion Games in Three-Dimensional Flow Fields Abstract In this paper, we deal with a pursuit-evasion differential game between multiple pursuers and multiple evaders in the three-dimensional space under dynamic environmental disturbances (e.g., winds, underwater currents). We first recast the problem in terms of partitioning the pursuer set and assign each pursuer to an evader. We present two algorithms to partition the pursuer set from either the pursuer’s perspective or the evader’s perspective. Within each partition, the problem is reduced into a multi-pursuer/single-evader game. This problem is then addressed through a reachability-based approach. We give conditions for the game to terminate in terms of reachable set inclusions. The reachable sets of the pursuers and the evader are obtained by solving their corresponding level set equations through the narrow band level set method. We further demonstrate why fast marching or fast sweeping schemes are not applicable to this problem for a general class of disturbances. The time-optimal trajectories and the corresponding optimal strategies can be retrieved afterward by traversing these level sets. The proposed scheme is implemented on problems with both simple and realistic flow fields.