Title: Strategic Resource Coordination for Detecting Illegal Activity
Committee:
Dr. Mathieu Dahan (advisor), School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Alejandro Toriello, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Juba Ziani, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Santanu Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Saurabh Amin, Department of Civil and Environmental Engineering, Massachusetts Institute of Technology
Date and Time: Tuesday, August 13th, 10:00am - 11:30am ET
Location: Groseclose 402
Virtual Link: Microsoft Teams Join the meeting now
Meeting ID: 213 214 055 157
Passcode: 8wQ5Rd
Abstract:
In an increasingly complex and interconnected world, ensuring security and resilience requires effective allocation of inspection resources to detect illegal activities. The evolving nature of threats, coupled with resourceful adversaries and limited inspection resources, makes it imperative to develop strategic inspection operations. Challenges include coordinating multiple resources, accounting for imperfect detection capabilities and asymmetric valuations of targets. New opportunities, such as advances in sensing technologies and data analytics, offer potential solutions to enhance the effectiveness of inspection operations.
This thesis leverages game theory for the strategic coordination of inspection resources, focusing on Nash Equilibria (NE) as the main solution concept. It aims to provide valuable insights and efficient algorithms for inspection operations across various security domains.
Chapter 2 examines a variant of the hide-and-seek game, motivated by the challenge of detecting smuggled commodities hidden by criminal organizations. In this game, a seeker inspects multiple hiding locations to find multiple items hidden by a hider. Each hiding location has a maximum hiding capacity and a probability of detecting its hidden items upon inspection. The seeker (resp. hider) aims to minimize (resp. maximize) the expected number of undetected items. We develop a two-step solution approach to compute NE for this zero-sum game. First, we solve a lower-dimensional continuous game to derive closed-form expressions for the equilibrium marginal distributions. Second, we design a combinatorial algorithm to compute mixed strategies that satisfy these marginal distributions. Our approach reveals novel equilibrium behaviors influenced by the complex interplay of game parameters and computes NE in quadratic time with linear support.
Chapter 3 explores a nonzero-sum variant of the hide-and-seek game, driven by the asymmetric valuations that security agencies and criminal organizations place on the outcomes of their interactions. Here, a seeker inspects multiple locations with unit hiding capacities to find items hidden by a hider. Each location is associated with different utility values for the seeker and hider. The seeker (resp. hider) aims to maximize the utility from inspected (resp. uninspected) locations containing hidden items. We extend the previous two-step approach to obtain NE by deriving closed-form expressions for the equilibrium marginal distributions and computing compatible mixed strategies, resulting in a quadratic-time algorithm for solving this nonzero-sum game. Our analysis not only reveals complex equilibrium behaviors influenced by the players' asymmetric and heterogeneous valuations, but also addresses strategic interactions in various contexts beyond security domains, such as animal behavior and political campaigns. By offering both an intuitive analysis and an efficient solution method, this work bridges a gap in the study of equilibrium behavior in nonzero-sum games of strategic mismatch.
Chapter 4 addresses strategic inspection problems in critical infrastructure resilience through a network inspection game, where a defender positions detectors on a network to detect multiple attacks on its components caused by an attacker. Each detector location has a probability of detecting attacks within its monitored components. The defender (resp. attacker) aims to minimize (resp. maximize) the expected number of undetected attacks. This model extends the hide-and-seek game of Chapter 2 by allowing for detection from multiple locations. To compute NE for this large-scale zero-sum game, we formulate a linear program with a small number of constraints and solve it using Column Generation. We provide an exact mixed-integer program for the pricing problem, which entails computing a defender's pure best response, and leverage its supermodular structure to derive two efficient approaches for obtaining approximate NE with theoretical guarantees: a Column Generation and a Multiplicative Weights Update (MWU) algorithm with approximate best responses. Each iteration of our MWU algorithm requires computing a projection under the unnormalized relative entropy, for which we provide a closed-form solution and a linear-time algorithm. Our computational results in real-world gas distribution networks demonstrate the performance and scalability of our solution approaches.