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

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