Some Polynomial-time Algorithms for Solving Zero-Sum and Nonzero-Sum Security Game Problems

Document Type : Original Article

Authors

1 University of Birjand

2 Department of Mathematics, Faculty of Mathematical Science and Statistics, University of Birjand, Birjand, Iran

3 Researcher, Institute for the Study of War, Command and Staff University, Tehran, I.R. Iran army

Abstract

Given the importance of security, optimal force allocation is a topic of interest to researchers. Over the past two decades, a new branch of game theory called the security game, has been successfully used as a method to calculate the optimal defense policy for security issues. In these games, in addition to the limitations of security resources, the logical reaction of the attacker to any defender's strategy, is considered. Formerly, some optimization problems have been proposed to optimize the force allocation using the game theory, and some algorithms have been proposed that do not work for all types of security games and in all situations. In this paper, an algorithm with polynomial execution time is proposed to calculate the optimal coverage of the targets. The basis of this algorithm is expanding a set of targets called the attack set, which is included in the set of the attacker's best responses; and finally, limiting this set to a target with the maximum defender's payoff. Next, a zero-sum security game is introduced, in which by choosing any defender's strategy, the sum of defender's and attacker's payoffs are zero. It is proved that to calculate the optimal strategy in this game, it is enough to calculate the largest attack set. Accordingly, a polynomial-time algorithm is also proposed for this type of the game. 
 

Keywords

Main Subjects

Smiley face

