Interdependent Security Game Design over Constrained Linear Influence Networks



1 Department of Computer Engineering, University of Isfahan, Isfahan, Iran

2 Department of Computer Engineering, University of Isfahan, Isfahan, Iran.

3 Department of Electrical and Electronic Engineering, The University of Melbourne, Melbourne, Australia.


In today's highly interconnected networks, security of the entities are often interdependent. This means security decisions of the agents are not only influenced by their own costs and constraints, but also are affected by their neighbors’ decisions. Game theory provides a rich set of tools to analyze such influence networks. In the game model, players try to maximize their utilities through security investments considering the network structure, costs and constraints, which have been set by the network owner. However, decisions of selfish entities to maximize their utilities do not always lead to a socially optimum solution. Therefore, motivating players to reach the social optimum is of high value from the network owner’s point of view. The network owner wants to maximize the overall network security by designing the game's parameters. As far as we know, there is no notable work in the context of linear influence networks to introduce appropriate game design for this purpose. This paper presents design methods that make use of the adjustments of players’ costs, interdependencies, and constraints to align players' incentives with a network-wide global objective. We present a comprehensive investigation of existence and uniqueness conditions of Nash Equilibrium in such environments. Furthermore, numerical results of applying the proposed mechanisms in a sample real-world example are illustrated.


[1]R Miura-Ko, Benjamin Yolken, Nicholas Bambos, and John Mitchell. Security investment games of interdependent organizations. In Communication, Control, and Computing, 46th Annual Allerton Conference on, pages 252–260. IEEE,2008.
[2] Sara Robinson. The price of anarchy. SIAM News, 37(5):1–4, 2004.
[3] Ramesh Johari, Shie Mannor, and John N Tsitsiklis. Efficiency loss in a network resource allocation game: the case of elastic supply. Automatic Control, IEEE Transactions on, 50(11):1712–1724, 2005.
[4] Aron Laszka, Mark Felegyhazi, and Levente Buttyan. A survey of interdependent information security games. ACM Computing Surveys (CSUR), 47(2):23:1–23:38, 2014.
[5] Randall A Berry and Ramesh Johari. Economic Modeling in Networking: A Primer. Foundations and Trends in Networking, 6(3):165–286, 2013.
[6] Tansu Alpcan and Lacra Pavel. Nash equilibrium design and optimization. In International Conference on Game Theory for Networks, GameNets’ 09., pages 164–170. IEEE, 2009.
[7] Anil Kumar Chorppath and Tansu Alpcan. Mechanism design for incentive compatible control of networks. In Complex Systems, pages 73–100. 2016.
[8] Benjamin Henry Yolken. Incentive-based resource allocation and control for large-scale computing services. PhD thesis, Stanford University, 2009.
[9] R Miura-Ko, Benjamin Yolken, John Mitchell, and Nicholas Bambos. Security decision-making among interdependent organizations. In Computer Security Foundations Symposium, CSF’08. IEEE 21st, pages 66–80. IEEE, 2008.
[10] Ishai Menache and Asuman Ozdaglar. Network games: Theory, models, and dynamics. Synthesis
Lectures on Communication Networks, 4(1):1–159, 2011.
[11] Dimitris E Charilas and Athanasios D Panagopoulos. A survey on game theory applications in wireless networks. Computer Networks,54(18):3421–3430, 2010.
[12] Ross Anderson. Why information security is hard-an economic perspective. In 17th annual Computer security applications conference, pages 358–365. IEEE, 2001.
[13] Hal Varian. System reliability and free riding. In L. Jean Camp and Stephen Lewis, editors, Economics of information security, pages 1–15. Springer, 1 edition, 2004.
[14] Jens Grossklags, Nicolas Christin, and John Chuang. Secure or insure? a game-theoretic analysis of information security games. In the 17th international conference on World Wide Web, pages 209–218. ACM, 2008.
[15] Joshua Gans, Stephen King, and Gregory Mankiw. Principles of microeconomics. Cengage Learning, 2012.
[16] Paul Krugman, Robin Wells, and Elizabeth Sawyer Kelly. Microeconomics study guide. Worth, 2009.

