The Price of Defence

13^th March 2019, 13:00
Paul Spirakis
University of Liverpool

Abstract

We examine here a game on a graph G(V,E) between ? attacker players and a single defender. Each attacker selects (as a pure strategy) a vertex ; the defender selects an edge. The defender seeks to maximize the number of attackers he catches. The Price of Defence (PoD) is the worst case ratio over all Nash Equilibria of ? divided by the expected utility of the defender at the Nash Equilibrium. We show a lower bound of n/2 (n is the number of vertices in G) for PoD. We characterize the defence-optimal graphs and show that they can be efficiently recognized. We define several classes of Nash Equilibria by imposing structure on players randomized strategies. We show trade-offs between the computational complexity of such equilibria and their price of defence.

This is joint work with M. Mavronicolas, L. Michael, V. Papapdopoulou Lesta, A. Philippou, and G. Persiano.