{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/140615"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/140615","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Park, Seonghun"],"institution":"Virginia Tech","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Industrial and Systems Engineering","degree_department":"Industrial and Systems Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":["Bansal, Manish"],"committee_members":["Tunc, Sait","Chen, Xi","Freeman, Laura June"],"year":2026,"date_issued":"2026-01-06","date_published":"2026-01-06","updated_at":"2026-07-22T22:19:27Z","subjects":["Stackelberg Game","Distributionally Robust Optimization","Risk-Receptiveness","Submodular Function","Cutting-plane Method"],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:45286"],"render_values":[{"text":"vt_gsexam:45286","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10919/140615","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Bansal, Manish"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Tunc, Sait","Chen, Xi","Freeman, Laura June"]},{"key":"dc:contributor.department","label":"Department","values":["Industrial and Systems Engineering"]},{"key":"dc:creator","label":"Author","values":["Park, Seonghun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-01-07T09:01:10Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-01-07T09:01:10Z"]},{"key":"dc:date.issued","label":"Date","values":["2026-01-06"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial and Systems Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Stackelberg Game","Distributionally Robust Optimization","Risk-Receptiveness","Submodular Function","Cutting-plane Method"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:45286"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10919/140615"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["The security of critical systems, where failure can lead to severe consequences, requires strategic decision-making against intelligent adversary (attacker) with directly opposing ob- jectives. Unlike passive or random threats, such adversary anticipates the systems user's (defender's) best response to a potential attack and choose their actions accordingly, cre- ating a structured attack where one side's gain directly corresponds to the other's loss. Therefore, rigorous analytical approaches are essential for the decision-making of both the attacker and the defender. This dissertation models these adversarial interactions with the mathematical framework akin to the Stackelberg zero-sum games, which captures the se- quential nature of decision making between a proactive attacker and a reactive defender. A key challenge arises when game parameters are uncertain and historical data is limited to derive precise probability distribution associated with uncertain parameters. This distri- butional ambiguity complicates the search for optimal strategies for attacker and effective vulnerability assessments for defender. This research addresses this challenge by developing models that analyze two distinct risk preferences of the attacker towards the distributional ambiguity. The risk-averse approach models a cautious attacker, providing conservative strategies that guarantee a consistent level of impact. In contrast, the risk-receptive approach models an aggressive attacker willing to accept higher variability in attack impact in exchange for the potential of a more damaging attack. For a defender, analyzing both models is critical for a comprehensive vulnerability assessment of system, as the former reveals the most probable threats while the latter exposes the most severe ones. Likewise, these frameworks are equally applicable when planning interdiction actions against an adversary (e.g., an evader or enemy) when the decision maker is protagonist. First, this dissertation provides analytical tools for the security of telerobotic camera systems used in critical roles like surveillance, search and rescue, and satellite imaging, especially in environments where collecting information is difficult for humans. Applying the risk-averse framework offers a dual advantage: it allows a defender to identify vulnerable cameras (or the vehicles carrying them) that are susceptible to attacks from a rational adversary, while also providing a tool for planning interdiction actions to minimize an enemy's information acquisition. To solve this problem, we present an exact cutting planes based algorithm. Moreover, to ensure the framework's computational practicality, we also develop improved algorithms for the defender's underlying placement subproblem, including a faster exact method and heuristics. Second, we tackle games where the defender's objective is to maximize a k-submodular func- tion. This function, a generalization of standard submodular function, is widely used to model practical optimization problems such as multi-topic influence maximization and fea- ture selection. We explore this framework across two critical problems: the feature selection interdiction problem, where an adversary attacks data features to degrade machine learn- ing model performance, and the weighted coverage interdiction problem, where an attacker blocks sensor installations to minimize maximum coverage. We present finitely convergent exact algorithms for these games and, through computational experiments, demonstrate the practical utility of our models for both decision-makers. For instance, using the Wisconsin Breast Cancer dataset, our risk-receptive model successfully identifies feature attacks that most significantly degrade the predictive model's accuracy. Third contribution extends the strategic scope of these games by introducing a mathematical model for proactive defense. This framework moves beyond a purely reactive defensive posture, allowing decision-makers to quantitatively assess the value of investing in fortifying assets before an attack occurs, thus enabling more effective long-term security planning."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Doctor of Philosophy"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Distributionally Ambiguous Stackelberg Combinatorial Games for Submodular Optimization and Camera View-Frame Placement"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Bansal, Manish"],"dc:contributor.committeemember":["Tunc, Sait","Chen, Xi","Freeman, Laura June"],"dc:contributor.department":["Industrial and Systems Engineering"],"dc:creator":["Park, Seonghun"],"dc:date.accessioned":["2026-01-07T09:01:10Z"],"dc:date.available":["2026-01-07T09:01:10Z"],"dc:date.issued":["2026-01-06"],"dc:description.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."],"dc:description.abstractgeneral":["The security of critical systems, where failure can lead to severe consequences, requires strategic decision-making against intelligent adversary (attacker) with directly opposing ob- jectives. Unlike passive or random threats, such adversary anticipates the systems user's (defender's) best response to a potential attack and choose their actions accordingly, cre- ating a structured attack where one side's gain directly corresponds to the other's loss. Therefore, rigorous analytical approaches are essential for the decision-making of both the attacker and the defender. This dissertation models these adversarial interactions with the mathematical framework akin to the Stackelberg zero-sum games, which captures the se- quential nature of decision making between a proactive attacker and a reactive defender. A key challenge arises when game parameters are uncertain and historical data is limited to derive precise probability distribution associated with uncertain parameters. This distri- butional ambiguity complicates the search for optimal strategies for attacker and effective vulnerability assessments for defender. This research addresses this challenge by developing models that analyze two distinct risk preferences of the attacker towards the distributional ambiguity. The risk-averse approach models a cautious attacker, providing conservative strategies that guarantee a consistent level of impact. In contrast, the risk-receptive approach models an aggressive attacker willing to accept higher variability in attack impact in exchange for the potential of a more damaging attack. For a defender, analyzing both models is critical for a comprehensive vulnerability assessment of system, as the former reveals the most probable threats while the latter exposes the most severe ones. Likewise, these frameworks are equally applicable when planning interdiction actions against an adversary (e.g., an evader or enemy) when the decision maker is protagonist. First, this dissertation provides analytical tools for the security of telerobotic camera systems used in critical roles like surveillance, search and rescue, and satellite imaging, especially in environments where collecting information is difficult for humans. Applying the risk-averse framework offers a dual advantage: it allows a defender to identify vulnerable cameras (or the vehicles carrying them) that are susceptible to attacks from a rational adversary, while also providing a tool for planning interdiction actions to minimize an enemy's information acquisition. To solve this problem, we present an exact cutting planes based algorithm. Moreover, to ensure the framework's computational practicality, we also develop improved algorithms for the defender's underlying placement subproblem, including a faster exact method and heuristics. Second, we tackle games where the defender's objective is to maximize a k-submodular func- tion. This function, a generalization of standard submodular function, is widely used to model practical optimization problems such as multi-topic influence maximization and fea- ture selection. We explore this framework across two critical problems: the feature selection interdiction problem, where an adversary attacks data features to degrade machine learn- ing model performance, and the weighted coverage interdiction problem, where an attacker blocks sensor installations to minimize maximum coverage. We present finitely convergent exact algorithms for these games and, through computational experiments, demonstrate the practical utility of our models for both decision-makers. For instance, using the Wisconsin Breast Cancer dataset, our risk-receptive model successfully identifies feature attacks that most significantly degrade the predictive model's accuracy. Third contribution extends the strategic scope of these games by introducing a mathematical model for proactive defense. This framework moves beyond a purely reactive defensive posture, allowing decision-makers to quantitatively assess the value of investing in fortifying assets before an attack occurs, thus enabling more effective long-term security planning."],"dc:description.degree":["Doctor of Philosophy"],"dc:format.medium":["ETD"],"dc:identifier.other":["vt_gsexam:45286"],"dc:identifier.uri":["https://hdl.handle.net/10919/140615"],"dc:language.iso":["en"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["Stackelberg Game","Distributionally Robust Optimization","Risk-Receptiveness","Submodular Function","Cutting-plane Method"],"dc:title":["Distributionally Ambiguous Stackelberg Combinatorial Games for Submodular Optimization and Camera View-Frame Placement"],"dc:type":["Dissertation"],"thesis:degree_discipline":["Industrial and Systems Engineering"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:27Z"}