research-article

Public Access

Security Game with Non-additive Utilities and Multiple Attacker Resources

Authors:

Ness ShroffAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 1, Issue 1

Article No.: 13, Pages 1 - 32

https://doi.org/10.1145/3084450

Published: 13 June 2017 Publication History

Abstract

There has been significant interest in studying security games for modeling the interplay of attacks and defenses on various systems involving critical infrastructure, financial system security, political campaigns, and civil safeguarding. However, existing security game models typically either assume additive utility functions, or that the attacker can attack only one target. Such assumptions lead to tractable analysis, but miss key inherent dependencies that exist among different targets in current complex networks. In this paper, we generalize the classical security game models to allow for non-additive utility functions. We also allow attackers to be able to attack multiple targets. We examine such a general security game from a theoretical perspective and provide a unified view. In particular, we show that each security game is equivalent to a combinatorial optimization problem over a set system ε, which consists of defender's pure strategy space. The key technique we use is based on the transformation, projection of a polytope, and the ellipsoid method. This work settles several open questions in security game domain and significantly extends the state-of-the-art of both the polynomial solvable and NP-hard class of the security game.

References

[1]

Bo An, Eric Shieh, Milind Tambe, Rong Yang, Craig Baldwin, Joseph DiRenzo, Ben Maule, and Garrett Meyer. 2012. PROTECT--A Deployed Game Theoretic System for Strategic Security Allocation for the United States Coast Guard. AI Magazine 33, 4 (2012), 96.

[2]

Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. 2015. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the Sixteenth ACM Conference on Economics and Computation. ACM, 61--78.

Digital Library

[3]

Sayan Bhattacharya, Vincent Conitzer, and Kamesh Munagala. 2011. Approximation algorithm for security games with costly resources. In International Workshop on Internet and Network Economics. Springer, 13--24.

Digital Library

[4]

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 AAAI conference on Artificial Intelligence (AAAI).

Digital Library

[5]

Xi Chen, Xiaotie Deng, and Shang-Hua Teng. 2009. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM) 56, 3 (2009), 14.

Digital Library

[6]

Vincent Conitzer and Tuomas Sandholm. 2006. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM conference on Electronic commerce. ACM, 82--90.

Digital Library

[7]

Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. 2009. The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 1 (2009), 195--25

Digital Library

[8]

Fei Fang, Albert Xin Jiang, and Milind Tambe. 2013. Optimal patrol strategy for protecting moving targets with multiple mobile resources. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems. International Foundation for Autonomous Agents and Multiagent Systems, 957--964.

Digital Library

[9]

Fei Fang, Thanh H 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. In Proceedings of the Twenty-Eighth Innovative Applications of Artificial Intelligence Conference.

Digital Library

[10]

Fedor V Fomin and Dieter Kratsch. 2010. Exact exponential algorithms. Springer Science & Business Media.

Digital Library

[11]

Martin Grötschel, László Lovász, and Alexander Schrijver. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 2 (1981), 169--197.

[12]

Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz. 2011. Dueling algorithms. In Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM, 215--224.

Digital Library

[13]

M. Jain, D. Korzhyk, O. Vaněk, V. Conitzer, M. Pěchouček, and M Tambe. 2011. A double oracle algorithm for zero-sum security games on graphs. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 1 (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems, 327--334.

Digital Library

[14]

Robert Kennes and Philippe Smets. 1990. Computational aspects of the Mobius transformation. In Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence. Elsevier Science Inc., 401--416.

Digital Library

[15]

C. Kiekintveld, M. Jain, J. Tsai, J. Pita, F. Ordóñez, and M. Tambe. 2009. Computing optimal randomized resource allocations for massive security games. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). International Foundation for Autonomous Agents and Multiagent Systems, 689--696.

Digital Library

[16]

Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. 2010. Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games. In AAAI.

Digital Library

[17]

Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. 2011. Security games with multiple attacker resources. In IJCAI Proceedings- International Joint Conference on Artificial Intelligence, Vol. 22. Citeseer, 273--279.

Digital Library

[18]

Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe. 2011. Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness. J. Artif. Intell. Res.(JAIR) 41 (2011), 297--327.

Digital Library

[19]

Carlton E Lemke and Joseph T Howson, Jr. 1964. Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12, 2 (1964), 413--423.

[20]

Joshua Letchford and Vincent Conitzer. 2013. Solving Security Games on Graphs via Marginal Probabilities. In AAAI.

Digital Library

[21]

Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. 2003. Playing large games using simple strategies. In Proceedings of the 4th ACM conference on Electronic commerce (EC). ACM, 36--41.

Digital Library

[22]

Praveen Paruchuri, Jonathan P Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, and Sarit Kraus. 2008. Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2. International Foundation for Autonomous Agents and Multiagent Systems, 895--902.

Digital Library

[23]

