<p>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. </p>

<p>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 &lt; |T|$. The defender can place at most one resource on one target to cover it.</p>

<p>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)$. </p>

<p>The attacker succeeds if <em>all</em> the targets he attacks are not covered by the defender. If <em>at least one</em> of the targets that he attacks <em>is</em> covered by the defender, he fails. </p>

<p>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. </p>

<p>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).</p>

<p>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.</p>

<p>I read <a href="https://www.cs.duke.edu/~conitzer/graph_securityAAMAS11.pdf" rel="nofollow">this</a> 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. </p>

<p>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.</p>

<p><strong>EDIT:</strong>  Each target $t \in T$ has an associated payoff of $\tau_t$.</p>

CC BY-SA 3.0
2015-04-20T03:56:47.453Z
Ah, I forgot to mention that this is a Stackelberg game; the defender can commit to an optimal mixed-strategy. I think my question is more about how I would deal with such a huge strategy space. In the paper I linked to, they are also dealing with a 2-person zero-sum game and aiming to find an optimal mixed strategy for the defender. They also showed that finding a pure strategy for the defender given the attacker's mixed-strategy (and vice versa) is NP-hard. I'm trying to do the same here.
Vivin Paliath
CC BY-SA 3.0
2015-04-20T08:47:57.027Z
I must be missing something here.. If you consider a zero-sum game where the attacker payoff to be 1 if the attack succeeds, there is no point in attacking multiple targets.. The strategy of attacking $\{a,b\}$ is dominated by simply attacking $a$, or $b$. Moreover, since targets are symmetric, the best the attacker could do is pick one randomly, and the defender has nothing more than picking $k$ random targets to defend..
R B
CC BY-SA 3.0
2015-04-20T09:16:50.830Z
That's a good point. I think I need to associate a payoff with each target then, such that the targets are not symmetric. Or, I can just define the payoff for the attacker if he succeeds, as the total number of targets he attacked. Otherwise, he gets 0. Does that make more sense?
Vivin Paliath
<np-hardness><gt.game-theory><np><np-complete><combinatorial-game-theory>
Finding an equivalent NP-complete instance for this game-theory problem
Vivin Paliath
# Finding an equivalent NP-complete instance for this game-theory problem

(Asked by: username_0 on 2015-04-20)

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](https://www.cs.duke.edu/~conitzer/graph_securityAAMAS11.pdf) 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$.

**Tags:** np-hardness, gt.game-theory, np, np-complete, combinatorial-game-theory

> **Comments:**
> **username_0**: Ah, I forgot to mention that this is a Stackelberg game; the defender can commit to an optimal mixed-strategy. I think my question is more about how I would deal with such a huge strategy space. In the paper I linked to, they are also dealing with a 2-person zero-sum game and aiming to find an optimal mixed strategy for the defender. They also showed that finding a pure strategy for the defender given the attacker's mixed-strategy (and vice versa) is NP-hard. I'm trying to do the same here.  
> **username_1**: I must be missing something here.. If you consider a zero-sum game where the attacker payoff to be 1 if the attack succeeds, there is no point in attacking multiple targets.. The strategy of attacking $\{a,b\}$ is dominated by simply attacking $a$, or $b$. Moreover, since targets are symmetric, the best the attacker could do is pick one randomly, and the defender has nothing more than picking $k$ random targets to defend..  
> **username_0**: That's a good point. I think I need to associate a payoff with each target then, such that the targets are not symmetric. Or, I can just define the payoff for the attacker if he succeeds, as the total number of targets he attacked. Otherwise, he gets 0. Does that make more sense?  

---

## 0 answers

