{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:11:18Z","timestamp":1760242278159,"version":"build-2065373602"},"reference-count":60,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2017,2,16]],"date-time":"2017-02-16T00:00:00Z","timestamp":1487203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>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\u2019s deliberate behavior. We define the attacker\u2019s 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\u2019s 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 (\u224827 K nodes and \u2248100 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.<\/jats:p>","DOI":"10.3390\/g8010013","type":"journal-article","created":{"date-parts":[[2017,2,16]],"date-time":"2017-02-16T12:55:34Z","timestamp":1487249734000},"page":"13","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Interdependent Defense Games with Applications to Internet Security at the Level of Autonomous Systems"],"prefix":"10.3390","volume":"8","author":[{"given":"Hau","family":"Chan","sequence":"first","affiliation":[{"name":"Department of Computer Science, Trinity University, San Antonio, TX 78212, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Ceyko","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA"},{"name":"Tumblr, 35 E 21 Street, Ground Floor, New York, NY 10010, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0330-3069","authenticated-orcid":false,"given":"Luis","family":"Ortiz","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, University of Michigan-Dearborn, Dearborn, MI 48128, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,2,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Bier, V.M., and Azaiez, M.N. (2009). Game Theoretic Risk Analysis of Security Threats, Springer.","DOI":"10.1007\/978-0-387-87767-9"},{"key":"ref_2","first-page":"49","article-title":"A Strategic Analysis of the War against Transnational Terrorism","volume":"7","author":"Tauman","year":"2011","journal-title":"Games Eco. Behav."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1023\/A:1024119208153","article-title":"Interdependent Security","volume":"26","author":"Kunreuther","year":"2003","journal-title":"J. Risk Uncertain."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1177\/0022002704272833","article-title":"IDS Models of Airline Security","volume":"49","author":"Heal","year":"2005","journal-title":"J. Confl. Resolut."},{"key":"ref_5","unstructured":"O\u2019Connor, A., and Schmitt, E. Terror Attempt Seen as Man Tries to Ignite Device on Jet. Available online: http:\/\/www.nytimes.com\/2009\/12\/26\/us\/26plane.html."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s12198-010-0047-y","article-title":"Container transportation as an interdependent security problem","volume":"3","author":"Gkonis","year":"2010","journal-title":"J. Transp. Secur."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Johnson, B., Grossklags, J., Christin, N., and Chuang, J. (2010, January 22\u201323). Uncertainty in Interdependent Security Games. Proceedings of the First International Conference on Decision and Game Theory for Security, GameSec\u201910, Berlin, Germany.","DOI":"10.1007\/978-3-642-17197-0_16"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Dingledine, R., and Golle, P. (2009). Financial Cryptography and Data Security, Springer.","DOI":"10.1007\/978-3-642-03549-4"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Roy, S., Ellis, C., Shiva, S., Dasgupta, D., Shandilya, V., and Wu, Q. (2010, January 5\u20138). A Survey of Game Theory as Applied to Network Security. Proceedings of the 2010 43rd Hawaii International Conference on System Sciences, HICSS \u201910, Honolulu, HI, USA.","DOI":"10.1109\/HICSS.2010.35"},{"key":"ref_10","unstructured":"Syverson, P.F., and Systems, A.C. (1997, January 10\u201312). A Different Look at Secure Distributed Computation. Proceedings of the CSFW-10, Rockport, MA, USA."},{"key":"ref_11","unstructured":"Lye, K.W., and Wing, J. (2002, January 24\u201326). Game Strategies in Network Security. Proceedings of the Workshop on Foundations of Computer Security, Cape Breton, NS, Canada."},{"key":"ref_12","unstructured":"Jain, M., Korzhyky, D., Vanek, O., Conitzery, V., Pechoucek, M., and Tambe, M. (2011, January 2\u20136). A Double Oracle Algorithm for Zero-Sum Security Games on Graphs. Proceedings of the AAMAS, Taipei, Taiwan."},{"key":"ref_13","unstructured":"Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ord\u00f3\u00f1ez, F., and Tambe, M. (2009, January 10\u201315). Computing Optimal Randomized Resource Allocations for Massive Security Games. Proceedings of the AAMAS, Budapest, Hungary."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Korzhyk, D., Conitzer, V., and Parr, R. (2010, January 11\u201315). Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games. Proceedings of the AAAI, Atlanta, GA, USA.","DOI":"10.1609\/aaai.v24i1.7638"},{"key":"ref_15","unstructured":"Korzhyk, D., Conitzer, V., and Parr, R. (2011, January 16\u201322). Security Games with Multiple Attacker Resources. Proceedings of the IJCAI, Catalonia, Spain."},{"key":"ref_16","unstructured":"Korzhyk, D., Conitzer, V., and Parr, R. (2011, January 2\u20136). Solving Stackelberg Games with Uncertain Observability. Proceedings of the AAMAS, Taipei, Taiwan."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/2627534.2627536","article-title":"MultiDefender Security Games on Networks","volume":"41","author":"Smith","year":"2014","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"ref_18","unstructured":"Lou, J., and Vorobeychik, Y. (2015, January 25\u201331). Equilibrium Analysis of Multi-Defender Security Games. Proceedings of the International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Laszka, A., Lou, J., and Vorobeychik, Y. (2016, January 12\u201317). Multi-Defender Strategic Filtering Against Spear-Phishing Attacks. Proceedings of the AAAI, Phoenix, AZ, USA.","DOI":"10.1609\/aaai.v30i1.10020"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Liu, P. (2003, January 27\u201330). Incentive-Based Modeling and Inference of Attacker Intent, Objectives, and Strategies. Proceedings of the 10th ACM Computer and Communications Security Conference (CCS\u201903), Washington, DC, USA.","DOI":"10.1145\/948134.948135"},{"key":"ref_21","unstructured":"Cremonini, M., and Nizovtsev, D. (2006, January 26\u201328). Understanding and Influencing Attackers\u2019 Decisions: Implications for Security Investment Strategies. Proceedings of the Fifth Workshop on the Economics of Information Security (WEIS 2006), Cambridge, UK."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Khouzani, M., Panaousis, E., and Theodorakopoulos, G. (2015). Decision and Game Theory for Security, Proceedings of the 6th International Conference, GameSec 2015, London, UK, 4\u20135 November 2015, Springer International Publishing.","DOI":"10.1007\/978-3-319-25594-1"},{"key":"ref_23","unstructured":"Agiwal, S., and Mohtadi, H. (2008, January 27\u201329). Risk Mitigating Strategies in the Food Supply Chain. Proceedings of the American Agricultural Economics Assocation (Annual Meeting), Orlando, FL, USA."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Dvijotham, K., Chertkov, M., Van Hentenryck, P., Vuffray, M., and Misra, S. (2016). Graphical models for optimal power flow. Constraints, 1\u201326.","DOI":"10.1007\/s10601-016-9253-y"},{"key":"ref_25","unstructured":"Kearns, M., and Ortiz, L.E. (2003, January 11\u201313). Algorithms for Interdependent Security Games. Proceedings of the Neural Information Processing Systems (NIPS), Whistler, BC, Canada."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1613\/jair.1683","article-title":"Pure Nash equilibria: Hard and easy games","volume":"24","author":"Gottlob","year":"2005","journal-title":"J. Artif. Intell. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","article-title":"Nash and correlated equilibria: Some complexity considerations","volume":"1","author":"Gilboa","year":"1989","journal-title":"Games Econ. Behav."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1516512.1516516","article-title":"Settling the complexity of computing two-player Nash equilibria","volume":"56","author":"Chen","year":"2009","journal-title":"J. ACM"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1137\/070699652","article-title":"The Complexity of Computing a Nash Equilibrium","volume":"39","author":"Daskalakis","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","article-title":"On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence","volume":"48","author":"Papadimitriou","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1145\/1461928.1461951","article-title":"The complexity of computing a Nash equilibrium","volume":"52","author":"Daskalakis","year":"2009","journal-title":"Commun. ACM"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/j.geb.2008.02.015","article-title":"New complexity results about Nash equilibria","volume":"63","author":"Conitzer","year":"2008","journal-title":"Games Econ. Behav."},{"key":"ref_33","unstructured":"Shavitt, Y., and Shir, E. DIMES\u2014Letting the Internet Measure Itself. Available online: http:\/\/www.arxiv.org\/abs\/cs.NI\/0506099."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/1096536.1096546","article-title":"DIMES: Let the Internet Measure Itself","volume":"35","author":"Shavitt","year":"2005","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_35","unstructured":"Fudenberg, D., and Levine, D. (1999). The Theory of Learning in Games, MIT Press."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., \u00c9va, T., and Vaziran, V.V. (2007). Algorithmic Game Theory, Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"ref_37","unstructured":"Kearns, M., Littman, M., and Singh, S. (2001, January 2\u20135). Graphical Models for Game Theory. Proceedings of the Conference on Uncertainty in Artificial Intelligence, Seattle, WA, USA."},{"key":"ref_38","unstructured":"Heal, G., and Kunreuther, H. You Only Die Once: Managing Discrete Interdependent Risks. Available online: http:\/\/ssrn.com\/abstract=430599."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1111\/j.1539-6924.2007.00904.x","article-title":"Modeling Interdependent Risks","volume":"27","author":"Heal","year":"2007","journal-title":"Risk Anal."},{"key":"ref_40","unstructured":"Ortiz, L.E. (2014). On Sparse Discretization for Graphical Games. CoRR, abs\/1411.3320."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.artint.2014.06.004","article-title":"On influence, stable behavior, and the most influential individuals in networks: A game-theoretic approach","volume":"215","author":"Irfan","year":"2014","journal-title":"Artif. Intell."},{"key":"ref_42","unstructured":"Koller, D., and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques, MIT Press."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Kakade, S., Kearns, M., Langford, J., and Ortiz, L. (2003, January 9\u201312). Correlated Equilibria in Graphical Games. Proceedings of the 4th ACM conference on Electronic commerce, EC \u201903, San Diego, CA, USA.","DOI":"10.1145\/779928.779934"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0304-4068(74)90037-8","article-title":"Subjectivity and Correlation in Randomized Strategies","volume":"1","author":"Aumann","year":"1974","journal-title":"J. Math. Econ."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/1911154","article-title":"Correlated Equilibrium as an Expression of Bayesian Rationality","volume":"55","author":"Aumann","year":"1987","journal-title":"Econometrica"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1103\/PhysRev.106.620","article-title":"Information Theory and Statistical Mechanics","volume":"106","author":"Jaynes","year":"1957","journal-title":"Phys. Rev."},{"key":"ref_47","unstructured":"Thrun, S., Saul, L.K., and Sch\u00f6lkopf, B. (2004). Advances in Neural Information Processing Systems 16, MIT Press."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","article-title":"A random polynomial time algorithm for approximating the volume of a convex body","volume":"38","author":"Dyer","year":"1991","journal-title":"JACM"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Elkind, E., Goldberg, L.A., and Goldberg, P.W. (2006, January 11\u201315). Nash Equilibria in Graphical Games on Trees Revisited. Proceedings of the 7th ACM Conference on Electronic Commerce, EC \u201906, Ann Arbor, MI, USA.","DOI":"10.1145\/1134707.1134719"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Cai, Y., and Daskalakis, C. (2011, January 23\u201325). On Minmax Theorems for Multiplayer Games. Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201911, San Francisco, CA, USA.","DOI":"10.1137\/1.9781611973082.20"},{"key":"ref_51","unstructured":"Singh, S.P., Kearns, M.J., and Mansour, Y. (July, January 30). Nash Convergence of Gradient Dynamics in General-Sum Games. Proceedings of the UAI, Stanford, CA, USA."},{"key":"ref_52","unstructured":"Kearns, M. Economics, Computer Science, and Policy. Available online:http:\/\/issues.org\/21-2\/kearns\/."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1006\/game.1995.1023","article-title":"Quantal Response Equilibria for Normal Form Games","volume":"10","author":"McKelvey","year":"1995","journal-title":"Games Econ. Behav."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., \u00c9va, Tardos., and Vazirani, V.V. (2007). Algorithmic Game Theory, Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"ref_55","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley & Sons. [2nd ed.]."},{"key":"ref_56","unstructured":"Boyd, S., and Vandenberghe, L. (2006). Convex Optimization, Cambridge University Press."},{"key":"ref_57","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_58","unstructured":"Vazirani, V.V. (2001). Approximation Algorithms, Springer."},{"key":"ref_59","unstructured":"Bellman, R.E. (2003). Dynamic Programming, Dover Publications."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","article-title":"Non-cooperative games","volume":"54","author":"Nash","year":"1951","journal-title":"Ann. Math."}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/8\/1\/13\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:28:26Z","timestamp":1760207306000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/8\/1\/13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,16]]},"references-count":60,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,3]]}},"alternative-id":["g8010013"],"URL":"https:\/\/doi.org\/10.3390\/g8010013","relation":{},"ISSN":["2073-4336"],"issn-type":[{"type":"electronic","value":"2073-4336"}],"subject":[],"published":{"date-parts":[[2017,2,16]]}}}