Formulations and Algorithms for General and Security Stackelberg Games - Archive ouverte HAL Access content directly
Theses Year : 2017

Formulations and Algorithms for General and Security Stackelberg Games

Formulations et algorithmes pour les jeux de Stackelberg et les jeux de sécurité

(1, 2)
1
2

Abstract

General Stackelberg games (GSG) confront two contenders, each wanting to optimize their rewards. One of the players, referred to as the leader, can commit to a given action or strategy first, and the other player, referred to as the follower, then responds by selecting an action or strategy of his own. The objective of the game is for the leader to commit to a reward-maximizing strategy, anticipating that the follower will best respond.Finding an optimal mixed strategy for the leader in a GSG is NP-hard when the leader faces one out of a group of several followers and polynomial when there exists a single follower. Additionally, GSGs in which the strategies of the leader consist in covering a subset of at most $m$ targets and the strategies of the followers consist in attacking some target, are called Stackelberg security games (SSG) and involve an exponential number of pure strategies for the leader.The goal of this thesis is to provide efficient algorithms to solve GSGs and SSGs. These algorithms must not only be able to produce optimal solutions quickly, but also be able to solve real life, and thus large scale, problems efficiently. To that end, the main contributions of this thesis are divided into three parts:First, a comparative study of existing mixed integer linear programming (MILP) formulations is carried out for GSGs, where the formulations are ranked according to the tightness of their linear programming (LP) relaxations. A formal theoretical link is established between GSG and SSG formulations through projections of variables and this link is exploited to extend the comparative study to SSG formulations. A new strong SSG MILP formulation is developed whose LP relaxation is shown to be the tightest among SSG formulations. When restricted to a single attacker type, the new SSG formulation is ideal, i.e., the constraints of its LP relaxation coincide with its convex hull of feasible solutions. Computational experiments show that the tightest formulations in each setting are the fastest. Notably, the new SSG formulation proposed is competitive with respect to solution time, and due to the tightness of its LP relaxation, it is better suited to tackle large instances than competing formulations.Second, the bottleneck encountered when solving the formulations studied in the first part of the thesis is addressed: The tightest formulations in each setting have heavy LP relaxations which can be time-consuming to solve and thus limit the effectiveness of the formulations to tackle instances. To address this issue, in both the general and the security case, Benders cuts from the LP relaxation of the tightest MILP formulations are embedded into a Cut and Branch scheme on a sparse equivalent formulation in each setting. By combining the tightness of the bound provided by the strong formulations with the resolution speed of the formulations, the proposed algorithm efficiently solves large GSG and SSG instances which were out of the scope of previous methods.Third, a special type of SSG, defined on a network, is studied, where the leader has to commit to two coverage distributions, one over the edges of the network and one over the targets, which are contained inside the nodes. A particular case of this SSG is used to tackle a real life border patrol problem proposed by the Carabineros de Chile in which the use of their limited security resources is optimized while taking into account both global and local planning considerations. A methodology is provided to adequately generate the game's parameters. Computational experiments show the good performance of the approach and a software application developed for Carabineros to schedule their border resources is described.
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.
Fichier principal
Vignette du fichier
Tesis.pdf (12.76 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

tel-01666449 , version 1 (18-12-2017)

Identifiers

  • HAL Id : tel-01666449 , version 1

Cite

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. ⟨NNT : ⟩. ⟨tel-01666449⟩
377 View
378 Download

Share

Gmail Facebook Twitter LinkedIn More