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 | 2008 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/54494 | |
dc.description.abstract | Consider an information network with threats called attackers | en |
dc.description.abstract | each attacker uses a probability distribution to choose a node of the network to damage. Opponent to the attackers is a protector entity called defender | en |
dc.description.abstract | the defender scans and cleans from attacks some part of the network (in particular, a link), which it chooses independently using its own probability distribution. Each attacker wishes to maximize the probability of escaping its cleaning by the defender | en |
dc.description.abstract | towards a conflicting objective, the defender aims at maximizing the expected number of attackers it catches. We model this network security scenario as a non-cooperative strategic game on graphs. We are interested in its associated Nash equilibria, where no network entity can unilaterally increase its local objective. We obtain the following results: • We obtain an algebraic characterization of (mixed) Nash equilibria. • No (non-trivial) instance of the graph-theoretic game has a pure Nash equilibrium. This is an immediate consequence of some covering properties we prove for the supports of the players in all (mixed) Nash equilibria. • We coin a natural subclass of mixed Nash equilibria, which we call Matching Nash equilibria, for this graph-theoretic game. Matching Nash equilibria are defined by enriching the necessary covering properties we proved with some additional conditions involving other structural parameters of graphs, such as Independent Sets. - We derive a characterization of graphs admitting Matching Nash equilibria. All such graphs have an Expanding Independent Set. The characterization enables a non-deterministic, polynomial time algorithm to compute a Matching Nash equilibrium for any such graph. - Bipartite graphs are shown to satisfy the characterization. So, using a polynomial time algorithm to compute a Maximum Matching for a bipartite graph, we obtain, as our main result, a deterministic, polynomial time algorithm to compute a Matching Nash equilibrium for any instance of the game with a bipartite graph. © 2007 Springer Science+Business Media, LLC. | en |
dc.source | Algorithmica (New York) | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-43949096885&doi=10.1007%2fs00453-007-9109-3&partnerID=40&md5=ecdd0c51bdd41f6df662784cc7c4f214 | |
dc.subject | Security | en |
dc.subject | Information analysis | en |
dc.subject | Optimization | en |
dc.subject | Game theory | en |
dc.subject | Graph theory | en |
dc.subject | Probability distributions | en |
dc.subject | Polynomials | en |
dc.subject | Nash equilibria | en |
dc.subject | Strategic game | en |
dc.subject | Attacks and defenses | en |
dc.subject | Polynomial time algorithm | en |
dc.title | A network game with attackers and a defender | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1007/s00453-007-9109-3 | |
dc.description.volume | 51 | |
dc.description.issue | 3 | |
dc.description.startingpage | 315 | |
dc.description.endingpage | 341 | |
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 :10</p> | en |
dc.source.abbreviation | Algorithmica (New York) | 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 | |