Faster Algorithms for Security Games on Matroids

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 \in E\). The attacker incurs a cost c(e) for choosing an element e, and if \(e \in 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 Szeszler (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 Szeszler (2016). We also treat the case when the defender chooses a rooted arborescence in a directed graph \(D=(V,\mathscr {A})\), and the attacker chooses an arc, we use this structure to give an algorithm that requires \(O(|V||\mathscr {A}|^3 \log (|V|^2/|\mathscr {A}|) \log |\mathscr {A}|)\) time.