research unit 1
 

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

Publication

Type of publication:Inproceedings
Entered by:
TitleThe Price of Defense
Bibtex cite IDRACTI-RU1-2006-74
Booktitle Mathematical Foundations of Computer Science (MFCS 2006)
Series Lecture Notes in Computer Science
Year published 2006
Month August
Volume 4162/2006
Pages 717-728
Publisher Springer Berlin / Heidelberg
URL http://www.mfcs.sk/mfcs2006/
Abstract
We consider a strategic game with two classes of confronting randomized players on a graph G(V,E): í attackers, each choosing vertices and wishing to minimize the probability of being caught, and a defender, who chooses edges and gains the expected number of attackers it catches. The Price of Defense is the worst-case ratio, over all Nash equilibria, of the optimal gain of the defender over its gain at a Nash equilibrium. We provide a comprehensive collection of trade-offs between the Price of Defense and the computational efficiency of Nash equilibria. Through reduction to a Two-Players, Constant-Sum Game, we prove that a Nash equilibrium can be computed in polynomial time. The reduction does not provide any apparent guarantees on the Price of Defense. To obtain such, we analyze several structured Nash equilibria: In a Matching Nash equilibrium, the support of the defender is an Edge Cover. We prove that they can be computed in polynomial time, and they incur a Price of Defense of á(G), the Independence Number of G. In a Perfect Matching Nash equilibrium, the support of the defender is a Perfect Matching. We prove that they can be computed in polynomial time, and they incur a Price of Defense of |V | 2 . In a Defender Uniform Nash equilibrium, the defender chooses uniformly each edge in its support. We prove that they incur a Price of Defense falling between those for Matching and Perfect Matching Nash Equilibria; however, it is NP-complete to decide their existence. In an Attacker Symmetric and Uniform Nash equilibrium, all attackers have a common support on which each uses a uniform distribution. We prove that they can be computed in polynomial time and incur a Price of Defense of either |V | 2 or á(G).
Authors
Mavronicolas, Marios
Michael, Loizos
Spirakis, Paul
Topics
BibTeXBibTeX
RISRIS
Attachments
fulltext.pdf (main file)
 
Publication ID338