home · mobile · calendar · colloquia · 2009-2010 · 

Colloquium - Chapman

Valued Nash Propagation: A Distributed Algorithm for Optimising over Pure Strategy Nash Equilibria
Archie Chapman
University of Southampton

Game theory is increasingly being used as a modelling and design framework in artificial intelligence, particularly in the field of multi-agent systems. Now, such systems are starting to contain large numbers of agents, producing three computational problems. The first is to find compact representations of games, and in this work, we consider two compact graphical representations known as "graphical normal form" and "hypergraphical normal form". Both representations use a graph or hypergraph to summarise utility dependencies, and can be exponentially more compact than the standard normal form if the agents' interaction structure is sufficiently sparse. The second problem is to derive efficient methods for solving such games, typically in the form of a Nash equilibrium. Furthermore, in many multi-agent settings, a system designer particularly wants solutions that are pure strategy Nash equilibria (PSNE), because they imply a stable action profile and do not rely on utilities representing a cardinal ordering over outcomes, unlike mixed strategy equilibria. Consequently, we concentrate on computing such PSNE. The third challenge, in the presence of multiple equilibria, is to choose between them according to some criterion. This is particularly important in control settings in which the designer not only wants to find a stable configuration of variables, but also faces an optimisation problem. In such settings, equilibrium is a necessary, but insufficient, condition for a solution.

In response to these challenges, we develop an efficient algorithm for computing pure strategy Nash equilibria that satisfy various criteria (such as the utilitarian or Nash-Bernoulli social welfare functions) in games with sparse interaction structure. Our algorithm, called Valued Nash Propagation (VNP), integrates the optimisation problem of maximising a criterion with the constraint satisfaction problem of finding a game's equilibria to construct a criterion that defines a c-semiring. Given a suitably compact game structure, this criterion can be efficiently optimised using message-passing. To this end, we first show that VNP is complete in games whose interaction structure forms a hypertree. Then, we go on to provide theoretic and empirical results justifying its use on games with arbitrary structure.

Archie Chapman is a Research Fellow in the IAM group at the University of Southampton, where he completed a PhD in Computer Science in the summer of 2009. Archie's research interests lie in all aspects of decentralised and automatic control and regulation of complex systems, whether they be for industrial uses, computational problems, or problems of economic and social organisation. His current focus is on game-theoretic models for distributed decision making in multi-agent systems, reinforcement learning, and distributed optimisation, and has published papers on learning in games, task allocation and scheduling, constraint optimisation problems and policies for multi-armed bandit problems.

Sponsored by the Department of Electrical, Computer and Energy Engineering.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)