Goto

Collaborating Authors

Jiang, Albert Xin


Resource Graph Games: A Compact Representation for Games with Structured Strategy Spaces

AAAI Conferences

In many real-world systems, strategic agents' decisions can be understood as complex - i.e., consisting of multiple sub-decisions - and hence can give rise to an exponential number of pure strategies. Examples include network congestion games, simultaneous auctions, and security games. However, agents' sets of strategies are often structured, allowing them to be represented compactly. There currently exists no general modeling language that captures a wide range of commonly seen strategy structure and utility structure. We propose Resource Graph Games (RGGs), the first general compact representation for games with structured strategy spaces, which is able to represent a wide range of games studied in literature. We leverage recent results about multilinearity, a key property of games that allows us to represent the mixed strategies compactly, and, as a result, to compute various equilibrium concepts efficiently. While not all RGGs are multilinear, we provide a general method of converting RGGs to those that are multilinear, and identify subclasses of RGGs whose converted version allow efficient computation.


Jiang

AAAI Conferences

In many real-world systems, strategic agents' decisions can be understood as complex - i.e., consisting of multiple sub-decisions - and hence can give rise to an exponential number of pure strategies. Examples include network congestion games, simultaneous auctions, and security games. However, agents' sets of strategies are often structured, allowing them to be represented compactly. There currently exists no general modeling language that captures a wide range of commonly seen strategy structure and utility structure. We propose Resource Graph Games (RGGs), the first general compact representation for games with structured strategy spaces, which is able to represent a wide range of games studied in literature. We leverage recent results about multilinearity, a key property of games that allows us to represent the mixed strategies compactly, and, as a result, to compute various equilibrium concepts efficiently. While not all RGGs are multilinear, we provide a general method of converting RGGs to those that are multilinear, and identify subclasses of RGGs whose converted version allow efficient computation.


Combining Compact Representation and Incremental Generation in Large Games with Sequential Strategies

AAAI Conferences

Many search and security games played on a graph can be modeled as normal-form zero-sum games with strategies consisting of sequences of actions. The size of the strategy space provides a computational challenge when solving these games. This complexity is tackled either by using the compact representation of sequential strategies and linear programming, or by incremental strategy generation of iterative double-oracle methods. In this paper, we present novel hybrid of these two approaches: compact-strategy double-oracle (CS-DO) algorithm that combines the advantages of the compact representation with incremental strategy generation. We experimentally compare CS-DO with the standard approaches and analyze the impact of the size of the support on the performance of the algorithms. Results show that CS-DO dramatically improves the convergence rate in games with non-trivial support


Reports of the 2014 AAAI Spring Symposium Series

AI Magazine

The Association for the Advancement of Artificial Intelligence was pleased to present the AAAI 2014 Spring Symposium Series, held Monday through Wednesday, March 24–26, 2014. The titles of the eight symposia were Applied Computational Game Theory, Big Data Becomes Personal: Knowledge into Meaning, Formal Verification and Modeling in Human-Machine Systems, Implementing Selves with Safe Motivational Systems and Self-Improvement, The Intersection of Robust Intelligence and Trust in Autonomous Systems, Knowledge Representation and Reasoning in Robotics, Qualitative Representations for Robots, and Social Hacking and Cognitive Security on the Internet and New Media). This report contains summaries of the symposia, written, in most cases, by the cochairs of the symposium.


Reports of the 2014 AAAI Spring Symposium Series

AI Magazine

The Association for the Advancement of Artificial Intelligence was pleased to present the AAAI 2014 Spring Symposium Series, held Monday through Wednesday, March 24–26, 2014. The titles of the eight symposia were Applied Computational Game Theory, Big Data Becomes Personal: Knowledge into Meaning, Formal Verification and Modeling in Human-Machine Systems, Implementing Selves with Safe Motivational Systems and Self-Improvement, The Intersection of Robust Intelligence and Trust in Autonomous Systems, Knowledge Representation and Reasoning in Robotics, Qualitative Representations for Robots, and Social Hacking and Cognitive Security on the Internet and New Media). This report contains summaries of the symposia, written, in most cases, by the cochairs of the symposium.


Give a Hard Problem to a Diverse Team: Exploring Large Action Spaces

AAAI Conferences

Recent work has shown that diverse teams can outperform a uniform team made of copies of the best agent. However, there are fundamental questions that were not asked before. When should we use diverse or uniform teams? How does the performance change as the action space or the teams get larger? Hence, we present a new model of diversity for teams, that is more general than previous models. We prove that the performance of a diverse team improves as the size of the action space gets larger. Concerning the size of the diverse team, we show that the performance converges exponentially fast to the optimal one as we increase the number of agents. We present synthetic experiments that allow us to gain further insights: even though a diverse team outperforms a uniform team when the size of the action space increases, the uniform team will eventually again play better than the diverse team for a large enough action space. We verify our predictions in a system of Go playing agents, where we show a diverse team that improves in performance as the board size increases, and eventually overcomes a uniform team.


Solving Zero-Sum Security Games in Discretized Spatio-Temporal Domains

AAAI Conferences

Among the many deployment areas of Stackelberg Security games, a major area involves games played out in space and time, which includes applications in multiple mobile defender resources protecting multiple mobile targets. Previous algorithms for such spatio-temporal security games fail to scale-up and little is known ofthe computational complexity properties of these problems.This paper provides a novel oracle-based algorithmic framework for a systematic study of different problem variants of computing optimal (minimax) strategies in spatio-temporal security games. Our framework enables efficient computation of a minimax strategy when the problem admits a polynomial-time oracle. Furthermore,for the cases in which efficient oracles are difficultto find, we propose approximations or prove hardness results.


Modeling Crime Diffusion and Crime Suppression on Transportation Networks: An Initial Report

AAAI Conferences

In urban transportation networks, crime diffuses as criminals travel through the networks and look for illicit opportunities. It is important to first model this diffusionin order to recommend actions or patrol policies to control the diffusion of such crime. Previously, game theory has been used for such patrol policy recommendations, but these applications of game theory for security have not modeled the diffusion of crime that comes about due to criminals seeking opportunities; instead the focus has been on highly strategic adversaries that plan attacks in advance. To overcome this limitation of previous work, this paper provides the following key contributions. First, we provide a model of crime diffusion based on a quantal biased random movement(QBRM) of criminals opportunistically and repeatedly seeking targets. Within this model, criminals react to real-time information, rather than strategically planning their attack in advance. Second, we provide a game theoretic approach to generate randomized patrol policies for controlling such diffusion.


Efficiently Solving Joint Activity Based Security Games

AAAI Conferences

Despite recent successful real-world deployments of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, this paper presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. We provide extensive experimental results and formal analyses.


Multi-Agent Team Formation: Diversity Beats Strength?

AAAI Conferences

Team formation is a critical step in deploying a multi-agent team. In some scenarios, agents coordinate by voting continuously. When forming such teams, should we focus on the diversity of the team or on the strength of each member? Can a team of diverse (and weak) agents outperform a uniform team of strong agents? We propose a new model to address these questions. Our key contributions include: (i) we show that a diverse team can overcome a uniform team and we give the necessary conditions for it to happen; (ii) we present optimal voting rules for a diverse team; (iii) we perform synthetic experiments that demonstrate that both diversity and strength contribute to the performance of a team; (iv) we show experiments that demonstrate the usefulness of our model in one of the most difficult challenges for Artificial Intelligence: Computer Go.