Addressing problem size in Stackelberg security games

Abstract

En esta tesis presentamos contribuciones algorítmicas y de modelación para Juegos de Stackelberg para problemas de gran tamaño. Juegos de Stackelberg es un tipo de juego en el que un jugador, llamado líder, utiliza una estrategia y luego el otro jugador, llamado seguidor, observa esta estrategia y juega una mejor respuesta. En el contexto de seguridad, el lider se le denomina defensor, y al seguidor se le denomina atacante. En el Capítulo 1, presentamos una situación en donde el defensor tiene que emparejar recursos para poder desarrollar labores de patrullaje. En este caso, el conjunto de estrategias puras es de tamaño exponencial. Presentamos una formulación en programación lineal entera mixta con un número polinomial de variables y un número exponencial de restricciones que pueden ser separadas en tiempo polinomial. Además, se diseñó un método de sampleo para recuperar estrategias implementables para el defensor. Por otra parte, mostramos un caso de estudio basado en el patrullaje fronterizo de Carabineros de Chile. Finalmente mostramos que nuestro modelo con el generación de cortes funciona considerablemente mejor que cualquier modelo en la literatura. En el Capítulo 2, se muestra una manera de escalar un algoritmo basado en Aprendizaje de M\'aquinas, realizando multiples capas de clusters de territorios en donde en cada cluster el algoritmo resuelve en tiempos razonables. En el Capítulo 3 se realiza un estudio sobre existencia de estrategias estacionarias que formen equilibrios de estrategias fuertes. Se detecta una familia de instancias en las cuales algoritmos de programación dinámica pueden encuentran el único equilibrio de Stackelberg fuerte. En este caso, se demuestra que Iteración de políticas y de valores convergen a los únicos valores de equilibrio. Se muestra vía contraejemplo que no siempre programación dinámica puede encontrar equilibrios de Stackelberg en estrategias estacionarias. Computacionalmente se encuentra que la estructura de juegos de seguridad presentara características que hace aplicable la teoría de operadores para encontrar equilibrios de Stackelberg. Finalmente se estudian formulaciones basadas en programación matemática para calcular equilibrios de Stackelberg. Finalmente, en el Capítulo 4 mostramos un juego dinámico, en donde un agente central tiene como objetivo la sobreexplotación de agua en el contexto agrícola, controlando los costos marginales de extracción que enfrentan los agricultores. Modelamos esta situación como un juego estocástico en donde se busca un equilibrio de Stackelberg en donde el líder es la agencia central, y los seguidores son los agricultores. Computacionalmente se encuentra que se pueden alcanzar mejores niveles de agua en el estado estacionario controlando los costos marginales a través de las tasas de descuento del líder, aunque los agricultures sean miopes. Finalmente, nosotros proponemos una formulación de programación robusta para incluir incertidumbre en nuestros modelos.