An Efficient Heuristic for Security Against Multiple Adversaries

In adversarial multiagent domains, security, commonly de-fined as the ability to deal with intentional threats from other agents, is a critical issue. This paper focuses on domains where these threats come from unknown adversaries. These domains can be modeled as Bayesian games; much work has been done on finding equilibria for such games. However, it is often the case in multiagent security domains that one agent can commit to a mixed strategy which its adversaries observe before choosing their own strategies. In this case, the agent can maximize reward by finding an optimal strategy, without requiring equilibrium. Previous work has shown this problem of optimal strategy selection to be NP-hard. There-fore, we present a heuristic called ASAP, with three key ad-vantages to address the problem. First, ASAP searches fo