Formulations and Algorithms for General and Security Stackelberg Games

Carlos Casorrán-Amilburu 1, 2
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
Résumé : Les jeux de Stackelberg (GSG) affrontent deux prétendants, chacun voulant optimiser ses récompenses. Un des joueurs, appelé le leader, peut d'abord s'engager dans une action ou une stratégie donnée, et l'autre joueur, appelé le suiveur, répond alors en sélectionnant une action ou une stratégie qui lui est propre. L'objectif du jeu est que le leader s'engage dans une stratégie de maximisation de la récompense, anticipant que le suiveur répondra le mieux. Trouver une stratégie mixte optimale pour le leader dans un GSG est NP-difficile quand le leader fait face à un groupe de plusieurs suiveurs et polynomial lorsqu'il existe un seul suiveur. De plus, les GSG dans lesquels les stratégies du leader consistent à couvrir un sous-ensemble de cibles de $ m $ et les stratégies des suiveurs consistent à attaquer une cible, sont appelées Stackelberg security games (SSG) et impliquent un nombre exponentiel de stratégies pures Le but de cette thèse est de fournir des algorithmes efficaces pour résoudre les GSG et les SSG. Ces algorithmes doivent non seulement être capables de produire rapidement des solutions optimales, mais aussi être capables de résoudre efficacement les problèmes réels et donc à grande échelle. À cette fin, les principales contributions de cette thèse sont divisées en trois parties: Premièrement, une étude comparative des formulations MILP (mixed integer programmation) existantes est réalisée pour les GSG, où les formulations sont classées en fonction de la qualité de leur relaxation linéaire. Un lien théorique formel est établi entre les formulations GSG et SSG à travers des projections de variables et ce lien est exploité pour étendre l'étude comparative aux formulations SSG. Une nouvelle formulation forte de SSG MILP est développée, dont la relaxation LP est la plus forte parmi les formulations SSG. Lorsqu'elle est limitée à un seul type d'attaquant, la nouvelle formulation SSG est idéale, c'est-à-dire que les contraintes de sa relaxation LP coïncident avec sa coque convexe de solutions réalisables. Des expériences computationnelles montrent que les formulations les plus serrées dans chaque configuration sont les plus rapides. Notamment, la nouvelle formulation de SSG proposée est compétitive en ce qui concerne le temps de solution, et en raison de l'étroitesse de sa relaxation LP, elle est mieux adaptée aux grandes instances que les formulations concurrentes. Deuxièmement, le goulot d'étranglement rencontré lors de la résolution des Une partie de la thèse est abordée: Les formulations les plus serrées dans chaque contexte ont de fortes relaxations LP qui peuvent prendre beaucoup de temps à résoudre et donc limiter l'efficacité des formulations pour s'attaquer aux cas. Pour résoudre ce problème, en général et en matière de sécurité, les d«compositions de Benders de la relaxation LP des formulations MILP les plus strictes sont intégrées dans un schéma Cut & Branch sur une formulation équivalente clairsemée dans chaque paramètre. En combinant la force des formulations avec la vitesse de résolution des formulations, l'algorithme proposé résout efficacement les grandes instances GSG et SSG qui étaient hors de portée des méthodes précédentes. Troisièmement, un type spécial de SSG, défini sur un réseau est étudié, où le leader doit s'engager sur deux distributions de couverture, l'une sur les bords du réseau et l'autre sur les cibles, qui sont contenues à l'intérieur des nœuds. Un cas particulier de cette SSG est utilisé pour résoudre un problème de patrouille frontalière réel proposé par les carabiniers du Chili dans lequel l'utilisation de leurs ressources de sécurité limitées est optimisée tout en tenant compte des considérations de planification à la fois globales et locales. Une méthodologie est fournie pour générer correctement les paramètres du jeu. Des expériences computationnelles montrent la bonne performance de l'approche et une application logicielle développée pour les carabiniers pour planifier leurs ressources frontalières est décrite.
Type de document :
Thèse
Operations Research [cs.RO]. Université libre de Bruxelles; Universidad de Chile, 2017. English
Liste complète des métadonnées

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

https://hal.inria.fr/tel-01666449
Contributeur : Bernard Fortz <>
Soumis le : lundi 18 décembre 2017 - 13:28:56
Dernière modification le : mardi 3 juillet 2018 - 11:36:03

Fichier

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

Identifiants

  • HAL Id : tel-01666449, version 1

Collections

Citation

Carlos Casorrán-Amilburu. Formulations and Algorithms for General and Security Stackelberg Games. Operations Research [cs.RO]. Université libre de Bruxelles; Universidad de Chile, 2017. English. 〈tel-01666449〉

Partager

Métriques

Consultations de la notice

401

Téléchargements de fichiers

228