Addressing Problem Size in Stackelberg Security Games.

Abstract

In this thesis we present algorithmic and modeling contributions for Stackelberg games that help address challenges due to problem size. Stackelberg games consider that one player, called leader, commits a strategy first and the other player, named follower, observes this strategy and plays a best response.

In this thesis we address the problem size that arises due to large leader action space, or because the interaction between the leader and the follower is evolving over time. In the last case, we model this interaction as a stochastic game.

In Chapter 1, we present a situation where a defender, the leader in the Stackelberg game, has to pair up resources to do patrol labor. In this case the set of pure strategies is exponentially large. We show a mixed integer programming formulation with polynomial number of variables and an exponentially sized set of constraints that can be separated in polynomial time. Moreover, we design sampling methods to retrieve implementable strategies for the defender. We show a case study in border patrolling labor of Carabineros de Chile. We show that our model with the cut-generation scheme outperforms other models, scaling up to large size instances.

In Chapter 2 we show a method to scale up an algorithm to compute optimal strategies in the context of opportunistic crime modelling, via a multi-layer clustering. Inside each cluster the algorithm can scale up in reasonable times. This methodology can be adapted to any problem where geographical aspects are important and the number of targets is large.

In Chapter 3 we face the problem of computing stationary policies that form a strong Stackelberg equilibrium in stochastic games. We find a family of instances where both, Value Iteration and Policy iteration converge to a strong Stackelberg equilibrium. We show via a counterexample that this is not always possible. Also, we show computationally that Value Iteration applied to security games instances seem to always converge to a unique strong Stackelberg equilibrium. Finally, we study mathematical programming formulations to compute a Stackelberg equilibrium in stochastic games.

Finally, in Chapter 4 we study a dynamic game, where a central agency aim to avoid the overexploitation of water, controlling the marginal cost of water extraction in agriculture. We model this situation as a stochastic game where the leader is the central agency and the followers are farmers who seek to maximize an instantaneous reward function at each period. In our setting, the leader maximizes the total discounted reward of the whole set of farmers. We find that we can achieve better levels of water in the steady-state by controlling the marginal cost. Finally, we propose a robust optimization approach to include uncertainty in our model.