A graph-theoretic network security game
SourceInternational Journal of Autonomous and Adaptive Communications Systems
Google Scholar check
MetadataShow full item record
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. Copyright © 2008 Inderscience Enterprises Ltd.
Showing items related by title, author, creator and subject.
Belk, Marios; Fidas, Christos A.; Germanakos, Panagiotis; Samaras, George S. (2014)The purpose of this paper is to propose a preliminary framework for supporting usable security on the World Wide Web through adaptivity in user interface designs. In particular we elaborate the concept of "Adaptive Usable ...
Stavrou, Eliana (Πανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημών / University of Cyprus, Faculty of Pure and Applied Sciences, 2006-06)This research work addresses security-related issues in the electronic and mobile healthcare environments and proposes an appropriate security framework. The proposed framework will identify the necessary security technologies ...
Pissarides, Christopher A.; Zabalza, Antoni; Piachaud, D. (Scientechnica, 1980)