Non-MILP Approaches to Stackelberg Security Games
In this talk I will introduce our two recently-proposed metaheuristic non-MILP methods for approximation of Strong Stackelberg Equilibrium in general-sum sequential Security Games (SGs) with imperfect information, played on graphs. Both methods search the Leader’s strategy space in the quest for finding their optimal mixed strategy. The first one (Mixed-UCT) utilizes Upper Confidence Bound applied to Trees algorithm – a variant of Monte Carlo Tree Search sampling and the other one (EASG) employs Evolutionary Algorithms with adequately designed chromosomes encoding potential strategies.
Experimental evaluation indicates that both approaches scale in time and memory better than state-of-the-art MILP methods while providing optimal or close-to-optimal solutions in the vast majority of the cases. Time and memory savings result from searching, in each time moment, only a relevant part of a game tree with no need to store and access the whole tree at once.
Except for competitive time and memory scalability, an additional asset of proposed metaheuristic methods is flexibility of potential game formulations they are able to tackle. Both approaches are generic and largely game-independent, which allows for their application to a wide range of SGs with just little adjustments. Furthermore, Mixed-UCT and EASG are anytime methods – they can be terminated in any moment and still yield a reasonably good solution – the best one found so-far. Hence they are particularly well suited for time-critical SG applications.
Prof. Jacek Mańdziuk, Ph.D., D.Sc., received M.Sc. (Honors) and Ph.D. in Applied Mathematics from the Warsaw University of Technology (WUT), Poland in 1989 and 1993, resp. and D.Sc. degree in Computer Science from the Polish Academy of Sciences in 2000. In 2011 he was awarded the title of Professor Titular.
He is Full Professor at the Faculty of Mathematics and Information Science, WUT, Head of Division of Artificial Intelligence and Computational Methods, and Head of Doctoral Programme in Computer Science, at this faculty.
He is the author of 3 books (including Knowledge-free and Learning-based Methods in Intelligent Game Playing, Springer, 2010) and 140+ research papers. He served as Program Committee Member for 100+ international conferences. Recently he has been the organizer and Chair of the IEEE SSCI Symposium on Computational Intelligence for Human-like Intelligence (Singapore 2013, Orlando 2014, Cape Town 2015, Athens 2016, Honolulu 2017, Bengaluru 2018, Xiamen 2019, Canberra 2020). He is a General Co-Chair of the 2021 IEEE Congress on Evolutionary Computation (Krakow, Poland).
He was a recipient of the Fulbright Senior Advanced Research Award (UC Berkeley and ICSI Berkeley, USA) and the Robert Schuman Foundation Fellowship (CNRS, Besacon, France). Recently he has been a visiting professor in the School of Computer Engineering, Nanyang Technological University in Singapore (2015-2017). He was also a visiting professor at the University of New South Wales (Australia, 2013), Yonsei University (South Korea, 2011) and the University of Alberta (Canada, 2011).
His research interests include application of Computational Intelligence and Artificial Intelligence methods to games, dynamic optimization problems, human-machine cooperation and financial modeling. He is also interested in development of general-purpose human-like learning and problem-solving methods which involve intuition, creativity and multitasking. For more information please visit http://www.mini.pw.edu.pl/~mandziuk