Mitigating the Curse of Correlation in Security Games by Entropy Maximization (Extended Abstract)

Citation:

Haifeng Xu, Shaddin Dughmi, Milind Tambe, and Venil Loyd Noronha. 2018. “Mitigating the Curse of Correlation in Security Games by Entropy Maximization (Extended Abstract).” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS-18).

Abstract:

In Stackelberg security games, a defender seeks to randomly allocate limited security resources to protect critical targets from an attack. In this paper, we study a fundamental, yet underexplored, phenomenon in security games, which we term the Curse of Correlation (CoC). Specifically, we observe that there are inevitable correlations among the protection status of different targets. Such correlation is a crucial concern, especially in spatio-temporal domains like conservation area patrolling, where attackers can surveil patrollers at certain areas and then infer their patrolling routes using such correlations. To mitigate this issue, we propose to design entropy-maximizing defending strategies for spatio-temporal security games, which frequently suffer from CoC. We prove that the problem is #P-hard in general. However, it admits efficient algorithms in well-motivated special settings.
See also: Conservation, 2018
Last updated on 07/26/2021