1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ What exactly are you looking for as the solution? When you say that you are looking for the optimal mixed strategy for the defender, it sounds like what you mean is the Nash equilibrium. Of course, if the game is a 2-person finite zerosum game with perfect information, then there is a single complete solution to the game (see: en.wikipedia.org/wiki/Minimax#Minimax_theorem ). Ordinarily (when the game isn't 2-person/zerosum), finding the mixed-strategy Nash equilibrium is PPAD-complete...but this really depends on how the game is represented in the input. $\endgroup$ – Philip White Apr 20 '15 at 3:51
  • $\begingroup$ 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. $\endgroup$ – Vivin Paliath Apr 20 '15 at 3:56
  • $\begingroup$ 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.. $\endgroup$ – R B Apr 20 '15 at 8:47
  • $\begingroup$ 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? $\endgroup$ – Vivin Paliath Apr 20 '15 at 9:16
  • $\begingroup$ I don't know much about Stackelberg games, but according to the Wikipedia page, such games appear to be merely a certain kind of sequential move game. So you're still looking for the Nash equilibrium; also, the "huge strategy set" can be handled with an algorithm for Nash equilibrium computation, as I mentioned. While (I think that) you are right that pure-strategy Nash equilibrium computation is generally NP-complete, even PPAD mixed-strategy Nash equilibrium can be approximated in polytime. See: dl.acm.org/citation.cfm?id=1483719 $\endgroup$ – Philip White Apr 20 '15 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.