A Bi-level formulation for a sequential stochastic attacker-defender game via conditional value at risk

Abstract

In this study, we present a bi-level formulation for a sequential stochastic attacker-defender game with multiple targets. In this game, the vulnerability of targets is a stochastic parameter, and the attacker has only one attack type. The defender’s aim is to find the optimal allocation of the budget to minimize the conditional value at risk of damage. In response to the defender’s decisions, the attacker seeks an optimal allocation of its budget to maximize the expected damage. By using Karush-Kuhn-Tucker transformations, we reduce the proposed bi-level formulation to a single-level one. We also explore some important relationships between the solutions of the single-level and bi-level problems. Finally, by means of numerical experiments, we apply our formulation to several stochastic attacker-defender games to show the efficiency of our formulation in practice.

Keywords

• game theory
• bi-level optimization
• attacker-defender
• stochastic