FlipDyn in Graphs: Resource Takeover Games in Graphs

We present $\mathtt{\text{FlipDyn-G}}$, a dynamic game model extending the $\mathtt{\text{FlipDyn}}$ framework to a graph-based setting, where each node represents a dynamical system. This model captures the interactions between a defender and an adversary who strategically take over nodes in a graph to minimize (resp. maximize) a finite horizon additive cost. At any time, the $\mathtt{\text{FlipDyn}}$ state is represented as the current node, and each player can transition the $\mathtt{\text{FlipDyn}}$ state to a depending based on the connectivity from the current node. Such transitions are driven by the node dynamics, state, and node-dependent costs. This model results in a hybrid dynamical system where the discrete state ($\mathtt{\text{FlipDyn}}$ state) governs the continuous state evolution and the corresponding state cost. Our objective is to compute the Nash equilibrium of this finite horizon zero-sum game on a graph. Our contributions are two-fold. First, we model and characterize the $\mathtt{\text{FlipDyn-G}}$ game for general dynamical systems, along with the corresponding Nash equilibrium (NE) takeover strategies. Second, for scalar linear discrete-time dynamical systems with quadratic costs, we derive the NE takeover strategies and saddle-point values independent of the continuous state of the system. Additionally, for a finite state birth-death Markov chain (represented as a graph) under scalar linear dynamical systems, we derive analytical expressions for the NE takeover strategies and saddle-point values. We illustrate our findings through numerical studies involving epidemic models and linear dynamical systems with adversarial interactions.