CMU talk: Scaling Up Game Theory: Representation and Reasoning with Action Graph Games

Intelligence Seminar

February 24, 2009

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.