Visible to the public Security Games with Protection ExternalitiesConflict Detection Enabled

TitleSecurity Games with Protection Externalities
Publication TypeConference Paper
Year of Publication2015
AuthorsGan, Jiarui, An, Bo, Vorobeychik, Yevgeniy
Conference NameProceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Conference LocationAustin, Texas
ISBN Number0-262-51129-0
KeywordsFoundations, Game theory; Stackelberg game; Protection externality; Stackelberg game, Resilient Systems, science of security, SURE Project

Stackelberg security games have been widely deployed in recent years to schedule security resources. An assumption in most existing security game models is that one security resource assigned to a target only protects that target. However, in many important real-world security scenarios, when a resource is assigned to a target, it exhibits protection externalities: that is, it also protects other "neighbouring" targets. We investigate such Security Games with Protection Externalities (SPEs). First, we demonstrate that computing a strong Stackelberg equilibrium for an SPE is NP-hard, in contrast with traditional Stackelberg security games which can be solved in polynomial time. On the positive side, we propose a novel column generation based approach--CLASPE--to solve SPEs. CLASPE features the following novelties: 1) a novel mixed-integer linear programming formulation for the slave problem; 2) an extended greedy approach with a constant-factor approximation ratio to speed up the slave problem; and 3) a linear-scale linear programming that efficiently calculates the upper bounds of target-defined subproblems for pruning. Our experimental evaluation demonstrates that CLASPE enable us to scale to realistic-sized SPE problem instances.

Citation KeyGan:2015:SGP:2887007.2887134