research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleThe Price of Defense and Fractional Matchings
Bibtex cite IDRACTI-RU1-2006-72
Booktitle Distributed Computing and Networking (ICDCN 2006)
Year published 2006
Month December
Volume 4308
Pages 115-126
Publisher Springer, Berlin
Consider a network vulnerable to security attacks and equipped with defense mechanisms. How much is the loss in the provided security guarantees due to the selfish nature of attacks and defenses? The Price of Defense was recently introduced in [7] as a worst-case measure, over all associated Nash equilibria, of this loss. In the particular strategic game considered in [7], there are two classes of confronting randomized players on a graph G(V,E): v attackers, each choosing vertices and wishing to minimize the probability of being caught, and a single defender, who chooses edges and gains the expected number of attackers it catches. In this work, we continue the study of the Price of Defense. We obtain the following results: - The Price of Defense is at least |V| 2; this implies that the Perfect Matching Nash equilibria considered in [7] are optimal with respect to the Price of Defense, so that the lower bound is tight. - We define Defense-Optimal graphs as those admitting a Nash equilibrium that attains the (tight) lower bound of |V| 2. We obtain: A graph is Defense-Optimal if and only if it has a Fractional Perfect Matching. Since graphs with a Fractional Perfect Matching are recognizable in polynomial time, the same holds for Defense-Optimal graphs. We identify a very simple graph that is Defense-Optimal but has no Perfect Matching Nash equilibrium. - Inspired by the established connection between Nash equilibria and Fractional Perfect Matchings, we transfer a known bivaluedness result about Fractional Matchings to a certain class of Nash equilibria. So, the connection to Fractional Graph Theory may be the key to revealing the combinatorial structure of Nash equilibria for our network security game.
Mavronicolas, Marios
Papadopoulou, Viki
Persiano, Giuseppe
Philippou, Anna
Spirakis, Paul
ICDCN.pdf (main file)
Publication ID336