Security Games with Limited Surveillance: An Initial Report

Stackelberg games have been used in several deployed applications of game theory to make recommendations for allocating limited resources for protecting critical infrastructure. The resource allocation strategies are randomized to prevent a strategic attacker from using surveillance to learn and exploit patterns in the allocation. An important limitation of previous work on security games is that it typically assumes that attackers have perfect surveillance capabilities, and can learn the exact strategy of the defender. We introduce a new model that explicitly models the process of an attacker observing a sequence of resource allocation decisions and updating his beliefs about the defender's strategy. For this model we present computational techniques for updating the attacker's beliefs and computing optimal strategies for both the attacker and defender, given a specific number of observations. We provide multiple formulations for computing the defender's optimal strategy, including non-convex programming and a convex approximation. We also present an approximate method for computing the optimal length of time for the attacker to observe the defender's strategy before attacking. Finally, we present experimental results comparing the efficiency and runtime of our methods.