A Successive Refinement Algorithm for Tri-Level Stochastic Defender-Attacker Problems with Decision-Dependent Probability Distributions
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917774928904192 |
|---|---|
| author | Affar, Samuel Medal, Hugh |
| author_facet | Affar, Samuel Medal, Hugh |
| contents | Tri-level defender-attacker game models are a well-studied method for determining how best to protect a system (e.g., a transportation network) from attacks. Existing models assume that defender and attacker actions have a perfect effect, i.e., system components hardened by a defender cannot be destroyed by the attacker, and attacked components always fail. Because of these assumptions, these models produce solutions in which defended components are never attacked, a result that may not be realistic in some contexts. This paper considers an imperfect defender-attacker problem in which defender decisions (e.g., hardening) and attacker decisions (e.g., interdiction) have an imperfect effect such that the probability distribution of a component's capacity depends on the amount of defense and attack resource allocated to the component. Thus, this problem is a stochastic optimization problem with decision-dependent probabilities and is challenging to solve because the deterministic equivalent formulation has many high-degree multilinear terms. To address the challenges in solving this problem, we propose a successive refinement algorithm that dynamically refines the support of the random variables as needed, leveraging the fact that a less-refined support has fewer scenarios and multilinear terms and is, therefore, easier to solve. A comparison of the successive refinement algorithm versus the deterministic equivalent formulation on a tri-level stochastic maximum flow problem indicates that the proposed method solves many more problem instances and is up to $66$ times faster. These results indicate that it is now possible to solve tri-level problems with imperfect hardening and attacks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08385 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Successive Refinement Algorithm for Tri-Level Stochastic Defender-Attacker Problems with Decision-Dependent Probability Distributions Affar, Samuel Medal, Hugh Optimization and Control Combinatorics 90B08, 90B10, 90C08, 90C10 Tri-level defender-attacker game models are a well-studied method for determining how best to protect a system (e.g., a transportation network) from attacks. Existing models assume that defender and attacker actions have a perfect effect, i.e., system components hardened by a defender cannot be destroyed by the attacker, and attacked components always fail. Because of these assumptions, these models produce solutions in which defended components are never attacked, a result that may not be realistic in some contexts. This paper considers an imperfect defender-attacker problem in which defender decisions (e.g., hardening) and attacker decisions (e.g., interdiction) have an imperfect effect such that the probability distribution of a component's capacity depends on the amount of defense and attack resource allocated to the component. Thus, this problem is a stochastic optimization problem with decision-dependent probabilities and is challenging to solve because the deterministic equivalent formulation has many high-degree multilinear terms. To address the challenges in solving this problem, we propose a successive refinement algorithm that dynamically refines the support of the random variables as needed, leveraging the fact that a less-refined support has fewer scenarios and multilinear terms and is, therefore, easier to solve. A comparison of the successive refinement algorithm versus the deterministic equivalent formulation on a tri-level stochastic maximum flow problem indicates that the proposed method solves many more problem instances and is up to $66$ times faster. These results indicate that it is now possible to solve tri-level problems with imperfect hardening and attacks. |
| title | A Successive Refinement Algorithm for Tri-Level Stochastic Defender-Attacker Problems with Decision-Dependent Probability Distributions |
| topic | Optimization and Control Combinatorics 90B08, 90B10, 90C08, 90C10 |
| url | https://arxiv.org/abs/2409.08385 |