Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains

Among the many deployment areas of Stackelberg Security games, a major area involves games played out in space and time, which includes applications in multiple mobile defender resources protecting multiple mobile targets. Previous algorithms for such spatio-temporal security games fail to scale-up and little is known ofthe computational complexity properties of these problems.This paper provides a novel oracle-based algorithmic framework for a systematic study of different problem variants of computing optimal (minimax) strategies in spatio-temporal security games. Our framework enables efficient computation of a minimax strategy when the problem admits a polynomial-time oracle. Furthermore,for the cases in which efficient oracles are difficultto find, we propose approximations or prove hardness results.

• Publication year

  2014

• Venue

  AAAI Conference on Artificial Intelligence

• Publication date

  2014-06-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1609/aaai.v28i1.8878
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Solving Security Games on Graphs via Marginal Probabilities

  2013cited by this paper
• Double-oracle algorithm for computing an exact nash equilibrium in zero-sum extensive-form games

  2013cited by this paper
• Optimal patrol strategy for protecting moving targets with multiple mobile resources

  2013cited by this paper
• PROTECT: a deployed game theoretic system to protect the ports of the United States

  2012cited by this paper
• TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems

  2012cited by this paper
• A double oracle algorithm for zero-sum security games on graphs

  2011cited by this paper
• Computing time-dependent policies for patrolling games with mobile targets

  2011influential reference
• Computing Randomized Security Strategies in Networked Domains

  2011cited by this paper
• Security Games with Arbitrary Schedules: A Branch and Price Approach

  2010cited by this paper
• Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games

  2010cited by this paper
• Computing optimal randomized resource allocations for massive security games

  2009cited by this paper
• Multi-Step Multi-Sensor Hider-Seeker Games

  2009cited by this paper
• Leader-follower strategies for robotic patrolling in environments with arbitrary topologies

  2009cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• The ellipsoid method and its consequences in combinatorial optimization

  1981cited by this paper
• Best Algorithms for Approximating the Maximum of a Submodular Set Function

  1978cited by this paper
• Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence Scaling-Up Security Games with Boundedly Rational Adversaries: A Cutting-Plane Approach

  year unknowncited by this paper

• Polynomial-Time Computation of Exact Φ-Equilibria in Polyhedral Games

  2024cites this paper
• Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?

  2024cites this paper
• Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable

  2021cites this paper
• Software Diversity for Cyber Deception

  2020cites this paper
• An Agent-Based Empirical Game Theory Approach for Airport Security Patrols

  2020cites this paper
• Computing Stackelberg Equilibria of Large General-Sum Games

  2019cites this paper
• Proactive Network Defense with Game Theory

  2019cites this paper
• Solving Stackelberg security Markov games employing the bargaining Nash approach: Convergence analysis

  2018cites this paper
• Spatio-Temporal Games Beyond One Dimension

  2018influential citation
• Policy Learning for Continuous Space Security Games Using Neural Networks

  2018cites this paper
• From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games

  2018cites this paper
• Security Game with Non-additive Utilities and Multiple Attacker Resources

  2017cites this paper
• Learning for Continuous Space Security Games using Neural Networks

  2017cites this paper
• A Polynomial Time Algorithm for Spatio-Temporal Security Games

  2017influential citation
• Security Game with Non-additive Utilities and Multiple Attacker Resources

  2017cites this paper
• Designing game-theoretic security strategies for large public events

  2017cites this paper
• From Duels to Battlefields: Computing Equilibria of Blotto and Other Games

  2016cites this paper
• NASG Compact NASG Defender Oracle Problem ⇑ Theorem 4 Algorithm 1 Lemma 2 Theorem 1 ⇑ ↙

  2016cites this paper
• Signaling in Bayesian Stackelberg Games

  2016cites this paper
• Game-Theoretically Allocating Resources to Catch Evaders and Payments to Stabilize Teams

  2016influential citation
• Non-Additive Security Games

  2016cites this paper
• Adversarial Risk Analysis for Urban Security Resource Allocation

  2016cites this paper
• The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design

  2016cites this paper
• Abstraction Methods for Solving Graph-Based Security Games

  2016cites this paper
• Improvements to the Linear Optimization Models of Patrol Scheduling for Mobile Targets

  2015cites this paper
• Computing Optimal Mixed Strategies for Security Games with Dynamic Payoffs

  2015cites this paper
• Exploring Information Asymmetry in Two-Stage Security Games

  2015cites this paper
• Security Games with Protection Externalities

  2015cites this paper