The Price of Defense

Mavronicolas, Marios, Michael, Loizos, Papadopoulou Lesta, Vicky, Persiano, Giuseppe, Philippou, Anna and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2021) The Price of Defense. Algorithmica, 83 (5). pp. 1256-1315.

Text AlgorithmicaPriceOfDefense.pdf - Author Accepted Manuscript Download (828kB) | Preview

Abstract

We consider a game on a graph G= ⟨ V, E⟩ with two confronting classes of randomized players: νattackers, who choose vertices and seek to minimize the probability of getting caught, and a single defender, who chooses edges and seeks to maximize the expected number of attackers it catches. In a Nash equilibrium, no player has an incentive to unilaterally deviate from her randomized strategy. The Price of Defense is the worst-case ratio, over all Nash equilibria, of ν over the expected utility of the defender at a Nash equilibrium. We orchestrate a strong interplay of arguments from Game Theory and Graph Theory to obtain both general and specific results in the considered setting: (1) Via a reduction to a Two-Players, Constant-Sum game, we observe that an arbitrary Nash equilibrium is computable in polynomial time. Further, we prove a general lower bound of |V|2 on the Price of Defense. We derive a characterization of graphs with a Nash equilibrium attaining this lower bound, which reveals a promising connection to Fractional Graph Theory; thereby, it implies an efficient recognition algorithm for such Defense-Optimal graphs. (2) We study some specific classes of Nash equilibria, both for their computational complexity and for their incurred Price of Defense. The classes are defined by imposing structure on the players’ randomized strategies: either graph-theoretic structure on the supports, or symmetry and uniformity structure on the probabilities. We develop novel graph-theoretic techniques to derive trade-offs between computational complexity and the Price of Defense for these classes. Some of the techniques touch upon classical milestones of Graph Theory; for example, we derive the first game-theoretic characterization of König-Egerváry graphs as graphs admitting a Matching Nash equilibrium.

Item Type:	Article
Uncontrolled Keywords:	Game theory, Graph theory, Security, Nash equilibria, Attacks and defenses
Depositing User:	Symplectic Admin
Date Deposited:	15 Jan 2021 10:59
Last Modified:	18 Jan 2023 23:03
DOI:	10.1007/s00453-020-00783-7
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3113734