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

Document Type : Original Article

Authors

Imam Ali University, Faculty of sciences, Department of mathematics, Tehran, Iran

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

Main Subjects

References

[1] J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications, Nonconvex Optimization and Its Applications (NOIA, volume 30), Springer, 1998.
[2] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, 3rd ed., 2006.
[3] J. F. Bonnans, J. C. Gilbert, C. Lemarechal, and C. A. Sagastiz ´ abal ´ , Numerical Optimization: Theoretical and Practical Aspects, Universitext (UTX), Springer Berlin, Heidelberg, 1998.
[4] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
[5] S. Dempe and J. Dutta, Is bilevel programming a special case of a mathematical program with complementarity constraints?, Math. Program., 131 (2012), pp. 37–48.
[6] Q. Feng, H. Cai, and Z. Chen, Using game theory to optimize the allocation of defensive resources on a city scale to protect chemical facilities against multiple types of attackers, Reliab. Eng. Syst. Saf., 191 (2019), p. 105900.
[7] H.-M. Kaltenbach, A concise guide to statistics, SpringerBriefs in Statistics, Springer, Heidelberg, 2012.
[8] J. Kisiala, Conditional value-at-risk: Theory and applications, Master’s thesis, University of Edinburgh, 2015.
[9] M. Ouyang, M. Xu, C. Zhang, and S. Huang, Mitigating electric power system vulnerability to worst-case spatially localized attacks, Reliab. Eng. Syst. Saf., 165 (2017), pp. 144–154.
[10] P. J. Phillips, Applying modern portfolio theory to the analysis of terrorism. computing the set of attack method combinations from which the rational terrorist group will choose in order to maximise injuries and fatalities, Defence and Peace Economics, 20 (2009), pp. 193–213.
[11] R. Powell, Defending against terrorist attacks with limited resources, American Political Science Review, 101 (2007), pp. 527–541.
[12] S. M. Robinson, Generalized equations and their solutions, part II: Applications to nonlinear programming, Springer Berlin Heidelberg, 1982, pp. 200–221.
[13] X. Shan and J. Zhuang, Hybrid defensive resource allocations in the face of partially strategic attackers in a sequential defender–attacker game, Eur. J. Oper. Res., 228 (2013), pp. 262–272.
[14] , Modeling cumulative defensive resource allocation against a strategic attacker in a multi-period multi[1]target sequential game, Reliab. Eng. Syst. Saf., 179 (2018), pp. 12–26.
[15] Z. Yazdaniyan, M. Shamsi, Z. Foroozandeh, and M. R. D. Pinho, A numerical method based on the complementarity and optimal control formulations for solving a family of zero-sum pursuit-evasion differential games, J. Comput. Appl. Math., 368 (2020), p. 112535.
[16] Z. Yazdaniyan, M. Shamsi, M. R. D. Pinho, and Z. Foroozandeh, Heuristic artificial bee colony algorithm for solving the homicidal chauffeur differential game, AUT J. Math. Com., 1 (2020), pp. 153–163.
[17] C. Zhang and J. E. Ramirez-Marquez, Protecting critical infrastructures against intentional attacks: A two-stage game with incomplete information, Iie Transactions, 45 (2013), pp. 244–258.
[18] C. Zhang, J. E. Ramirez-Marquez, and J. Wang, Critical infrastructure protection using secrecy–a discrete simultaneous game, Eur. J. Oper. Res., 242 (2015), pp. 212–221.
[19] J. Zhang and J. Zhuang, Modeling a multi-target attacker-defender game with multiple attack types, Reliab. Eng. Syst. Saf., 185 (2019), pp. 465–475.
[20] J. Zhang, J. Zhuang, and V. R. R. Jose, The role of risk preferences in a multi-target defender-attacker resource allocation game, Reliab. Eng. Syst. Saf., 169 (2018), pp. 95–104.
[21] J. Zhuang and V. M. Bier, Balancing terrorism and natural disasters—defensive strategy with endogenous attacker effort, Oper. Res., 55 (2007), pp. 976–991.
AUT Journal of Mathematics and Computing
Volume 4, Issue 2
March 2023
Pages 169-181

Files

Share

How to cite

Statistics