Publications

Security games with surveillance cost and optimal timing of attack execution

An, Bo; Brown, Matthew; Vorobeychik, Yevgeniy V.; Tambe, Milind

Stackelberg games have been used in several deployed applications to allocate limited resources for critical infrastructure protection. These resource allocation strategies are randomized to prevent a strategic attacker from using surveillance to learn and exploit patterns in the allocation. Past work has typically assumed that the attacker has perfect knowledge of the defender's randomized strategy or can learn the defender's strategy after conducting a fixed period of surveillance. In consideration of surveillance cost, these assumptions are clearly simplistic since attackers may act with partial knowledge of the defender's strategies and may dynamically decide whether to attack or conduct more surveillance. In this paper, we propose a natural model of limited surveillance in which the attacker dynamically determine a place to stop surveillance in consideration of his updated belief based on observed actions and surveillance cost. We show an upper bound on the maximum number of observations the attacker can make and show that the attacker's optimal stopping problem can be formulated as a finite state space MDP. We give mathematical programs to compute optimal attacker and defender strategies. We compare our approaches with the best known previous solutions and experimental results show that the defender can achieve significant improvement in expected utility by taking the attacker's optimal stopping decision into account, validating the motivation of our work. Copyright © 2013, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.