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

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

some polynomial-time algorithms for solving zero-sum and nonzero-sum security game problems

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.