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 The attacker incurs in a cost c(e) for choosing an element e, and if 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 [21]. Its time complexity is where IO is the time that it takes one call to the independence oracle. Here we present an algorithm that requires 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 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 [21]. We also treat the case when the defender chooses a rooted arborescence in a directed graph, and the attacker chooses an arc, we use this structure to give an algorithm that requires time.