Faster Algorithms for Security Games on Matroids

Abstract

Given a matroid M defined by an independence oracle on a ground set E, the Matroid Base Game is played by two players: the defender chooses a basis B and (simultaneously) the attacker chooses an element e∈ E. The attacker incurs a cost c(e) for choosing an element e, and if e∈ B then there is a probability p(e) that the attacker will detect the defender. The defender has to find a bases-selection strategy that minimizes the average probability of being detected. The attacker has to find a probabilistic selection strategy that maximizes the average detection probability minus its average cost. An algorithm to compute Nash-equilibrium mixed strategies was given in Szeszlér (Math Program 161:347–364, 2016). Its time complexity is O(| E| 10 IO) , where IO is the time that it takes one call to the independence oracle. Here we present an algorithm that requires O(| E| 6 IO) time. For graphic matroids, i.e., when the defender chooses a spanning tree in a graph G= (V, E) , and the attacker chooses an edge, we give an algorithm that takes O(| V| 4 | E| 1 / 2 ) time. This type of game is extended to common bases of two matroids. For this case we give a strongly polynomial algorithm, settling a question that was left open in Szeszlér (2016). We also treat the case when the defender chooses a rooted arborescence in a directed graph D= (V, A) , and the attacker chooses an arc, we use this structure to give an algorithm that requires O(| V| | A| 3 log (| V| 2 / | A|) log | A|) time.