A study of general and security Stackelberg game formulations
Author
dc.contributor.author
Casorrán, Carlos
Author
dc.contributor.author
Fortz, Bernard
Author
dc.contributor.author
Labbé, Martine
Author
dc.contributor.author
Ordoñez Pizarro, Fernando
Admission date
dc.date.accessioned
2020-01-07T12:24:55Z
Available date
dc.date.available
2020-01-07T12:24:55Z
Publication date
dc.date.issued
2019
Cita de ítem
dc.identifier.citation
European Journal of Operational Research 278 (2019) 855–868
es_ES
Identifier
dc.identifier.other
10.1016/j.ejor.2019.05.012
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/173075
Abstract
dc.description.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.