AAMAS-2019 Tutorial
Solving Games with Complex Strategy Spaces
Presenters:
Albert Xin Jiang
Trinity University
Fei Fang
Carnegie Mellon University
Hau Chan
University of Nebraska-Lincoln
Tutorial Description:
A central problem of computational game theory is the computation of game-theoretic solution concepts given a description of the game. Classical results focused on solving finite games represented in normal form, where the strategies and utility functions are given explicitly in a tabular representation. However, in many real-world multi-agent domains including infrastructure security, environmental protection, electronic commerce, and network routing, each agent need to make a complex decision consisting of multiple components, such as choosing a path in a network, selecting a subset of targets to protect/attack, executing a patrol route for each patrol unit, bidding in multiple auctions, or taking actions in continuous areas. The resulting strategy space may consist of an exponential number or even infinite number of pure strategies, and as a result the standard normal form representation and its associated algorithms are inadequate.
This tutorial will summarize recent advances in developing efficient algorithms for games with complex strategy spaces, including the use of marginal probabilities, general framework for representing and solving games with structured strategy spaces, and the use of differentiable learning and (multi-agent) deep reinforcement learning. We will cover application domains ranging from infrastructure security to environmental and wildlife protection.
Presenters' Short Bios:
Albert Xin Jiang, Department of Computer Science, Trinity University, One Trinity Place, San Antonio, TX 78212. Phone: 210-999-7487. Email: xjiang@trinity.edu.
Dr. Jiang has published research articles on security games, on compact representations of games and their computation, which received the best student paper award at ACM-EC 2011, and specifically resource graph games.
He has taught as an assistant professor in computer science at Trinity University since 2014. Courses taught includes Principles of Computer Science I, Data Abstraction, Algorithms, Artificial Intelligence, and Computational Game Theory.
He has given tutorials on topics in computational game theory, at ACM-EC (2012,2016), AAAI (2013,2014), CREATE (2012,2013).
Fei Fang, School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA 15213. Phone: 412-268-5529. Email: feifang@cmu.edu.
Dr. Fang has worked on multi-agent systems for more than seven years, focusing on integrating game theory and machine learning with applications to security, sustainability, and mobility domains. Her recent work on differentiable learning in games has won the Distinguished Paper at the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI'18). Her work on Green Security Games and PAWS (Protection Assistant for Wildlife Security) has won the the Outstanding Paper Award in Computational Sustainability Track at the International Joint Conferences on Artificial Intelligence (IJCAI'15) and the Innovative Application Award at Innovative Applications of Artificial Intelligence (IAAI'16).
She has given tutorials on topics in computational game theory, including IJCAI 2018 Tutorial on Game Theory and Machine Learning for Security, AAMAS 2018 Tutorial on AI for Social Good, and ACM-EC 2017 Tutorial on Advances in Game Theory for Security and Privacy.
She has been teaching as an assistant professor at Carnegie Mellon University since 2017. Courses taught includes Artificial Intelligence Methods for Social Good, and Artificial Intelligence: Representation and Problem Solving.
Hau Chan, Department of Computer Science and Engineering, University of Nebraska-Lincoln, 1400 R St, Lincoln, NE 68588. Phone: 402-472-5091. Email: hchan3@unl.edu.
Dr. Chan has worked at the intersection of multi-agent systems and economic. His earlier work focuses on applying graphical games to model and study interdependent security domains (e.g., security investment decisions). His recent and ongoing work with the first presenter (Dr. Jiang) extensively studies games with complex strategy spaces. Their joint-work includes introducing a first compact representation for games with complex strategy spaces, providing theoretical insights to computing solution concepts in such representations, and applying the representations to model problems in popular application domains (e.g., security, network congestion, and auctions).
Dr. Chan is currently an assistant professor. He has taught Networks, Markets, and Crowds and Computational Game Theory and Its Applications.
Tutorial Notes:
Slides will be available here before the tutorial.