[Intelligence Seminar] February 24: Kevin Leyton-Brown, Wean 5409, 3:30 - "Scaling Up Game Theory: Representation and Reasoning with Action Graph Games"

[Noah A Smith]

Intelligence Seminar

February 24, 2009
3:30 pm
Wean 5409
For meetings, contact Michelle Martin (michelle324w at cs.cmu.edu).

Scaling Up Game Theory: Representation and Reasoning with Action Graph Games
Kevin Leyton-Brown
Computer Science Department, University of British Columbia

Abstract:

Game theory is the mathematical study of interaction among
independent, self-interested agents. It has wide applications,
including the design of government auctions (e.g., for distressed
securities), urban planning, and the analysis of internet traffic
patterns. Interestingly, most work in game theory is analytic; it is
less common to analyze a model's properties computationally. Key
reasons for this are that game representation size tends to grow
exponentially in the number of players--making all but the simplest
games infeasible to write down--and that even when games can be
represented, existing algorithms (e.g., for finding equilibria) tend
to have worst-case performance exponential in the game's size.

This talk describes Action-Graph Games (AGG), which make it possible
to extend computational analysis to games that were previously far too
large to consider. I will give an overview of our five-year effort
developing AGGs, emphasizing the twin threads of representational
compactness and computational tractability.

More specifically, the first part of the talk will describe the core
ideas of the AGG representation. AGGs are a fully-expressive,
graph-based representation that can compactly express both strict and
context-specific independencies in players' utility functions. I will
illustrate the representation by describing several practical examples
of games that may be compactly represented as AGGs. The second part of
the talk will examine algorithmic considerations. First, I'll describe
a dynamic programming algorithm for computing a player's expected
utility under a given mixed-strategy profile, which is tractable for
bounded-in-degree AGGs. This algorithm can be leveraged to provide an
exponential speedup in the computation of best response, Nash
equilibrium, and correlated equilibrium.  Second, I'll describe a
message-passing algorithm for computing pure-strategy Nash equilibria
in symmetric AGGs, which is tractable for graphs with bounded
treewidth; again, this implies an exponential speedup over the
previous state of the art. Finally, I'll more briefly describe some
current directions in our work on AGGs: the modeling, evaluation, and
comparison of different advertising auction designs; the extension of
AGGs to both temporal and stochastic settings; and the design of free
software tools to make it easier for other researchers to use AGGs.

This talk is based on joint work with Albert Xin Jiang, David
R.M. Thompson, and Navin A.R. Bhat.

Bio:

Kevin Leyton-Brown is an assistant professor in computer science at
the University of British Columbia.  He received a B.Sc. from McMaster
University (1998), and an M.Sc. and PhD from Stanford University
(2001; 2003). Much of his work is at the intersection of computer
science and microeconomics, addressing computational problems in
economic contexts and incentive issues in multi-agent systems. He also
studies the application of machine learning to the design and analysis
of algorithms for solving hard computational problems. He has
co-written two Multiagent Essentials of Game and over forty
peer-refereed technical articles. He is an associate editor of the
Journal of Artificial Intelligence Research (JAIR) and a member of the
editorial board of the Artificial Intelligence Journal (AIJ). He has
served as a consultant for Trading Dynamics Inc., Ariba Inc., and
Cariocas Inc., and is currently scientific advisor to Worio Inc.