Multiagent Systems [2nd ed.]

The new edition of an introduction to multiagent systems that captures the state of the art in both theory and practice, suitable as textbook or reference.Multiagent systems are made up of multiple interacting intelligent agents—computational entities to some degree autonomous and able to cooperate, compete, communicate, act flexibly, and exercise control over their behavior within the frame of their objectives. They are the enabling technology for a wide range of advanced applications relying on distributed and parallel processing of data, information, and knowledge relevant in domains ranging from industrial manufacturing to e-commerce to health care. This book offers a state-of-the-art introduction to multiagent systems, covering the field in both breadth and depth, and treating both theory and practice. It is suitable for classroom use or independent study.This second edition has been completely revised, capturing the tremendous developments in multiagent systems since the first edition appeared in 1999. Sixteen of the book's seventeen chapters were written for this edition; all chapters are by leaders in the field, with each author contributing to the broad base of knowledge and experience on which the book rests.The book covers basic concepts of computational agency from the perspective of both individual agents and agent organizations; communication among agents; coordination among agents; distributed cognition; development and engineering of multiagent systems; and background knowledge in logics and game theory. Each chapter includes references, many illustrations and examples, and exercises of varying degrees of difficulty. The chapters and the overall book are designed to be self-contained and understandable without additional material. Supplemental resources are available on the book's Web site.ContributorsRafael Bordini, Felix Brandt, Amit Chopra, Vincent Conitzer, Virginia Dignum, Jürgen Dix, Ed Durfee, Edith Elkind, Ulle Endriss, Alessandro Farinelli, Shaheen Fatima, Michael Fisher, Nicholas R. Jennings, Kevin Leyton-Brown, Evangelos Markakis, Lin Padgham, Julian Padget, Iyad Rahwan, Talal Rahwan, Alex Rogers, Jordi Sabater-Mir, Yoav Shoham, Munindar P. Singh, Kagan Tumer, Karl Tuyls, Wiebe van der Hoek, Laurent Vercouter, Meritxell Vinyals, Michael Winikoff, Michael Wooldridge, Shlomo Zilberstein Brief Contents......Page 3 Contents......Page 6 Figures......Page 22 Tables......Page 27 Preface......Page 28 --- Agent Architectures & Organizations......Page 36 1 Intelligent Agents......Page 37 What are Agents......Page 38 Architectures for Intelligent Agents......Page 47 Exercises......Page 76 Refs......Page 79 2 Multiagent Organizations......Page 85 Background......Page 87 Multiagent Organizations......Page 96 Institutions......Page 106 Agents in Organizations......Page 116 Evolution of Organizations......Page 119 Conclusions......Page 122 Exercises......Page 123 Refs......Page 126 --- Communication......Page 133 3 Agent Communication......Page 134 Conceptual Foundations of Communication in MAS......Page 139 Traditional Software Engineering Approaches......Page 141 Traditional AI Approaches......Page 147 Commitment-Based Multiagent Approaches......Page 151 Engineering with Agent Communication......Page 155 Advanced Topics & Challenges......Page 161 Conclusions......Page 163 Exercises......Page 166 Refs......Page 169 4 Negotiation & Bargaining......Page 175 Aspects of Negotiation......Page 176 Game-Theoretic Approaches for Single-Issue Negotiation......Page 178 Game-Theoretic Approaches for Multi-Issue Negotiation......Page 188 Heuristic Approaches for Multi-Issue Negotiation......Page 193 Negotiating with Humans......Page 197 Argumentation-based Negotiation......Page 199 Conclusions......Page 201 Exercises......Page 202 Refs......Page 203 5 Argumentation among Agents......Page 209 What is Argument......Page 210 Evaluating an Argument......Page 213 Argumentation Protocols......Page 217 Strategic Argumentation & Game Theory......Page 222 Argument Interchange Format......Page 233 Conclusion......Page 236 Exercises......Page 237 Refs......Page 238 --- Basic Coordination......Page 243 6 Computational Social Choice......Page 244 Preference Aggregation......Page 250 Voting......Page 257 Combinatorial Domains......Page 272 Fair Division......Page 278 Conclusion......Page 288 Exercises......Page 291 Refs......Page 297 7 Mechanism Design & Auctions......Page 315 Mechanism Design with Unrestricted Preferences......Page 316 Quasilinear Preferences......Page 321 Efficient Mechanisms......Page 326 Single-Good Auctions......Page 334 Position Auctions......Page 342 Combinatorial Auctions......Page 345 Conclusions......Page 348 Exercises......Page 350 Refs......Page 355 8 Computational Coalition Formation......Page 358 Definitions......Page 360 Solution Concepts......Page 364 Representation Formalisms......Page 372 Coalition Structure Generation......Page 381 Exercises......Page 401 Refs......Page 403 9 Trust & Reputation in Multiagent Systems......Page 410 Computational Representation of Trust & Reputation Values......Page 411 Trust Processes in Multiagent Systems......Page 417 Reputation in Multiagent Societies......Page 425 Trust, Reputation & other Agreement Technologies......Page 436 Conclusions......Page 442 Exercises......Page 443 Refs......Page 444 --- Distributed Cognitive Abilities......Page 449 10 Multiagent Learning......Page 450 Challenges in Multiagent Learning......Page 452 Reinforcement Learning for Multiagent Systems......Page 459 Evolutionary Game Theory as Multiagent Learning Paradigm......Page 470 Swarm Intelligence as Multiagent Learning Paradigm......Page 478 Neuro-Evolution as Multiagent Learning Paradigm......Page 484 Case Study - Air Traffic Control......Page 487 Exercises......Page 495 Refs......Page 502 11 Multiagent Planning, Control & Execution......Page 511 Characterizing Multiagent Planning & Control......Page 513 Coordination Prior to Local Planning......Page 514 Local Planning Prior to Coordination......Page 523 Decision-Theoretic Multiagent Planning......Page 538 Multiagent Execution......Page 553 Conclusions......Page 558 Exercises......Page 559 Refs......Page 565 12 Distributed Constraint Handling & Optimization......Page 572 Distributed Constraint Handling......Page 574 Applications & Benchmarking Problems......Page 576 Solution Techniques - Complete Algorithms......Page 579 Solution Techniques - Approximate Algorithms......Page 590 Solution Techniques with Quality Guarantees......Page 595 Conclusions......Page 602 Exercises......Page 603 Refs......Page 605 --- Development & Engineering......Page 609 13 Programming Multiagent Systems......Page 610 From AGENT0 to Modern Agent Languages......Page 613 Abstractions in the MAOP Paradigm......Page 616 Examples of Agent Programming Languages......Page 619 Organization & Environment Programming......Page 632 Example of Full MAOP in JaCaMo......Page 643 Conclusions......Page 652 Exercises......Page 653 Refs......Page 656 14 Specification & Verification of Multiagent Systems......Page 663 Agent Specification......Page 666 From Specifications to Implementations......Page 678 Formal Verification......Page 681 Deductive Verification of Agents......Page 685 Algorithmic Verification of Agent Models......Page 689 Algorithmic Verification of Agent Programs......Page 698 Conclusions......Page 702 Exercises......Page 703 Refs......Page 705 15 Agent-oriented Software Engineering......Page 716 Agent Concepts......Page 721 Running Example......Page 723 Requirements......Page 725 Design......Page 731 Detailed Design......Page 738 Implementation......Page 748 Assurance......Page 749 Software Maintenance......Page 755 Comparing Methodologies......Page 756 Conclusions......Page 757 Exercises......Page 761 Agent UML Sequence Diagram Notation......Page 763 Refs......Page 765 --- Technical Background......Page 779 16 Logics for Multiagent Systems......Page 780 Representing Cognitive States......Page 788 Representing the Strategic Structure of System......Page 804 Conclusion & further Reading......Page 816 Exercises......Page 818 Refs......Page 819 17 Game-Theoretic Foundations of Multiagent Systems......Page 830 Normal-Form Games......Page 831 Extensive-Form Games......Page 847 Bayesian Games......Page 855 Exercises......Page 861 Refs......Page 866 Index......Page 868 "This is the first comprehensive introduction to multiagent systems and contemporary distributed artificial intelligence. The book provides detailed coverage of basic topics as well as several closely related ones and is suitable as a textbook." "The book can be used for teaching as well as self-study, and it is designed to meet the needs of both researchers and practitioners. In view of the interdisciplinary nature of the field, it will be a useful reference not only for computer scientists and engineers, but for social scientists and management and organization scientists as well."--BOOK JACKET