[17] Andreu Mas-Colell, Michael Dennis Whinston, and Jerry R Green. Microeconomic theory. Oxford University Press, 1995.
[18] Kien Nguyen, Tansu Alpcan, and Tamer Basar. Stochastic games for security in networks with interdependent nodes. In International Conference on Game Theory for Networks, pages 697–703. IEEE, 2009.
[19] Matthew O Jackson. Social and economic networks, volume 3. Princeton University Press,2008.
[20] Andrea Galeotti, Sanjeev Goyal, Matthew O Jackson, Fernando Vega-Redondo, and Leeat Yariv. Network games. The review of economic studies, 77(1):218–244, 2010.
[21] Martin Kaae Jensen. Aggregative games and best-reply potentials. Economic theory, 43(1):45–66, 2010.
[22] Yann Bramoullé, Rachel Kranton, and Martin D’amours. Strategic interaction and networks. The American Economic Review, 104(3):898–930,2014.
[23] Victor M Preciado, Jaelynn Oh, and Ali Jadbabaie. Analysis of equilibria and strategic interaction in complex networks. In Decision and Control and European Control Conference (CDCECC), 50th IEEE Conference on, pages 4498–4503. IEEE, 2011.
[24] Coralio Ballester and Antoni Calvó-Armengol. Interactions with hidden complementarities. Regional
Science and Urban Economics, 40(6):397–406, 2010.
[25] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953.
[26] Geoffrey Heal and Howard Kunreuther. Interdependent security: A general model. National Bureau of Economic Research, 2004.
[27] Marc Lelarge and Jean Bolot. A local mean field analysis of security investments in networks. In
Proceedings of the 3rd international workshop on Economics of networked systems, pages 25–30. ACM, 2008.
[28] Libin Jiang, Venkat Anantharam, and Jean Walrand. How bad are selfish investments in network security? IEEE/ACM Transactions on Networking (TON), 19(2):549–560, 2011.
[29] Howard Kunreuther and Geoffrey Heal. Interdependent security. Journal of risk and uncertainty,
26(2-3):231–249, 2003.
[30] Marc Lelarge. Economics of malware: Epidemic risks model, network externalities and incentives.
In Communication, Control, and Computing,2009. Allerton 2009. 47th Annual Allerton Conference on, pages 1353–1360. IEEE, 2009.
[31] Rainer Böhme. Security audits revisited. In International Conference on Financial Cryptography and Data Security, pages 129–147. Springer,2012.
[32] Mansooreh Ezhei and Behrouz Tork Ladani. Interdependency analysis in security investment
against strategic attacks. Information Systems Frontiers, 2018.
[33] Mansooreh Ezhei and Behrouz Tork Ladani. Information sharing vs. privacy: A game theoretic analysis. Expert Systems with Applications, 88:327–337, 2017.
[34] Seyed Alireza Hasheminasab and Behrouz Tork Ladani. Security investment in contagious networks. Risk Analysis, 2018.
[35] Patrick Bolton and Mathias Dewatripont. The firm as a communication network. The Quarterly Journal of Economics, 109:809–839, 1994.
[36] Ludovic Renou and Tristan Tomala. Mechanism design and communication networks. Theoretical
economics, 7(3):489–533, 2012.
[37] Gerard Debreu. A social equilibrium existence theorem. Proceedings of the National Academy
of Sciences of the United States of America, 38(10):886, 1952.
[38] Ky Fan. Fixed-point and minimax theorems in locally convex topological linear spaces. Proceedings
of the National Academy of Sciences of the United States of America, 38(2):121, 1952.
[39] Irving L Glicksberg. A further generalization of the Kakutani fixed point theorem, with application
to Nash equilibrium points. Proceedings of the American Mathematical Society, 3(1):170–174, 1952.
[40] J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica:
Journal of the Econometric Society,33:520–534, 1965.
[41] Tansu Alpcan. Noncooperative games for control of networked systems. PhD thesis, University Illinois at Urbana-Champaign, 2006.