Multiagent Systems IntelligentRoboticsandAutonomousAgents EditedbyRonaldC.Arkin Dorigo, Marco, and Marco Colombetti, Robot Shaping: An Experiment in Behavior En- gineering Arkin,RonaldC.,Behavior-BasedRobotics Stone, Peter, Layered Learning in Multiagent Systems: A Winning Approach to Robotic Soccer Wooldridge,Michael,ReasoningAboutRationalAgents Murphy,RobinR.,AnIntroductiontoAIRobotics Mason,MatthewT.,MechanicsofRoboticManipulation Kraus,Sarit,StrategicNegotiationinMultiagentEnvironments Nolfi,Stefano,andDarioFloreano,EvolutionaryRobotics: TheBiology,Intelligence,and TechnologyofSelf-OrganizingMachines Siegwart,Roland,andIllahR.Nourbakhsh,IntroductiontoAutonomousMobileRobots Breazeal,CynthiaL.,DesigningSociableRobots Bekey, George A., Autonomous Robots: From Biological Inspiration to Implementation andControl Choset, Howie, Kevin M. Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, LydiaE.Kavraki,andSebastianThrun,PrinciplesofRobotMotion: Theory,Algorithms, andImplementations Thrun,Sebastian,WolframBurgard,andDieterFox,ProbabilisticRobotics Mataric,MajaJ.,TheRoboticsPrimer Wellman, Michael P., Amy Greenwald, and Peter Stone, Autonomous Bidding Agents: StrategiesandLessonsfromtheTradingAgentCompetition Floreano, Dario and Claudio Mattiussi, Bio-Inspired Artificial Intelligence: Theories, Methods,andTechnologies Sterling,LeonS.andKuldarTaveter,TheArtofAgent-OrientedModeling Stoy, Kasper, David Brandt, and David J. Christensen, An Introduction to Self- ReconfigurableRobots Lin, Patrick, Keith Abney, and George A. Bekey, editors, Robot Ethics: The Ethical and SocialImplicationsofRobotics Weiss,Gerhard,editor,MultiagentSystems,secondedition Multiagent Systems secondedition editedbyGerhardWeiss TheMITPress Cambridge,Massachusetts London,England (cid:2)c 2013MassachusettsInstituteofTechnology Allrightsreserved. Nopartofthisbookmaybereproducedinanyformbyanyelectronic ormechanicalmeans(includingphotocopying, recording, orinformationstorageandre- trieval)withoutpermissioninwritingfromthepublisher. MIT Press books may be purchased at special quantity discounts for business or sales promotional use. For information, please email [email protected] or write toSpecialSalesDepartment,TheMITPress,55HaywardStreet,Cambridge,MA02142. ThisbookwassetinTimesRomanbytheeditor. PrintedandboundintheUnitedStates ofAmerica. LibraryofCongressCataloging-in-PublicationData Multiagentsystems/editedbyGerhardWeiss. —Secondedition. p. cm.—(Intelligentroboticsandautonomousagentsseries) Includesbibliographicalreferencesandindex. ISBN978-0-262-01889-0(hardcover: alk. paper) 1. Intelligentagents(Computersoftware)2. Distributedartificialintelligence. I.Weiss,Gerhard,1962–editorofcompilation. QA76.76.I58M852013 006.3—dc23 2012024600 10987654321 ForSofie,Alina,andTina —G.W. Contents in Brief Preface xxxv • • TheSubjectofThisBook MainFeaturesofThisBook • • ReadershipandPrerequisites ChangesfromtheFirstEdition • • • StructureandChapters TheExercises HowtoUseThisBook • SlidesandMore–TheWebsiteoftheBook Acknowledgments xxxv ContributingAuthors xliii Part I Agent Architectures and Organizations 1 1 IntelligentAgents 3 MichaelWooldridge 2 MultiagentOrganizations 51 VirginiaDignumandJulianPadget Part II Communication 99 3 AgentCommunication 101 AmitK.ChopraandMunindarP.Singh 4 NegotiationandBargaining 143 ShaheenFatimaandIyadRahwan 5 ArgumentationamongAgents 177 IyadRahwan viii ContentsinBrief Part III Basic Coordination 211 6 ComputationalSocialChoice 213 FelixBrandt,VincentConitzer,andUlleEndriss 7 MechanismDesignandAuctions 285 KevinLeyton-BrownandYoavShoham 8 ComputationalCoalitionFormation 329 EdithElkind,TalalRahwan,andNicholasR.Jennings 9 TrustandReputationinMultiagentSystems 381 JordiSabater-MirandLaurentVercouter Part IV Distributed Cognitive Abilities 421 10 MultiagentLearning 423 KarlTuylsandKaganTumer 11 MultiagentPlanning,Control,andExecution 485 EdDurfeeandShlomoZilberstein 12 DistributedConstraintHandlingandOptimization 547 AlessandroFarinelli,MeritxellVinyals,AlexRogers,and NicholasR.Jennings ContentsinBrief ix Part V Development and Engineering 585 13 ProgrammingMultiagentSystems 587 RafaelH.BordiniandJürgenDix 14 SpecificationandVerificationofMultiagentSystems 641 JürgenDixandMichaelFisher 15 Agent-OrientedSoftwareEngineering 695 MichaelWinikoffandLinPadgham Part VI Technical Background 759 16 LogicsforMultiagentSystems 761 WiebevanderHoekandMichaelWooldridge 17 Game-TheoreticFoundationsofMultiagentSystems 811 EdithElkindandEvangelosMarkakis Subject Index 849