Introduction to MultiAgent Systems

Michael Wooldridge is a Professor of Computer Science at the University of Liverpool, UK. He obtained his PhD in 1992 for work in the theory of multiagent systems and has, since then, been active in multiagent systems research.

“Nevertheless, despite these minor issues, this book is highly recommended to all socio-economic agent-based modellers, beginners or otherwise. Wooldridge’s scope, rigor, and well-respected experience at the current coalface means there’s plenty in here of interest for old-timers, while beginners can skip some of the maths and more bleeding-edge theory and concentrate easily on the implementation without loosing much.” (Appl. Spatial Analysis, 2011)

• Preface xiiiAcknowledgements xxiPart I Setting the Scene 11 Introduction 31.1 The Vision Thing 61.2 Some Views of the Field 91.2.1 Agents as a paradigm for software engineering 91.2.2 Agents as a tool for understanding human societies 121.3 Frequently Asked Questions (FAQ) 12Part II Intelligent Autonomous Agents 192 Intelligent Agents 212.1 Intelligent Agents 262.2 Agents and Objects 282.3 Agents and Expert Systems 302.4 Agents as Intentional Systems 312.5 Abstract Architectures for Intelligent Agents 342.6 How to Tell an Agent What to Do 383 Deductive Reasoning Agents 493.1 Agents as Theorem Provers 503.2 Agent-Oriented Programming 553.3 Concurrent MetateM 564 Practical Reasoning Agents 654.1 Practical Reasoning = Deliberation +Means–Ends Reasoning 654.2 Means–Ends Reasoning 694.3 Implementing a Practical Reasoning Agent 754.4 The Procedural Reasoning System 795 Reactive and Hybrid Agents 855.1 Reactive Agents 855.1.1 The subsumption architecture 865.1.2 PENGI 905.1.3 Situated automata 905.1.4 The agent network architecture 915.1.5 The limitations of reactive agents 925.2 Hybrid Agents 925.2.1 Touring Machines 945.2.2 InteRRaP 965.2.3 3T 985.2.4 Stanley 99Part III Communication and Cooperation 1056 Understanding Each Other 1076.1 Ontology Fundamentals 1086.1.1 Ontology building blocks 1086.1.2 Anontology of ontologies 1106.2 Ontology Languages 1136.2.1 XML–adhoc ontologies 1136.2.2 OWL–The web ontology language 1146.2.3 KIF–ontologies in first-order logic 1206.3 RDF 1216.4 Constructing an Ontology 1246.5 Software Tools for Ontologies 1277 Communicating 1317.1 Speech Acts 1327.1.1 Austin 1327.1.2 Searle 1337.1.3 The plan-based theory of speech acts 1347.1.4 Speech acts as rational action 1357.2 Agent Communication Languages 1367.2.1 KQML 1367.2.2 The FIPA agent communication language  1407.2.3 JADE 1468 Working Together 1518.1 Cooperative Distributed Problem Solving 1518.2 Task Sharing and Result Sharing 1538.2.1 Task sharing in the Contract Net 1568.3 Result Sharing 1598.4 Combining Task and Result Sharing 1598.5 Handling Inconsistency 1618.6 Coordination 1628.6.1 Coordination through partial global planning 1638.6.2 Coordination through joint intentions 1658.6.3 Coordination by mutual modelling 1708.6.4 Coordination by norms and social laws 1738.7 Multiagent Planning and Synchronization 1779 Methodologies 1839.1 When is an Agent-Based Solution Appropriate? 1839.2 Agent-Oriented Analysis and Design 1849.2.1 The AAII methodology 1849.2.2 Gaia 1869.2.3 Tropos 1879.2.4 Prometheus 1889.2.5 Agent UML 1889.2.6 Agents in Z 1899.3 Pitfalls of Agent Development 1909.4 Mobile Agents 19310 Applications 20110.1 Agents for Workflow and Business Process Management 20110.2 Agents for Distributed Sensing 20310.3 Agents for Information Retrieval and Management 20510.4 Agents for Electronic Commerce 21110.5 Agents for Human–Computer Interfaces 21310.6 Agents for Virtual Environments 21410.7 Agents for Social Simulation 21410.8 Agents for X  218Part IV Multiagent Decision Making 22111 Multiagent Interactions 22311.1 Utilities and Preferences 22311.2 Setting the Scene 22611.3 Solution Concepts and Solution Properties 22911.3.1 Dominant strategies 23011.3.2 Nash equilibria 23011.3.3 Pareto efficiency 23311.3.4 Maximizing social welfare 23511.4 Competitive and Zero-Sum Interactions 23511.5 The Prisoner’s Dilemma 23611.5.1 The shadow of the future 24011.5.2 Program equilibria 24311.6 Other Symmetric 2 ×2Interactions 24511.7 Representing Multiagent Scenarios 24811.8 Dependence Relations in Multiagent Systems 24912 Making Group Decisions 25312.1 Social Welfare Functions and Social Choice Functions 25312.2 Voting Procedures 25512.2.1 Plurality 25512.2.2 Sequential majority elections 25712.2.3 The Borda count 26012.2.4 The Slater ranking 26012.3 Desirable Properties for Voting Procedures 26112.3.1 Arrow’s theorem 26312.4 Strategic Manipulation 26413 Forming Coalitions 26913.1 Cooperative Games 27013.1.1 The core 27213.1.2 The Shapley value 27413.2 Computational and Representational Issues 27713.3 Modular Representations 27813.3.1 Induced subgraphs 27813.3.2 Marginal contribution nets 28013.4 Representations for Simple Games 28113.4.1 Weighted voting games 28213.4.2 Network flow games 28513.5 Coalitional Games with Goals 28713.6 Coalition Structure Formation 28814 Allocating Scarce Resources 29314.1 Classifying Auctions 29414.2 Auctions for Single Items 29514.2.1 English auctions 29514.2.2 Dutch auctions 29614.2.3 First-price sealed-bid auctions 29614.2.4 Vickrey auctions 29614.2.5 Expected revenue 29714.2.6 Lies and collusion 29814.2.7 Counter speculation 29914.3 Combinatorial Auctions 29914.3.1 Bidding languages 30214.3.2 Winner determination 30614.3.3 The VCG mechanism 30814.4 Auctions in Practice 31014.4.1 Online auctions 31014.4.2 Adwords auctions 31114.4.3 The trading agent competition 31215 Bargaining 31515.1 Negotiation Parameters 31515.2 Bargaining for Resource Division 31715.2.1 Patient players 31715.2.2 Impatient players 32015.2.3 Negotiation decision functions 32115.2.4 Applications of alternating offers 32315.3 Bargaining for Task Allocation 32315.3.1 Themonotonic concession protocol 32615.3.2 The Zeuthen strategy 32715.3.3 Deception 32915.4 Bargaining for Resource Allocation 33016 Arguing 33716.1 Types of Argument 33816.2 Abstract Argumentation 33816.2.1 Preferred extensions 33916.2.2 Credulous and skeptical acceptance 34116.2.3 Preferences in abstract argument systems 34316.2.4 Values in abstract argument systems 34416.3 Deductive Argumentation Systems 34516.4 Dialogue Systems 34816.5 Implemented Argumentation Systems 35017 Logical Foundations 35517.1 Logics for Knowledge and Belief  35517.1.1 Possible-worlds semantics for modal logics 35717.1.2 Normal modal logics 35817.1.3 Normal modal logics as epistemic logics 36117.1.4 Logical omniscience 36317.1.5 Axioms for knowledge and belief 36417.1.6 Multiagent epistemic logics 36517.1.7 Common and distributed knowledge 36717.2 Logics for Mental States 36917.2.1 Cohen and Levesque’s intention logic 36917.2.2 Modelling speech acts 37117.3 Logics for Cooperation 37317.3.1 Incomplete information 37517.3.2 Cooperation logics for social choice 37617.4 Putting Logic to Work 37617.4.1 Logic in specification 37717.4.2 Logic in implementation 37817.4.3 Logic in verification 381Part V Coda 391A A History Lesson 393B Afterword 405Glossary of Key Terms 407References 425Index 453