<p>Game theory involves the study of how self-interested agents interact in various settings. Perhaps the best-known game theoretic solution concept is that of Nash equilibrium. However, Nash equilibrium makes a number of assumptions, such as rationality of all of the players and the ability of the players to choose the same equilibrium when more than one exists. Because of these assumptions, it is unclear if simply solving for Nash equilibrium is always the correct thing to do. In some settings, one player can instead credibly commit to a strategy, and communicate this to the other player, before the other player can make a decision. This has become known as a Stackelberg game. Computing optimal strategies to commit to in normal-form or Bayesian Stackelberg games is a topic that has recently been gaining attention, in part due to the application of such algorithms in various security and law enforcement scenarios. My work on Stackelberg games falls into three main areas. </p><p>First, I focus on general games, where we give efficient algorithms and hardness results for Bayesian, extensive-form and stochastic games. In each of these settings we study the relationship between different modeling assumptions and the tractability of finding an optimal strategy to commit to. For Bayesian games our results are mainly negative; we show that not only are the problems here NP-hard, but in many cases they are also inapproximable. Our results for extensive-form games are more mixed; we are able to give polynomial time algorithms for four cases. However, we also show that if we relax the assumptions made in these four cases, then the problem usually becomes NP-hard. Finally, our results for stochastic games are again somewhat negative, as we show that the problem is NP-hard is most reasonable cases. However, here we are also able to give an approximation algorithm to compute optimal commitment strategies in a setting where correlation is allowed.</p><p>I next focus on Stackelberg security games. Stackelberg security games usually involve the scheduling of scarce defense resources to cover some subset of potential targets. We first study methods for going from marginal solutions (which ignore overlapping coverage between different schedules) to valid mixed commitment strategies in graphical settings. Here we are able to characterize two new classes of games where mixed strategies corresponding to the marginal probabilities are guaranteed to exist, and give algorithms for finding them. Next, we offer a simple model of interdependencies between nodes in a network based on probabilistic failure cascades, extending the well-known independent cascade model of the spread of infectious diseases or ideas. We give an algorithm for this problem and experimentally show that this algorithm scales to realistic security settings and outperforms the state of-the-art alternatives. Finally, we create an approach for optimal interdiction of attack plans. We show how to model an attack plan interdiction problem as a large-scale integer linear program similar to an integer programming approach for solving partial satisfaction planning problems. We also give several oracle-based approaches for solving this and then evaluate them experimentally. </p><p>Third, I analyze how much benefit a player can derive from commitment in various types of games, in a quantitative sense that is similar to known concepts such as the value of mediation and the price of anarchy. To do this we introduce and study the value of pure commitment (the benefit of committing to a pure strategy), the value of mixed commitment (the benefit of committing to a mixed strategy), and the mixed vs. pure commitment ratio (how much can be gained by committing to a mixed strategy rather than a pure one).</p> / Dissertation

No description available.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / O objetivo desse trabalho à estudarmos a controlabilidade aproximada, via estratÃgia de Stackeberg-Nash, para equaÃÃo do calor em domÃnios ilimitados, bem como para equaÃÃo da onda e para fluidos micropolares em domÃnios com fronteira variÃvel . / The purpose of this work is study the approximate controllability, via Stackelberg-Nash strategies to heat equation in unlimited domains, as well to wave equation and for micropolars fluids in domains with moving boundary.

De type parabolique et soumis à l’action d’un couple de contrôles (h, k) où h et k jouent des rôles différents ; le contrôle k étant de type "contrôlabilité" et h de type "contrôle optimal".Il est alors naturel de considérer un problème d’optimisation multi-critères. Il existe plusieurs façons d’étudier de tels problèmes. Nous proposons, dans cette thèse, le contrôle de Stackelberg. Il s’agit d’une notion d’optimisation hiérarchique avec, ici, h qui est le "Leader" et k le "Follower". / In this thesis, we are interested in evolution problems governed by parabolic equations subjected to the action of a pair of controls (h, k) where h and k play different roles : the control k being of "controllability" type and h of "optimal control" type.It is then natural to consider a multi-criteria optimization problem. There are several ways to study such problems. We propose in this thesis, the Stackelberg control which is a notion of hierarchical optimization with here, h which is the "Leader" and k the "Follower".

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. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Magíster en Gestión de Operaciones / 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.

