Interdependent Defense Games: Modeling Interdependent Security under Deliberate Attacks
This work addresses security modeling for multi-agent systems under deliberate attacks, but it is incremental as it builds upon existing interdependent security games.
The authors tackled the problem of modeling interdependent security in multi-agent systems under deliberate attacks by proposing interdependent defense (IDD) games, a computational game-theoretic framework, and they provided a complete characterization of mixed-strategy Nash equilibria with a polynomial-time algorithm for a subclass, along with empirical results on a real-world Internet-derived graph.
We propose interdependent defense (IDD) games, a computational game-theoretic framework to study aspects of the interdependence of risk and security in multi-agent systems under deliberate external attacks. Our model builds upon interdependent security (IDS) games, a model due to Heal and Kunreuther that considers the source of the risk to be the result of a fixed randomizedstrategy. We adapt IDS games to model the attacker's deliberate behavior. We define the attacker's pure-strategy space and utility function and derive appropriate cost functions for the defenders. We provide a complete characterization of mixed-strategy Nash equilibria (MSNE), and design a simple polynomial-time algorithm for computing all of them, for an important subclass of IDD games. In addition, we propose a randominstance generator of (general) IDD games based on a version of the real-world Internet-derived Autonomous Systems (AS) graph (with around 27K nodes and 100K edges), and present promising empirical results using a simple learning heuristics to compute (approximate) MSNE in such games.