James Pita, Manish Jain, Janusz Marecki, Fernando Ordóñez, 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. In 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.

Digital Library

[24]

Maurice Sion and others. 1958. On general minimax theorems. Pacific J. Math 8, 1 (1958), 171--176. {25} M. Tambe. 2011. Security and game theory: Algorithms, deployed systems, lessons learned. Cambridge University Press.

Digital Library

[25]

Jason Tsai, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe, and Shyamsunder Rathi. 2009. IRIS-a tool for strategic security allocation in transportation networks. (2009).

[26]

Heinrich Von Stackelberg. 1934. Marktform und gleichgewicht. J. springer.

[27]

Bernhard Von Stengel and Shmuel Zamir. 2004. Leadership with commitment to mixed strategies. (2004).

[28]

Sinong Wang, Fang Liu, and Ness Shroff. 2016. Non-additive Security Game. arXiv preprint arXiv:1603.00749 (2016).

[29]

Haifeng Xu. 2016. The Mysteries of Security Games: Equilibrium Computation becomes Combinatorial Algorithm Design. arXiv preprint arXiv:1603.02377 (2016).

Digital Library

[30]

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. In AAAI. Citeseer, 1500--1506.

Digital Library

Cited By

Zhang MZheng ZShroff N(2020)Defending Against Stealthy Attacks on Multiple Nodes With Limited Resources: A Game-Theoretic AnalysisIEEE Transactions on Control of Network Systems10.1109/TCNS.2020.29932817:4(1665-1677)Online publication date: Dec-2020
https://doi.org/10.1109/TCNS.2020.2993281
Baarzi AZhu TUrgaonkar B(2019)BurScaleProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362706(126-138)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362706
Li YDai WBai JGan XWang JWang X(2019)An Intelligence-Driven Security-Aware Defense Mechanism for Advanced Persistent ThreatsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2018.284767114:3(646-661)Online publication date: Mar-2019
https://doi.org/10.1109/TIFS.2018.2847671
Show More Cited By

Index Terms

Security Game with Non-additive Utilities and Multiple Attacker Resources
1. Security and privacy
  1. Network security
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design

Recommendations

Security Game with Non-additive Utilities and Multiple Attacker Resources
Performance evaluation review

There has been significant interest in studying security games for modeling the interplay of attacks and defenses on various systems involving critical infrastructure, financial system security, political campaigns, and civil safeguarding. However, ...
Security Game with Non-additive Utilities and Multiple Attacker Resources
SIGMETRICS '17 Abstracts: Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

There has been significant interest in studying security games for modeling the interplay of attacks and defenses on various systems involving critical infrastructure, financial system security, political campaigns, and civil safeguarding. However, ...
On the parameterized complexity of dominant strategies
ACSC '12: Proceedings of the Thirty-fifth Australasian Computer Science Conference - Volume 122

In game theory, a strategy for a player is dominant if, regardless of what any other player does, the strategy earns a better payoff than any other. If the payoff is strictly better, the strategy is named strictly dominant, but if it is simply not worse,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 1, Issue 1

June 2017

712 pages

EISSN:2476-1249

DOI:10.1145/3107080

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2017

Published in POMACS Volume 1, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Army Research Office
Office of Naval Research
Defense Thrust Reduction Agency

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
348
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)20

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang MZheng ZShroff N(2020)Defending Against Stealthy Attacks on Multiple Nodes With Limited Resources: A Game-Theoretic AnalysisIEEE Transactions on Control of Network Systems10.1109/TCNS.2020.29932817:4(1665-1677)Online publication date: Dec-2020
https://doi.org/10.1109/TCNS.2020.2993281
Baarzi AZhu TUrgaonkar B(2019)BurScaleProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362706(126-138)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362706
Li YDai WBai JGan XWang JWang X(2019)An Intelligence-Driven Security-Aware Defense Mechanism for Advanced Persistent ThreatsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2018.284767114:3(646-661)Online publication date: Mar-2019
https://doi.org/10.1109/TIFS.2018.2847671
Emadi HBhattacharya S(2019)On Security Games with Additive UtilityIFAC-PapersOnLine10.1016/j.ifacol.2019.12.18052:20(351-356)Online publication date: 2019
https://doi.org/10.1016/j.ifacol.2019.12.180
Larsen-Ledet IKorsgaard H(2019)Territorial Functioning in Collaborative WritingComputer Supported Cooperative Work10.1007/s10606-019-09359-828:3-4(391-433)Online publication date: 31-Jul-2019
https://dl.acm.org/doi/10.1007/s10606-019-09359-8
Zhang XHipel KGe BTan Y(2019)A game‐theoretic model for resource allocation with deception and defense effortsSystems Engineering10.1002/sys.2147922:3(282-291)Online publication date: 17-Feb-2019
https://doi.org/10.1002/sys.21479

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents