Hierarchical planning in security games: a game theoretic approach to strategic, tactical and operational decision making

In the presence of an intelligent adversary, game theoretic models such as security games, have proven to be effective tools for mitigating risks from exploitable gaps in protection and security protocols, as they model the strategic interaction between an adversary and defender, and allow the defender to plan the use of scarce or limited resources in the face of such an adversary. However, standard security game models have limited expressivity in the types of planning they allow the defender to perform, as they look only at the deployment and allocation of a fixed set of security resources. This ignores two very important planning problems which concern the strategic design of the security system and resources to deploy as well as the usability and implementation of the security protocols. When these problems appear in real world systems, significant losses in utility and efficiency of security protocols can occur if they are not dealt with in a principled way. ❧ To address these limitations, in this thesis I introduce a new hierarchical structure of planning problems for security games, dividing the problem into three levels of planning (i) Strategic Planning, which considers long term planning horizons, and decisions related to game design which constrain the possible defender strategies, (ii) Tactical Planning, which considers shorter term horizons, dealing with the deployment of resources, and selection of defender strategies subject to strategic level constraints and (iii) Operational Planning, dealing with implementation of strategies in real world setting. ❧ First, focusing on Strategic Planning, I address the design problem of selecting a set of resource and schedule types. I introduce a new yet fundamental problem, the Simultaneous Optimization of Resource Teams and Tactics (SORT) which models the coupled problem of both strategic and tactical planning, optimizing over both game design with respect to selection of resource types, as well as their deployment actual in the field. I provide algorithms for efficiently solving the SORT problem, which use hierarchical relaxations of the optimization problem to compute these strategic level investment decisions. I show that this more expressive model allows the defender to perform more fine grained decision making that results in significant gains in utility. Second, motivated by the relevance and hardness of security games with resource heterogeneity, I also address challenges in tactical planning by providing a framework for computing adaptive strategies with heterogeneous resources. Lastly, I look at the problem of operational planning, which has never been formally studied in the security game literature. I propose a new solution concept of operationalizable strategies, which randomize over an optimally chosen subset of pure strategies whose cardinality is selected by the defender. I show hardness of computing such operationalizable strategies and provide an algorithm for computingε-optimal equilibria which are operationalizable. ❧ In all of these problems, I am motivated by real world challenges, and developing solution methods that are usable in the real world. As such, much of this work has been in collaboration with organizations such as Panthera, WWF and other non-governmental organizations (NGOs), to help protect the national parks and wildlife against deforestation and poaching, and the TSA, to protect critical infrastructure such as our airports from terrorist attacks. Because of this, in addressing these three levels of planning, I develop solutions which are not only novel and academically interesting, but also deployable with a real world impact.在智能对抗者存在的场景下，博弈论模型（game theoretic models），例如安全博弈（security games），已被证实为缓解防护与安全协议中可利用漏洞带来风险的有效工具：这类模型可刻画对抗者与防御者之间的策略性互动，并允许防御者在面对此类对抗者时，规划稀缺或有限资源的使用方案。然而，标准安全博弈模型仅能支持固定安全资源集的部署与分配，其允许防御者开展的规划类型表达能力有限。这忽略了两类极为关键的规划问题：一是安全系统与待部署资源的策略性设计，二是安全协议的可用性与落地实现。若不对这些问题进行原则性处理，现实系统中的安全协议效用与效率将遭受显著损失。 ❧ 为解决上述局限，本文提出一种面向安全博弈的规划问题分层新架构，将原问题划分为三个规划层级：(1) 战略规划（Strategic Planning）：考量长期规划周期，以及约束防御者可行策略的博弈设计相关决策；(2) 战术规划（Tactical Planning）：着眼于短期规划周期，负责资源部署以及在战略层级约束下选择防御者策略；(3) 运营规划（Operational Planning）：处理现实场景中的策略落地问题。 ❧ 首先，聚焦战略规划层面，本文研究资源与调度类型选择的设计问题。本文提出一项全新且具备基础意义的问题——资源团队与策略同步优化（Simultaneous Optimization of Resource Teams and Tactics, SORT），该模型对战略与战术规划的耦合问题进行建模，同时优化资源类型选择相关的博弈设计，以及资源的实地部署方案。本文提供了可高效求解SORT问题的算法，该算法通过对优化问题进行分层松弛来计算战略层级的投资决策。研究表明，这种表达能力更强的模型可支持防御者开展更精细的决策，从而带来效用的显著提升。 其次，鉴于资源异质性安全博弈的现实相关性与求解难度，本文针对战术规划面临的挑战，提出了面向异质资源的自适应策略计算框架。 最后，本文针对安全博弈领域尚未被正式研究的运营规划问题展开探讨。本文提出了可落地策略（operationalizable strategies）这一全新的解概念：该策略在防御者选定基数的最优纯策略子集上进行随机化。本文证明了此类可落地策略的求解难度，并给出了可生成ε-最优均衡的求解算法。 ❧ 上述所有研究均以现实挑战为驱动，致力于开发可落地应用的求解方法。本文的大量研究工作与Panthera、世界自然基金会（WWF）等非政府组织（NGOs）及美国运输安全管理局（TSA）展开合作：前者用于协助保护国家公园与野生动物免遭森林砍伐与偷猎，后者则用于保障机场等关键基础设施免受恐怖袭击。因此，针对上述三个规划层级的研究不仅具备新颖性与学术价值，同时具备可部署性与现实影响力。