Gradient Methods for Stackelberg Games

Abstract

Stackelberg games are two-stage games in which the first player (called the leader) commits to a strategy, after which the other player (the follower) selects a best-response. These types of games have seen numerous practical application in security settings, where the leader (in this case, a defender) must allocate resources to protect various targets. Real world applications include the scheduling of US federal air marshals to international flights, and resource allocation at LAX airport. However, the best known algorithm for solving general Stackelberg games requires solving Integer Programs, and fails to scale beyond a few (significantly smaller than 100) number of leader actions, or follower types. In this paper, we present a new approach for solving large Stackelberg games in the security settings, using techniques from AI. Large-scale control problems are often times solved by restricting the controller to a rich, but parameterized, class of policies; the optimal control can then be computed using Monte Carlo gradient methods. We demonstrate that the same approach can be taken in a strategic setting. We evaluate our strategies empirically, demonsrating they have negligible regret against the leader's true equilibrium strategy, while scaling to large games.