Author name cluster

Albert Jiang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

AAAI Conference 2017 Conference Paper

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

Albert Jiang
Hau Chan
Kevin Leyton-Brown

In many real-world systems, strategic agents’ decisions can be understood as complex—i. e. , consisting of multiple subdecisions—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 ﬁrst 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 efﬁciently. 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 efﬁcient computation.

PDF Details

NeurIPS Conference 2014 Conference Paper

Diverse Randomized Agents Vote to Win

Albert Jiang
Leandro Soriano Marcolino
Ariel Procaccia
Tuomas Sandholm
Nisarg Shah
Milind Tambe

We investigate the power of voting among diverse, randomized software agents. With teams of computer Go agents in mind, we develop a novel theoretical model of two-stage noisy voting that builds on recent work in machine learning. This model allows us to reason about a collection of agents with different biases (determined by the first-stage noise models), which, furthermore, apply randomized algorithms to evaluate alternatives and produce votes (captured by the second-stage noise models). We analytically demonstrate that a uniform team, consisting of multiple instances of any single agent, must make a significant number of mistakes, whereas a diverse team converges to perfection as the number of agents grows. Our experiments, which pit teams of computer Go agents against strong agents, provide evidence for the effectiveness of voting when agents are diverse.

PDF Details

AAAI Conference 2014 Conference Paper

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

Haifeng Xu
Fei Fang
Albert Jiang
Vincent Conitzer
Shaddin Dughmi
Milind Tambe

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 of the 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 difficult to find, we propose approximations or prove hardness results.

PDF Details

NeurIPS Conference 2010 Conference Paper

Bayesian Action-Graph Games

Albert Jiang
Kevin Leyton-Brown

Games of incomplete information, or Bayesian games, are an important game-theoretic model and have many applications in economics. We propose Bayesian action-graph games (BAGGs), a novel graphical representation for Bayesian games. BAGGs can represent arbitrary Bayesian games, and furthermore can compactly express Bayesian games exhibiting commonly encountered types of structure including symmetry, action- and type-specific utility independence, and probabilistic independence of type distributions. We provide an algorithm for computing expected utility in BAGGs, and discuss conditions under which the algorithm runs in polynomial time. Bayes-Nash equilibria of BAGGs can be computed by adapting existing algorithms for complete-information normal form games and leveraging our expected utility algorithm. We show both theoretically and empirically that our approaches improve significantly on the state of the art.

PDF Details