Magíster en Gestión de Operaciones / Uno de los desafíos importantes que enfrenta un grupo de defensores corresponde a su coordinación con el objetivo de poder brindar una mayor protección al sistema que defienden. En este trabajo, se estudia el desarrollo de algoritmos eficientes y garantías de optimalidad para un modelo de juego de seguridad de Stackelberg que resuelve la coordinación de múltiples recursos defensivos descentralizados. Este modelo asume la presencia de incertidumbre en las acciones efectuadas por cada recurso defensor y la ausencia de comunicación entre ellos. En específico, el modelo de juego de seguridad de este trabajo consiste en resolver un número pequeño de problemas de programación lineal, que se pueden resolver mediante un esquema de generación de columnas. El subproblema de dicha generación de columnas corresponde a la resolución de un problema de decisión markoviana descentralizado. Estos problemas de decisión markoviana descentralizados son de difícil solución; sin embargo, es posible resolver estos subproblemas mediante heurísticas, dando como resultado un enfoque capaz de obtener soluciones subóptimas para el modelo de juego de seguridad. Se presentan diversas heurísticas para la resolución de dicho subproblema, y se realiza un estudio para evaluar su uso dentro del esquema de generación de columnas. Este estudio consiste en la simulación de instancias de prueba aleatorias para evaluar el desempeño, tanto en el valor del resultado obtenido como en el tiempo de resolución de cada heurística. Se presenta una cota para el valor óptimo de un problema de decisión markoviana descentralizado que se obtiene al resolver un problema de optimización entero relacionado. Nuestros estudios computacionales muestran que esta cota es menor a un 10% del valor óptimo. Se presentan además, variantes del enfoque de generación de columnas, buscando reducir los tiempos de solución sin sacrificar calidad de la respuesta. Estos enfoques también están basados en generación de columnas y otorgan una solución subóptima al problema planteado. Con el objetivo de evaluar el comportamiento de los enfoques presentados, se recurre a la simulación de instancias aleatorias y una instancia inspirada en parte de la red de metro de Santiago. Además, con el objetivo de poder evaluar las soluciones subóptimas otorgadas por dichos enfoques, se desarrolla un método que permite obtener garantías para la solución del problema de generación de columnas. En específico, el algoritmo desarrollado permite resolver el problema de patrullar descentralizadamente una red conformada por 16 estaciones de metro, durante 12 períodos de tiempo y utilizando 6 recursos. Esta solución se obtiene, en promedio, en un tiempo de 400 [s] y con una garantía del 20%. / Este trabajo ha sido parcialmente financiado por CONICYT-PCHA/Magíster Nacional/2015 - 22152053 Powered@NLHPC: Esta investigación fue parcialmente apoyada por la infraestructura de supercómputo del NLHPC (ECM-02)

Doctor en Sistemas de Ingeniería / 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. / Este trabajo ha sido parcialmente financiado por CONICYT

Magíster en Gestión de Operaciones / Las agencias de seguridad alrededor del mundo enfrentan el reto de proteger objetivos sensibles, tales como aeropuertos, puertos u otras infraestructuras críticas. Para ello, toman acciones preventivas y asignan recursos de defensa a patrullar un objetivo. El problema es que, por lo general, los recursos a su disposición son limitados y la cantidad de objetivos a defender puede llegar a ser muy grande, por lo que la labor de asignación de recursos puede llegar a ser muy compleja y costosa en términos computacionales. Para enfrentar este problema, un enfoque es utilizar técnicas de teoría de juegos para captar el razonamiento entre el defensor y los atacantes o criminales, específicamente se usan los Juegos de Seguridad de Stackelberg, ó SSG por sus siglas en inglés. Los SSGs son parte esencial de varias aplicaciones actualmente en uso por diversas agencias de seguridad en Estados Unidos y su éxito ha generado que el interés por estos aumente, por lo que muchos autores han dado diversas contribuciones sobre este tema. Sin embargo, uno de los puntos que aún es un tema abierto de estudio es la escalabilidad de las formulaciones, ya que los modelos existentes tienen un bajo desempeño cuando el número de tipos de atacantes es grande, lo que resulta inadecuado para problemas complejos del mundo real. Una instancia cualquiera de SSG tiene muchas posibles formulaciones, este trabajo de tesis estudia tres: (SSMG), (DOBSS-SSG) y (MIP-SSG). Estas formulaciones son equivalentes entre sí, que tienen diferencias en términos de tamaño y fortaleza, lo que hace que no sea evidente cúal es la de mejor desempeño, pero todas resuelven el problema, en ámbitos con múltiples tipos de atacantes, aprovechando la estructura propia de los juegos de seguridad donde la utilidad de los jugadores depende solamente de si el objetivo atacado esta protegido o no, logrando de esta manera una representación compacta y acelerando los tiempos de ejecución. Este trabajo describe y analiza cada una de estas formulaciones comparándolas tanto desde el punto de vista de modelación como computacional. En el aspecto de modelación se muestra el efecto de incorporar una representación logarítmica de las las variables enteras y el efecto de restringir el espacio de soluciones. En el aspecto computacional, el enfoque esta en el rendimiento, en términos del tiempo de ejecución requerido para hallar una solución, sobre un conjunto amplio de instancias, poniendo énfasis en escalar tanto el número de tipos de atacantes como el número de objetivos a defender. Se compara las formulaciones entre sí y se detalla las ventajas de estas sobre las formulaciones presentes en la literatura.