Learning Optimal Commitment to Overcome Insecurity
Game-theoretic algorithms for physical security have made an impressive realworld impact. These algorithms compute an optimal strategy for the defender to commit to in a Stackelberg game, where the attacker observes the defender's strategy and best-responds. In order to build the game model, though, the payoffs of potential attackers for various outcomes must be estimated; inaccurate estimates can lead to significant inefficiencies. We design an algorithm that optimizes the defender's strategy with no prior information, by observing the attacker's responses to randomized deployments of resources and learning his priorities. In contrast to previous work, our algorithm requires a number of queries that is polynomial in the representation of the game.
security games is that even in the simplest security game, the number of pure defender strategies is exponential in the representation of the game. For example, if each of the defender's resources can protect one of two potential targets, there is an exponential number of ways in which resources can be assigned to targets. 1 Our approach and results. We design an algorithm that learns an (additively) -optimal strategy for the defender with probability 1 − δ, by asking a number of queries that is polynomial in the representation of the security game, and logarithmic in 1/ and 1/δ. Our algorithm is completely different from that of Letchford et al. [8]. Its novel ingredients include:
• We work in the space of feasible coverage probability vectors, i.e., we directly reason about the probability that each potential target is protected under a randomized defender strategy. Denoting the number of targets by n, this is an n-dimensional space. In contrast, Letchford et al. [8] study the exponential-dimensional space of randomized defender strategies. We observe that, in the space of feasible coverage probability vectors, the region associated with a specific best response for the attacker (i.e., a specific target being attacked) is convex.
• To optimize within each of these convex regions, we leverage techniques -developed by Tauman Kalai and Vempala [14] -for optimizing a linear objective function in an unknown convex region using only membership queries. In our setting, it is straightforward to build a membership oracle, but it is quite nontrivial to satisfy a key assumption of the foregoing result: that the optimization process starts from an interior point of the convex region. We do this by constructing a hierarchy of nested convex regions, and using smaller regions to obtain interior points in larger regions.
• We develop a method for efficiently discovering new regions. In contrast, Letchford et al. [8] find regions (in the high-dimensional space of randomized defender strategies) by sampling uniformly at random; their approach is inefficient when some regions are small.
This paper considers the problem of learning an attacker’s payoffs in a security game. In deployed application, game-theoretic solutions to security games have had much success but crucially rely upon experts to provide the payoffs for the attackers (terrorists, drug smugglers, etc) to the equilibrium solvers. This paper suggests replacing this expert-provided knowledge by learning the payoffs from the attacker by observing attacker responses in repeated plays of the attacker-defender game. The authors make use of techniques by Kalai and Vempala which uses an initial feasible point and a membership oracle to optimize the defender’s objective. To do so, the authors prove in this paper that the optimization region is reasonably well-behaved, most notably that there exists initial points that are sufficiently far from the boundaries of the optimization region. Using all of this, they show that the optimal defender strategy can be computed with a polynomial number of queries (plays of the security game), improving over the previous result of an exponential number of plays. On the high level, I think this paper has a good idea of attempting to correct for the uncertainty in payoff knowledge and uses sophisticated techniques in their chosen approach. If the best way to correct for this uncertainty was to explore the strategy space and find the exact optimal solution, then this paper does offer a significant improvement over the prior method to do so. Indeed, the techniques in this paper is non-trivial and has some nice applications of convex optimization methods to game theoretic settings, i.e. the interpretation of the attacker’s best response as the membership oracle. However, I’m not convinced that this approach is the right way of solving this problem and the authors don’t make an argument for it. Its not clear that a polynomial number of plays of this security game represents a reasonable amount of computation in the studied contexts. What is the rate that such games occur? Do attacker utility functions remain constant for long enough to actually learn in this context? I think this work could have benefited from empirical analysis in a couple of ways. First, I would have been very interested to see the practical convergence rate on some typical instances of these games (for example, instances of the games used for the empirical testing in [1]). Perhaps the convergence rate is practically very fast, so the concern about the number of games played is not necessary. Second, it would have been great to see the proposed method compared to some other strategies used to address this uncertainty like the robust optimization methods or distribution knowledge methods as mentioned by the authors in the introduction. Maybe its the case that the method in this paper finds such a better solution that its worthwhile to wait for the convergence of this algorithm. Finally, for realistic scenarios, is finding the exact optimal solution is the right objective, especially if the defender sacrifices a lot of interim utility in order to find it? A concept like regret might be better suited as it allows for the examination of the trade-offs between exploring the entire strategy-space versus exploiting good strategies that may be learned very quickly. [1]: Jain, Manish, et al. "Software assistants for randomized patrol planning for the lax airport police and the federal air marshal service." Interfaces 40.4 (2010): 267-290.