Spatio-Temporal Games Beyond One Dimension

ABSTRACT

Protecting valuable \em targets from an adversary is an ever-important international concern with far-reaching applications in wildlife protection, border protection, counter-terrorism, protection of ships from piracy, etc. As a successful recent approach, \em security games cast these issues as two-player games between a \em defender and an \em attacker. The defender decides on how to allocate the available \em resources to protect targets against the attacker who strives to inflict damage on them. The main question of interest here is equilibrium computation. Our focus in this paper is on \em spatio-temporal security games. However, inspired by the paper of Xu [EC'16], we start with a general model of security games and show that any approximation (of any factor) for the defender's best response (DBR) problem leads to an approximation of the same factor for the actual game. In most applications of security games, the targets are mobile. This leads to a well-studied class of succinct games, namely \em spatio-temporal security games, that is played in space and time. In such games, the defender has to specify a time-dependent patrolling strategy over a spatial domain to protect a set of moving targets. We give a generalized model of prior spatio-temporal security games that is played on a base graph G . That is, the patrols can be placed on the vertices of G and move along its edges over time. This unifies and generalizes prior spatio-temporal models that only consider specific spatial domains such as lines or grids. Graphs can further model many other domains of practical interest such as roads, internal maps of buildings, etc. Finding an optimal defender strategy becomes NP-hard on general graphs. To overcome this, we give an LP relaxation of the DBR problem and devise a rounding technique to obtain an almost optimal integral solution. More precisely, we show that one can achieve a $(1-ε)$-approximation in polynomial time if we allow the defender to use $łceil łn(1/ε)\rceil$ times more patrols. We later show that this result is in some sense the best possible polynomial time algorithm (unless P=NP). Furthermore, we show that by using a novel \em dependent rounding technique, the same LP relaxation gives an optimal solution for specific domains of interest, such as one-dimensional spaces. This result simplifies and improves upon the prior algorithm of Behnezhad et al. ~[EC'17] on several aspects and can be generalized to other graphs of interest such as cycles. Lastly, we note that most prior algorithms for security games assume that the attacker attacks only once and become intractable for a super-constant number of attacks. Our algorithms are fully polynomial in the input size and work for any given number of attacks.

References

1. AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini, and Saeed Seddighin . 2016. From Duels to Battlefields: Computing Equilibria of Blotto and Other Games. AAAI. 376--382.
2. Soheil Behnezhad, Sina Dehghani, Mahsa Derakhshan, MohammadTaghi HajiAghayi, and Saeed Seddighin . 2017 a. Faster and Simpler Algorithm for Optimal Strategies of Blotto Game Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence.
3. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Aleksandrs Slivkins . 2017 b. A Polynomial Time Algorithm for Spatio-Temporal Security Games Proceedings of the 2017 ACM Conference on Economics and Computation. ACM, 697--714.
4. Branislav Bovsanskỳ, Viliam Lisỳ, Michal Jakob, and Michal Pvechouvcek . 2011. Computing time-dependent policies for patrolling games with mobile targets The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 3. International Foundation for Autonomous Agents and Multiagent Systems, 989--996.
5. Matthew Brown, Arunesh Sinha, Aaron Schlenker, and Milind Tambe . 2016. One Size Does Not Fit All: A Game-Theoretic Approach for Dynamically and Effectively Screening for Threats. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. 425--431.
6. Vincent Conitzer and Tuomas Sandholm . 2006. Computing the optimal strategy to commit to. In Proceedings 7th ACM Conference on Electronic Commerce (EC-2006). 82--90.
7. Bruno Escoffier and Vangelis Th Paschos . 2006. Completeness in approximation classes beyond apx. Theoretical computer science Vol. 359, 1--3 (2006), 369--377.
8. Fei Fang, Albert Xin Jiang, and Milind Tambe . 2013. Optimal patrol strategy for protecting moving targets with multiple mobile resources Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. International Foundation for Autonomous Agents and Multiagent Systems, 957--964.
9. Fei Fang, Thanh Hong Nguyen, Rob Pickles, Wai Y Lam, Gopalasamy R Clements, Bo An, Amandeep Singh, Milind Tambe, and Andrew Lemieux . 2016. Deploying PAWS: Field Optimization of the Protection Assistant for Wildlife Security. AAAI. 3966--3973.
10. Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz . 2011. Dueling algorithms Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, 215--224.
11. Manish Jain, Erim Kardes, Christopher Kiekintveld, Fernando Ordónez, and Milind Tambe . 2010. Security Games with Arbitrary Schedules: A Branch and Price Approach. AAAI.
12. Christopher Kiekintveld, Manish Jain, Jason Tsai, James Pita, Fernando Ordó nez, and Milind Tambe . 2009. Computing optimal randomized resource allocations for massive security games Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 689--696.
13. Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr . 2010. Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games.. In AAAI.
14. Joshua Letchford and Vincent Conitzer . 2013. Solving Security Games on Graphs via Marginal Probabilities Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence.
15. James Pita, Manish Jain, Janusz Marecki, Fernando Ordó nez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, and Sarit Kraus . 2008. Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport. Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track. International Foundation for Autonomous Agents and Multiagent Systems, 125--132.
16. Tim Roughgarden . 2010. Computing Equilibria: A Computational Complexity Perspective. Economic Theory, Vol. 42, 1 (2010), 193--236.
17. Milind Tambe . 2011. Security and game theory: algorithms, deployed systems, lessons learned. Cambridge University Press.
18. Haifeng Xu . 2016. The mysteries of security games: Equilibrium computation becomes combinatorial algorithm design. In Proceedings of the 2016 ACM Conference on Economics and Computation. ACM, 497--514.
19. Haifeng Xu, Fei Fang, Albert Xin Jiang, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe . 2014. Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains. AAAI. Citeseer, 1500--1506.
20. Zhengyu Yin, Albert Xin Jiang, Milind Tambe, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, and John P Sullivan . 2012. TRUSTS: Scheduling randomized patrols for fare inspection in transit systems using game theory. AI Magazine, Vol. 33, 4 (2012), 59.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design