Yoav Shoham and Kevin Leyton-Brown
CAMBRIDGE UNIVERSITY PRESS 2009, 483 PAGES PRICE (HARDBACK) £37.00 ISBN 978-0-521-89943-7
One of the characteristics of society is interaction, with many different people coming together either to achieve a common goal, for example electing a government, or to compete with each other, for example in a business context.
It is not surprising therefore that systems of multiple interacting agents have been studied for many years – the earliest reference in this book’s extensive bibliography dates from the eighteenth century. Despite this long history, the field is of great relevance today. Developments in computing have not only allowed new topics to be investigated, but the field has also helped provide answers to some of the challenges associated with exploiting these developments.
The book begins by examining constraint satisfaction problems, including the famous problem, where ‘n queens’ have to be placed on an n by n chessboard in such a way that no queen can take another. It then moves on to discuss optimisation. Given the book’s subject matter, it is not surprising that both of these topics are considered in a ‘distributed’ fashion, with multiple agents being used to solve each problem.
The next chapters provide a comprehensive introduction to game theory. As would be expected, these include discussion of the Prisoner’s Dilemma, Nash equilibria and dominant strategies, as well as the normal and extensive forms. The computer science perspective that is used throughout the text is evident in the use of a computer network, rather than a road network, to illustrate Braess’ Paradox.
Discussions then move on to consider learning and teaching, where either single agents or entire populations have to learn about game structures and payoffs. The way that their actions can provide information to other agents in the system constitutes the teaching part of the equation. This naturally develops into a discussion of communication. Social choice mechanisms, which can be used when agents have different views on a topic, are then covered. As with the earlier chapters all the expected content is present, including Condorcet conditions (which point back to the reference from the eighteenth century) and Arrow’s theorem. The discussion of social choice neatly segues into auctions and coalition game theory. A discussion of logic systems follows before the book concludes with a discussion of probabilistic beliefs.
The text is intended to be a reference guide, suitable for advanced undergraduate or postgraduate study. Somewhat surprisingly little prior knowledge is assumed. Whilst a general understanding of probability, optimisation and logic systems would be helpful, a series of brief appendices provide enough detail to either jog the memory or to provide the necessary introduction and to direct to more detailed sources of information, should these be required. A clear and engaging tone is used throughout the book with, for example, agents being asked to ‘put their payoff where their mouth is’ and Oscar Wilde being quoted in a footnote. This tone is reinforced by well chosen examples. For example, the graph colouring problem is translated into a sensor network where neighbouring sensors cannot share the same frequency and the discussion of logic systems finds space to mention Sidney Bechet, who was apparently a great jazz soprano saxophonist. Even the independence day of Micronesia finds its way into the text.
Whilst no exercises are present, the authors are not beyond issuing the occasional challenge. This is normally done by asking ‘Do you see why?’ just after having stated something that should be obvious, but which inevitably takes some thought to establish. There is an awful lot to praise in this book. The chapters on game theory could have merited a tome of their own. The discussions of social choice and auctions are similarly detailed, and there are a host of references.
There is, however, a very slight feeling that the various sections of the book are not drawn together as thoroughly as might be the case. Whilst the foundations are laid in an excellent manner, some indication of the type of structure that could be built upon them might also have been helpful. That said, as the authors intended, the book will prove a highly valuable reference for practitioners or researchers in this area.
Rob Ashmore CMath FIMA, CSci
Defence Science and Technology Laboratory
Mathematics Today December 2011
The views and opinions expressed herein are those of the author and do not necessarily reflect those of the Defence Science and Technology Laboratory.
Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations can be purchased at Amazon.co.uk
The effects of economic depression are mirrored within this predicament,
which proceeds to become worse.