Distributionally Ambiguous Stackelberg Combinatorial Games for Submodular Optimization and Camera View-Frame Placement

Abstract

This dissertation develops exact solution methodologies for Stackelberg zero-sum games, which model sequential decision-making between an attacker and a defender. Our work specifically addresses challenging settings where the defender's recourse is a complex com- binatorial optimization problem and the attacker faces uncertainty and distributional am- biguity. We analyze these games through two complementary frameworks. Distributionally Robust Optimization (DRO) framework provides a risk-averse attacker with robust attack- ing strategy, while offering defender insights into the most probable threats. In contrast, Distributionally Risk-Receptive (DRR) frameworks provides high-impact strategy for a risk- receptive attacker, thereby serving as a powerful tool for the defender's vulnerability analysis by exposing the system's most critical weakness. This dissertation makes three primary contributions, each developing novel decomposition methods based on structural insights. First, we introduce and solve a Stackelberg game, where the defender's problem is the camera view-frame placement problem. We address this setting under a DRO framework to explicitly model uncertainty in attack success, incomplete information, and the adversary's varying levels of risk-appetite. For this setting, we develop a cutting-plane-based algorithm that leverages a key geometric property: an optimal placement under one attack remains a feasible recourse under any other, to derive a new class of valid inequalities. Since our algorithm repeatedly solves the defender's problem, placing p camera view frames to maximize the coverage, we also contribute efficient exact methods for p = 1 and novel heuristics for p ≥ 2, validated through simulation experiments of finding a hidden object. Second, we solve the game when the defender's objective is maximizing k-submodular func- tion, under both DRO and DRR frameworks. To solve problem, we derive valid inequalities from the diminishing property of k-submodular function, and strengthen them further by imposing an ordering over elements in the defender's solution sets. The optimal values from these dual frameworks offer a confidence interval-like range for the defender's expected out- come, where the DRO solution provides robust attack strategies and the DRR solution iden- tifies critical data vulnerabilities. We demonstrate effectiveness of our frameworks through computational experiments on instances of feature selection and sensor placement problems, using Wisconsin breast cancer data and synthetic data, respectively. Third, we extend the strategic scope to a three-stage Defender-Attacker-Defender (DAD) model with fortification, where the defender's final recourse is the maximization of a sub- modular function. To solve this game, where the standard attacker-defender interdiction game appears as a subproblem, we derive another class of valid inequalities that are con- structed for an arbitrary fortification strategy by leveraging the diminishing return property of the defender's objective function. Empirical validation on real-world datasets with pre- dictive models (e.g., Support Vector Classifiers, logistic regression) confirms the practical impact of our frameworks.