I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't explicitly required it, I'd like to prove the NP-hardness or completeness of the problem since it's something I'd like to learn to do. I'm pretty new at theoretical CS since I've been working as a software-engineer for the past 8 or so years. My problem is as follows. The defender has a set of targets $T = \{a, b, c, d, e, f, g\}$ and $k$ resources, where $k < |T|$. The defender can place at most one resource on one target to cover it.There is an attacker who can attack any subset of targets in $T$. So the attacker's pure strategy $A \subseteq T$ and $A \in \mathcal{P}(T)$. The attacker succeeds if all the targets he attacks are not covered by the defender. If at least one of the targets that he attacks is covered by the defender, he fails. The defender does not know which targets the attacker will attack, and he also does not know the number of targets either. The defender's job is to come up with an optimal mixed strategy (a vector with a probability assigned to each pure strategy) to guard against the attacker. The probability assigned to a pure-strategy is the probability that the defender will play that pure strategy. This information is also known to the attacker. I know that the strategy space for both players is large. The total number of pure strategies for the defender is $\binom{|T|}{k}$, and for the attacker it is $2^{|T|}$. There is a standard algorithm that generates a set of linear programs to solve for the defender's mixed strategy. However, we will end up with $2^{|T|}$ linear programs, each with $\binom{|T|}{k}$ variables. So the complexity is $O\big(2^{|T|} \times \binom{|T|}{k}^{3.5}\big)$ (Karmarkar's algorithm).The algorithm won't perform well at all, because there combinatorial explosion in the strategy space for both the defender and attacker. I'm trying to see if there is an NP-complete problem I can reduce this to, but I'm not sure where to go from here. I have looked at set cover, and exact set cover, but I'm still not sure how I would reduce it to that, or even if those are applicable here.I read this paper where they deal with a somewhat similar problem (urban network graph, where an attacker can attack any target from a starting point by using any of the paths available; the defender has $k$ resources that he can place on edges to block the attacker). Here, they use a double oracle approach and then prove the NP hardness of the defender and attacker oracle by reducing to set-cover and 3-SAT respectively. The defender oracle tries to find a pure strategy for a given attacker mixed-strategy, and the attacker tries to find a pure strategy for a given defender mixed-strategy. I'm trying to do something similar, but I'm not sure where to start, or even of it would be applicable in my case. For example, if we have an attacker with the following mixed-strategy $\{\{b, c\}, \{a, b, c,\}, \{a, b, d\}, \{b, c\}\}$ (where each one has an associated probability), the defender needs to find the optimal pure strategy that covers the most targets and gives him the most payoff. If we assume that the defender has 3 resources, the optimal pure strategy would be one of $\{\{a, b, c\}, \{a, b, d\}, \{a, c, d\}, \{b, c, d\}\}$. Here, it doesn't look like finding a cover would help, since the defender only has 3 resources. So I'm not sure where to go from here.EDIT:  Each target $t \in T$ has an associated payoff of $\tau_t$.
Finding an equivalent NP-complete instance for this game-theory problem
np hardness;gt.game theory;np;np complete;combinatorial game theory