Playing Games with Games

Michael Wooldridge (University of Liverpool)

Info

Date	22nd November 2011 (week 7, Michaelmas Term 2011)
Time	16:30
Place	Lecture Theatre B

Abstract

The past decade has been witness to a huge explosion of interest in the
computational aspects of game theory. One topic that has received much
attention is that of mechanism design. Crudely, mechanism design can be
understood as the problem of designing games so that, if every player in the
game acts rationally, certain desirable outcomes will result. In mechanism
design, it is usually assumed that the designer of the mechanism has
complete freedom to design a mechanism as desired. But this is not the
reality of most real-world mechanism design problems: when a Government
develops a new law, for example, they do not usually have a blank slate, but
must start from the framework of society as it exists. In this talk, I will
present work we have done on the computational aspects of such "mechanism
design for legacy systems". In the settings we will consider here, a
principal external to a system must try to engineer a mechanism to influence
the system so that certain desirable outcomes will result from the rational
action of agents within the system. We focus specifically on the possibility
of imposing taxation schemes upon a system, so that the preferences of
participants are perturbed in such a way that they collectively and
rationally choose socially desirable outcomes. The specific framework within
which we express these ideas is a framework known as Boolean games. We
discuss the computational complexity of the "implementation" problem for
Boolean games, and derive a formal characterisation of feasible
implementation problems for such games. If time permits, we will discuss
extensions to the framework that take it much closer to contemporary CAV
models, and will briefly survey some of the problems that arise in these
richer settings, which will be studied in a 5-year ERC Advanced Grant,
awarded in October 2011.

Speaker bio

Michael Wooldridge is a Professor in the Department of Computer Science at the University of Liverpool, UK. He has been active in multi-agent systems research since 1989, and has published over two hundred articles in the area. His main interests are in the use of formal methods for reasoning about autonomous agents and multi-agent systems. Wooldridge was the recipient of the ACM Autonomous Agents Research Award in 2006. He is an associate editor of the journals ``Artificial Intelligence'' and ``Journal of AI Research (JAIR)''. His introductory textbook ``An Introduction to Multiagent Systems'' was published by Wiley in 2002 (Chinese translation 2003; Greek translation 2008; second edition 2009). In October 2011, he was awarded a prestigious 5-year ERC Advanced Grant entitled "RACE -- Reasoning about Computational Economies".