dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Lesta, Vicky Papadopoulou | en |
dc.contributor.author | Philippou, Anna | en |
dc.contributor.author | Spirakis, Paul G. | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Lesta, Vicky Papadopoulou | en |
dc.creator | Philippou, Anna | en |
dc.creator | Spirakis, Paul G. | en |
dc.date.accessioned | 2019-11-13T10:41:11Z | |
dc.date.available | 2019-11-13T10:41:11Z | |
dc.date.issued | 2008 | |
dc.identifier.issn | 1754-8632 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/54493 | |
dc.description.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. Copyright © 2008 Inderscience Enterprises Ltd. | en |
dc.source | International Journal of Autonomous and Adaptive Communications Systems | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-81855194700&doi=10.1504%2fIJAACS.2008.021488&partnerID=40&md5=71e5f56185694a07f028cf0be99fd354 | |
dc.subject | Non-cooperative | en |
dc.subject | Graph theory | en |
dc.subject | Network security | en |
dc.subject | System security | en |
dc.subject | Trees (mathematics) | en |
dc.subject | Computer viruses | en |
dc.subject | Viruses | en |
dc.subject | Linear functions | en |
dc.subject | NP Complete | en |
dc.subject | Price of anarchy | en |
dc.subject | Multiplayer games | en |
dc.subject | Nash equilibria | en |
dc.subject | Pure Nash equilibrium | en |
dc.subject | Perfect matchings | en |
dc.subject | Existence problems | en |
dc.subject | Graph-theoretic | en |
dc.subject | Network scenario | en |
dc.subject | Network security games | en |
dc.subject | Regular graphs | en |
dc.subject | Security software | en |
dc.subject | Viral infections | en |
dc.title | A graph-theoretic network security game | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1504/IJAACS.2008.021488 | |
dc.description.volume | 1 | |
dc.description.issue | 4 | |
dc.description.startingpage | 390 | |
dc.description.endingpage | 410 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :3</p> | en |
dc.source.abbreviation | Int.J.Auton.Adapt.Commun.Syst. | en |
dc.contributor.orcid | Spirakis, Paul G. [0000-0001-5396-3749] | |
dc.contributor.orcid | Lesta, Vicky Papadopoulou [0000-0003-2920-8473] | |
dc.gnosis.orcid | 0000-0001-5396-3749 | |
dc.gnosis.orcid | 0000-0003-2920-8473 | |