Layered Graph Security Games
Authors: Jakub Cerny, Chun Kai Ling, Christian Kroer, Garud Iyengar
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Empirical Evaluation We seek to answer the following questions. (i) Performance: how does DO compare with the full LP solver? (ii) Sparsity: how do sizes of the (approximate) NE s support and DO subgames compare to the game size itself? (iii) Factors: how does performance scale with other game parameters? The experiments were conducted on an Intel Xeon Gold 6226, 2.9Ghz on a Linux 64-bit platform. We used Gurobi 10.0.3 [Gurobi Optimization, LLC, 2023] for MILPs and LPs. Each run was restricted to 8 threads and 32GB of RAM. Our DO algorithm was implemented in Python 3.7.9 and configured with a tolerance of ϵ = 10 3. The real-world physical graphs were obtained using OSMnx [Boeing, 2017]. For experiments with randomness, 20 instances were generated and solved. We report their standard errors in plots, noting that in almost all cases these are negligible. We limit solvers to 6 hours for each instance . Game sizes are defined as |Pd|+|Pa| when reporting runtimes. We allow loops in Gi and set R such that the attacker is interdicted when players share a vertex. Application specific instantiations of R and r , as well as additional setup and results are deferred to the appendix. A link to the source code is included in the full paper. |
| Researcher Affiliation | Academia | Jakub ˇCern y , Chun Kai Ling , Christian Kroer and Garud Iyengar Department of Industrial Engineering and Operations Research, Columbia University |
| Pseudocode | Yes | Algorithm 1 Double Oracle for LGSGs |
| Open Source Code | Yes | Full paper and source code: https://arxiv.org/abs/2405.03070. [...] A link to the source code is included in the full paper. |
| Open Datasets | Yes | The real-world physical graphs were obtained using OSMnx [Boeing, 2017]. For experiments with randomness, 20 instances were generated and solved. [...] We experiment on (a) a synthetic 4-connected 5 × 5 grid world, with a few edges randomly removed per player (making the grids unique), and (b) the map of Lower Manhattan in New York City, USA, with 87 nodes and 191 edges (depicted in Figure 3). [...] Consider Minnewaska State Park in NY, USA (138 nodes, 201 edges, Figure 3). [...] (ii) the city of Bakhmut, Ukraine (denoted BK, 721 nodes, 1229 edges, Figure 3). |
| Dataset Splits | No | The paper does not mention specific training, validation, or test dataset splits. The 'data' in this context refers to graph structures (synthetic and real-world maps) used to define the games, not datasets typically split for machine learning model training. |
| Hardware Specification | Yes | The experiments were conducted on an Intel Xeon Gold 6226, 2.9Ghz on a Linux 64-bit platform. Each run was restricted to 8 threads and 32GB of RAM. |
| Software Dependencies | Yes | We used Gurobi 10.0.3 [Gurobi Optimization, LLC, 2023] for MILPs and LPs. Our DO algorithm was implemented in Python 3.7.9 and configured with a tolerance of ϵ = 10 3. The real-world physical graphs were obtained using OSMnx [Boeing, 2017]. |
| Experiment Setup | Yes | Our DO algorithm was implemented in Python 3.7.9 and configured with a tolerance of ϵ = 10 3. We limit solvers to 6 hours for each instance. |