Algoritmo heurístico para juego de seguridad de Stackelberg en una red

Abstract

El objetivo principal de este trabajo es proporcionar un algoritmo que resuelve instancias de gran tamaño para problemas de juegos de seguridad de Stackelberg con un énfasis en reducir el número de recursos necesarios requeridos para calcular dicha solución. Para ello se utilizan los principios de generación de columnas para desarrollar un algoritmo que procede mediante la resolución de un problema más pequeño (menor número de restricciones). Entonces, de forma iterativa, añadimos restricciones hasta que el problema llega a las condiciones de parada definidas. Básicamente, partimos de un problema secundario del original con dos jugadores que juegan a la seguridad y cuentan con un espacio de estrategia limitado, ya que este considera sólo un número limitado de restricciones. Iterativamente, verificamos si algún jugador le gustaría cambiar su estrategia con el fin de incrementar sus utilidades, añadimos la estrategia candidata y resolvemos una vez más. Esto sugiere un método de descomposición que es capaz de estimar el conjunto mínimo de restricciones a tener en cuenta con el fin de encontrar también la solución óptima para el problema global. En el transcurso de nuestros estudios identificamos que el proceso de iteración no siempre encuentra la solución óptima para el problema global. Luego, proporcionamos un análisis y caracterización de la estructura de las funciones de utilidad para ambos jugadores con el fín comprender más la dinámica de los jugadores e identificar las situaciones en las que la solución óptima global efectivamente es encontrada. Más tarde, se presenta una implementación que incluye datos del mundo real a través de una red en el centro de Santiago, Chile. Las recompensas se calcularon teniendo en cuenta el promedio histórico robado en cada lugar y un valor estimado de la falta de voluntad de ir a la cárcel para efectos de los asaltantes. Finalmente, comparamos nuestro algoritmo con los demás ya la literatura en escenarios similares. Mostramos que nuestros métodos nos permiten ofrecer de manera eficiente soluciones razonables para los problemas de seguridad en tamaño del mundo real. Además comparamos nuestros resultados con los resultados utilizando la metodología estándar de resolución de problemas lineales y mostramos que se pueden reducir ampliamente la necesidad de recursos computacionales y en algunos casos, el tiempo de ejecución para llegar a la solución.