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

Abstract

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