Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 278, Issue 3, Pages 855-868Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2019.05.012
Keywords
Integer programming; Discrete optimization; Game theory; Bilevel optimization
Funding
- FNRS through a FRIA grant
- Fonds de la Recherche Scientique - FNRS [PDR T0098.18]
- CONICYT [FONDECYT-1171419]
- Complex Engineering Systems Institute [CONICYT-PIA-FB0816]
Ask authors/readers for more resources
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 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 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. (C) 2019 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available