FlipDyn in Graphs: Resource Takeover Games in Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917703500955648 |
|---|---|
| author | Banik, Sandeep Bopardikar, Shaunak D. Hovakimyan, Naira |
| author_facet | Banik, Sandeep Bopardikar, Shaunak D. Hovakimyan, Naira |
| contents | We present \texttt{FlipDyn-G}, a dynamic game model extending the \texttt{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 \texttt{FlipDyn} state is represented as the current node, and each player can transition the \texttt{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 (\texttt{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 \texttt{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16812 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | FlipDyn in Graphs: Resource Takeover Games in Graphs Banik, Sandeep Bopardikar, Shaunak D. Hovakimyan, Naira Computer Science and Game Theory We present \texttt{FlipDyn-G}, a dynamic game model extending the \texttt{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 \texttt{FlipDyn} state is represented as the current node, and each player can transition the \texttt{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 (\texttt{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 \texttt{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. |
| title | FlipDyn in Graphs: Resource Takeover Games in Graphs |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2406.16812 |