Distributed AI (DAI) studies issues of coordination between intelligent agents. Classical game theory has a long tradition of examining similar problems. This book draws on a detailed knowledge of the game theory literature to define protocols that automated agents can use to reach agreements that are good by some appropriate measures. The presentation is clear and readable. Though the argument is developed through formal definitions and theorems, there is abundant expository text, and all proofs are relegated to Appendix C.
Chapter 1, “Machines that Make Deals,” introduces automated agents that negotiate to reach agreements, and describes the role of game theory in developing appropriate protocols. The chapter introduces DAI but defers a lengthy discussion of previous work to Appendix B, and clearly states the authors’ intent to exploit existing game theory concepts rather than to contribute to game theory research.
Chapter 2, “Interaction Mechanisms,” defines three dimensions along which interagent negotiation can be discussed. The first dimension distinguishes negotiation by its granularity (whether agents negotiate over complete tasks, states of the world, or the worth that each agent sees) and provides the framework for the rest of the book. The second dimension defines five attributes by which proposed negotiation mechanisms can be evaluated: efficiency, stability, simplicity, distribution, and symmetry. The third dimension describes the assumptions or axioms on which the book’s theory is constructed. Compared with real-life negotiation situations, these assumptions are simplistic, and may limit the deployment of the book’s conclusions in real engineered environments. For example, it is assumed that agents will not take future negotiations into account in a current negotiation; that all agents offer the same operations in the world at identical costs; and that there is no money or other mechanism for explicit transfer of utility among agents. This last restriction is particularly troublesome, because a dissipative mechanism such as currency flow is necessary if a collection of agents is to exhibit self-organizing behavior.
Chapter 3, “Task Oriented Domains,” discusses interactions in which agents reason over the coarsest granularity of work, namely, complete tasks that have no side effects. An example of such a domain is delivery of letters, in which a task is the delivery of a single letter to its destination, agents can carry any number of letters, and each agent seeks a division of the total set of letters that minimizes the distance it will have to travel. Discussion of alternative approaches to making such assignments leads to the definition of product maximizing mechanisms, which maximize the product of the utilities realized by individual agents. Chapter 4, “Deception-free Protocols,” analyzes the kinds of lies that agents might tell in negotiations to try to increase their actual utility at the expense of their partners, and shows how protocols can be designed to eliminate the benefits of these lies.
In chapter 5, “State Oriented Domains,” agents’ atomic actions are permitted to have side effects, and thus can unintentionally assist or hinder the objectives of other agents. Agents negotiate over goals expressed in terms of the final state of the world, rather than the accomplishment of specific tasks. This domain supports the definition of both cooperative and compromise situations, as well as semi-cooperative deals, in which agents in a conflict situation maximize their utility by cooperating up to a point and then flipping a coin. The chapter then generalizes semicooperative deals to unified negotiation protocols, which can be used even in non-conflict situations. Chapter 6, “Strategic Manipulation,” extends the mechanisms for state-oriented domains to situations where participating agents do not have full information about one another’s goals or the worths that the other assigns to various outcomes. The approach is developed more fully in Appendix A.
Chapter 7, “Worth Oriented Domains,” further relaxes the domain within which negotiation takes place to permit worth to be associated with partial achievement of an agent’s goals. Now deals are evaluated on the basis of a worth function over all possible final states, rather than over discrete goals.
After three appendices, the book closes with an integrated bibliography (143 items, through 1993) and index.
This work diligently seeks out and exploits existing research in a relevant cognate field. By appropriately segregating proofs, it achieves exemplary clarity without sacrificing formal rigor. It constructs several useful hierarchies of concepts that will serve the field well as a basis for further discussion and analysis. The authors have not escaped from the classical AI problem of oversimplifying the problem to the point that it is no longer relevant to real applications, and by typesetting the work themselves, they have kept the price down but left a number of embarrassing typographical errors.
