A study of general and security Stackelberg game formulations
A study of general and security Stackelberg game formulations
复制标题
DOI：
10.1016/j.ejor.2019.05.012
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Carlos Casorrán;B. Fortz;M. Labbé;F. Ordóñez
中科院分区：
文献类型：
--
作者：
Carlos Casorrán;B. Fortz;M. Labbé;F. Ordóñez
本文分析了一般Stackelberg对策(GSG)和Stackelberg安全对策(SSGs)的不同数学公式。我们考虑GSG，其中单个领导者致力于效用最大化的策略，知道可能的追随者在考虑领导者的策略的情况下优化自己的效用。SSG是出现在安全应用中的一种GSG，其中领导者的策略包括保护目标的子集，而追随者的策略包括攻击单个目标。我们比较了现有的混合整数线性规划(MILP)公式，并根据它们的线性规划(LP)松弛的紧性对它们进行了排序。我们证明了SSG公式是GSG公式的投影，并利用这一联系导出了一个新的SSG MILP公式，它(I)具有已知的SSG MILP公式中最紧的Lp松弛，(Ii)在单个跟随者的情况下具有与可行解的凸壳重合的Lp松弛。我们提供了计算实验，经验性地比较了在一般设置和安全设置下求解公式的难度。随着问题规模的增大，新的SSG MILP公式在计算上仍然有效。
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 maximizing strategy knowing thatppossible 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 thepfollowers consist of attacking a single 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 formulations 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.