الگوریتم‌هایی با پیچیدگی زمانی چندجمله‌ای برای حل مسائل بازی امنیتی مجموع صفر و مجموع ناصفر

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، گروه ریاضی، دانشگاه بیرجند،ایران

2 دانشیار دانشکده علوم ریاضی وآمار، دانشگاه بیرجند، ایران

3 استادیار پژوهشکده عالی جنگ، تهران، ایران

چکیده

با توجه به اهمیت مسئله امنیت، تخصیص بهینه نیرو از موضوعات مورد توجه پژوهشگران است. در دو دهه گذشته، شاخه جدیدی از نظریه بازی‌ به نام بازی امنیتی برای محاسبه سیاست دفاعی بهینه با موفقیت برای مسائل امنیتی به‌کار گرفته شده است. در این بازی‌ها علاوه بر محدودیت منابع، عکس‌العمل منطقی مهاجم به هر راهبرد مدافع نیز درنظر گرفته می‌شود. پیش از این با تحلیل نظریه بازی، مسائلی بهینه‌سازی به‌منظور تخصیص بهینه نیرو ارائه شده و الگوریتم‌هایی نیز پیشنهاد شده‌اند که برای هر نوع بازی امنیتی و در هر شرایطی کارایی ندارند. در این مقاله الگوریتمی با زمان اجرای چندجمله‌ای برای محاسبه میزان پوشش بهینه اهداف ارائه شده است. اساس کار الگوریتم، گسترش مجموعه اهدافی موسوم به مجموعه حمله است که در مجموعه بهترین پاسخ‌های مهاجم قرار می‌گیرند؛ و درنهایت محدود کردن این مجموعه به هدفی با بیشینه عایدی مدافع است. در ادامه، بازی امنیتی مجموع صفر معرفی شده است که در آن با انتخاب هر راهبرد مدافع، مجموع عایدی مدافع و مهاجم صفر است. ثابت می‌شود که برای محاسبه جواب بهینه در این بازی، کافی است بزرگ‌ترین مجموعه حمله محاسبه شود. بر این اساس، الگوریتمی زمان چندجمله‌ای برای این نوع بازی نیز ارائه شده است.

کلیدواژه‌ها

موضوعات

Smiley face

مراجع

  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‎.

فایل ها

سابقه مقاله

  • تاریخ دریافت: 18 آبان 1400
  • تاریخ بازنگری: 25 فروردین 1401
  • تاریخ پذیرش: 16 اردیبهشت 1401

هم رسانی

ارجاع به این مقاله

آمار