The 16th of October, 2017, Carlos Casorrán Amilburu succesfully defended his thesis titled
Formulations and Algorithms for General and Security Stackelberg Games.
The jury was composed by:
- Yves Crama, Professor, Université de Liège
- Bernard Fortz, Professor, Université Libre de Bruxelles
- Martine Labbé, Professor, Université Libre de Bruxelles
- Patrice Marcotte, Professor, Université de Montréal
- Thierry Massart, Professor, Université Libre de Bruxelles
- Fernando Ordóñez, Professor, Universidad de Chile
- Richard Weber, Professor, Universidad de Chile
Thesis 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.
This thesis is dedicated to the algorithmic and theoretical analysis of an important class of problems related to security. The framework chosen to study said problems is that of Game Theory and, more specifically, Stackelberg games. The main contributions of the thesis are theoretical, algorithmic and practical. We study mathematical formulations and enhance them through the use of well-established integer programming techniques, we exploit problem structure to develop valid inequalities for the formulations and develop decomposition approaches and we present a Stackelberg approach to tackle a real-life border patrol problem along the border of the northernmost province of Chile. The theoretical and algorithmic advancements are aimed at speeding up problem resolution with respect to state of the art methods and to scale-up the sizes of the instances that can be currently solved.
