A graph-theoretic network security game. (1st December 2008)

• Record Type: Journal Article
• Authors: Mavronicolas, Marios; Papadopoulou, Vicky G.; Philippou, Anna; Spirakis, Paul G.
• Is Part Of: International journal of autonomous and adaptive communications systems. Volume 1:Number 4(2008)
• Page Start: 390
• Page End: 410
• Publication Date: 2008-12-01
• Subjects: graph theory -- Nash equilibria -- network security games -- viral infections; Adaptive computing systems -- Periodicals; Wireless communication systems -- Periodicals; Computer networks -- Periodicals; 004.6
• Languages: English
• ISSNs: 1754-8632

Abstract

Consider a network vulnerable to viral infection, where the security software can guarantee safety only to a limited part of it. We model this practical network scenario as a non-cooperative multi-player game on a graph, with two kinds of players, a set of attackers and a protector player, representing the viruses and the system security software, respectively. We are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. We obtain the following results: for certain families of graphs, mixed Nash equilibria can be computed in polynomially time. These families include, among others, regular graphs, graphs with perfect matchings and trees. The corresponding price of anarchy for any mixed Nash equilibria of the game is upper and lower bounded by a linear function of the number of vertices of the graph. (We define the price of anarchy to reflect the utility of the protector). Finally, we introduce a generalised version of the game. We show that the existence problem of pure Nash equilibria here is NP complete.