Robust Solutions for Multi-Defender Stackelberg Security Games

Robust Solutions for Multi-Defender Stackelberg Security Games

Dolev Mutzari, Yonatan Aumann, Sarit Kraus

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 433-439. https://doi.org/10.24963/ijcai.2022/62

Multi-defender Stackelberg Security Games (MSSG) have recently gained increasing attention in the literature. However, the solutions offered to date are highly sensitive, wherein even small perturbations in the attacker's utility or slight uncertainties thereof can dramatically change the defenders' resulting payoffs and alter the equilibrium. In this paper, we introduce a robust model for MSSGs, which admits solutions that are resistant to small perturbations or uncertainties in the game's parameters. First, we formally define the notion of robustness, as well as the robust MSSG model. Then, for the non-cooperative setting, we prove the existence of a robust approximate equilibrium in any such game, and provide an efficient construction thereof. For the cooperative setting, we show that any such game admits a robust approximate (alpha) core, and provide an efficient construction thereof. Lastly, we show that stronger types of the core may be empty. Interestingly, the robust solutions can substantially increase the defenders' utilities over those of the non-robust ones.
Keywords:
Agent-based and Multi-agent Systems: Cooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Noncooperative Games