Multiagent systems : a modern approach to distributed artificial intelligence

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 Contents in Brief......Page 8 Contents......Page 12 List of Figures......Page 28 List of Tables......Page 34 The Subject of This Book......Page 36 Readership and Prerequisites......Page 38 Structure and Chapters......Page 39 The Exercises......Page 40 How to Use This Book......Page 41 Acknowledgments......Page 42 Contributing Authors......Page 44 Part I. Agent Architectures and Organizations......Page 50 1. Introduction......Page 52 2. What Are Agents?......Page 53 3. Architectures for Intelligent Agents......Page 62 5. Exercises......Page 91 References......Page 94 1. Introduction......Page 100 2. Background......Page 102 3. Multiagent Organizations......Page 111 4. Institutions......Page 121 5. Agents in Organizations......Page 131 6. Evolution of Organizations......Page 134 7. Conclusions......Page 137 8. Exercises......Page 138 References......Page 141 Part II. Communication......Page 148 1. Introduction......Page 150 2. Conceptual Foundations of Communication in MAS......Page 155 3. Traditional Software Engineering Approaches......Page 157 4. Traditional AI Approaches......Page 163 5. Commitment-Based Multiagent Approaches......Page 167 6. Engineering with Agent Communication......Page 171 7. Advanced Topics and Challenges......Page 177 8. Conclusions......Page 179 Acknowledgments......Page 181 9. Exercises......Page 182 References......Page 185 1. Introduction......Page 192 2. Aspects of Negotiation......Page 193 3. Game-Theoretic Approaches for Single-Issue Negotiation......Page 195 4. Game-Theoretic Approaches for Multi-Issue Negotiation......Page 205 5. Heuristic Approaches for Multi-Issue Negotiation......Page 210 6. Negotiating with Humans......Page 214 7. Argumentation-Based Negotiation......Page 216 8. Conclusions......Page 218 9. Exercises......Page 219 References......Page 220 1. Introduction......Page 226 2. What Is an Argument?......Page 227 3. Evaluating an Argument......Page 230 4. Argumentation Protocols......Page 234 5. Strategic Argumentation and Game Theory......Page 239 6. The Argument Interchange Format......Page 250 Acknowledgment......Page 253 8. Exercises......Page 254 References......Page 255 Part III. Basic Coordination......Page 260 1. Introduction......Page 262 2. Preference Aggregation......Page 268 3. Voting......Page 275 4. Combinatorial Domains......Page 290 5. Fair Division......Page 296 6. Conclusion......Page 306 7. Exercises......Page 309 References......Page 315 1. Introduction......Page 334 2. Mechanism Design with Unrestricted Preferences......Page 335 3. Quasilinear Preferences......Page 340 4. Efficient Mechanisms......Page 345 5. Single-Good Auctions......Page 353 6. Position Auctions......Page 361 7. Combinatorial Auctions......Page 364 8. Conclusions......Page 367 9. Exercises......Page 369 References......Page 374 1. Introduction......Page 378 2. Definitions......Page 380 3. Solution Concepts......Page 384 4. Representation Formalisms......Page 392 5. Coalition Structure Generation......Page 401 7. Exercises......Page 421 References......Page 423 1. Introduction......Page 430 2. Computational Representation of Trust and Reputation Values......Page 431 3. Trust Processes in Multiagent Systems......Page 437 4. Reputation in Multiagent Societies......Page 445 5. Trust, Reputation, and Other Agreement Technologies......Page 456 6. Conclusions......Page 462 7. Exercises......Page 463 References......Page 464 Part IV. Distributed Cognitive Abilities......Page 470 1. Introduction......Page 472 2. Challenges in Multiagent Learning......Page 474 3. Reinforcement Learning for Multiagent Systems......Page 481 4. Evolutionary Game Theory as a Multiagent Learning Paradigm......Page 492 5. Swarm Intelligence as a Multiagent Learning Paradigm......Page 500 6. Neuro-Evolution as a Multiagent Learning Paradigm......Page 506 7. Case Study: Air Traffic Control......Page 509 9. Exercises......Page 517 References......Page 524 1. Introduction......Page 534 2. Characterizing Multiagent Planning and Control......Page 536 3. Coordination Prior to Local Planning......Page 537 4. Local Planning Prior to Coordination......Page 546 5. Decision-Theoretic Multiagent Planning......Page 561 6. Multiagent Execution......Page 576 7. Conclusions......Page 581 8. Exercises......Page 582 References......Page 588 1. Introduction......Page 596 2. Distributed Constraint Handling......Page 598 3. Applications and Benchmarking Problems......Page 600 4. Solution Techniques: Complete Algorithms......Page 603 5. Solution Techniques: Approximate Algorithms......Page 614 6. Solution Techniques with Quality Guarantees......Page 619 7. Conclusions......Page 626 8. Exercises......Page 627 References......Page 629 Part V. Development and Engineering......Page 634 1. Introduction......Page 636 2. From AGENT0 to Modern Agent Languages......Page 639 3. Abstractions in the MAOP Paradigm......Page 642 4. Examples of Agent Programming Languages......Page 645 5. Organization and Environment Programming......Page 658 6. Example of Full MAOP in JaCaMo......Page 669 7. Conclusions......Page 678 8. Exercises......Page 679 References......Page 682 1. Introduction......Page 690 2. Agent Specification......Page 693 3. From Specifications to Implementations......Page 705 4. Formal Verification......Page 708 5. Deductive Verification of Agents......Page 712 6. Algorithmic Verification of Agent Models......Page 716 7. Algorithmic Verification of Agent Programs......Page 725 8. Conclusions......Page 729 9. Exercises......Page 730 References......Page 732 1. Introduction......Page 744 2. Agent Concepts......Page 749 3. Running Example......Page 751 4. Requirements......Page 753 5. Design......Page 759 6. Detailed Design......Page 766 7. Implementation......Page 776 8. Assurance......Page 777 9. Software Maintenance......Page 783 10. Comparing Methodologies......Page 784 11. Conclusions......Page 785 12. Exercises......Page 789 Appendix: Agent UML Sequence Diagram Notation......Page 791 References......Page 793 Part VI. Technical Background......Page 808 1. Introduction......Page 810 2. Representing Cognitive States......Page 818 3. Representing the Strategic Structure of a System......Page 834 4. Conclusion and Further Reading......Page 846 5. Exercises......Page 848 References......Page 849 1. Introduction......Page 860 2. Normal-Form Games......Page 861 3. Extensive-Form Games......Page 877 4. Bayesian Games......Page 885 6. Exercises......Page 891 References......Page 896 Subject Index......Page 898 "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