A study of general and security Stackelberg game formulations

Abstract

In this paper, we analyze different mathematical formulations for general Stackelberg games (GSGs) and Stackelberg security games (SSGs). We consider GSGs in which a single leader commits to a utility maxi- mizing strategy knowing that p possible followers optimize their own utility taking the leader’s strategy into account. SSGs are a type of GSG that arise in security applications where the strategies of the leader consist of protecting a subset of targets and the strategies of the p followers consist of attacking a sin- gle target. We compare existing mixed integer linear programming (MILP) formulations for GSGs, ranking them according to the tightness of their linear programming (LP) relaxations. We show that SSG formu- lations are projections of GSG formulations and exploit this link to derive a new SSG MILP formulation that (i) has the tightest LP relaxation known among SSG MILP formulations and (ii) has an LP relaxation that coincides with the convex hull of feasible solutions in the case of a single follower. We present computational experiments empirically comparing the difficulty of solving the formulations in the general and security settings. The new SSG MILP formulation remains computationally efficient as problem size increases.