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.

By: Mourad Baïou, Francisco Barahona

Published in: RC25637 in 2016


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .