Introduction to game theory. (English) Zbl 07526396
Kamhoua, Charles A. (ed.) et al., Game theory and machine learning for cyber security. Piscataway, NJ: IEEE Press; Hoboken, NJ: John Wiley & Sons. 21-46 (2021).
MSC:
| 68M25 | Computer security |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 91A80 | Applications of game theory |
References:
| [1] | EitanAltman , KonstantinAvratchenkov , NicolasBonneau , MérouaneDebbah , RachidEl‐Azouzi , and Daniel SadocMenasché . Constrained stochastic games in wireless networks. In IEEE GLOBECOM 2007‐IEEE Global Telecommunications Conference , pp. 315 - 320 . IEEE, 2007 . |
| [2] | Robert G.Bland , DonaldGoldfarb , and Michael J.Todd . The ellipsoid method: A survey . Operations Research , 29 ( 6 ): 1039 - 1091 , 1981 . · Zbl 0474.90056 |
| [3] | Stephen P.Bradley , Arnoldo C.Hax , and Thomas L.Magnanti . Applied Mathematical Programming . Addison‐Wesley , 1977 . |
| [4] | William AustinCasey , QuanyanZhu , Jose AndreMorales , and BudMishra . Compliance control: Managed vulnerability surface in social‐technological systems via signaling games. In Proceedings of the 7th ACM CCS International Workshop on Managing Insider Security Threats , pp. 53 - 62 . ACM , 2015 . |
| [5] | GeorgiosChalkiadakis , EdithElkind , and MichaelWooldridge . Computational aspects of cooperative game theory . Synthesis Lectures on Artificial Intelligence and Machine Learning , 5 ( 6 ): 1 - 168 , 2011 . |
| [6] | JuntaoChen and QuanyanZhu . Optimal contract design under asymmetric information for cloud‐enabled internet of controlled things . In International Conference on Decision and Game Theory for Security , pp. 329 - 348 . Springer , 2016 . |
| [7] | JuntaoChen and QuanyanZhu . Security as a service for cloud‐enabled internet of controlled things under advanced persistent threats: A contract design approach . IEEE Transactions on Information Forensics and Security , 12 ( 11 ): 2736 - 2750 , 2017 . |
| [8] | XiChen and XiaotieDeng . 3‐Nash is ppad‐complete . Electronic Colloquium on Computational Complexity , 134 : 2 - 29 . Citeseer, 2005 . |
| [9] | XiChen and XiaotieDeng . Settling the complexity of two‐player Nash equilibrium. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) , pp. 261 - 272 . IEEE, 2006 . |
| [10] | VincentConitzer and TuomasSandholm . Computing the optimal strategy to commit to. In Proceedings of the 7th ACM Conference on Electronic Commerce , pp. 82 - 90 . ACM , 2006 . |
| [11] | Edward A.Cranford , Chris tian Lebiere , CleotildeGonzalez , SarahCooney , PhebeVayanos , and MilindTambe . Learning about cyber deception through simulations: Predictions of human decision making with deceptive signals in Stackelberg security games . In Proceedings of the 40th Annual Meeting of the Cognitive Science Society, CogSci 2018, Madison, WI, USA, 25-28 July 2018 , 2018 . |
| [12] | ConstantinosDaskalakis , Paul W.Goldberg , and Christos H.Papadimitriou . The complexity of computing a Nash equilibrium . SIAM Journal on Computing , 39 ( 1 ): 195 - 259 , 2009 . · Zbl 1185.91019 |
| [13] | Mary‐AnnDimand and Robert W.Dimand . The History of Game Theory, Volume 1: From the Beginnings to 1945 , Volume 1. Routledge , 1996 . |
| [14] | Cuong T.Do , Nguyen H.Tran , ChoongseonHong , Charles A.Kamhoua , Kevin A.Kwiat , ErikBlasch , ShaoleiRen , NikiPissinou , and Sundaraja SitharamaIyengar . Game theory for cyber security and privacy . ACM Computing Surveys (CSUR) , 50 ( 2 ): 1 - 37 , 2017 . |
| [15] | Prajit K.Dutta . A folk theorem for stochastic games . Journal of Economic Theory , 66 ( 1 ): 1 - 32 , 1995 . · Zbl 0835.90139 |
| [16] | FeiFang , Thanh H.Nguyen , RobPickles , Wai Y.Lam , Gopalasamy R.Clements , BoAn , AmandeepSingh , MilindTambe , and AndrewLemieux . Deploying paws: Field optimization of the protection assistant for wildlife security. In Proceedings of the Twenty‐Eighth Innovative Applications of Artificial Intelligence Conference (IAAI 2016) , pp. 3996 - 3973 . AAAI Press , 2016 . |
| [17] | Muhammad JunaidFarooq and QuanyanZhu . Optimal dynamic contract for spectrum reservation in mission‐critical UNB‐IoT systems. In 2018 16th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) , pp. 1 - 6 . IEEE , 2018 . |
| [18] | JerzyFilar and KoosVrieze . Competitive Markov Decision Processes . Springer Science & Business Media , 2012 . |
| [19] | DrewFudenberg , DavidLevine , and EricMaskin . The folk theorem with imperfect public information . Econometrica , 62 ( 5 ): 997 - 1039 , 1994 . · Zbl 0819.90137 |
| [20] | John C.Harsanyi . Games with incomplete information played by Bayesian players, I-III: Part I. The basic model . Management Science , 14 ( 3 ): 159 - 182 , 1967 . · Zbl 0207.51102 |
| [21] | John C.Harsanyi . Games with incomplete information played by bayesian players, Part II. Bayesian equilibrium points . Management Science , 14 ( 5 ): 320 - 334 , 1968 . · Zbl 0177.48402 |
| [22] | KarelHorák , BranislavBos̆anskỳ , and MichalPěchouček . Heuristic search value iteration for one‐sided partially observable stochastic games. In Thirty‐First AAAI Conference on Artificial Intelligence . AAAI Press , 2017a . |
| [23] | KarelHorák , QuanyanZhu , and BranislavBos̆anskỳ . Manipulating adversary’s belief: A dynamic game approach to deception by design for proactive network security. In International Conference on Decision and Game Theory for Security , pp. 273 - 294 . Springer , 2017b . |
| [24] | LinanHuang and QuanyanZhu . Dynamic Bayesian games for adversarial and defensive cyber deception . In Autonomous Cyber Deception , pp. 75 - 97 . Springer , 2019 . |
| [25] | LinanHuang and QuanyanZhu . Dynamic games of asymmetric information for deceptive autonomous vehicles . 2020 . |
| [26] | ZhuJi , WeiYu , and K. J. RayLiu . A belief evaluation framework in autonomous MANETs under noisy and imperfect observation: Vulnerability analysis and cooperation enforcement . IEEE Transactions on Mobile Computing , 9 ( 9 ): 1242 - 1254 , 2010 . |
| [27] | LibinJiang , VenkatAnantharam , and JeanWalrand . How bad are selfish investments in network security?IEEE/ACM Transactions on Networking , 19 ( 2 ): 549 - 560 , 2010 . |
| [28] | ChristopherKiekintveld , ManishJain , JasonTsai , JamesPita , FernandoOrdóñez , and MilindTambe . Computing optimal randomized resource allocations for massive security games. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, Volume 1, AAMAS ’09 , pp. 689 - 696 . International Foundation for Autonomous Agents and Multiagent Systems , Richland, SC, 2009 . |
| [29] | David M.Kreps and Rober t Wilson . Sequential equilibria . Econometrica: Journal of the Econometric Society , 50 ( 4 ): 863 - 894 , 1982 . · Zbl 0483.90092 |
| [30] | Carlton E.Lemke and Joseph T.Howson , Jr. Equilibrium points of bimatrix games . Journal of the Society for industrial and Applied Mathematics , 12 ( 2 ): 413 - 423 , 1964 . · Zbl 0128.14804 |
| [31] | KevinLeyton‐Brown and YoavShoham . Essentials of game theory: A concise multidisciplinary introduction . Synthesis Lectures on Artificial Intelligence and Machine Learning , 2 ( 1 ): 1 - 88 , 2008 . · Zbl 1203.91002 |
| [32] | BoLi and YevgeniyVorobeychik . Feature cross‐substitution in adversarial classification. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 8-13 December 2014, Montreal, Quebec, Canada , pp. 2087 - 2095 , 2014 . |
| [33] | BoLi and YevgeniyVorobeychik . Scalable optimization of randomized operational decisions in adversarial classification settings. In Artificial Intelligence and Statistics , pp. 599 - 607 , 2015 . |
| [34] | Richard D.McKelvey and Thomas R.Palfrey . Quantal response equilibria for normal form games . Games and Economic Behavior , 10 ( 1 ): 6 - 38 , 1995 . · Zbl 0832.90126 |
| [35] | Richard D.McKelvey , Andrew M.McLennan , and Theodore L.Turocy . Gambit: Software tools for game theory . 2006 . www.gambit‐project.org (accessed 18 March 2021). |
| [36] | SanjayMehrotra . On the implementation of a primal‐dual interior point method . SIAM Journal on Optimization , 2 ( 4 ): 575 - 601 , 1992 . · Zbl 0773.90047 |
| [37] | FeiMiao and QuanyanZhu . A moving‐horizon hybrid stochastic game for secure control of cyber‐physical systems. In Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on , pp. 517 - 522 . IEEE , 2014 . |
| [38] | AminMohammadi , Mohammad HosseinManshaei , Monireh MohebbiMoghaddam , and QuanyanZhu . A game‐theoretic analysis of deception over social networks using fake avatars . In International Conference on Decision and Game Theory for Security , pp. 382 - 394 . Springer , 2016 . · Zbl 1453.91035 |
| [39] | Roger B.Myerson . Optimal auction design . Mathematics of Operations Research , 6 ( 1 ): 58 - 73 , 1981 . · Zbl 0496.90099 |
| [40] | Roger B.Myerson . Mechanism design . In Allocation, Information and Markets , pp. 191 - 206 . Springer , 1989 . |
| [41] | Roger B.Myerson . Game Theory: Analysis of Conflict . Harvard University Press , 1991 . http://www.jstor.org/stable/j.ctvjsf522 . · Zbl 0729.90092 |
| [42] | JohnNash . Non‐cooperative games . Annals of Mathematics , 54 ( 2 ): 286 - 295 , 1951 . · Zbl 0045.08202 |
| [43] | John A.Nelder and RogerMead . A simplex method for function minimization . The Computer Journal , 7 ( 4 ): 308 - 313 , 1965 . · Zbl 0229.65053 |
| [44] | J. v.Neumann . Zur theorie der gesellschaftsspiele . Mathematische Annalen , 100 ( 1 ): 295 - 320 , 1928 . · JFM 54.0543.02 |
| [45] | Thanh HongNguyen , RongYang , AmosAzaria , SaritKraus , and MilindTambe . Analyzing the effectiveness of adversary modeling in security games . Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 27 , No. 1 . AAAI , 2013 . |
| [46] | PraveenParuchuri , Jonathan P.Pearce , JanuszMarecki , MilindTambe , FernandoOrdonez , and SaritKraus . 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, AAMAS ’08 , pp. 895 - 902 . International Foundation for Autonomous Agents and Multiagent Systems , Richland, SC, 2008 . |
| [47] | ShuvaPaul and ZhenNi . A strategic analysis of attacker‐defender repeated game in smart grid security. In 2019 IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT) , pp. 1 - 5 . IEEE , 2019 . |
| [48] | JeffreyPawlick and QuanyanZhu . Proactive defense against physical denial of service attacks using poisson signaling games . In International Conference on Decision and Game Theory for Security , pp. 336 - 356 . Springer , 2017 . |
| [49] | JeffreyPawlick , Edward Co lbert , and QuanyanZhu . Modeling and analysis of leaky deception using signaling games with evidence . IEEE Transactions on Information Forensics and Security , 14 ( 7 ): 1871 - 1886 , 2018 . |
| [50] | JeffreyPawlick , EdwardColbert , and QuanyanZhu . A game‐theoretic taxonomy and survey of defensive deception for cybersecurity and privacy . ACM Computing Surveys (CSUR) , 52 ( 4 ): 1 - 28 , 2019 . |
| [51] | JamesPita , ManishJain , FernandoOrdonez , MilindTambe , and SaritKraus . Robust solutions to Stackelberg games: Addressing bounded rationality and limited observations in human cognition . Artificial Intelligence Journal , 174 ( 15 ): 1142 - 1171 , 2010 . · Zbl 1237.91065 |
| [52] | J.Rosenmüller . On a generalization of the Lemke-Howson algorithm to noncooperative n‐person games . SIAM Journal on Applied Mathematics , 21 ( 1 ): 73 - 79 , 1971 . · Zbl 0222.90053 |
| [53] | AaronSchlenker , HaifengXu , MinaGuirguis , ChristopherKiekintveld , AruneshSinha , MilindTambe , SolomonSonya , DarrylBalderas , and NoahDunstatter . Don’t bury your head in warnings: A game‐theoretic approach for intelligent allocation of cyber‐security alerts . In Proceedings of the Twenty‐Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, 19-25 August 2017 , pp. 381 - 387 , 2017 . https://doi.org/10.24963/ijcai.2017/54. |
| [54] | AaronSchlenker , OmkarThakoor , HaifengXu , MilindTambe , PhebeVayanos , FeiFang , LongTran‐Thanh , and YevgeniyVorobeychik . Deceiving cyber adversaries: A game theoretic approach. In International Conference on Autonomous Agents and Multiagent Systems, Stockholm, Sweden. 10-15 July , 2018 . |
| [55] | YoavShoham and KevinLeyton‐Brown . Multiagent Systems: Algorithmic, Game‐Theoretic, and Logical Foundations . Cambridge University Press , 2008 . |
| [56] | MilindTambe . Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned . Cambridge University Press , 2011 . |
| [57] | OmkarThakoor , MilindTambe , PhebeVayanos , HaifengXu , ChristopherKiekintveld , and FeiFang . Cyber camouflage games for strategic deception . In International Conference on Decision and Game Theory for Security , pp. 525 - 541 . Springer , 2019 . |
| [58] | KunWang , LiYuan , ToshiakiMiyazaki , YuanfangChen , and YanZhang . Jamming and eavesdropping defense in green cyber-physical transportation systems using a Stackelberg game . IEEE Transactions on Industrial Informatics , 14 ( 9 ): 4232 - 4242 , 2018 . |
| [59] | ZhihengXu and QuanyanZhu . A cyber‐physical game framework for secure and resilient multi‐agent autonomous systems. In Decision and Control (CDC), 2015 IEEE 54th Annual Conference on , pp. 5156-5161. IEEE , 2015 . |
| [60] | ZhihengXu and QuanyanZhu . Cross‐layer secure and resilient control of delay‐sensitive networked robot operating systems. In 2018 IEEE Conference on Control Technology and Applications (CCTA) , pp. 1712 - 1717 . IEEE , 2018 . |
| [61] | RongYang , FernandoOrdonez , and MilindTambe . Computing optimal strategy against quantal response in security games. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Volume 2 , pp. 847 - 854 . International Foundation for Autonomous Agents and Multiagent Systems , 2012 . |
| [62] | RongYang , BenjaminFord , MilindTambe , and AndrewLemieux . Adaptive resource allocation for wildlife protection against illegal poachers. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Paris, France, 5-9 May , 2014 . |
| [63] | YuanYuan , FuchunSun , and HuapingLiu . Resilient control of cyber‐physical systems against intelligent attacker: A hierarchal Stackelberg game approach . International Journal of Systems Science , 47 ( 9 ): 2067 - 2077 , 2016 . · Zbl 1345.93049 |
| [64] | TaoZhang and Quanyan Zhu . Strategic defense against deceptive civilian gps spoofing of unmanned aerial vehicles . In International Conference on Decision and Game Theory for Security , pp. 213 - 233 . Springer , 2017 . |
| [65] | TaoZhang , LinanHuang , JeffreyPawlick , and QuanyanZhu . Game‐theoretic analysis of cyber deception: Evidence‐based strategies and dynamic risk mitigation . In Charles A.Kamhoua (ed.) , Laurent L.Njilla (ed.) , AlexanderKott (ed.) , and SachinShetty (ed.) , editors. Modeling and Design of Secure Internet of Things , pp. 27 - 58 . Wiley Online Library , 2020 . |
| [66] | MinghuiZhu and SoniaMartinez . Stackelberg‐game analysis of correlated attacks in cyber‐physical systems. In Proceedings of the 2011 American Control Conference , pp. 4063-4068. IEEE , 2011 . |
| [67] | QuanyanZhu and TamerBaşar . Dynamic policy‐based IDS configuration. In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference , pp. 8600 - 8605 . IEEE , 2009 . |
| [68] | QuanyanZhu , HushengLi , ZhuHan , and TamerBaşar . A stochastic game model for jamming in multi‐channel cognitive radio systems. In 2010 IEEE International Conference on Communications , pp. 1 - 6 . IEEE , 2010a . |
| [69] | QuanyanZhu , HamidouTembine , and TamerBaşar . Network security configurations: A nonzero‐sum stochastic game approach. In Proceedings of the 2010 American Control Conference , pp. 1059 - 1064 . IEEE , 2010b . |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
