Orateur
Description
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 pro-
duce 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 com-
ponent’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 equiv-
alent formulation has many high-degree multilinear terms. To address the challenges
in solving this problem, we propose a successive refinement algorithm that dynami-
cally 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 determinis-
tic 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.
