Multiagent Systems
Multiagent Systemssecond editionedited by Gerhard WeissThe MIT PressCambridge, MassachusettsLondon, England
ContentsPrefacexxxvThe Subject of This Book Main Features of This Book Readership and Prerequisites Changes from the First Edition Structure and Chapters The Exercises How to Use This Book Slides and More - The Website of the Book AcknowledgmentsContributing AuthorsParti1Agent Architectures and OrganizationsIntelligent AgentsMichael Wooldridge1Introduction2What Are Agents?2.1Examples of Agents2.2Intelligent Agents2.3Agents and Objects2.4Agents and Expert Systems2.5Sources and Further Reading3Architectures for Intelligent Agents3.1Logic-Based Architectures3.1.1Sources and Further Reading3.2Reactive Architectures3.2.1The Subsumption Architecture3.2.2Markov Decision Processes3.2.3Sources and Further Reading3.3Belief-Desire-Intention Architectures3.3.1Sources and Further Reading3.4Layered Architecturesxliii13347810121313141920212527283536
eferences2TouringMachinesInteRRaPSources and Further ReadingMultiagent OrganizationsVirginia Dignum and Julian Padget1Introduction2Background2.1From Intelligent Agents to Multiagent Systems2.2From Multiagent Systems to Multiagent Organizations . .2.3Sources of Inspiration2.3.1Organization as Structure2.3.2Organization as Institution2.3.3Organization as Agent2.4Autonomy and Regulation2.5Example Scenario3Multiagent Organizations3.1Organization Concepts3.2Example of Organization Modeling: The OperA Framework3.2.1The Social Structure3.2.2The Interaction Structure3.2.3The Normative Structure3.2.4The Communication Structure4Institutions4.1Organizations, Institutions, and Norms4.2Events and States4.3Obligations, Permission, and Power4.4Example of Institutional Modeling: InstAL4.4.1The Formal Model4.4.2The Conference Scenario5Agents in Organizations6Evolution of Organizations6.1Organizational Adaptation6.2Emergent 778787882858687888992
ContentsPart II3xiiiCommunication99Agent Communication101Amit K. Chopra and Munindar P. Singh1Introduction1.1Autonomy and Its Implications1.2Criteria for Evaluation2Conceptual Foundations of Communication in MAS2.1Communicative Acts2.2Agent Communication Primitives3Traditional Software Engineering Approaches3.1Choreographies3.2Sequence Diagrams3.3State Machines3.4Evaluation with Respect to MAS4Traditional AI Approaches4.1KQML4.2FIPAACL4.3Evaluation with Respect to MAS5Commitment-Based Multiagent Approaches5.1Commitments5.2Commitment Protocol Specification5.3Evaluation with Respect to MAS6Engineering with Agent Communication6.1Programming with Communications6.2Modeling Communications6.2.1Business Patterns6.2.2Enactment Patterns6.2.3Semantic Antipatterns6.3Communication-Based Methodologies7Advanced Topics and Challenges7.1Primacy of Meaning7.2Verifying Compliance7.3Protocol Refinement and Aggregation7.4Role 122123124125125126127128128129129130130133136
xiv45ContentsNegotiation and BargainingShaheen Fatima and Iyad Rahwan1Introduction2Aspects of Negotiation3Game-Theoretic Approaches for Single-Issue Negotiation3.1Cooperative Models of Single-Issue Negotiation3.2Non-Cooperative Models of Single-Issue Negotiation . . .4Game-Theoretic Approaches for Multi-Issue Negotiation4.1Cooperative Models of Multi-Issue Negotiation4.2Non-Cooperative Models of Multi-Issue Negotiation . . .5Heuristic Approaches for Multi-Issue Negotiation5.1Heuristics for Generating Counteroffers5.2Heuristics for Predicting Opponent's Preferences andGenerating Counteroffers5.3Heuristics for Generating Optimal Agendas5.4Heuristics for Reasoning about Deliberation Cost6Negotiating with Humans7Argumentation-Based tation among AgentsIyad Rahwan1Introduction2What Is an Argument?2.1Arguments as Chained Inference Rules2.2Argument as an Instance of a Scheme2.3Abstract Arguments3Evaluating an Argument4Argumentation Protocols4.1Abstract Argument Games4.2Dialogue Systems5Strategic Argumentation and Game Theory5.1Glazer and Rubinstein's Model5.2Game Theory Background5.2.1Mechanism Design5.2.2The Revelation Principle5.3Argumentation Mechanism Design5.4Case Study: Implementing the Grounded 91192194195196. . . 198
ContentsXV6The Argument Interchange Format7Conclusion8ExercisesReferencesPart III6201204205206Basic CoordinationComputational Social ChoiceFelix Brandt, Vincent Conitzer, and Ulle Endriss1Introduction1.1Introductory Example1.2History of the Field1.3Applications1.4Chapter Outline2Preference Aggregation2.1Social Welfare Functions2.2Social Choice Functions2.2.1The Weak Axiom of Revealed Preference2.2.2Contraction and Expansion Consistency3Voting3.1Voting Rules3.1.1Scoring Rules3.1.2Condorcet Extensions3.1.3Other Rules3.2Manipulation3.2.1The Gibbard-Satterthwaite Impossibility3.2.2Restricted Domains of Preferences3.2.3Computational Hardness of Manipulation3.2.4Probabilistic Voting Rules3.2.5Irresolute Voting Rules3.3Possible and Necessary Winners4Combinatorial Domains4.1Preference Representation4.2Sequential Voting4.3Voting with Compactly Represented Preferences5Fair Division5.1Preference Representation5.2Fairness and Efficiency5.3Computing Fair and Efficient Allocations211213. . . . . . 33233235238239240241243245246247249251253
xvi7Contents5.4Convergence to Fair and Efficient Allocations6Conclusion6.1Additional Topics6.2Further nism Design and AuctionsKevin Leyton-Brown and Yoav Shoham1Introduction2Mechanism Design with Unrestricted Preferences2.1Implementation2.2The Revelation Principle2.3Impossibility of General, Dominant-StrategyImplementation3Quasilinear Preferences3.1Mechanism Design in the Quasilinear Setting4Efficient Mechanisms4.1Groves Mechanisms4.2The VCG Mechanism4.3Properties of VCG4.3.1VCG and Individual Rationality4.3.2VCG and Weak Budget Balance4.3.3Drawbacks of VCG4.4Budget Balance and Efficiency5Single-Good Auctions5.1Canonical Auction Families5.1.1English Auctions5.1.2Japanese Auctions5.1.3Dutch Auctions5.1.4Sealed-Bid Auctions5.2Auctions as Bayesian Mechanisms5.3Second-Price, Japanese, and English Auctions5.4First-Price and Dutch Auctions5.5Revenue Equivalence6Position Auctions7Combinatorial 306306306308310311312315318320325
Contentsxvii8329Computational Coalition FormationEdith Elkind, Talal Rahwan, and Nicholas R. Jennings1Introduction1.1Coalitional Games: A Bird's Eye View2Definitions2.1Outcomes2.2Subclasses of Characteristic Function Games2.2.1Monotone Games2.2.2Superadditive Games2.2.3Convex Games2.2.4Simple Games3Solution Concepts3.1Shapley Value3.2Banzhaflndex3.3Core3.3.1The Core of Simple Games3.3.2The Core of Convex Games3.4The Least Core3.5Other Solution Concepts4Representation Formalisms4.1Weighted Voting Games4.1.1Computational Issues4.1.2Expressivity and Vector Weighted Voting Games4.2Combinatorial Optimization Games4.2.1Induced Subgraph Games4.2.2Network Flow Games4.2.3Matching and Assignment Games4.3Complete Representation Languages4.3.1Marginal Contribution Nets4.3.2Synergy Coalition Groups4.3.3Skill-Based Representations4.3.4Agent-Type Representation5Coalition Structure Generation5.1Space Representation5.2Dynamic Programming Algorithms5.3Anytime Algorithms5.3.1Identifying Subspaces with Worst-Case Guarantees5.3.2Integer Partition-Based Search5.3.3Integer 1352353354356356359360
xviiiContents5.45.5Metaheuristic AlgorithmsCoalition Structure Generation under Compact Representations5.5.1Distributed Constraint Optimization5.5.2Marginal Contribution Nets5.5.3Coalitional Skill Games5.5.4Agent-Type Representation5.6Constrained Coalition 2364366368369372372374Trust and Reputation in Multiagent Systems381Jordi Sabater-Mir and Laurent Vercouter1Introduction3812Computational Representation of Trust and Reputation Values . . 3822.1Boolean Representation3832.2Numerical Values3832.3Qualitative Labels3842.4Probability Distribution and Fuzzy Sets3842.5Trust and Reputation as Beliefs3852.6The Reliability of a Value3873Trust Processes in Multiagent Systems3883.1General Overview of Trust-Related Processes3883.2Trust Evaluations3903.2.1Filtering the Inputs3913.2.2Statistical Aggregation3923.2.3Logical Beliefs Generation3933.3Trust Decision3943.3.1Single Trust Values andProbability Distributions3953.3.2Trust Beliefs3953.4Coping with the Diversity of Trust Models3964Reputation in Multiagent Societies3964.1Reputation-Building Process3984.1.1Communicated Image as a Source forReputation3984.1.2Communicated Reputation4004.1.3Inherited Reputation4004.1.4Putting It All Together401
xixContents4.2Centralized vs. Decentralized Models4.2.1Centralized Approaches4.2.2Decentralized Approaches4.3Using Reputation4.3.1Reputation as a Source of Trust4.3.2Reputation for Social Order4.4Pitfalls When Using Reputation4.4.1Unfair Ratings4.4.2Ballot-Stuffing4.4.3Dynamic il Attacks4.4.7Reputation Lag Exploitation5Trust, Reputation, and Other Agreement 5.4Organizations5.5Ontologies and Semantics6Conclusions7ExercisesReferencesPart IV Distributed Cognitive Abilities10 Multiagent LearningKarl Tuyls and Kagan Turner1Introduction2Challenges in Multiagent Learning2.1State, Action, and Outcome Space Problems2.2Multiagent Credit Assignment Problem2.3Agent Rewards and System Dynamics2.4Two Simple Multiagent Learning Paradigms2.4.1Action-Value Learning2.4.2Direct Policy Adjustment3Reinforcement Learning for Multiagent Systems3.1Markov Decision Processes3.2Action Selection and Exploration-Exploitation Dilemma 432433434
ContentsXX3.33.43.53.6Model-Free and Model-Based ApproachesMultiagent MDP FormulationsMarkov GamesState-of-the-Art Algorithms3.6.1Joint Action Learning3.6.2Nash-Q Learning3.6.3Gradient Ascent Algorithms3.6.4Other Approaches4Evolutionary Game Theory as a Multiagent Learning Paradigm . .4.1Matrix Games4.2Solution Concepts4.3Evolutionary Stable Strategies4.4Replicator Dynamics4.5The Role of Game Theory for Multiagent Learning . . . .4.6Evolutionary Game Theory as a Theoretical Framework .5Swarm Intelligence as a Multiagent Learning Paradigm5.1Ant Colony Optimization5.2Bee Colony Optimization6Neuro-Evolution as a Multiagent Learning Paradigm6.1Evolutionary Algorithm Basics6.2Linking Multiagent Reinforcement Learning to theNeuro-Evolutionary Approach7Case Study: Air Traffic Control7.1Motivation7.2Simulation and System Performance7.3Agent-Based Air Traffic7.4Multiagent Air Traffic 11 Multiagent Planning, Control, and ExecutionEd Durfee and Shlomo Zilberstein1Introduction2Characterizing Multiagent Planning and Control3Coordination Prior to Local Planning3.1Social Laws and Conventions3.2Organizational Structuring3.2.1Organizational 85487488489490491
Contentsxxi3.2.2Organizational Execution and FunctionallyAccurate Cooperation3.3The Contract-Net Protocol and Role Assignment4Local Planning Prior to Coordination4.1State-Space Techniques4.2Plan-Space Techniques4.2.1Single-Agent Plans4.2.2Multiagent Plans4.2.3Multiagent Plan Coordination by Plan Modification4.3Hierarchical Multiagent Plan Coordination5Decision-Theoretic Multiagent Planning5.1Models for Decision-Theoretic Multiagent Planning . . .5.1.1Solution Representation and Evaluation5.1.2The Complexity of DEC-POMDPs5.2Solving Finite-Horizon DEC-POMDPs5.3Solving Infinite-Horizon DEC-POMDPs5.3.1Correlated Joint Controllers5.3.2Policy Iteration for Infinite-HorizonDEC-POMDPs5.3.3Optimizing Fixed-Size Controllers UsingNon-Linear Programming6Multiagent Execution6.1Multiagent Plan Monitoring6.2Multiagent Plan Recovery6.3Multiagent Continuous Planning7Conclusions8ExercisesReferences12 Distributed Constraint Handling and OptimizationAlessandro Farinelli, Meritxell Vinyals, Alex Rogers, andNicholas R. Jennings1Introduction2Distributed Constraint Handling2.1Constraint Networks2.2Distributed Constraint Processing3Applications and Benchmarking Problems3.1Real-World Applications3.1.1Meeting 551551552
xxiiContents3.1.2Target Tracking5533.2Exemplar and Benchmarking Problems5534Solution Techniques: Complete Algorithms5544.1Search-Based: ADOPT5554.2Dynamic Programming: DPOP5615Solution Techniques: Approximate Algorithms5655.1Local Greedy Approximate Algorithms5655.1.1The Distributed Stochastic Algorithm5665.1.2The Maximum Gain Message Algorithm . . . . 5675.2GDL-Based Approximate Algorithms5685.2.1The Max-Sum Algorithm5686Solution Techniques with Quality Guarantees5706.1Off-line Guarantees5716.2Online s580PartVDevelopment and Engineering58513 Programming Multiagent Systems587Rafael H. Bordini and Jürgen Dix1Introduction5871.1Relation to Other Chapters5891.2Organization of This Chapter5892From AGENTO to Modern Agent Languages5902.1A Brief History of Agent-Oriented Programming (AOP) . 5902.2Features of Multiagent-Oriented Programing (MAOP) . . 5913Abstractions in the MAOP Paradigm5933.1Agent Level5933.2Environment Level5953.3Social Level5964Examples of Agent Programming Plans4.1.4SemanticsOther BDl-Based Languages596597598599600601
Contentsxxiii4.35Approaches Based on Executable Logics6034.3.1607METATEM4.3.2ConGolog and IndiGologOrganization and Environment Programming5.1Organizations5.1.1MoiSE5.1.2Other ple of Full МАОР in JaCaMo6.1The Application Scenario6.2Organization Program6.3Agent Programs6.4Environment Program7Conclusions8ExercisesReferences14 Specification and Verification of Multiagent SystemsJürgen Dix and Michael Fisher1Introduction1.1Why Logic, Specification, and Verification?1.2Limits and Relation to Other Chapters1.3Organization of This Chapter2Agent Specification2.1Logics of Agency and Specification Languages2.2Approaches Based on Temporal roaches Based on Dynamic Logic2.4Combinations2.4.1BDI2.4.2KARO2.4.3Dynamic Epistemic Logic2.5Sample Specifications3From Specifications to Implementations3.1Toward Formal 649650652653653653654654656656657
xxiv3.3Synthesis3.4Specifications as Programs4Formal Verification4.1What Is Formal Verification?4.2Deductive Verification4.3Algorithmic Verification4.4Program Verification4.5Runtime Verification5Deductive Verification of Agents5.1The Problem5.2Direct Proof5.3Use of Logic Programming5.4Example6Algorithmic Verification of Agent Models6.1The Representation and Size of the Model6.2(Im-)Perfect Information, (Im-)Perfect Recall6.3Modular Interpreted Systems6.4MC Complexity for LTL, CTL, ATL, and MIS6.5Model Checking Agent Language Models7Algorithmic Verification of Agent Programs7.1General Problem7.2AIL Semantic Toolkit7.3Multiple Semantic Definitions7.4Model Checking AIL Through es15 Agent-Oriented Software EngineeringMichael Winikoffand Lin Padgham1Introduction1.1History of AOSE2Agent Concepts3Running Example4Requirements5Design6Detailed Design6.1Example Design: BDI Platform6.1.1Initial 3695695698700702704710717719719
ContentsXXV6.1.2Subgoal Structure for build27206.1.3Subgoal Structure for addPart and complete . . 7206.1.4Finalizing the Design7226.1.5Multiple Plans7246.1.6Control Information7256.2Example Design: Finite-State Automaton7256.3Final ng and Debugging7298.2Formal Methods7329Software Maintenance73410 Comparing Methodologies73511 Conclusions73612 Exercises740Appendix: Agent UML Sequence Diagram Notation742References744Part VI Technical Background16 Logics for Multiagent SystemsWiebe van der Hoek and Michael Wooldridge1Introduction1.1A Logical Toolkit2Representing Cognitive States2.1Intention Logic2.2BDI Logic2.3Discussion2.4Cognitive Agents in Practice2.4.1Specification senting the Strategic Structure of a System3.1Coalition Logic3.2Strategic Temporal Logic: ATL3.3Knowledge in Strategic Temporal Logics: ATEL3.4CL-PC4Conclusion and Further 90794796797
xxvi5ExercisesReferencesContents79980017 Game-Theoretic Foundations of Multiagent Systems811Edith Elkind and Evangelos Markakis1Introduction8112Normal-Form Games8122.1Dominant Strategy8142.2Nash Equilibrium8162.3Mixed Strategies and Mixed Nash Equilibrium8182.4Elimination of Dominated Strategies8202.5Games with Infinite Action Spaces8212.5.1Games with Differentiable Payoff Functions . . 8232.6Zero-Sum Games8242.7Computational Aspects8273Extensive-Form Games8283.1Nash Equilibrium and Critiques8313.2Subgame-Perfect Equilibrium8323.3Backward Induction8344Bayesian Games8364.1Two Examples8374.2Formal es847Subject Index849
2 Multiagent Organizations 51 Virginia Dignum and Julian Padget 1 Introduction 51 2 Background 53 2.1 From Intelligent Agents to Multiagent Systems 53 2.2 From Multiagent Systems to Multiagent Organizations . . 55 2.3 Sources of Inspiration 56 2.3.1 Organization as Structure 56 2.3.2 Organization as Institution 58 2.3.3 Organization as Agent 59
of multiagent systems, multiagent principles which are used in the optimization method, and the previous multiagent approaches in engineering design and optimization. Multiagent learning Multiagent systems are systems in which multiple agents autono-mously interact with each other and the environment (Stone and Veloso, 2000; Weiss, 2013).
Chapter 2 in G. Weiss (Ed.), Multiagent Systems, MIT Press, 2nd edition, 2012 Virginia Dignum and Julian Padget May 7, 2012. Contents Introduction Multiagent Organizations Institutions Agents in Organizations Evolution of Organizations. Content Introduction Multiagent Organizations Institutions Agents in Organizations
works on multiagent learning systems can be found in the literature—see, for example, the surveys works of [6,39]. However, most multiagent RL research focuses on problems in which the state-space is typically finite and not too large,1 and only a few works on multiagent learning address prob-lems with very large/infinite state-spaces.
Outline 1 Multiagent Problems in General 2 Dynamic Programming Formulation 3 Agent-by-Agent Policy Improvement 4 Approximate Policy Iteration - Use of Value and/or Policy Networks 5 Autonomous Multiagent Rollout with Signaling Policies 6 Multirobot Repair - A Large-Scale Multiagent POMDP Problem Bertsekas Reinforcement Learning 3 / 29
We first discuss multiagent POMDPs and previous work on Monte Carlo tree search and Bayesian reinforcement learning (BRL) for POMDPs. 2.1 Multiagent POMDPs An MPOMDP (Messias, Spaan, and Lima, 2011) is a multiagent planning model that unfolds over a number of steps. At every stage, agents take individual actions and receive individual .
Multiagent Systems B. Nebel, C. Becker-Asano, S. Wöl General information Agents (once again) Abstract Architectures for Agents Summary General information Recommended reading: Wooldridge, An Introduction to MultiAgent Systems - Second Edition, Wiley & Sons, 2009. Russell & Norvig, Arti cial Intelligence: A Modern Approach, third edition .
Multiagent Systems I Prof. Dr. Jürgen Dix Department of Informatics Clausthal University of Technology SS 2012 Prof. Dr. Jürgen Dix Department of Informatics, TUC Multiagent Systems I, SS 2012 1
Adventure tourism is generally thought to involve land-, air-, and water-based activities, ranging from short, adrenalin-fuelled encounters, such as bungee jumping and wind-surfing, to longer experiences, such as cruise expeditions and mountaineering. Yet, these activities overlap with other types of tourism, such as activity tourism and ecotourism, and this presents problems in clearly .
