تعداد نشریات | 38 |
تعداد شمارهها | 1,244 |
تعداد مقالات | 9,009 |
تعداد مشاهده مقاله | 7,865,040 |
تعداد دریافت فایل اصل مقاله | 4,718,101 |
الگوریتمهایی با پیچیدگی زمانی چندجملهای برای حل مسائل بازی امنیتی مجموع صفر و مجموع ناصفر | ||
علوم و فناوریهای پدافند نوین | ||
مقاله 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 | ||
مراجع | ||
| ||
آمار تعداد مشاهده مقاله: 229 تعداد دریافت فایل اصل مقاله: 147 |