IJCAI-2020 Tutorial
Computational Game Theory and Its Applications
Presenters:
Hau Chan
University of Nebraska-Lincoln
Arunesh Sinha
Singapore Management University
Mohammad Irfan
Bowdoin College
Tutorial Description:
We Don’t Live In A Vacuum! We interact with other agents in our environment to make rational decisions. For example, selecting the quickest or easiest route to go from your apartment to campus, selecting the best amount to bid in an eBay auction, determining whether to fold in a 2-player poker game or selecting a winning move in a Rock-paper-scissors game. In all of these examples, we must interact with other agents when making decisions. In particular, our best strategy depends on the behavior of other agents in the environment (e.g., the chosen route depends on the number of others are using those routes, play rock if my opponent plays scissors). How do we make rational decisions when facing other strategic agents in a given environment? What is the best strategy? Game theory helps us to answer these questions.
Game theory is a mathematical tool that allows us to reason about the strategic interaction of self-interest and rational agents in a given environment. The construct provides a framework that characterizes the rational outcomes in such an environment of strategic agents. While the area of game theory is originated from the economic literature, computer scientists have made significant contributions to this area from the modeling and computational perspectives in the last decades (which led to computational game theory). Moreover, numerous applications of game theory have deployed in the real world (e.g., allocating policing resources to checkpoints in the LAX airport, allocating patrollers to protect wildlife, and predicting the voting behavior of the senators in the U.S. for a bill).
In the proposed tutorial on Computational Game Theory and Its Applications, the audiences will be
(1) introduced to fundamental game-theoretic decision-making tools for modeling and understanding the strategic interaction of self-interested and strategic agents;
(2) exposed to the modeling tools’ solution concepts and how they can be used to predict decision-making behavior of agents;
(3) introduced to computational aspects of computing these solution concepts;
(4) exposed to some of the main applications of game theory to security and social science domains.
In addition, this tutorial will summarize recent and modern advances in developing efficient algorithms for games with complex strategy spaces, including the use of marginal probabilities and general framework for representing and solving games with structured strategy spaces.We will cover application domains ranging from infrastructure security to environmental and wildlife protection.
Presenters' Short Bios:
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 extensively studies games with complex strategy spaces. The relevant 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 in the Department of Computer Science and Engineering at the University of Nebraska-Lincoln. He has taught Networks, Markets, and Crowds, Computational Game Theory and Its Applications, and Data Structures and Algorithms.
Dr. Chan has given a tutorial on topics in computational game theory at AAMAS 2019, IJCAI 2019, and AAMAS 2020.
Arunesh Sinha, School of Information Systems, Singapore Management University, 80 Stamford Rd, Singapore. Email: aruneshs@smu.edu.sg
Dr. Arunesh Sinha is an Assistant Professor in the School of Information Systems at Singapore Management University. He received his Ph.D. from Carnegie Mellon University. He obtained his undergraduate degree in Electrical Engineering from IIT Kharagpur in India.
Dr. Sinha has conducted research at the intersection of security, machine learning and game theory. His interests lie in the theoretical aspects of multi-agent interaction, machine learning, security and privacy, along with an emphasis on the real-world applicability of the theoretical models. He was awarded the Bertucci fellowship at CMU in appreciation of his novel research. His paper was nominated for the best application paper at AAMAS 2016. He has organized workshops at the intersection of AI and computer security such as AISec as CCS and AICS at AAAI.
Dr. Sinha's work has provided novel approaches to solve the optimization problem used in computing Stackelberg equilibrium in security games. This approach has allowed solving large scale security games, where prior methods such as column generation completely fail to scale up. This novel approach is being used in an airport screening application by TSA (called the DARMS project). Dr. Sinha has also provided mathematical foundations for the use of learning in security games, revealing the circumstances in which the composition of learning and optimization leads to sub-optimal outputs.
Mohammad Irfan, Computer Science and Digital & Computational Studies, Bowdoin College, 255 Maine St, Brunswick, ME 04011. Email: mirfan@bowdoin.edu
Mohammad T. Irfan is an Assistant Professor at Bowdoin College in Maine. He holds a joint appointment with Computer Science and Digital & Computational Studies. He got his PhD in Computer Science from Stony Brook University in 2013. His research involves interdisciplinary problems at the intersection of AI and social sciences that arise in complex, strategic, and network-structured domains. He also dabbled a little bit in the image analysis of Jackson Pollock's paintings. His research is supported by NSF. Mohammad comes from Bangladesh and loves nature, soccer, and tennis.