References

  1. An, B.; Shieh, E.; Tambe, M.; Yang, R.; Baldwin, C.; DiRenzo, J.; Maule, B.; Meyer, G. “PROTECT: A Deployed Game Theoretic System for Strategic Security Allocation for the United States Coast Guard”; Ai Magazine 2012, 96-96.
  2. Hunt, K.; Agarwal, P.; Zhuang, J. “Technology Adoption for Airport Security: Modeling Public Disclosure and Secrecy in an Attacker-Defender Game”; Reliab. Eng. Syst. Safe 2021, 107355.‎
  3. Pita, J.; Tambe, M.; Kiekintveld, C.; Cullen, S.; Steigerwald, E. “Guards: Game Theoretic Security Allocation on a National Scale”; Tenth Int. Conf. on Autonomous Agents and Multiagent Syst. 2011, 37-44.
  4. Jain, M.; Korzhyk, D.; Vaněk, O.; Conitzer, V.; Pěchouček, M.; Tambe, M. “A Double Oracle Algorithm for Zero-sum Security Games on Graphs”; Tenth Int. Conf. on Autonomous Agents and Multiagent Syst. 2011, 327-334.
  5. Gnecco, G.; Hadas, Y.; Sanguineti, M. “Some Properties of Transportation Network Cooperative Games”; Networks 2019, 74, 161-173.
  6. Takalloo, M. “Game Theory Approaches for Transportation Problems”; PhD Diss., University of South Florida, 2020‎.
  7. Bansal, G.; Sikdar B. “Security Service Pricing Model for UAV Swarms: A Stackelberg Game Approach”; IEEE Conf. Comput. 2021, 1-6.
  8. Οικονομάκης, Π. “Strategic Military Deception Prerequisites of Success in Technological Environment”; 2015.‎
  9. Zhang, Y.; Malacaria, P. “Bayesian Stackelberg Games for Cyber-Security Decision Support”; Decis. Support Syst. 2021, 113599.
  10. Yuan, Y.; Sun, F.; Liu, H. “Resilient Control of Cyber-physical Systems against Intelligent Attacker: a Hierarchal Stackelberg Game Approach”; Int. J. Syst. Sci. 2016, 47, 2067-2077.
  11. Basilico N.; Celli A.; De Nittis G.; Gatti N. “Coordinating Multiple Defensive Resources in Patrolling GGames with Alarm Systems”; 16th Autonomous Agents and MultiAgent Syst. 2017, 678-686.
  12. Garrec, T. “Continuous Patrolling and Hiding Games”; Eur. J. Oper. Res. 2019, 277, 42-51.
  13. Albarran, S. E.; Clempner, J. B. “A Stackelberg Security Markov Game Based on Partial Information for Strategic Decision Making Against Unexpected Attacks”; Eng. Appl. Artif. Intel. 2019, 81, 408-19‎.
  14. Anwar, F.; Khan, B. U. I.; Olanrewaju, R. F.; Pampori, B. R.; Mir, R. N. “A Comprehensive insight into Game Theory in Relevance to Cyber Security”; Indonesian J. Elect. Eng. Informatics 2020, 8, 189-203.
  15. Sinha, A.; Fang, F.; An, B.; Kiekintveld, C.; Tambe, M. “Stackelberg Security Games: Looking beyond a Decade of Success”; Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018.
  16. Conitzer, V.; Sandholm, T. “Computing the Optimal Strategy to Commit to”; Seventh ACM Conf. Elect. Commerce 2006, 82-90.
  17. Paruchuri, P.; Pearce, J. P.; Tambe, M.; Ordonez, F.; Kraus, S. “An Efficient Heuristic Approach for Security Against Multiple Adversaries”; 6th Autonomous Agents and Multiagent Syst., 2007, 1-8‎.
  18. Letchford, J.; MacDermed, L.; Conitzer, V.; Parr, R.; Isbell, C. L. “Computing Optimal Strategies to Commit to in Stochastic Games”; Twenty-Sixth AAAI Conf. Artif. Intel., 2012.‎
  19. Letchford, J.; Vorobeychik, Y. “Computing Randomized Security Strategies in Networked Domains”; Twenty-Fifth AAAI Conf. Artif. Intel. 2011.
  20. Bigdeli, H.; Hassanpour, H.; Tayyebi, J. “Optimistic and Pessimistic Solutions of Single and Multi-Objective Matrix Games with Fuzzy Payoffs and Analysis of Some Military Cases”; Adv. Defence Sci. & Technol. 2017, 8, 133-145 (In Persian).
  21. Bigdeli, H.; Hassanpour, H.; Tayyebi, J. “Multiobjective Security Game with Fuzzy Payoffs”; Iran J. Fuzzy Syst. 2019, 16, 89-101.
  22. Conti, S. “Algorithms for Finding Leader-Follower Equilibrium with Multiple Followers”; PhD Thesis, Politecnico Di Milano, 2013‎.
  23. Trejo, K. K.; Clempner, J. B.; Poznyak, A. S. “A Stackelberg Security Game with Random Strategies Based on the Extraproximal Theoretic Approach”; Eng. Appl. Artif. Intel. 2015, 37, 145-153.
  24. Esmaeeli, S.; Hassanpour, H.; Bigdeli, H. “Deception in Multi Attacker Security Game with Nonfuzzy and Fuzzy Payoffs”; Iranian Journal of Numerical Analysis and Optimization 2022, 12, 542–566.‎
  25. Esmaieli, S.; Hassanpour, H.; Bigdeli, H. “Lexicographic Programming for Solving Security Game with Fuzzy Payoffs and Computing Optimal Deception Strategy”; Defensive Future Study Researches J. 2020, 5, 89-108 (In Persian).‎
  26. Tambe, M.; Jiang, A. X.; An, B.; Jain, M. “Computational Game Theory for Security: Progress and Challenges”; AAAI Spring Symposium on Applied Computational Game Theory, 2014.
  27. An, B.;  Ordóñez, F.; Tambe, M.; Shieh, E.; Yang, R.; Baldwin, C.; DiRenzo III, J.; Moretti, K.; Maule, B. Meyer, G. “A Deployed Quantal Response-based Patrol Planning System for the US Coast Guard”; Interfaces 2013, 43, 400-20‎.

Files

History

  • Receive Date: 09 November 2021
  • Revise Date: 14 April 2022
  • Accept Date: 06 May 2022
  • Publish Date: 22 May 2022

Share

How to cite

Statistics