Security games on matroids

Two players, the Defender and the Attacker play the following game. A matroid $$M=(S,\mathcal {I})$$M=(S,I), a weight function $$d:S\rightarrow \mathbb {R}^+$$d:SźR+ and a cost function $$c:S\rightarrow \mathbb {R}$$c:SźR are given. The Defender chooses a base B of the matroid M and the Attacker chooses an element $$s\in S$$sźS of the ground set. In all cases, the Attacker pays the Defender the cost of attack c(s). Besides that, if $$s\in B$$sźB then the Defender pays the Attacker the amount d(s); if, on the other hand, $$s\notin B$$sźB then there is no further payoff. Special cases of this two-player, zero-sum game were considered and solved in various security-related applications. In this paper we show that it is also possible to compute Nash-equilibrium mixed strategies for both players in strongly polynomial time in the above general matroid setting. We also consider a further generalization where common bases of two matroids are chosen by the Defender and apply this to define and efficiently compute a new reliability metric on digraphs.