آمار

تعداد نشریات36
تعداد شماره‌ها1,178
تعداد مقالات8,477
تعداد مشاهده مقاله6,614,713
تعداد دریافت فایل اصل مقاله3,721,577
اسماعیلی, سمانه, حسن پور, حسن, بیگدلی, حمید. (1401). الگوریتم‌هایی با پیچیدگی زمانی چندجمله‌ای برای حل مسائل بازی امنیتی مجموع صفر و مجموع ناصفر. پدافند الکترونیکی و سایبری, 13(1), 23-34.
سمانه اسماعیلی; حسن حسن پور; حمید بیگدلی. "الگوریتم‌هایی با پیچیدگی زمانی چندجمله‌ای برای حل مسائل بازی امنیتی مجموع صفر و مجموع ناصفر". پدافند الکترونیکی و سایبری, 13, 1, 1401, 23-34.
اسماعیلی, سمانه, حسن پور, حسن, بیگدلی, حمید. (1401). 'الگوریتم‌هایی با پیچیدگی زمانی چندجمله‌ای برای حل مسائل بازی امنیتی مجموع صفر و مجموع ناصفر', پدافند الکترونیکی و سایبری, 13(1), pp. 23-34.
اسماعیلی, سمانه, حسن پور, حسن, بیگدلی, حمید. الگوریتم‌هایی با پیچیدگی زمانی چندجمله‌ای برای حل مسائل بازی امنیتی مجموع صفر و مجموع ناصفر. پدافند الکترونیکی و سایبری, 1401; 13(1): 23-34.

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

علوم و فناوریهای پدافند نوین
مقاله 3، دوره 13، شماره 1 - شماره پیاپی 47، خرداد 1401، صفحه 23-34    اصل مقاله (1.22 M)
نوع مقاله: مقاله پژوهشی
نویسندگان
سمانه اسماعیلی1؛ حسن حسن پور* 2؛ حمید بیگدلی3
1دانشجوی دکتری، گروه ریاضی، دانشگاه بیرجند،ایران
2دانشیار دانشکده علوم ریاضی وآمار، دانشگاه بیرجند، ایران
3استادیار پژوهشکده عالی جنگ، تهران، ایران
تاریخ دریافت: 18 آبان 1400،  تاریخ بازنگری: 25 فروردین 1401،  تاریخ پذیرش: 16 اردیبهشت 1401 
چکیده
با توجه به اهمیت مسئله امنیت، تخصیص بهینه نیرو از موضوعات مورد توجه پژوهشگران است. در دو دهه گذشته، شاخه جدیدی از نظریه بازی‌ به نام بازی امنیتی برای محاسبه سیاست دفاعی بهینه با موفقیت برای مسائل امنیتی به‌کار گرفته شده است. در این بازی‌ها علاوه بر محدودیت منابع، عکس‌العمل منطقی مهاجم به هر راهبرد مدافع نیز درنظر گرفته می‌شود. پیش از این با تحلیل نظریه بازی، مسائلی بهینه‌سازی به‌منظور تخصیص بهینه نیرو ارائه شده و الگوریتم‌هایی نیز پیشنهاد شده‌اند که برای هر نوع بازی امنیتی و در هر شرایطی کارایی ندارند. در این مقاله الگوریتمی با زمان اجرای چندجمله‌ای برای محاسبه میزان پوشش بهینه اهداف ارائه شده است. اساس کار الگوریتم، گسترش مجموعه اهدافی موسوم به مجموعه حمله است که در مجموعه بهترین پاسخ‌های مهاجم قرار می‌گیرند؛ و درنهایت محدود کردن این مجموعه به هدفی با بیشینه عایدی مدافع است. در ادامه، بازی امنیتی مجموع صفر معرفی شده است که در آن با انتخاب هر راهبرد مدافع، مجموع عایدی مدافع و مهاجم صفر است. ثابت می‌شود که برای محاسبه جواب بهینه در این بازی، کافی است بزرگ‌ترین مجموعه حمله محاسبه شود. بر این اساس، الگوریتمی زمان چندجمله‌ای برای این نوع بازی نیز ارائه شده است.
کلیدواژه‌ها
تخصیص بهینه نیرو؛ بازی امنیتی؛ بازی مجموع ناصفر؛ بازی مجموع صفر؛ الگوریتم زمان چندجمله‌ای
مراجع
  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‎.
آمار
تعداد مشاهده مقاله: 177
تعداد دریافت فایل اصل مقاله: 81