Linear-Time Resource Allocation in Security Games with Identical Fully Protective Resources

O Lerma, V Kreinovich, C Kiekintveld

In Proceedings of the AAAI Workshop on Applied Adversarial Reasoning and Risk Modeling (AARM 2011).

This is the author's version of the work.

Download

Abstract

Game theory has become an important tools for making resource allocations decision in security domains, including critical infrastructure protection. Many of these games are formulated as Stackelberg security games. We present new analysis and algorithms for a class of Stackelberg security games with identical, fully protective defender resources. The first algorithm has worst-case complexity linear in the number of possible targets, but works only for a restricted case. The second algorithm can find and optimal resource allocation for the general case in time O(n log(n)).