AAAI Publications, Workshops at the Twenty-Fifth AAAI Conference on Artificial Intelligence

Font Size: 
Linear-Time Resource Allocation in Security Games with Identical Fully Protective Resources
Octavio Lerma, Vladik Kreinovich, Christopher Kiekintveld

Last modified: 2011-08-24


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)).

Full Text: PDF