Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations

Post date: Oct 01, 2011 10:13:50 AM

Loosely defined, “multiagent systems are those systems that include multiple autonomous entities with either diverging information or diverging interests, or both.” Obviously, this definition is broad enough to cover a wide variety of real-world systems, from different kinds of complex networks to interactions among human individuals and organizations. In fact, many of the ideas discussed in this book apply to situations that have nothing to do with multiagent systems, commonly viewed as the modern approach to artificial intelligence (AI).

This thorough textbook on multiagent systems mainly focuses on game theory. Written from a computer scientist’s perspective, this book surveys many of the game-theoretic ideas that have been developed since the Second World War, when von Neumann and Morgenstern’s landmark book [1] created the interdisciplinary field of game theory. Game theory, as a branch of applied mathematics, is typically associated with economics and other social sciences. However, as the study of the interaction among independent agents, its strong connections to multiagent systems is self-evident, so a textbook on game theory from a computer scientist’s perspective is more than welcome.

Most of the book is devoted to game-theoretic concepts. Many chapters study competition among agents or noncooperative game theory, while coalitional game theory is addressed in a separate chapter. In these chapters, readers will find the most important topics in game theory, as well as the essential mathematics behind them and some detailed proofs. Apart from the mathematical proof that every game with a finite number of players and action profiles has at least one Nash equilibrium--a result that gave Nash a Nobel Prize in economics and was, let’s say, freely interpreted in the Hollywood blockbuster A Beautiful Mind--you will also find discussions on the computational complexity of computing solution concepts of normal-form and extensive-form games. A variety of other game representations are also reviewed.

Another group of chapters is devoted to “protocols for groups,” a term used by the authors to refer to social choice. From the designer’s perspective, these chapters analyze what rules should be put in place by the designer orchestrating a set of agents. These rules include voting schemes and ranking systems. Mechanism design, as “an exercise in incentive engineering,” is the strategic version of social choice theory. Its better-known application, auctions, also deserves its own chapter, since it is directly related to multiagent resource allocation.

A few chapters address other important topics in multiagent systems, from coordination and communication to learning. The coordination chapters deal with distributed problem solving, focusing on constraint satisfaction (for example, using asynchronous backtracking) and optimization (for example, distributed dynamic programming and learning real-time A*). The short communication chapter discusses when talk precedes action (cheap talk and speech-act theory) and when actions speak louder than words (that is, talking by doing--signaling games as games of asymmetric information). Finally, the chapter on multiagent learning also approaches the topic from a game-theoretic perspective, and is based on an AI paper written by Shoham and other collaborators [2].

The book ends with a couple of chapters on logical theories, which will interest those who work on multiagent systems, and a few short technical appendices. The chapters on logic explore modal logics and beyond. Modal logics qualify the truth of a judgment by means of unary modal operators. The authors also study how knowledge and belief statements change over time (belief dynamics) and how to formalize the notion of goals and intentions. The brief technical appendices provide quick refreshers on probability, linear/integer programming, Markov decision problems, and classical logic--subjects that are needed to understand the rest of the book.

The authors’ style is quite formal, since the textbook is mainly addressed to graduate students and researchers. Although Shoham and Leyton-Brown often refer to their chapters as crash courses, casual readers should not start their inroads into game theory by reading this book. Later, they can refer to this rigorous textbook, if they want to plow through the mathematical details.

[ACM Computing Reviews, September 2009]

También disponible en