Security on Networks

Abstract

As epidemics spread on computer, disease propagation, and financial networks, agents in the network often undertake costly investments in security to protect themselves from infection. However, these investments are often imperfect and typically succeed with some probability less than one. Furthermore, the cost of a security investment and its probability of success both increase with the chosen level of security. Thus agents face a tradeoff between choosing high investment in security to minimize infection probability and choosing low investment to minimize cost. Given the easily constructible utility functions of agents, it is appropriate to model the choice of security as a game on a network. In this paper, we extend the game theoretic framework developed in unpublished work from Acemoglu et al. (2013) to random graph models. We spend the majority of the paper considering the static model of infection in which each agent chooses a security level once before the attacker initiates the infection. In the static infection model, we specifically concern ourselves with characterizing the difference in infection rates between the Nash equilibrium and the social optimum. We also discuss some simulation results on the dynamic model, in which agents observe the infection state of their k-neighborhood at each timestep and update their security investments accordingly. Finally, we present some results on the intractability of computing infection probabilities exactly, and we provide a fully polynomial time approximation scheme for arbitrarily small .