Interdependent Defense Games with Applications to Internet Security at the Level of Autonomous Systems

Hau Chan, Michael Ceyko and Luis Ortiz
Additional contact information
Hau Chan: Department of Computer Science, Trinity University, San Antonio, TX 78212, USA
Michael Ceyko: Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA
Luis Ortiz: Department of Computer and Information Science, University of Michigan-Dearborn, Dearborn, MI 48128, USA

Games, 2017, vol. 8, issue 1, 1-60

Abstract: 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 by Heal and Kunreuther that considers the source of the risk to be the result of a fixed randomized-strategy . 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. We also show that an efficient algorithm to determine whether some attacker’s strategy can be a part of an MSNE in an instance of IDD games is unlikely to exist. Yet, we provide a dynamic programming ( DP ) algorithm to compute an approximate MSNE when the graph/network structure of the game is a directed tree with a single source. We also show that the DP algorithm is a fully polynomial-time approximation scheme . In addition, we propose a generator of random instances of IDD games based on the real-world Internet-derived graph at the level of autonomous systems (?27 K nodes and ?100 K edges as measured in March 2010 by the DIMES project). We call such games Internet games. We introduce and empirically evaluate two heuristics from the literature on learning-in-games, best-response gradient dynamics ( BRGD ) and smooth best-response dynamics ( SBRD ), to compute an approximate MSNE in IDD games with arbitrary graph structures, such as randomly-generated instances of Internet games. In general, preliminary experiments applying our proposed heuristics are promising. Our experiments show that, while BRGD is a useful technique for the case of Internet games up to certain approximation level, SBRD is more efficient and provides better approximations than BRGD. Finally, we discuss several extensions, future work, and open problems.

Keywords: computational game theory; interdependent security; equilibrium computation; equilibrium characterization; fully polynomial-time approximation scheme; learning in games; autonomous-systems internet security application (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/8/1/13/pdf (application/pdf)
https://www.mdpi.com/2073-4336/8/1/13/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:8:y:2017:i:1:p:13-:d:90557

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().