The dissertation deals with the interplay of fiscal and monetary policy in face of uncertainty about the estimation of the true output gap. Theoretical framework of the dissertation set this interplay of monetary and fiscal policy into the realm of game theory, in particularly non-cooperative games of the Nash and Stackelberg equilibrium, respectively. The theoretical framework continued with a description of various methods used for estimation of potential output and output gap, with a special emphasis on methods used in both the Czech National Bank and Czech Ministry of Finance. In the applied part of the dissertation, I studied the interplay of monetary and fiscal policy in the case of Czech economy facing an uncertainty about the estimation of the true output gap. I studied the impact of this interplay on major macroeconomic variables and I tried to determine, which of these two policies plays the role of a leader and which plays the role of a follower in the case of Czech economic environment.

Ingeniero Civil Industrial / Ingeniero Civil Mecánico / Muchas empresas poseen numerosos equipos mecánicos que son ocupados en sus procesos productivos, donde el mantenimiento de ellos es realizado por equipos de técnicos propios llevando también los costos y la derivación de las capacidades y habilidades. Otras firmas, consideran la estrategia de externalizar ciertos procesos, relacionados o no, con el negocio que está abocada la empresa, delegando a terceras entidades la realización de estas. La externalización es normada por medio de contratos que clarifican deberes y obligaciones de las partes. En Chile la externalización u outsourcing en mantenimiento de activos fijos es una de las actividades estratégicas más recurridas, además de ser una de las mejor evaluadas (Menéndez [11]). Las fallas de los equipos son hechos aleatorios por lo que no pueden ser previstos y que afectan la producción de la empresa. Estas son modeladas probabilísticamente en relación a la política de mantenimiento, aquí mantenimiento perfecto. El tiempo en que los equipos están no operativos siendo intervenidos también afectan la producción. Desde la perspectiva del proveedor del servicio juegan a favor la cantidad de intervenciones correctivas y preventivas que realice, marginalizando por cada una de ellas, juega en contra, por concepto de multa, el tiempo excesivo en que los equipos no son devueltos operativos al cliente. Estas constituyen los beneficios para el cliente y desutilidad para el proveedor. En esta memoria se determinarán los precios que caracterizan a los contratos, tanto de la intervención preventiva como de la correctiva. Esto se logrará mediante la teoría de juegos como un problema principal-agente, donde el principal es el cliente, con alto poder de negociación y el proveedor será el agente con escaso poder en relación a una estrategia, sea esta: mantenimiento correctivo, preventivo (intervención por edad y por bloque de tiempo).

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)

In this dissertation, an important homeland security problem is studied. With the focus on wildfire and pyro-terrorism management. We begin the dissertation by studying the vulnerability of landscapes to pyro-terrorism. We develop a maximal covering based optimization model to investigate the impact of a pyro-terror attack on landscapes based on the ignition locations of fires. We use three test case landscapes for experimentation. We compare the impact of a pyro-terror wildfire with the impacts of naturally-caused wildfires with randomly located ignition points. Our results indicate that a pyro-terror attack, on average, has more than twice the impact on landscapes than wildfires with randomly located ignition points. In the next chapter, we develop a Stackelberg game model, a min-max network interdiction framework that identifies a fuel management schedule that, with limited budget, maximally mitigates the impact of a pyro-terror attack. We develop a decomposition algorithm called MinMaxDA to solve the model for three test case landscapes, located in Western U.S. Our results indicate that fuel management, even when conducted on a small scale (when 2% of a landscape is treated), can mitigate a pyro-terror attack by 14%, on average, comparing to doing nothing. For a fuel management plan with 5%, and 10% budget, it can reduce the damage by 27% and 43% on average. Finally, we extend our study to the problem of suppression response after a pyro-terror attack. We develop a max-min model to identify the vulnerability of initial attack resources when used to fight a pyro-terror attack. We use a test case landscape for experimentation and develop a decomposition algorithm called Bounded Decomposition Algorithm (BDA) to solve the problem since the model has bilevel max-min structure with binary variables in the lower level and therefore not solvable by conventional methods. Our results indicate that although pyro-terror attacks with one ignition point can be controlled with an initial attack, pyro-terror attacks with two and more ignition points may not be controlled by initial attack. Also, a faster response is more promising in controlling pyro-terror fires.