Research map / Learning theory and algorithms / Submodular and game algorithms
GUARD: Constructing Realistic Two-Player Matrix and Security Games for Benchmarking Game-Theoretic Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces GUARD, a framework that builds realistic matrix and security game instances from open data (Movebank animal tracks, OSM infrastructure, Census population), and shows theoretically and empirically that random games give degenerate Stackelberg equilibria.
Problem
Algorithmic game theory benchmarks rely on recreational games, classical economic games, or random payoff matrices, while realistic security games are hard to evaluate because target-value data is inaccessible.
Approach
Derive target values for green and infrastructure security games from open-access datasets (animal movement, OpenStreetMap, census population), and prove that Stackelberg equilibria in random uniform games are sparse and degenerate, favoring the defender.
Key results
- In random general-sum uniform games, the optimal 1-sparse Stackelberg strategy already achieves expected value 1-1/(n+1), and the optimal SSE value is within O(sqrt(log n)/n^1.5) of 1.
- In the GSG general-schedule SSE experiment, the real instance has support 9 versus 2, 1.7 and 1.4 for randomized baselines.
- In the ISG general-schedule experiment, the real instance has support 14 and defender utility -0.408, while randomized baselines have supports of about 1-1.7 and utilities near -0.03.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace GUARD real target values with randomized target values | GSG simple-schedule SSE · GSG, simple schedules | defender utility: -0.390 -> -0.298 $\pm$ 0.03 | Helped |
| replace GUARD real target values with randomized target values | ISG simple-schedule SSE · ISG, simple schedules | defender utility: -0.429 -> -0.214 $\pm$ 0.05 | Helped |
| replace GUARD real target values with randomized target values | GSG simple-schedule SSE · GSG, simple schedules | support size: 6 -> 5.0 $\pm$ 0.52 | Hurt |
| replace GUARD real target values with randomized target values | ISG simple-schedule SSE · ISG, simple schedules | support size: 11 -> 7.5 $\pm$ 1.20 | Hurt |
| randomize expanded NFG matrices instead of using GUARD instance | GSG general-schedule SSE · GSG, general schedules | defender utility: -0.207 -> -0.035 $\pm$ 0 | Helped |
| randomize target values instead of using GUARD instance | GSG general-schedule SSE · GSG, general schedules | support size: 9 -> 1.7 $\pm$ 0.26 | Hurt |
| randomize target values and schedule assignments instead of using GUARD instance | GSG general-schedule SSE · GSG, general schedules | support size: 9 -> 1.4 $\pm$ 0.16 | Hurt |
| randomize expanded NFG matrices instead of using GUARD instance | ISG general-schedule SSE · ISG, general schedules | defender utility: -0.408 -> -0.026 $\pm$ 0 | Helped |
| randomize target values instead of using GUARD instance | ISG general-schedule SSE · ISG, general schedules | support size: 14 -> 1 $\pm$ 0 | Hurt |
| randomize target values and schedule assignments instead of using GUARD instance | ISG general-schedule SSE · ISG, general schedules | support size: 14 -> 1 $\pm$ 0 | Hurt |
Surprising findings
- Randomized Stackelberg games give the defender near-maximal utility with pure or very sparse strategies, effectively ignoring the attacker.
- With simple schedules, real instances had slightly lower defender utility and larger support than randomized counterparts.
Limitations
- Scalability: defender path action sets explode at high timestep counts, making utility matrices intractable.
- Only tested on GSG and ISG domains; data may imperfectly capture real-world dynamics.
- Some realistic instances degenerate due to unreachable targets under game length and home-base constraints.
Experimental setup
Datasets: Movebank African elephant GPS collar data (Lobéké National Park, 3,183 observations) OpenStreetMap infrastructure features via Overpass Turbo (23,607 features, NYC) 2020 US Census TIGER/Line block population (288,819 blocks, New York)
Benchmarks: GUARD preset GSG instances (Lobéké elephants) GUARD preset ISG instances (Manhattan Chinatown)
Metrics: defender utility support size runtime convergence gap
Baselines: random uniform games (RM) randomized target values (RT) randomized target values and schedules (RTS) Regret Matching Regret Matching+ Predictive Regret Matching+ Double Oracle
Builds on: OpenSpiel Gamut GraphChase Double Oracle Regret Matching+
Closest papers by meaning
- Non-Additive Security Games (AAAI 2017 · similarity 0.87)
- Safe Search for Stackelberg Equilibria in Extensive-Form Games (AAAI 2021 · similarity 0.87)
- Preventing Illegal Logging: Simultaneous Optimization of Resource Teams and Tactics for Security (AAAI 2016 · similarity 0.87)
- Improving Community-Participated Patrol for Anti-Poaching (AAAI 2025 · similarity 0.86)
- Regret Minimization in Stackelberg Games with Side Information (NeurIPS 2024 · similarity 0.85)
- The Attacker in the Mirror: Breaking Self-Consistency in Safety via Anchored Bipolicy Self-Play (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.