Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2015 | PROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE | stackelberg game,game theory |
Field | DocType | Citations |
Linear programming formulation,Mathematical optimization,Column generation,Computer science,Game theory,Linear programming,Externality,Time complexity,Stackelberg competition,Speedup | Conference | 10 |
PageRank | References | Authors |
0.64 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jiarui Gan | 1 | 39 | 9.05 |
| Bo An | 2 | 892 | 106.05 |
| Yevgeniy Vorobeychik | 3 | 625 | 94.05 |