مقاله ارزیابی عملکرد عمومی برای بازی های تخصیص منابع رقابتی از طریق برآورد بازپرداخت دیده نشده

چکیده

Many high-stakes decision-making problems, such as those found within cybersecurity and economics, can be modeled as competitive resource allocation games. In these games, multiple players must allocate limited resources to overcome their opponent(s), while minimizing any induced individual losses. However, existing means of assessing the performance of resource allocation algorithms are highly disparate and problem-dependent. As a result, evaluating such algorithms is unreliable or impossible in many contexts and applications, especially when considering differing levels of feedback. To resolve this problem, we propose a generalized definition of payoff which uses an arbitrary user-provided function. This unifies performance evaluation under all contexts and levels of feedback. Using this definition, we develop metrics for evaluating player performance, and estimators to approximate them under uncertainty (i.e., bandit or semi-bandit feedback). These metrics and their respective estimators provide a problem-agnostic means to contextualize and evaluate algorithm performance. To validate the accuracy of our estimator, we explore the Colonel Blotto ($\mathcal{CB}$) game as an example. To this end, we propose a graph-pruning approach to efficiently identify feasible opponent decisions, which are used in computing our estimation metrics. Using various resource allocation algorithms and game parameters, a suite of $\mathcal{CB}$ games are simulated and used to compute and evaluate the quality of our estimates. These simulations empirically show our approach to be highly accurate at estimating the metrics associated with the unseen outcomes of an opponent’s latent behavior.

چکیده به فارسی (ترجمه ماشینی)

بسیاری از مشکلات تصمیم گیری با خطر ، مانند موارد موجود در امنیت سایبری و اقتصاد ، می توانند به عنوان بازی های تخصیص منابع رقابتی مدل شوند.در این بازی ها ، چندین بازیکن برای غلبه بر حریف (های) خود باید منابع محدودی اختصاص دهند ، در حالی که هرگونه ضرر فردی ناشی از آن را به حداقل می رسانند.با این حال ، وسایل موجود برای ارزیابی عملکرد الگوریتم های تخصیص منابع بسیار متفاوت و وابسته به مشکل هستند.در نتیجه ، ارزیابی چنین الگوریتم ها در بسیاری از زمینه ها و برنامه ها غیر قابل اعتماد یا غیرممکن است ، به ویژه هنگام در نظر گرفتن سطح مختلف بازخورد.برای حل این مشکل ، ما یک تعریف کلی از بازپرداخت را پیشنهاد می کنیم که از یک عملکرد خودسرانه تهیه شده توسط کاربر استفاده می کند.این ارزیابی عملکرد را در همه زمینه ها و سطوح بازخورد متحد می کند.با استفاده از این تعریف ، ما معیارهایی را برای ارزیابی عملکرد بازیکن و برآوردگرها برای تقریب آنها تحت عدم اطمینان (یعنی بازخورد راهزن یا نیمه باند) ایجاد می کنیم.این معیارها و برآوردگرهای مربوطه آنها وسیله ای برای آژانسیک مسئله برای زمینه سازی و ارزیابی عملکرد الگوریتم را ارائه می دهند.برای تأیید صحت برآوردگر ما ، ما به عنوان نمونه بازی سرهنگ Blotto ($ \ Mathcal {CB} $) را کشف می کنیم.برای این منظور ، ما یک رویکرد هولناک را برای شناسایی کارآمد تصمیمات حریف امکان پذیر ، که در محاسبه معیارهای تخمین ما استفاده می شود ، پیشنهاد می کنیم.با استفاده از الگوریتم های مختلف تخصیص منابع و پارامترهای بازی ، مجموعه ای از $ \ Mathcal {CB} $ شبیه سازی شده و برای محاسبه و ارزیابی کیفیت تخمین های ما استفاده می شود.این شبیه سازی ها به صورت تجربی نشان می دهد که رویکرد ما در برآورد معیارهای مرتبط با نتایج غیب رفتار نهفته یک حریف بسیار دقیق است.