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:12Z | |
dc.date.available | 2019-11-13T10:41:12Z | |
dc.date.issued | 2005 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/54496 | |
dc.description.abstract | Consider an information network with harmful procedures called attackers (e.g., viruses) | en |
dc.description.abstract | each attacker uses a probability distribution to choose a node of the network to damage. Opponent to the attackers is the system protector scanning and cleaning from attackers some part of the network (e.g., an edge or a path), which it chooses independently using another probability distribution. Each attacker wishes to maximize the probability of escaping its cleaning by the system protector | en |
dc.description.abstract | towards a conflicting objective, the system protector aims at maximizing the expected number of cleaned attackers. We model this network scenario as a non-cooperative strategic game on graphs. We focus on the special case where the protector chooses a single edge. We are interested in the associated Nash equilibria, where no network entity can unilaterally improve its local objective. We obtain the following results: No instance of the game possesses a pure Nash equilibrium. Every mixed Nash equilibrium enjoys a graph-theoretic structure, which enables a (typically exponential) algorithm to compute it. We coin a natural subclass of mixed Nash equilibria, which we call matching Nash equilibria, for this game on graphs. Matching Nash equilibria are defined using structural parameters of graphs, such as independent sets and matchings. We derive a characterization of graphs possessing matching Nash equilibria. The characterization enables a linear time algorithm to compute a matching Nash equilibrium on any such graph with a given independent set and vertex cover. Bipartite graphs are shown to satisfy the characterization. So, using a polynomial-time algorithm to compute a perfect matching in a bipartite graph, we obtain, as our main result, an efficient graph-theoretic algorithm to compute a matching Nash equilibrium on any instance of the game with a bipartite graph. © Springer-Verlag Berlin Heidelberg 2005. | en |
dc.source | 16th International Symposium on Algorithms and Computation, ISAAC 2005 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-33744965987&doi=10.1007%2f11602613_30&partnerID=40&md5=0c162d8d73d07ecd182310fccf60aef0 | |
dc.subject | Game theory | en |
dc.subject | Algorithms | en |
dc.subject | Graph theory | en |
dc.subject | Probability distributions | en |
dc.subject | Polynomials | en |
dc.subject | Computation theory | en |
dc.subject | Nash equilibria | en |
dc.subject | Bipartite graph | en |
dc.subject | System protector scanning | en |
dc.subject | Vertex cover | en |
dc.title | Network game with attacker and protector entities | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1007/11602613_30 | |
dc.description.volume | 3827 LNCS | en |
dc.description.startingpage | 288 | |
dc.description.endingpage | 297 | |
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>Sponsors: Academy of Mathematics and System Sciences | en |
dc.description.notes | Chinese Academy of Sciences | en |
dc.description.notes | City University of Hong Kong | en |
dc.description.notes | Conference code: 67466 | en |
dc.description.notes | Cited By :9</p> | en |
dc.source.abbreviation | Lect. Notes Comput. Sci. | 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 | |