The Price of Defense

• Published in: Algorithmica 2021-05, Vol.83 (5), p.1256-1315
• Main Authors: Mavronicolas, Marios, Michael, Loizos, Papadopoulou Lesta, Vicky, Persiano, Giuseppe, Philippou, Anna, Spirakis, Paul G.
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Apexes; Complexity; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Defense; Equilibrium; Expected utility; Game theory; Graph matching; Graph theory; Graphs; Lower bounds; Mathematics of Computing; Players; Polynomials; Supports; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-020-00783-7

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 .