Novel formulations for general and security Stackelberg games

Carlos Casorrán 1, 2 Bernard Fortz 1, 2 Martine Labbé 1, 2 Fernando Ordóñez 3
1 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : In this paper we analyze general Stackelberg games (SGs) and Stackelberg security games (SSGs). SGs are hierarchical adversarial games where players select actions or strategies to optimize their payoffs in a sequential manner. SSGs are a type of SGs that arise in security applications, where the strategies of the player that acts first consist in protecting subsets of targets and the strategies of the followers consist in attacking one of the targets. We review existing mixed integer optimization formulations in both the general and the security setting and present new formulations for both settings. We compare the SG formulations and the SSG formulations both from a theoretical and a computational point of view. Our theoretical results show that the new formulations provide tighter linear relaxations. Our computational experiments show that the new formulations give better solution times.
Type de document :
Pré-publication, Document de travail
2016
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01429265
Contributeur : Bernard Fortz <>
Soumis le : samedi 7 janvier 2017 - 15:16:26
Dernière modification le : mardi 17 avril 2018 - 09:04:54
Document(s) archivé(s) le : samedi 8 avril 2017 - 12:13:12

Fichier

PaperCasorran.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01429265, version 1

Collections

Citation

Carlos Casorrán, Bernard Fortz, Martine Labbé, Fernando Ordóñez. Novel formulations for general and security Stackelberg games. 2016. 〈hal-01429265〉

Partager

Métriques

Consultations de la notice

196

Téléchargements de fichiers

68