آمار

تعداد نشریات36
تعداد شماره‌ها1,192
تعداد مقالات8,579
تعداد مشاهده مقاله6,988,686
تعداد دریافت فایل اصل مقاله4,032,528
اسماعیلی, سمانه, حسن پور, حسن, بیگدلی, حمید. (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 
چکیده
با توجه به اهمیت مسئله امنیت، تخصیص بهینه نیرو از موضوعات مورد توجه پژوهشگران است. در دو دهه گذشته، شاخه جدیدی از نظریه بازی‌ به نام بازی امنیتی برای محاسبه سیاست دفاعی بهینه با موفقیت برای مسائل امنیتی به‌کار گرفته شده است. در این بازی‌ها علاوه بر محدودیت منابع، عکس‌العمل منطقی مهاجم به هر راهبرد مدافع نیز درنظر گرفته می‌شود. پیش از این با تحلیل نظریه بازی، مسائلی بهینه‌سازی به‌منظور تخصیص بهینه نیرو ارائه شده و الگوریتم‌هایی نیز پیشنهاد شده‌اند که برای هر نوع بازی امنیتی و در هر شرایطی کارایی ندارند. در این مقاله الگوریتمی با زمان اجرای چندجمله‌ای برای محاسبه میزان پوشش بهینه اهداف ارائه شده است. اساس کار الگوریتم، گسترش مجموعه اهدافی موسوم به مجموعه حمله است که در مجموعه بهترین پاسخ‌های مهاجم قرار می‌گیرند؛ و درنهایت محدود کردن این مجموعه به هدفی با بیشینه عایدی مدافع است. در ادامه، بازی امنیتی مجموع صفر معرفی شده است که در آن با انتخاب هر راهبرد مدافع، مجموع عایدی مدافع و مهاجم صفر است. ثابت می‌شود که برای محاسبه جواب بهینه در این بازی، کافی است بزرگ‌ترین مجموعه حمله محاسبه شود. بر این اساس، الگوریتمی زمان چندجمله‌ای برای این نوع بازی نیز ارائه شده است.
کلیدواژه‌ها
تخصیص بهینه نیرو؛ بازی امنیتی؛ بازی مجموع ناصفر؛ بازی مجموع صفر؛ الگوریتم زمان چندجمله‌ای
عنوان مقاله [English]
Some Polynomial-time Algorithms for Solving Zero-Sum and Nonzero-Sum Security Game Problems
نویسندگان [English]
Samaneh Esmaeeli1؛ Hassan Hassanpour2؛ Hamid Bigdeli3
1University of Birjand
2Department of Mathematics, Faculty of Mathematical Science and Statistics, University of Birjand, Birjand, Iran
3Researcher, Institute for the Study of War, Command and Staff University, Tehran, I.R. Iran army
چکیده [English]
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. 
 
کلیدواژه‌ها [English]
Optimal Power Allocation, Security Game, Non-Zero Sum Game, Zero Sum Game, Polynomial Time Algorithm
مراجع
  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‎.
آمار
تعداد مشاهده مقاله: 193
تعداد دریافت فایل اصل مقاله: 100