A study of general and security Stackelberg game formulations

Casorrán, Carlos; Fortz, Bernard; Labbé, Martine; Ordóñez, Fernando

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1016/j.ejor.2019.05.012

Titre :

A study of general and security Stackelberg game formulations

Auteur(s) :

Casorrán, Carlos [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Fortz, Bernard [Auteur]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Ordóñez, Fernando [Auteur]
Departamento de Ingenieria Industrial [Santiago] [DII]

Titre de la revue :

European Journal of Operational Research

Pagination :

855 - 868

Éditeur :

Elsevier

Date de publication :

2019

ISSN :

0377-2217

Mot(s)-clé(s) en anglais :

Integer programming
discrete optimization
game theory
bilevel optimization

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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 one of p possible followers optimizes its own utility taking this leader strategy into account. SSGs are a type of GSG that arise in security applications where the strategies of the leader consist in protecting subsets of targets and the strategies of the p followers consist in attacking a single target. We compare existing mixed integer linear programming (MILP) formulations for GSGs, sorting 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) its LP relaxation 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 is computationally efficient, in particular as the problem size increases.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :